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


Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

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.  

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.  

[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

Co ma wspólnego Google i Europride?

Co mam wspólnego Google, Android i Europride? Wszyscy są dzisiaj w Warszawie. Marsz z Pl. Bankowego na Pl. Konstytucji się jeszcze nie zakończył, ale już teraz przesyłam Wam zdjęcia platformy,  której tam się nie spodziewałem zobaczyć :) Chociaż, Google zawsze propagowało wolność…

Dodatkowo, jeśli w polskiej wersji wyszukiwarki, wpiszecie 'gej’ albo 'lesbijka’, na stronie z wynikami, pojawi się charakterystyczna tęcza, utożsamiana z homoseksualizmem.

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

Pamięć Transakcyjna – Od kuchni


Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

W poprzednim poście wprowadziłem Was wstępnie w zagadnienie Pamięci Transakcyjnej. Dzisiaj kolejna porcja informacji na temat STM.

Pamiętacie przykład z Bankiem? Zależało nam, aby dwie operacje, debetowa oraz kredytowa, były wykonane, w kontekście jednej. Do tego celu zdefiniowaliśmy transakcje. Przypominam kod transferu:

  1.  

Zgodnie założeniem transakcji (pamięci transakcyjnej) obydwie operacje powinniśmy umieścić w atomowym bloku.

  1.  

Przypuśćmy, że w tym samym czasie wykonywane są setki transakcji. Niektóre z nich używają tych samych kont bankowych. W takim przypadku transakcja powinna zachowywać się w następujący sposób: po wejściu w atmowy blok nic specjalnego nie powinno się wydarzyć. Pierwsza instrukcja – debetowa – modyfikuje stan konta, ale w taki sposób, że zmienione saldo tego konta widoczne jest jedynie wewnątrz transakcji (wewnątrz bloku atomic), a nie na zewnątrz. W podobny sposób wykonywana jest metoda kredytująca. Jeżeli mechnizm STM wykryje, że jakaś instrukcja modyfikuje/pobiera dane, które zmieniły się od chwili wejścia w blok atomowy, wszystkie instrukcje wykonane w tym bloku są wycofywane, a transakcja rozpoczyna się ponownie. Jeśli cała transakcja przebiegła poprawnie (bez wykrycia kolizji), to na końcu atomowego bloku zmienione dane są zatwierdzane (wykonany jest commit) i od tej chwili są widoczne dla wszystkich. Jak widać, założenie pamięci transakcyjnej jest bardzo optymistyczne.

Pewnie zadajecie sobie teraz pytanie, w jaki sposób wycofywać operacje? I słusznie. Oczywiście, w przypadku niektórych metod można zdefiniować „metodę wsteczną”, ale w ten sposób nie uzyskamy izolacji, jednej z czterech własności transakcji, a ponadto nadal będziemy zmagać się z wyścigami. Właśnie dlatego STM bardzo trudno zaimplementować jako zewnętrzną bibliotekę, ponieważ mechanizm ten musi być ściśle powiązany ze środowiskiem wykonawczym.

Każdy odczyt oraz każdy zapis w atomowym bloku powinien być umieszczany w logu. Wpisy te posłużą albo do wycofania transakcji, albo do jej zatwierdzania. Zarządzanie takim logiem jest kluczowym aspektem w mechnizmie STM. Drugą ważną kwestią jest wykrywanie konfliktów, podczas których transakcja powinna być wycofana.

Istnieją dwie metody implementacji STM: z blokowaniem lub bez, czyli podobnie jak w mechanizmie synchronizacji. Jeden z pierwszych pomysłów, opisany w dokumencie [1], przedstawia implementację STM dla języka Java. Ograniczeniem w tym rozwiązaniu jest możliwość operowania jedynie na danych długości jednego słowa. Używa się w nim dodatkowych struktur, które przechowują informacje o transakcji. Sam atomowy blok przedstawiony jest następująco:

  1. span class=”co1″>//tutaj umieszcza się operacje

Więcej informacji o tym rozwiązaniu w dokumencie [1]. W kolejnym wpisie skoncentruję się na wydajności STM oraz porównam go ze zwykłym mechanizmem synchronizacji. Zapraszam.

Źródła:

Promuj

Microsoft Biology Foundation

Microsoft Research opublikował pierwszą wersję Biology Foundation – zestawu narzędzi kierowanych do specjalistów od bioinformatyki, które stanowi rozszerzenie dla platformy .NET. Pierwsza wersja zawiera zbiór parserów, umożliwiających czytanie z popularnych formatów wykorzystywanych w bioinformatyce, a także zestaw algorytmów do manipulowania DNA, RNA oraz sekwencją białek. Ponadto rozszerzenie zawiera connectory do biolgicznych web serwisów takich jak NCBI BLAST.

Piszę o tym, ponieważ wiekszość zaimplementowanych algorytmów w tej bibliotece wykorzystuje potencjał Parallel Extensions. Algorytmy takie dają się łatwo zrównoleglić, ponieważ zawierają etapy, które można podzielić na mniejsze niezależne części, mogące zachodzić równolegle.

Zapraszam na stronę projektu.

Źródło: MSDN Blogs > External Research Team Blog

Promuj