Haskell. Po polsku.

Nowinki o funkcyjnym języku programowania Haskell

Równoległość /= współbieżność

leave a comment »

Tłumaczone z Parallelism /= Concurrency.

Jeśli chcesz przyspieszyć program na maszynie równoległej, potrzebujesz współbieżności, prawda?

W tym artykule postaram się wyjaśnić dlaczego powyższe zdanie jest fałszywe i dlaczego powinniśmy bardzo dobrze rozumieć różnicę pomiędzy współbieżnością a równoległością. Podkreślam, że niniejsze idee nie są ani moje ani w żadnym wypadku nowe, ale myślę, że powinny być dobrze zrozumiane, jeśli mamy umożliwić szerszej rzeszy programistów wykorzystanie procesorów wielordzeniowych. Poczułem się zmotywowany artykułem Tima Braya na Concur.next, by również napisać parę słów na ten temat. Zgadzam się z większością twierdzeń napisanych przez Tima, w szczególności:

Narażanie programistów aplikacji na używania wątków z wywłaszczaniem w połączeniu ze współdzielonymi zmienianymi strukturami danych jest złe.

Zdaje się, że równoległość oraz współbieżność dalej są mylone. Tak, potrzebujemy współbieżności w naszych językach programowania, ale jeśli jedynym celem jest przyspieszenie programów na maszynach wielordzeniowych, współbieżność powinna być ostatnią deską ratunku.

Po pierwsze ustalmy terminologię, definicje pojęć.

Program współbieżny to taki, który ma wiele wątków przepływu sterowania. Działanie każdego z tych wątków ma swoje skutki w świecie a wątki te są przeplatane w nieokreślony sposób przez algorytm szeregowania (scheduler). Mówimy, że program współbieżny jest niedeterministyczny, gdyż całkowity efekt programu może zależeć od sposobu poszeregowania akcji w wątkach podczas wykonania. Do programisty należy wtedy trudne zadanie kontrolowania niedeterminizmu przy użyciu mechanizmów synchronizacyjnych tak, aby program wykonywał swoje zadanie poprawnie, niezależnie od kolejności szeregowania. A to zdecydowanie nie jest proste, gdyż nie istnieje dobry sposób na przetestowanie wszystkich możliwych przypadków. I to niezależnie od wykorzystanej technologii synchronizacyjnej: tak, STM jest lepsze niż zamki, przesyłanie komunikatów ma swoje zalety, ale to wszystko są tylko sposoby na komunikację pomiędzy wątkami w niedeterministycznym języku.

Program równoległy to taki, który wykonuje się na wielu procesorach z nadzieją szybszego działania niż na pojedynczym CPU.

Zatem się skąd bierze to niebezpieczne założenie, że równoległość == współbieżność? Jest ono naturalną konsekwencją języków z efektami ubocznymi: jeśli twój język wszędzie ma efekty uboczne, to gdy próbujesz robić więcej niż jedną rzecz naraz w zasadzie zawsze otrzymujesz niedeterminizm wynikający z przeplotu efektów z każdej operacji. Czyli w języku z efektami ubocznymi jedynym sposobem uzyskania równoległości jest współbieżność. Nic dziwnego, że pojęcia te są często mylone.

Jednakże w językach bez efektów ubocznych można wykonywać różne części programu w tym samym czasie bez obserwowania jakichkolwiek różnic w wyniku. To jeden z powodów dlaczego uważam, że nasze wybawienie leży w językach programowania ściśle kontrolujących efekty uboczne. Drogą dla języków z efektami ubocznymi jest większa dosłowność jeśli chodzi o efekty, dzięki temu części bez efektów ubocznych będą mogły zostać zidentyfikowane i wykorzystane.

Boli mnie, gdy widzę porównanie współbieżności w Haskellu do wsparcia dla współbieżności w innych językach, gdy celem jest tylko i wyłącznie użycie wielordzeniowego procesora. Nie o to chodzi: tak, Haskell ma najlepsze wsparcie dla współbieżności (oczywiście), ale akurat w takim scenariuszu Haskell ma nawet coś lepszego: deterministyczną równoległość. W Haskellu możesz użyć wielu rdzeni bez babrania się we współbieżność i niedeterminizm, bez synchronizacji a za to z gwarancją, że twój równoległy program zawsze da ten sam wynik, najwyżej trochę szybciej.

Wsparcie dla równoległości w Haskellu ma dwa oblicza:

par/pseq i strategie. To daje możliwość dodania równoległości do już istniejącego programu, zwykle bez głębokiej zmiany jego struktury. Dla przykładu, istnieje równoległa wersja funkcji ‚map’. Wsparcie dla tego rodzaju równoległości właśnie dojrzewa i będzie niedługo dostępne w GHC 6.12.1. Dokonaliśmy w tym zakresie znaczących usprawnień wydajnościowych w porównaniu z wersjami poprzednimi.

Równoległość danych zagnieżdżonych (Nested Data Parallelism) umożliwia wykorzystania równoległości w algorytmach składających się z operacji na tablicach (również tablicach zagnieżdżonych). Kompilator zajmuje się spłaszczeniem struktury tablic, łączeniem operacji oraz dzieleniem pracy pomiędzy dostępne procesory. W przyszłości Data-Parallel Haskell umożliwi wykorzystanie GPU i innych architektur wielordzeniowych na większą skalę. A na razie DPH jest nadal rozwijane w ramach GHC i ma status eksperymentalny.

Oczywiście nie twierdzę, że współbieżność nie ma swoich zastosowań. Kiedy zatem powinno się używać współbieżności? Współbieżność jest najbardziej użyteczna jako struktura programu, który musi się komunikować jednocześnie z wieloma zewnętrznymi klientami albo odpowiadać na wiele asynchronicznych wejść. Jest idealna dla aplikacji GUI reagującej na akcje użytkownika jednocześnie komunikującego się z bazą danych i odświeżającej ekran, dla aplikacji sieciowej, która rozmawia z wieloma klientami jednocześnie czy też dla programu, który działa w połączeniu z wieloma fizycznymi urządzeniami. Współbieżność pozwala na takie sformułowanie struktury programu, że każda komunikacja jest zadaniem sekwencyjnym, jest wątkiem. Zwykle w takich sytuacjach współbieżność jest idealną abstrakcją. A STM potrafi wtedy znacząco uprościć programowanie.

Na szczęście możemy uruchamiać współbieżne pogramy równolegle bez zmiany ich semantyki. Jednakże współbieżne programy zwykle nie są ograniczone mocami obliczeniowymi, więc niewiele można ugrać uruchamiając je rzeczywiście równolegle, być może co najwyżej mniejsze opóźnienia w reakcjach programu.

Na koniec zauważmy, że jest pewna część wspólna współbieżności i równoległości. Niektóre algorytmy celowo używają wielu równoległych wątków, na przykład w problemach szukania wiele wątków ma za zadanie podzielić przestrzeń problemu na części, a wiedza uzyskana w jednym wątku może być użyta w innym, współbieżnym przeszukiwaniu. Przykładem takiego podejścia może być rozwiązywanie zadań logicznych (SAT) czy też algorytmy grające w gry. W jaki sposób wprowadzić takie niedeterministyczne rodzaje równoległości w bezpieczny sposób pozostaje pytaniem otwartym. W Haskellu takie algorytmy trafiłyby do monady IO, chociaż w rzeczywistości wyniki całościowe mogą być deterministyczne. Uważam, że tego typu problemy stanowią jednak niszę i możemy bardzo daleko zajść z czysto deterministyczną równoległością.

Na pewno ucieszy cie wiadomość, że w GHC możesz dowolnie łączyć równoległość i współbieżność na wielordzeniowych CPU zgodnie ze swoim upodobaniem. Przekonaj się sam!

About these ads

Written by gracjanpolak

Październik 7, 2009 at 16:11

Napisane w Haskell

Dodaj komentarz

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

Obserwuj

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.

%d bloggers like this: