thumb|Galera – komputer równoległy złożony z ponad 1000 procesorów. Obliczenia równoległe – forma wykonywania obliczeń, w której wiele instrukcji jest wykonywanych jednocześnieG.S. Almasi, A. Gottlieb, Highly Parallel Computing. Benjamin-Cummings publishers, Redwood city, CA, 1989.. Taka forma przetwarzania danych była wykorzystywana przez wiele lat, głównie przy wykorzystaniu superkomputerów, a szczególne znaczenie zyskała z uwagi na fizyczne ograniczenia uniemożliwiające dalsze zwiększanie częstotliwości taktowania procesorów. Obliczenia równoległe stały się dominującym wzorcem w architekturze komputerowej, głównie za sprawą upowszechnienia procesorów wielordzeniowychKrste Asanovic i in., The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Raport Techniczny numer UCB/EECS-2006-183. 18 grudnia 2006: „Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better’ position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit.”..
Ze względu na skalę można wyróżnić obliczenia równoległe na poziomie: bitów, instrukcji, danych, zadań.
Ze względu na poziom, na którym sprzęt wspomaga operacje równoległe, można wyróżnić komputery: jednoprocesorowe wielordzeniowe (zawierające jeden procesor wielordzeniowy), symetryczne wieloprocesorowe (zawierające kilka identycznych, równorzędnych procesorów), systemy składające się z wielu maszyn: klastry, systemy MPP, gridy.
Do prowadzenia obliczeń równoległych, oprócz sprzętu, konieczne są również odpowiednie algorytmy nazywane równoległymi. Są one trudniejsze w implementacji niż sekwencyjneDavid A. Patterson, John L. Hennessy, Computer Organization and Design (Second Edition), Morgan Kaufmann Publishers, 1998. , s. 715., ponieważ współbieżność wprowadza dodatkowe możliwości popełnienia błędu. Powstają również dodatkowe problemy w uzyskaniu wysokiej wydajności z powodu dodatkowych nakładów na komunikację i konieczność synchronizacji obliczeń.
Obliczenia zależne, niezależne i granica ich przyspieszania W przetwarzaniu sekwencyjnym, aby rozwiązać problem obliczeniowy, tworzony jest algorytm, który składa się z ciągu instrukcji. Instrukcje te są wykonywane, w ustalonej kolejności na jednej jednostce obliczeniowej. Nie można wykonywać więcej niż jednej instrukcji jednocześnie – po ukończeniu jednej instrukcji, wykonywana jest kolejna.
W obliczeniach równoległych, aby rozwiązać dany problem, wykorzystuje się wiele jednostek obliczeniowych jednocześnie. Można tak postąpić, dzieląc problem na mniejsze, niezależne części, z których jedna może być wykonywana niezależnie od pozostałych. Jeśli uda się przeprowadzić taki podział, każda z części może być wykonana na innej jednostce obliczeniowej w tym samym czasie co pozostałe.
Wyodrębnienie tych niezależnych części jest kluczowe w implementacji algorytmów równoległych. Żaden program nie może być wykonany szybciej niż najdłuższy łańcuch zależnych od siebie obliczeń (znanych jako ścieżka krytyczna), ponieważ obliczenia, które są zależne od poprzednich obliczeń w łańcuchu, muszą być wykonywane po sobie. Jednak większość algorytmów nie składa się tylko z długich łańcuchów zależnych od siebie obliczeń; najczęściej pojawia się możliwość wykonania niezależnych obliczeń równolegle.
Warunki Bernsteina Niech Pi i Pj będą dwoma fragmentami programu. Warunki BernsteinaA.J. Bernstein, Program Analysis for Parallel Processing, IEEE Trans. on Electronic Computers, EC-15, październik 1966, s. 757–762. opisują, kiedy dwa fragmenty są niezależne od siebie i mogą być wykonane równolegle bez żadnych przeszkód. Niech Ii będzie zbiorem wszystkich zmiennych wejściowych dla Pi, a Oi zbiorem jego zmiennych wyjściowych (podobnie Ij i Oj dla Pj). Pi i Pj są niezależne, jeśli spełniają następujące warunki:
Naruszenie pierwszego lub drugiego warunku wprowadza zależność przepływu, odpowiadającą sytuacji, w której wynikiem działania Pi jest wartość wykorzystywana przez Pj (lub odwrotnie). Trzeci warunek to wymaganie niezależności wyjścia. W sytuacji, gdy dwie wartości są zapisywane w jednym miejscu, to druga nadpisze pierwsząRoosta, Seyed H., Parallel processing and parallel algorithms: theory and computation, 2000, Springer, , s. 114..
Przykład 1 Poniżej przedstawiono dwie funkcje. Pierwsza zawiera przykładowe operacje zależne, a druga niezależne:
1: function Zależne(a, b) 2: c := a·b 3: d := 2·c 4: end function
Operacja 3 w Zależne(a, b) nie może być wykonana przed (czy nawet równolegle z) operacją 2, ponieważ operacja 3 wykorzystuje wynik z operacji 2. Narusza warunek 1 i w konsekwencji wymusza określony przepływ sterowania.
1: function Niezależne(a, b) 2: c := a·b 3: d := 2·b 4: e := a+b 5: end function
W tym przykładzie nie ma żadnych zależności pomiędzy operacjami, a więc mogą one być wykonane równolegle.
Przykład 2 Spełnienie warunków Bernsteina może zależeć również od tego, w jaki sposób zapisano program. Przykładowo w funkcji
1: function ZależneII(a, b) 2: a := b + 5 3: c := a + 10 4: end function
wartość c zależy od wyliczanego wcześniej a. Można jednak w prosty sposób usunąć tę zależność i napisać równoważnie:
1: function NiezależneII(a, b) 2: a := b + 5 3: c := b + 15 4: end function
Warunki Bernsteina nie zezwalają na współdzielenie pamięci, a w konsekwencji na wymianę informacji pomiędzy podprogramami. Aby zapewnić możliwość komunikacji, potrzebne jest więc ustalanie kolejności między dostępami do pamięci, korzystając z takich technik jak semafory, bariery czy inne techniki synchronizacji.
Sytuacje wyścigu, wzajemne wykluczanie, synchronizacja i spowolnienie równoległe Podczas wykonywania programu równoległego, poszczególne jego podzadaniaPodzadania składowe programu realizowanego równolegle mogą być wątkami tego samego procesu. Niektóre równolegle pracujące komputery zaprojektowane są tak, by wykorzystywać lżejsze odmiany wątków – włókna, możliwe jest również wykorzystanie oddzielnych procesów. komunikują się ze sobą, a ich poszczególne instrukcje mogą się przeplatać w dowolny sposób. W poniższym przykładzie dwa podzadania operują na współdzielonej zmiennej
Podzadanie APodzadanie B1A: Odczytaj zmienną V1B: Odczytaj zmienną V2A: Dodaj 1 do zmiennej V2B: Dodaj 1 do zmiennej V3A: Zapisz wartość w zmiennej V3B: Zapisz wartość w zmiennej V
Jeśli instrukcja 1B zostanie wykonana pomiędzy 1A i 3A, lub jeśli instrukcja 1A zostanie wykonana pomiędzy 1B i 3B, to wynik działania programu będzie nieprawidłowy. Zjawisko to jest znane jako wyścigi lub hazard (ang. race conditions), a fragment programu, który nie powinien być wykonywany przez kilka podzadań jednocześnie, nazywamy sekcją krytyczną. W takim przypadku jak powyżej programista powinien zapewnić wzajemne wykluczanie pomiędzy podzadaniami w dostępie do zmiennej Można to osiągnąć, stosując blokady – konstrukcje programistyczne, dzięki którym tylko jedno podzadania ma dostęp do określonego zasobu. Powyższy fragment programu przepisany z użyciem blokad mógłby zostać przepisany w następujący sposób:
Podzadanie APodzadanie B1A: Zablokuj zmienną V1B: Zablokuj zmienną V2A: Odczytaj zmienną V2B: Odczytaj zmienną V3A: Dodaj 1 do zmiennej V3B: Dodaj 1 do zmiennej V4A: Zapisz wartość w zmiennej V4B: Zapisz wartość w zmiennej V5A: Odblokuj zmienną V5B: Odblokuj zmienną V
Tylko jedno z podzadań z sukcesem zablokuje zmienną i uzyska do niej wyłączny dostęp, podczas gdy drugie będzie musiało czekać na jej odblokowanie. Zastosowanie powyższej konstrukcji daje gwarancję poprawnego wykonania programu, kosztem jest jednak jego spowolnienie, które może być znaczne.
Blokowanie wielu zmiennych przy użyciu nieatomowych blokad może spowodować zakleszczenie. Atomowość blokady to własność, która gwarantuje, że wszystkie zmienne blokowane są razem, to znaczy, jeśli dwa podzadania próbują zablokować kilka zmiennych, to uda się to tylko jednemu z nich i blokada powstanie na wszystkich zmiennych. Jeśli natomiast blokady nie są atomowe, to może się zdarzyć, że jeśli dwa podzadania próbują zablokować te same dwie zmienne, to jeden z nich zablokuje jedną, a drugi drugą. W powstałej sytuacji oba podzadania czekają na siebie nawzajem i żaden z nich nie może zakończyć działania. Taką sytuację nazywamy zakleszczeniem.
Wiele programów równoległych wymaga by ich podzadania były dodatkowo synchronizowane. Taką możliwość daje użycie bariery. Bariery są zwykle implementowane za pomocą blokad. Wyróżnia się klasa algorytmów, w których nie używa się ani blokad ani barier (ang. lock-free and wait-free algorithms). Jednak stosowanie tego podejścia napotyka spore trudności (za przedstawienie eleganckich dowodów, wykorzystujących elementy topologii algebraicznej, niemożliwości rozwiązania dość prostych problemów przyznano Nagrodę Gödla w 2004 roku).
Nie każda próba „zrównoleglenia” daje efekt w postaci przyspieszenia obliczeń. W ogólności, jeśli program jest dzielony na coraz więcej i więcej podzadań, to w pewnym momencie narzuty związane z komunikacją zaczynają przeważać nad zyskiem ze „zrównoleglenia” i pomimo zwiększania teoretycznej mocy obliczeniowej mamy do czynienia ze spowolnieniem obliczeń. Zjawisko to nazywane jest spowolnieniem równoległym (ang. parallel slowdown). Próbą górnego oszacowania możliwego przyspieszenia uzyskanego przez zrównoleglenie obliczeń dają prawa: Amdahla i Gustafsona.
Prawa Amdahla i Gustafsona thumbnail|Przykładowy wykres czasu wykonania programu (actual runtime) i jego przyspieszenie (actual speedup) w zależności od liczby procesorów. W pewnym momencie, pomimo zwiększania liczby procesorów, czas obliczeń przestaje maleć (podobnie przyspieszenie przestaje rosnąć). Zaznaczono również optymalny wzrost przyspieszenia (ideal speedup) oraz optymalny spadek czasu obliczeń (ideal runtime). Teoretycznie, przyspieszenie spowodowane zrównolegleniem mogłoby być co najwyżej liniowe – podwojenie liczby jednostek obliczeniowych nie może zmniejszyć czasu obliczeń o więcej niż połowę, jednak w praktyce osiągnięcie optymalnego przyspieszenia nie jest możliwe. Większość realizacji osiąga przyspieszenie bliskie optymalnemu tylko dla małej liczby jednostek obliczeniowych.
Potencjalne przyspieszenie algorytmu na platformie korzystającej z obliczeń równoległych jest określone przez prawo Amdahla sformułowane w latach 60. XX wiekuG. Amdahl, The validity of the single processor approach to achieving large-scale computing capabilities, Materiały konferencyjne AFIPS Spring Joint Computer Conference, s. 483–485, Atlantic City, N.J., kwiecień 1967. AFIPS Press.. Prawo to wychodzi z założenia, że duży matematyczny czy inżynierski problem typowo składa się z takich części, które udaje się zrównoleglić i z takich, dla których nie jest to możliwe. Prawo Amdahla stanowi, iż fragmenty programu, które nie mogą być zrównoleglone, ograniczają możliwe do osiągnięcia przyspieszenie całego procesu. Ten związek jest definiowany przez następujące równanie: