Wstęp do Pracy Magisterskiej

Napisałem już kilka pierwszych stron – tych teoretycznych – mojej pracy magisterskiej. Przedstawiam wam streszczenie, wstęp, cel i zakres mojej pracy.

Streszczenie:

„Praca prezentuje współczesne podejście do tworzenia oprogramowania na platformy wieloprocesorowe. Opisano podstawy przetwarzania równoległego oraz przedstawiono sprzętowe i programowe mechanizmy jego realizacji. W pracy skupiono się na konstrukcjach kodu sekwencyjnego, które mogą podlegać zrównolegleniu. Wyróżniono kilka konstrukcji, które następnie poddano szczegółowej analizie. Rezultatem pracy jest zbiór algorytmów, które na podstawie statycznej analizy sekwencyjnego kodu programu pozwalają stwierdzić, czy dane fragmenty kodu mogą zostać zrównoleglone. Algorytmy te również pokazują, w jaki sposób należy przekształcić istniejące konstrukcje tak, aby można je było wykonać równolegle. Jeden z zaproponowanych algorytmów został zaimplementowany w aplikacji demonstracyjnej, która analizuje programy sekwencyjne stworzone w języku C#.”

Wstęp:

„W branży informatycznej istnieje przekonanie, że na każdy wyprodukowany układ scalony można znaleźć oprogramowanie, które w pewien zamierzony sposób wykorzysta wszystkie dostępne zasoby. Ta nieformalna zależność powodowała rozwój zarówno sprzętu, jak i oprogramowania, który pozwolił m.in. na stworzenie graficznych interfejsów użytkownika i produkcję trójwymiarowych gier 3D. Trend ten utrzymuje się nadal, zmuszając producentów do tworzenia coraz to bardziej wydajnych układów.

Dotychczas przyspieszanie procesorów polegało m.in. na zwiększaniu częstotliwości zegara, powiększaniu pamięci podręcznej oraz optymalizacji wykonania kodu. Zwiększająca się zgodnie z prawem Moora (1) liczba tranzystorów w układzie scalonym pozwalała na wszystkie te modyfikacje. Jednak w roku 2003 producenci napotkali trudności w zwiększaniu częstotliwości swoich układów – przeszkodą były ograniczenia wykorzystywanych materiałów, m.in. krzemu. Dopóki nie zakończą się badania nad nowymi rodzajami tranzystorów, jakie prowadzi, np. Intel (2), prędkości procesorów dostępnych na rynku nie ulegną znaczącym zmianom. Inżynierowie postanowili zmienić kierunek rozwoju procesorów i zamiast poszukiwać metody na ciągłe przyspieszanie zegarów, zdecydowali się umieszczać kilka jednostek obliczeniowych w jednym układzie. W ten sposób powstały nowe architektury – wielordzeniowe, które zrewolucjonizowały rynek komputerów osobistych. Procesory jednordzeniowe zostały całkowicie wyparte z rynku, a ich miejsca zajęły 2-, 4- i 8-rdzeniowe jednostki obliczeniowe.

Mimo przemian w architekturze komputerów i wprowadzeniu wielu jednostek obliczeniowych, programiści nadal tworzą rozwiązania kierowane na maszyny jednordzeniowe. Takie programy nie są w stanie wykorzystać zasobów wielordzeniowych maszyn, przez co użytkownicy nie odczują różnicy w działaniu aplikacji niezależnie od tego, czy będzie ona uruchomiona na 1- czy 4-rdzeniowym procesorze. Aplikacje tego typu stanowią większość produkowanego w dzisiejszych czasach oprogramowania. Inżynierowie nie posiadają wystarczającej wiedzy w kwestii tworzenia rozwiązań równoległych, uważają tę dziedzinę za zbyt trudną i czasochłonną w realizacji. Trudnością może być również fakt, że człowiek – z założenia istota myśląca – posiada sekwencyjną świadomość postrzegania świata. Potrzeba jest zatem zestawu narzędzi, które pomogą programiście w opanowaniu równoległości, wskażą możliwe zagrożenia wynikające z przetwarzania równoległego i pomogą je zlikwidować. Na rynku istnieją narzędzia wspomagające tworzenie aplikacji na nowe platformy, jednak brakuje rozwiązań pomagających przystosowywać istniejące aplikacje do nowych środowisk.”

Cel i zakres pracy:

„Celem pracy jest stworzenie i implementacja algorytmów, które w podanym kodzie sekwencyjnego programu potrafiłyby znaleźć fragmenty możliwe do zrównoleglenia. Algorytmy te powinny także ocenić, czy zmiana danego fragmentu programu w sposób pozwalający wykonać go równolegle, przyniesie wzrost wydajności aplikacji (np. skróci czas jej wykonania). Do budowy algorytmów powinny zostać użyte różne metody analizy kodu źródłowego i testowania oprogramowania. Statyczna analiza kodu pozwoli zbadać przepływ sterowania i zależności danych fragmentów kodu, a testowanie pomoże w oszacowaniu zmian w wydajności.

Praca zapoznaje czytelnika z podstawami programowania równoległego oraz możliwościami jego wykorzystania w projektach zorientowanych na architektury wielordzeniowe. Zostanie zaprezentowana różnica między zwykłym – sekwencyjnym – modelem tworzenia oprogramowania a modelem równoległym. Opisane zostaną podstawowe prawa z dziedziny obliczeń równoległych (m.in. granice przyspieszania i warunki Bernsteina (3)). Przedstawione zostaną różne metody zrównoleglenia, poczynając od architektur komputerów po najnowsze biblioteki programistyczne.

Druga część pracy jest poświęcona analizie konstrukcji kodu sekwencyjnego, które mogą podlegać zrównolegleniu. Opisano dokładnie różne warianty występowania wybranych konstrukcji oraz zaproponowano możliwe podejście zrównoleglenia. Na tej podstawie stworzono algorytmy.

W ostatniej części pracy przedstawiona jest aplikacja demonstracyjna, w której zaimplementowano jeden z zaproponowanych algorytmów. Stworzone narzędzie potrafi analizować kod w języku C# (4) i wskazywać w nim te fragmenty, które można zrównoleglić.”

[Aktualizacja]

Praca zaliczona na 5 :)

Rozszerzamy Visual Studio 2010 – Wstęp

Celem mojej pracy magisterskiej jest nie tylko praca badawcza prowadząca do pewnych wniosków i algorytmów, ale również budowa narzędzia implementującego te algorytmy. W związku z tym, że koncentruję się na analizie statyczne/dynamicznej kodu, postanowiłem rozszerzyć Visual Studio 2010 o swoje własne narzędzie. Celem kolejnej serii wpisów na moim blogu będzie zapoznanie Was z możliwościami rozbudowy, jakie oferuje Visual Studio 2010.

Na samym początku chciałbym wspomnieć o myśli, która niemal co chwila przeplata się we wszystkich artykułach i wszystkich screencast dotyczących Visual Studio Extensibility: kiedyś pisanie rozszerzeń do Visual Studio było bardzo bolesne, teraz jest o wiele, wiele prościej.

Aby rozpocząć swoją przygodę z rozbudową Visual Studio, należy oczywiście posiadać owe IDE w wersji Proffesional lub lepszej oraz pobrać i zainstalować SDK (~10MB) dostępny tutaj [1]. Po pomyślnym zainstalowaniu powinniście w oknie nowego projektu posiadać dodatkową kategorię  „Extensibility” w poszczególnych sekcjach językowych.

Niestety budowanie wtyczek nie jest trywialne i nie da się po prostu stworzyć Hello World bez choćby chwili poświęconej na dokształcenie. Wszystkim zainteresowanym zatem polecam serię screencastów z Development Tools Ecosystem Summit dostępnych na kanale 9 [2]. Myślę, że przebrnięcie przez serię 100 da Wam w miarę jasny obraz sytuacji i bez problemów będziecie mogli stworzyć prostą wtyczkę. Seria 200 jest już bardziej ambitna (ale i trudniejsza), dlatego tym bardziej ją polecam ;-)

Kopalnia wiedzy znajduje się oczywiście w bibliotece MSDN w sekcji Visual Studio 2010 SDK [3]. Polecam ją wszystkim ciekawskim i spragnionym detali developerom. Jest również specjalna strona Extending Visual Studio [4] będąca MSDN’owym punktem wejściowym w świat rozszerzeń Visual Studio.

Nie należy również zapomnieć o blogu zespołu tworzącego Visual Studio [5].

Najlepszym jednak sposobem poznania VSX (Visual Studio Extensibility) jest (po uprzedniej krótkiej lekturze) grzebanie w kodzie. Stworzoną przy pomocy tutoriala wtyczkę rozkładałem na części pierwsze, a wszystkie niejasności sprawdzałem w bibliotece MSDN. Po dwóch takich wieczorach mam już ogólne pojęcie na temat architektury wtyczek, podstawowych zasad ich tworzenia, a także wiem, czego unikać i co należy stosować.

W kolejnych wpisach postaram się Wam pokazać, jak stworzyć już nietrywialne wtyczki. Zapraszam.

Linki:

Promuj

Axum – Agenci w akcji

Powakacyjna kontynuacja serii na temat różnych podejść w pisaniu aplikacji równoległych. Po koniec lipca przedstawiłem model Agenta, a dzisiaj chciałbym przedstawić jego Microsoftową implementację.

Axum to kolejny inkubacyjny projekt z Redmond, tak więc naprawdę nie wiadomo, co się z nim dalej stanie. Model agenta [1], który przedstawiłem w poprzednim poście, został przez giganta potraktowany całkiem poważnie. Solidna implementacja, skalowalność, wtyczka do Visual Studio – to wszystko daje całkiem duże pole do popisu, ale powoli…

Axum to jezyk programowania – pewnie się zdziwiliście – w 99% oparty na C# i w pełni współpracujący z platformą .NET. To narzędzie umożliwiające koordynację niezależnych komponentów aplikacji, definiujące agentów oraz ich interakcje. Jest to język „special-purpose”, więc z miejsca wprowadzona jest tu równoległość.

Najprościej przedstawić Axum budując bardzo prostą aplikację taką jak  kalkulator. Na początek zatem musimy zaplanować, jakie elementy będą nam potrzebne – myśląc naturalnie w świecie agentów. Otóż, potrzebny będzie nam agent wykonujący pojedyncze działanie, np. dodawanie, ale również agent, który przekaże mu dane jednocześnie odbierając je od nas (np. z konsoli), tj. agent utożsamiany z punktem wejściowym aplikacji. Agent powinien również definiować kanał, czyli określenie rodzaju wiadomości, jaką może obsłużyć.

Zacznijmy zatem od kanału. Nazwijmy go MathChannel:

  1. channel MathChannel
  2. {
  3.    input int X;
  4.    input int Y;
  5.    output int Z;
  6. }

Jak widać, kanał definiuje pewne pola zwane portami. Oprócz typu decyduje się również o kierunku. Porty to nic innego jak bufory. Kolejność używania portów przez agenta można zdefiniować w tzw. patternach, ale na tym etapie poznawania Axum nie będą one potrzebne.

Stwórzmy zatem agenta dodawania:

  1. public agent Adder : channel MathChannel
  2. {
  3.    public Adder()
  4.    {
  5.       while(true)
  6.       {
  7.          Z <– ( receive(X) + receive(Y) );
  8.       }
  9.    }
  10. }

Należy zauważyć, że definiując agenta, musimy zdecydować, jaki kanał będzie obsługiwał, a w tym wypadku oczywiście będzie to nasz kanał matematyczny. Jak widzicie, kanał nie decyduje o funkcjonalności, a jedynie o możliwym interfejsie obsługi. Konstruktor tego agenta jest punktem wejściowym. Czytanie z kanału jest blokujące, tak więc łatwo zauważyć, na czym polega działanie agenta: czeka on na parametr, który pojawi się na porcie X w kanale. Jeśli przyjdzie, czeka na Y, a jeśli i ten przyjdzie – na port Z wstawia wynik działania i znów nasłuchuje na porcie X. O ile konstrukcja pobierania z portu jest „normalna”, to wysyłanie wyniku na port operatorem „<–” może troszkę dziwić. Axum definiuje więcej podobnych operatorów.

Czas na kluczowego agenta:

  1. public agent App : channel Application
  2. {
  3.    public App()
  4.    {
  5.       var a = Adder.CreateInNewDomain();
  6.       while(true)
  7.       {
  8.          Console.Write("X: ");
  9.          int x = Int32.Parse(Console.ReadLine());
  10.          a::X <– x;
  11.  
  12.          Console.Write("X: ");
  13.          int y = Int32.Parse(Console.ReadLine());
  14.          a::Y <– y;
  15.  
  16.          int za = receive(a::Z);
  17.          Console.WriteLine("Adder Z: " + za);
  18.       }
  19.    }
  20. }

Agent będący punktem wejściowym aplikacji musi implementować kanał Application, co w tym wypadku polega jedynie na deklaracji. W konstruktorze (czyli w ciele wykonywania agenta) tworzymy pozostałych potrzebnych nam agentów, w tym wypadku tylko jednego – do dodawania. Zauważcie, że stworzony został w innej domenie niż obecny agent, przez co będzie mógł działać równolegle. Następnie najzwyczajniej w świecie pobieramy liczbę z konsoli i wysyłamy ją na dany port agenta – port który definiuje zgodnie z kanałem. To samo robimy z drugim argumentem. Znaną funkcją receive odbieramy wynik. Ciekawy jest sposób dostępu do portów, a mianowicie nie przez kropkę, jak przywykliśmy do tego typu konstrukcji, a przez podwójny dwukropek.

Myślę, że kod jest na tyle prosty, że każdy zrozumiał ideę, ale teraz więcej szczegółów.

  • każdy agent to oddzielny wątek
  • wysyłanie na porty odbywa się przez kopiowanie i jest nieblokujące
  • porty mogą być jedynie typów niezmiennych (immutable) lub w pełni serializowanych
  • możliwe są operacje Multiplex, Combine, Broadcast, Alternate
  • kanały są kompatybilne z WCF

Axum to naprawdę potężne narzędzie, które bez problemu można wpleść w istniejące projekty .NETowe. Jest skalowane, intuicyjne i proste w zaadaptowaniu. W powyższym wpisie przedstawiłem jedynie  zarys funkcjonalności, ale wszystkich gorąco zachęcam do przyjrzeniu się temu narzędziu bliżej.

Dostępna jest wersja Axum zarówno do VisualStudio 2008 oraz 2010 [2]. Dla ciekawskich powyższy projekt powiększony o jeszcze jednego agenta prezentuje na swoim googlowym hostingu kodu [3]. Zapraszam!

Źródła:

Promuj

Agent z wiadomością

Z implementacją równoległych zadań można sobie poradzić na wiele różnych sposobów. Zazwyczaj jednak instalujemy blokady, monitory, tworzymy transakcje, oplatamy synchroniczny kod. Człowiek myśli synchronicznie, działa synchronicznie i często pisze – jeśli potrafi – synchroniczny kod. Co by się jednak stało, gdyby całe takie podejście odwrócić do góry nogami? Takich przełomowych projektów było wiele, oferowały nowy model pisania równoległych aplikacji, bez pamięci wspólnej i z wymianą komunikatów. Takie rozwiązanie, mimo szeregu ograniczeń, jest bardzo skalowalne. Przejdźmy jednak do rzeczy. W dzisiejszym wpisie chciałbym przedstawić Wam Model Agenta [1] (czasami zwany również – Modelem Aktora).

Cała idea tego podejścia polega na wyodrębnieniu agentów/aktorów, którzy spełniają jakąś logicznie pojedynczą rolę. Agenci nie dzielą między sobą żadnych zasobów, chyba że umiejscowieni są w jednej domenie. Zasoby takiej domeny podlegają wtedy synchronizacji. Komunikacja między agentami odbywa się poprzez wiadomości, które są przekazywane – i tu uwaga – przez kopiowanie. W ten prosty sposób każda domena może działać równoległe względem innej – często bywa tak, że w domenie jest tylko jeden agent.

Aby zastosować Model Agenta, najlepiej jest wyobrazić sobie projektowaną aplikację jako – uwaga – osiedle. Cała aplikacja to jedno, przedmiejskie osiedle z domkami i pocztą – tyle. W każdym domku mieszka przynajmniej jeden agent/agentka – dom to właśnie domena. W domku z każdego sprzętu (zasobu) może korzystać tylko jeden agent – mieszkający w tym domku (sąsiad nie może niczego dotykać). Mamy więc synchronizację wewnątrz domeny. Agenci komunikują się ze sobą albo przez listy, które wkładają do skrzynki przed domkiem, a listonosz, zanosi je do odpowiedniej skrzynki adresata (listonosz jest w tym przypadku kanałem), albo przez karteczki na lodówce (wspólną pamięć), kiedy komunikujemy się z domownikiem (agentem w tym samym domu). Każdy agent jest inżynierem w danej kategorii. W listach dostaje dane do pracy i w listach również odsyła wyniki. Jeśli dwóch agentów w domku potrzebuje wiertarki, to jeden musi poczekać, aż drugi skończy swoją pracę. Dokładnie mówiąc, każdy domek działa w innym wątku, a osiedle utożsamiane jest z jednym procesem. Oczywiście, nic nie stoi na przeszkodzie komunikacji między innymi osiedlami :-)

Wiem że, jest to dość duża abstrakcja, ale na sam początek przygody z agentami powinna wystarczyć. Jest tam też kilka niedociągnięć, ale myślę, że kiedy będę omawiał implementacje, na wszystkie pytania, znajdzie się odpowiedź.

Każda implementacja posiada własne smaczki, które wprowadzają pewne udogodnienia w platformie/języku, na jakie dane rozwiązanie jest kierowane. Choć na rynku istnieje kilka implementacji kierowanych na platformę .NET, to w kolejnych wpisach, chciałbym się skoncentrować jedynie na rozwiązaniu zaproponowanym przez Microsoft – Axum [2]. Zapraszam wkrótce.

Źródła:

Promuj

Pamięć Transakcyjna – Istniejące implementacje – cz.2

W poprzednim poście przedstawiłem Wam kilka istniejących implementacji STM, a dzisiaj chciałbym dopełnić tę listę o kilka równie ważnych rozwiązań.

NSTM [2] to .NETowe rozwiązanie Ralfa Sudelbuchera, który na swoim blogu w kilku wpisach [1] wyjaśnia dokładnie, w jaki sposób z niego korzystać.  Tak jak poprzednio opisywane rozwiązania, NSTM opakowuje obiekty, ale w inny sposób, niż robi to np. SXM – opakowując wskazane metody i właściwości obiektu. NSTM trzyma wewnątrz fasady obiekt danej klasy, może go nam zwrócić (zapisze to wtedy w logu) i wtedy mamy możliwość jego modyfikacji, ale nastepnie należy go znów w całości zapisać. Przykład ze strony Ralfa:

  1. INstmObject<double> myAccount;
  2. INstmObject<double> yourAccount;
  3.  
  4. myAccount = NstmMemory.CreateObject(1000);
  5. yourAccount = NstmMemory.CreateObject(500);
  6.  
  7. using (INstmTransaction tx = NstmMemory.BeginTransaction())
  8. {
  9.    double amountToTransfer = 150;
  10.    myAccount.Write(myAccount.Read() – amountToTransfer);
  11.    yourAccount.Write(yourAccount.Read() + amountToTransfer);
  12.    tx.Commit();
  13. }

Kolejnym rozwiązaniem autorstwa trochę większego producenta niż jednoosobowy zespół Ralfa jest Intel® C++ STM Compiler, Prototype Edition 3.0 [3]. Na początek zachęcam do obejrzenia Flashowej prezentacji omawiającej problem transakcji. Choć wszystkie napisy w owej prezentacji brzmią „undefined„, to animacja przedstawiona na rysunku obok doskonale tłumaczy zasady STM. Wracając jednak do samego rozwiązania. Środowisko to oczywiście C++. Odpowiednie metody klas (te, których chcemy używać w transakcji) należy opatrzyć atrybutem __declspec(tm_callable), samą transakcję deklarujemy przy pomocy bloku __declspec(tm_callable). Przykład ze strony producenta, w powiązaniu z OpenMP:

  1. include<stdio.h>
  2.  
  3. int xx = 0;
  4.  
  5. class Base {
  6.   public:
  7.   __declspec(tm_callable)
  8.   virtual void TxnAddOne() {
  9.     xx = xx + 1;
  10.   }
  11. };
  12.  
  13. class Virtual : public Base {
  14.   public:
  15.   __declspec(tm_callable)
  16.   void TxnAddOne() {
  17.     xx = xx + 1;
  18.   }
  19. };
  20.  
  21. int main() {
  22.   Base *x, *y;
  23.  
  24.   __tm_atomic {
  25.     x = new Base();
  26.     x->TxnAddOne();
  27.   }
  28.  
  29.   __tm_atomic {
  30.     y = new Virtual();
  31.     y->TxnAddOne();
  32.   }
  33. }

[Pobierz cały kod ze strony Intela]

Na rozwiązaniu Intela chciałbym zakończyć przedstawianie implementacji STM. Większość tych, które nie zostały omówione, nie była uaktualniana od kilku lat, a jak wiemy, w branży IT 2-3 lata to przepaść.

Był to ostatni wpis na temat Pamięci Transakcyjnej. W następnych postach z cyklu „Go Parallel, be Master” postaram się opisać kolejny sposób na tworzenie aplikacji równoległych, jednak tym razem z wykorzystaniem agentów oraz wiadomości. Zapraszam.

Źródła:

Promuj

Pamięć Transakcyjna – Istniejące implementacje – cz.1

Na rynku istnieje wiele rozwiązań implementująych STM – zdziwilibyście się, jak wiele. Są to rozszerzenia dla więkoszści języków: zaczynając od C, przez C++, C#, Java, Haskell, Perl. Dość pokaźna lista znajduje się w wikipedii. W tym poście chciałbym omówić jedynie kilka.

Rozwiązanie, którego wydajność opisywałem w poprzednim poście, jest modyfikacją maszyny wirtualnej Javy. Dokładny opis znajduje się w dokumencie [1] oraz na tej stronie. Można pobrać przykładowy kod i spróbować samemu uruchomić to rozwiązanie.

Drugie rozwiązanie, jakie chciałbym zaprezentować, zostało stworzone w laboratoriach Microsoft Research (prawdopodobnie przy pomocy Brown University), i nosi nazwę SXM (dokumentacja znajduje się tutaj [2]). Wersję 1.0 można pobrać tutaj [3], a wersję 1.1 tutaj [4]. Jest to implementacja na platformę .NET w postaci specjalnej biblioteki. Zamysł jest prosty: klasy, których chcemy używać równolegle, musimy zarejestrować w fabryce obiektów i dzięki tej fabryce musimy te obiekty tworzyć. Właściwości, których będziemy używać, należy dodatkowo opatrzyć specjalnym atrybutem. Fabryka dynamicznie tworzy podklasę i opakowuje atrybuty w specjalne wywołania – to są właśnie atonomiczne bloki. Dynamiczne tworzenie podklas możliwe jest dzięki mechanizmom z przestrzeni nazw System.Reflection.Emit.  Ponadto kod źródłowy SXM, która można pobrać z podanych linków [3,4], zorganizowany jest jako benchmark. Zawiera dwie różne implementacje fabryk, nakłaniając programistę do napisania swojej i sprawdzenia jej wydajności z istniejącymi.

Kolejne rozwiązanie, również na platformę microsoftu, to STM.NET. Można śmiało założyć, że SXM był pierwowzorem, na którym bazowali inżynierowie tworzący STM.NET. Historia tego produktu jest jednak o wiele bardziej ciekawa. STM.NET funkcjonował od jakiegoś czasu jako projekt na DevLab’ach, czyli wyżej w hierarchii niż MS Research. Blog zespołu tworzącego można śledzić tutaj nadal, mimo tego, że projekt został zakończony – tak można przeczytać na oficjalnej stronie rozwiązania – dnia 13 maja br. Dla programisty zostawiono jedynie podręcznik użytkownika. Rozwiązanie to nie było biblioteką, a zmodyfikowaną wersją platformy .NET 4 beta 1. Jak wiemy, mechanizm transakcji najlepiej sprawdzi się wtedy, kiedy będzie na stałe zintegrowany z platformą, na jaką został napisany – tak właśnie uczynili inżynierowie.

Według mnie projektu nie wycofano, bo był on mało przydatny. Myślę, że wejdzie on w skład Parallel Extensions w następnej wersji platformy – ale to tylko moje domysły. Dlaczego tak uważam? Wiadomo dokładnie, jak nazywał się plik, który był do pobrania w czasie trwania projektu (dotNetFx40_STMNet_10_x86.exe). Na zagranicznych portalach, na których był udostępniany, została po nim tylko notka, że usunięto zasób ze względu na prawa autorskie (zobacz). Ktoś się natrudził, aby to uczynić. Nie ustrzeżono się jednak błędów. Mimo usunięcia strony pobierania archiwa z przykładami i dokumentacją bezpośredni link do pliku działał jeszcze przez ponad miesiąc. Spragniony tego rozwiązania nadal szukam w czeluściach Internetu pliku ze zmodyfikowaną wersją platformy…

W następnym poście opiszę kolejne implementacje. Zapraszam.

Źródła:

Update, godz 14:30:

Z nieznanych mi przyczyn, podany link do zmodyfikowanej platformy, w serwisie depositfiles, zaczął nagle działać.

Promuj

Pamięć Transakcyjna – Wydajność

W poprzednich wpisach przedstawiłem Wam mechanizm Pamięci Transakcyjnej, a teraz chciałbym skupić się na jego wydajności względem zwykłych metod synchronizacji. Niestety pod biurkiem nie posiadam maszyny z kilkunastoma procesorami, dlatego w całej mierze opieram się na badaniu opisanym w dokumencie [1].

Przeprowadzono dwa rodzaje testów (w dokumencie opisano jeden więcej) na dwóch rodzajach maszyn. Obydwa testy polegały na konkurencyjnym dostępie do różnie zaimplementowanej hashmapy. Pierwsza maszyna, na jakiej przeprowadzano testy, miała jedynie 4 procesory, druga zaś miała ich aż 106! (to był rok 2003). W obu testach sukcesywnie zwiększano liczbę dostępnych jednostek.

Porównano 3 różne implementacje Hashmapy. Pierwsza jest standardowo dostępna w pakiecie java.util, HaspMap<K,V>, którą przed współbieżnym dostępem chroni pojedynczy mutex. Druga – z pakietu java.util.concurrent, ConcurrentHashMap<K,V>, zaimplementowana o wiele sprytniej, umożliwiająca m.in. jednoczesne czytanie. Ostatnia implementacja to zmodyfikowana wersja podstawowej hashmapy, w której usunięto mutex, a odpowiednie sekcje opatrzono transakcjami.

Pierwszy test polega na równoczesnym czytaniu i uaktualnianiu wpisów w 4096-elementowej hashmapie. Wyróżniono dwa przypadki: w pierwszym 1% wpisów uaktualniano, a 99% czytano, natomiast w drugim 16% zmieniano, a 84% czytano. Wyniki z 4 procesorowej maszyny (rysunek 1, tabela na górze) wskazują, że najlepszą implementacje miała hashmapa z pakietu java.util.concurrency. Autorzy tłumaczą, że to rozwiązanie jest o wiele bardziej zintegrowane z platformą niż ich własne, a ponadto operacje na kolekcji wykonywane były jedna po drugiej, wykorzystując 100% mocy, a taki przypadek jest mało prawdopodobny w realnych rozwiązaniach.

Inaczej sytuacja wygląda na maszynie ze 106 procesorami. Przy 1% zapisie rozwiązanie wykorzystujące transakcje wygrywało, ale dopiero przy 30 równoległych procesorach. Wytłumaczenie, jakie przytaczali badacze, odnosi się do narzutu spowodowanego zarządzaniem transakcjami. Przy małej ilości równoległych zapisów narzut ten powodował przegraną transakcji. Jednak przy dużej ilości równoległych operacji, transakcje były o tyle bardziej wydajne od java.util.concurrency, że dodatkowy narzut nie przeszkadzał w wygranej. Pamiętajmy, że rozwiązanie z pakietu java.util.concurency pozwala równocześnie czytać, a w rozwiązaniu transakcyjnym czytanie wywołuje zarządzanie transakcjami. Przy 16% uaktualnianiu transakcje wygrywały już od 5 równoległych procesów, ale  w takim stopniu, jak Formuła 1 z Fiatem 126p na 1/4 mili. Prezentują to wykresy a i b na rysunku 2. We wszystkich przypadkach rozwiązanie z pojedynczym mutexem można porównać do ślimaka.

Drugi rodzaj testów polegał na równoległych operacjach „swap”. Wybierano dwa klucze z tablicy hashującej, a następnie zamieniano wartości, na które te klucze się mapowały. Założenie było takie, aby taka operacja była atonomiczna. Pierwsze rozwiązanie, podobnie jak w teście pierwszym, bazowało na pojedynczym mutexie, natomiast w drugiej implementacji (java.util.concurrency) dodano blokady per klucz, a w trzecim przypadku, znów podobnie, użyto transakcji. Do testu użyto map wielkości 256 oraz 4096.

W przypadku więcej niż jednego procesora rozwiązanie z transakcjami bije na głowę pojedynczą blokadę. W porównaniu ze współbieżną hashmapą transakcje wypadają gorzej dla malej liczby procesorów (rysunek 1, tabela na dole). W przypadku maszyny z setką procesorów, wyraźnie widać przewagę transkacji nad pozostałymi metodami. Spowodowane jest to faktem, że niekolidujące aktualizacje mogą być faktycznie wykonywane równolegle, kiedy przy współbieżnej hashmapie procesy walczą o jedną blokadę (rysunek 2, wykresy c i d).

Podsumowując, jeżeli operacje na kolekcji wykonywane są równolegle, a prawdopodobieństwo tego, że procesy będą korzystać z tych samych pól, jest małe, transakcje wykazują znaczącą przewagę nad pozostałymi metodami synchronizacji. Operacje takie mogą faktycznie wykonywać się równoległe, a narzut spowodowany obsługą transakcji jest relatywnie bardzo mały w stosunku do zyskanej wydajności.

W przypadku niejasności odsyłam zainteresowany do lektury dokumentu [1].

Rysunek 1, Maszyna 4 rdzeniowa

Rysunek 2, Maszyna 106 rdzeniowa

Źródła:

Promuj