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śnie^[1]. Taka forma przetwarzania danych była wykorzystywana przez wiele lat, z reguły przy wykorzystaniu superkomputerów, a szczególne zainteresowanie zyskała w ostatnich latach, z uwagi na fizyczne ograniczenia uniemożliwiające dalsze zwiększanie częstotliwości taktowania procesorów. Obliczenia równoległe są dominującym wzorcem w architekturze komputerowej, z reguły za sprawą upowszechnienia procesorów wielordzeniowych^[2].

Z uwagi na skalę da się wyróżnić obliczenia równoległe: na poziomie bitów, instrukcji, danych oraz zadań, natomiast ze względu na poziom, na którym sprzęt wspomaga operacje równoległe, da się wyróżnić komputery: jednoprocesorowe wielordzeniowe (zawierające jeden procesor wielordzeniowy), symetryczne wieloprocesorowe (zawierające parę identycznych, równorzędnych procesorów) oraz systemy składające się z wielu maszyn: klastry, systemy MPP czy gridy.

Do prowadzenia obliczeń równoległych, oprócz sprzętu, konieczne są także odpowiednie algorytmy nazywane równoległymi. Są one trudniejsze w implementacji niż sekwencyjne^[3], albowiem współbieżność wprowadza dodatkowe możliwości popełnienia błędu. Powstają także dodatkowe problemy w uzyskaniu wysokiej wydajności z powodu dodatkowych nakładów na komunikację oraz konieczność synchronizacji obliczeń.

Obliczenia zależne, niezależne oraz 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 da się wykonywać więcej niż jednej instrukcji równocześnie – po ukończeniu jednej instrukcji, wykonywana jest kolejna^[4].

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 bywa wykonywana niezależnie od pozostałych. Jeśli uda się przeprowadzić taki podział, każda z części bywa wykonana na innej jednostce obliczeniowej w tym samym czasie co pozostałe^[4].

Wyodrębnienie tych niezależnych części jest kluczowe w implementacji algorytmów równoległych. Żaden program nie bywa wykonany szybciej niż najdłuższy łańcuch zależnych od siebie obliczeń (znanych jako ścieżka krytyczna), albowiem obliczenia, które są zależne od poprzednich obliczeń w łańcuchu muszą być wykonywane po sobie. Jednak przeważajaca ilość algorytmów nie składa się tylko z długich łańcuchów zależnych od siebie obliczeń; najczęściej ukazuje się możliwość wykonania niezależnych obliczeń równolegle.

Warunki Bernsteina

Niech P_i oraz P_j będą dwoma fragmentami programu. Warunki Bernsteina^[5] opisują kiedy dwa fragmenty są niezależne od siebie oraz bywają wykonane równolegle bez żadnych przeszkód. Niech I_i będzie zbiorem wszystkich zmiennych wejściowych dla P_i, a O_i zbiorem jego zmiennych wyjściowych (podobnie I_j oraz O_j dla P_j). P_i oraz P_j są niezależne, jeśli spełniają następujące warunki:

• 
• 
• .

Naruszenie pierwszego albo drugiego warunku wprowadza zależność przepływu, odpowiadającą sytuacji, w której wynikiem działania P_i jest wartość wykorzystywana przez P_j (lub odwrotnie). Trzeci warunek to wymaganie niezależności wyjścia. W sytuacji, kiedy dwie wartości są zapisywane w jednym miejscu, to druga nadpisze pierwszą^[6].

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 bywa wykonana przed (czy nawet równolegle z) operacją 2, albowiem operacja 3 wykorzystuje wynik z operacji 2. Narusza warunek 1 oraz 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 potrafią one być wykonane równolegle.

Przykład 2

Spełnienie warunków Bernsteina może zależeć także od tego, w jaki sposób zapisano program. Dla przykładu 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ść oraz 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 pomiędzy dostępami do pamięci, korzystając z takich technik jak semafory, bariery czy inne techniki synchronizacji.

Sytuacje wyścigu, wzajemne wykluczanie, synchronizacja oraz spowolnienie równoległe

Podczas wykonywania programu równoległego, poszczególne jego podzadania^[7] komunikują się ze sobą, a ich poszczególne instrukcje potrafią się przeplatać w dowolny sposób. W poniższym przykładzie dwa podzadania operują na współdzielonej zmiennej V:

Jeśli instrukcja 1B zostanie wykonana pomiędzy 1A oraz 3A, albo jeśli instrukcja 1A zostanie wykonana pomiędzy 1B oraz 3B, to wynik działania programu będzie nieprawidłowy. Zjawisko to jest znane jako wyścigi albo hazard (ang. race conditions), a fragment programu, który nie powinien być wykonywany przez parę 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 V. 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:

Tylko jedno z podzadań z sukcesem zablokuje zmienną V oraz uzyska do niej wyłączny dostęp, z tym że 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 bywa 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ć parę zmiennych, to uda się to tylko jednemu z nich oraz 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 oraz ż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 nader prostych problemów przyznano Nagrodą Gödla w 2004).

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 oraz więcej podzadań, to w pewnym momencie narzuty związane z komunikacją zaczynają przeważać nad zyskiem ze "zrównoleglenia" oraz 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 oraz Gustafsona.

Prawa Amdahla oraz Gustafsona

Przykładowy wykres czasu wykonania programu (actual runtime) oraz 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 także 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. Przeważajaca ilość 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 wieku^[8]. 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ć oraz z takich, dla których nie jest to możliwe. Prawo Amdahla stanowi iż fragmenty programu które nie bywają zrównoleglone ograniczają możliwe do osiągnięcia przyspieszenie całego procesu. Ten związek jest definiowany przez następujące równanie:

gdzie: S jest maksymalnym, możliwym do osiągnięcia przyspieszeniem programu (jako ułamek swojej pierwotnej prędkości w przypadku wykonywania sekwencyjnego), a P jest ułamkiem który wyznacza jaką cząstka obliczeń da się "zrównoleglić". Na przykład, jeśli sekwencyjna cząstka programu stanowi 10% całkowitego czasu potrzebnego na jego wykonanie (), to da się osiągnąć nie więcej niż 10-krotne przyspieszenie, niezależnie od ilości procesorów jakie zostaną dodane. Tworzy to odgórny limit przydatności dodawania większej ilości jednostek obliczeniowych. "Jeśli zadanie nie bywa podzielone z uwagi na ograniczenia wynikające z sekwencyjności problemu, dodane mocy przetwarzania nie wpłynie na czas jego wykonania. Ciąża u ludzi trwa dziewięć miesięcy, obojętnie, ile kobiet uczestniczy w jej utrzymaniu"^[9].

Graficzna reprezentacja prawa Amdahla. Jeśli zadanie składa się z dwóch niezależnych części A oraz B oraz cząstka B stanowi około 25% czasu potrzebnego na wykonanie całego zadania, to pięciokrotne przyspieszenie wykonania części B skutkuje wydatnie mniejszym przyspieszeniem wykonania całości zadania niż zaledwie dwukrotne przyspieszenie wykonania części A.

Kolejne prawo, nazywane Prawem Gustafsona (ang. Gustafson's law) jest blisko spokrewnionym z prawem Amdahla. Gustafson w swojej pracy^[10] argumentował, że co prawda dla ustalonego rozmiaru problemu, prawo Amdahla jest słuszne, jednak z jego praktyki badawczej wynika, że dysponując większą liczbą procesorów, próbuje się także rozwiązywać większe problemy, co z kolei powoduje, że coraz większa cząstka obliczeń jest możliwa do zrównoleglenia.

Inne ograniczenie możliwości "zrównoleglania" algorytmów pochodzi z teorii złożoności obliczeniowej. Podobnie jak dla obliczeń sekwencyjnych istnieje klasa problemów NP-zupełnych tak w obliczeniach równoległych istnieje klasa problemów P-zupełnych, których dobre "zrównoleglenie" jest prawdopodobnie niemożliwe^[11].

Równoległość drobno- oraz gruboziarnista

Aplikacje bywają klasyfikowane pod względem tego jak wielokrotnie podzadania wymagają synchronizacji albo komunikują się ze sobą. Mówimy o równoległości drobnoziarnistej (ang. fine-grained), jeśli komunikacja następuje wielokrotnie w ciągu sekundy, a gruboziarnistej (ang. coarse-grained) jeśli jest rzadziej. Z najłatwiejszym przypadkiem mamy do czynienia, kiedy komunikacja nie jest w ogóle albo sporadycznie (żargonowo taką sytuację wyznacza się jako embarrassing parallelism).

Modele spójności

Leslie Lamport jako pierwszy zdefiniował koncepcję spójności sekwencyjnej. Jest także znany za swoją pracę w tworzeniu oprogramowania LaTeX.

W systemach przetwarzania równoległego w celu przyspieszenia wykonywania operacji na pamięci współdzielonej stosuje się lokalne pamięci podręczne oraz buforowanie operacji zapisu^[12]. Istnienie tych mechanizmów może prowadzić do niespójności (dla wielorakich procesów te same, wspólne dane potrafią przez pewien czas posiadać zróżnicowane wartości). Jako przykład da się podać następującą sekwencję instrukcji (x oraz y są zmiennymi współdzielonymi, początkowo obie są równe 0):

Realizacja wspomnianych mechanizmów może dopuścić sytuację, kiedy aktualizacja zmiennych x oraz y jest dostarczana do wątku A w zmienionej kolejności, a więc mogłoby się zdarzyć, że wynik porównania w 3A byłby fałszywy. Z uwagi na z tym języki programowania równoległego oraz komputery równoległe muszą posiadać model spójności (ang. consistency model), który definiuje zasady wykonywania operacji na zmiennych współdzielonych w pamięci komputera oraz w jaki sposób powstają wyniki tych operacji.

Jednym z pierwszych modeli spójności był model spójności sekwencyjnej Lesliego Lamporta. Spójność sekwencyjna oznacza, że wyniki każdego możliwego działania programu równoległego są takie same jak wynik działania dla pewnego ustalonego sekwencyjnego wykonania tych operacji, przy czym kolejność wykonywania operacji przez każdy pojedynczy procesor zgadza się z kolejnością wykonania zapisaną w jego programie^[13].

Powszechnym modelem spójności pamięci jest STM (ang. software transactional memory, w którym używa się koncepcji atomowych transakcji zapożyczonej z teorii baz danych.

Modele spójności pamięci bywają przedstawiane formalnie na wiele sposobów. Wczesnym matematycznym modelem dla dyskretnych systemów rozproszonych są sieci Petriego, które Carl Adam Petri zdefiniował w swojej rozprawie doktorskiej w 1962 roku.

Taksonomia Flynna oraz typy zrównoleglania

Taksonomia Flynna

Michael J. Flynn stworzył jedną z najwcześniejszych klasyfikacji systemów dla równoległych (i sekwencyjnych) komputerów oraz programów, znaną jako taksonomia Flynna. Flynn zaklasyfikował programy oraz komputery wedle tego czy dany program albo komputer wykorzystuje z jednego, czy z wielu zbiorów instrukcji oraz czy te instrukcje korzystają z jednego, czy z wielu zbiorów danych.

W obrębie podziału Flynn wyróżnił cztery klasy: SISD (ang. single-instruction-single-data) równoważną przetwarzaniu całkowicie sekwencyjnemu; SIMD (ang. single-instruction-multiple-data), gdzie wykonuje się te same operacje na wielorakich zbiorach danych − jak to ma wielokrotnie miejsce przy przetwarzaniu sygnałów; MISD (ang multiple-instruction-single-data) to sporadycznie używana klasa, w której wykonujemy zróżnicowane operacje na tym samym zbiorze danych (zob. systolic arrays); oraz w końcu MIMD (ang. Multiple-instruction-multiple-data), gdzie zróżnicowane operacje wykonywane są na wielorakich zbiorach danych − jest to najczęstszy przypadek w przetwarzaniu równoległym.

Wedle Davida Pattersona oraz Johna Hennesy'a, " Pewne maszyny są bez wątpienia hybrydami tych kategorii, jednak ten klasyczny model przetrwał albowiem jest prosty, łatwy do zrozumienia oraz daje dobry pierwszy ogląd zagadnienia. Jest także − prawdopodobnie dzięki swojej zrozumiałości − najbardziej powszechnym schematem"^[14].

Inny podział da się przeprowadzić nie ze względu na typ systemu, ale skalę w jakiej przebiega się zrównoleglanie. Wyróżniamy wtedy obliczenia równoległe: na poziomie bitów, instrukcji, danych oraz zadań.

Zrównoleglanie na poziomie bitów

Poczynając od powszechnego zastosowania technologii VLSI (produkcji układów scalonych o wielkiej skali integracji) w latach siedemdziesiątych aż do roku około 1986 przyspieszenie działania komputerów było uzyskiwane poprzez podwajanie długości słowa maszynowego (czyli podstawowej jednostki informacji przetwarzanej przez procesor w jednym cyklu, w uproszczeniu jest to liczba bitów będąca rozmiarem szyny danych oraz rejestrów procesora)^[15]. Zwiększenie rozmiaru słowa maszynowego zmniejsza liczbę instrukcji jaką procesor musi wykonać realizując operację na zmiennych, których rozmiar jest większy niż długość słowa maszynowego. Dla przykładu jeśli 8-bitowy procesor realizuje dodawanie dwóch 16-bitowych liczb całkowitych, to trzeba oddzielnie wykonać działanie na młodszych i, z uwzględnieniem przeniesienia (ang. carry bit), starszych bajtach obu liczb. Tak więc w tym przypadku konieczne było wykonanie dwóch dodawań 8-bitowych, z tym że 16-bitowy procesor mógłby wykonać tę operację jako jedną instrukcję.

Historycznie, 4-bitowe procesory zostały zastąpione 8-bitowymi, te z kolei 16-bitowymi, a następnie 32-bitowymi. Ten trend nieco się zatrzymał, albowiem procesory 32-bitowe są standardem aż do lat 2003-2004, kiedy na rynku upowszechniły się procesory z architekturą 64-bitową.

Zrównoleglanie na poziomie instrukcji

Klasyczny pięciostopniowy potok w maszynie typu RISC (IF = Pobranie instrukcji, ID = Zdekodowanie instrukcji, EX = Wykonanie instrukcji, MEM = Dostęp do pamięci, WB = Zapisanie wyników działania instrukcji)

Program komputerowy, technicznie rzecz biorąc, jest ciągiem instrukcji wykonywanym przez procesor. Instrukcje te bywają grupowane, a kolejność ich wykonania zmieniana w taki sposób, aby da się było wykonać je równolegle bez zmiany wyniku programu. Technika ta nazywana jest zrównoleglaniem na poziomie instrukcji, postęp w jej stosowaniu zdominował rozwój architektury komputerów od połowy lat osiemdziesiątych do połowy lat dziewięćdziesiątych XX wieku^[16].

Współczesne procesory posiadają wielostopniowe potoki instrukcji. Każdy stopień potoku odpowiada za inną czynność jaką procesor wykonuje na danej instrukcji w danym etapie; innymi słowy, proces z N-stopniowym potokiem może posiadać do N wielorakich instrukcji na różnym etapie wykonywania. Klasycznym przykładem potokowego procesora jest procesor RISC z pięciostopniowym potokiem: pobranie instrukcji, zdekodowanie instrukcji, wykonanie instrukcji, dostęp do pamięci oraz zapisanie wyników działania instrukcji do rejestru. Procesor Pentium 4 ma 35-stopniowy potok^[17].

Pięciostopniowy potok w superskalarnym procesorze, który może wykonywać dwie instrukcje podczas jednego cyklu zegara. Na każdym etapie potoku potrafią się znajdować dwie instrukcje co daje jednoczesne wykonywanie 10 instrukcji.

Pewne procesory potrafią wykonywać więcej niż jedną instrukcję w ciągu cyklu, stosując inne techniki niż przetwarzanie potokowe opisane powyżej. Procesory te, nazywane superskalarnymi, grupują, przestawiają instrukcje nie powiązane zależnością danych oraz wykonują je jednocześnie. Dwie najczęściej stosowane w tym celu techniki to technika notowania (ang. scoreboarding) oraz podobna, nazywana algorytmem Tomasulo, w której stosuje się przemianowanie rejestrów (ang. register renaming). Możliwe jest także wykonywanie instrukcji, co do których nie ma jeszcze pewności, czy powinny być wykonane, aby ostatecznie przyjąć albo odrzucić wyniki ich działania. Jest to tak zwane spekulatywne wykonywanie instrukcji.

Zrównoleglanie przetwarzania danych

Zrównoleglanie przetwarzania danych jest właściwe przetwarzaniu iteracyjnemu oraz skupia się na rozdzielaniu danych pomiędzy zróżnicowane jednostki obliczeniowe w taki sposób aby zminimalizować ich wzajemne zależności. Na poziomie kodu źródłowego powiada się o zrównoleglaniu pętli (ang. parallelization of loops), gdzie wielokrotnie wykonuje się podobne (niekoniecznie identyczne) ciągi operacji na elementach dużej struktury"^[18]. Tego typu równoległość wykorzystuje wiele naukowych oraz inżynierskich aplikacji.

Rozdzielenie danych nie stale jest możliwe. Jeśli dla przykładu obliczenia w każdej kolejnej iteracji zależą od wyników poprzedniej, to zrównoleglenie pętli nie jest możliwe. Taka zależność ma miejsce w poniższym przykładzie obliczającym pierwsze parę liczb z ciągu Fibonacciego:

1:    prev2 := 0
2:    prev1 := 1
3:    cur := 1
4:    do:
5:       CUR := PREV1 + PREV2
6:       PREV2 := PREV1
7:       PREV1 := CUR
8:    while (CUR < 10)

Pętla ta nie może zostać zrównoleglona, albowiem zmienne (PREV1) oraz PREV2 użyte do obliczenia CUR są na nowo obliczane w każdym obiegu pętli.

Zrównoleglanie zadań

Zrównoleglanie zadań jest cechą charakterystyczną programu, w którym "zupełnie różniące się obliczenia bywają wykonywane na tych samych albo innych zbiorach danych"^[18]. Różni się ono od zrównoleglania danych, gdzie te same obliczenia wykonywane są na tych samych albo innych zbiorach danych. Programy charakteryzujące się zrównolegleniem zadań zwykle nie skalują się dobrze wraz ze wzrostem rozmiaru problemu^[19].

Sprzęt

Pamięć oraz komunikacja

Pamięć operacyjna w komputerze równoległym jest pamięcią współdzieloną przez wszystkie jednostki w jednej przestrzeni adresowej, albo pamięcią rozproszoną, w której każda jednostka prowadzi obliczenia we własnej przestrzenie adresowej^[20]. Pojęcie pamięci rozproszonej oznacza logiczny podział przestrzeni adresowych (fizycznie potrafią one należeć do tej samej maszyny), choć zwykle oznacza to także rozproszenie fizyczne. Rozproszona pamięć dzielona odnosi się do połączenia powyższych koncepcji, gdzie logicznie pamięć jest współdzielona chociaż fizycznie mamy do czynienia z pamięcią rozproszoną (każda jednostka ma swoją fizyczną pamięć lokalną, ale na poziomie logicznym/programowym ma dostęp do pamięci innych jednostek). Rozproszona pamięć dzielona jest więc symulacją pamięci współdzielonej, co ułatwia wykonywanie oprogramowania, a równocześnie może powodować opóźnienia (dostęp do pamięci lokalnej jest typowo wydatnie szybszy niż dostęp do pamięci zdalnej).

Diagram przedstawiający strukturę logiczną architektury NUMA. Bliskie sobie procesory posiadają dostęp do swojej pamięci z mniejszym opóźnieniem niż pozostałe.

Architektury komputerowe, w których cała pamięć operacyjna jest dostępna z takim samym opóźnieniem oraz częstotliwością są nazywane UMA (ang. Uniform Memory Access). Tę cechę potrafią posiadać właściwie tylko systemy z pamięcią dzieloną. Pozostałe systemy określamy mianem NUMA (ang. Non-Uniform Memory Access) – do tej kategorii zaliczamy systemy z pamięcią rozproszoną.

W kwestii poprawy wydajności systemu komputerowego stosuje się niewielkie, ale szybkie pamięci podręczne (ang. cache memory), które potrafią przechowywać tymczasowe dane. Stosowanie ich w architekturach równoległych nastręcza problemy związane z zachowaniem spójności danych (ang. cache coherency), albowiem te same dane bywają przechowywane w pamięciach podręcznych wielorakich procesorów. Zapewnienie poprawności obliczeń wymusza stosowanie dodatkowych technik, z których najpopularniejsza to bus snooping. Mimo ich istnienia projektowanie wydajnych pamięci podręcznych przysparza wiele trudności, dlatego architektury oparte na pamięci dzielonej należą do trudniej skalowalnych niż te oparte na pamięci rozproszonej^[20].

Komunikacja pomiędzy dwoma procesorami oraz procesorem oraz pamięcią może zostać zrealizowana sprzętowo na parę sposobów: poprzez wieloportową (ang. multiported) albo multipleksowaną pamięć dzieloną, przełącznicę krzyżową (ang. crossbar switch), współdzieloną magistralę (ang. shared bus) albo sieć o jednej z wielu topologii (gwiazdy, pierścienia, drzewa, hiperkostki oraz innych). Komputery równoległe zbudowane w oparciu o sieć (ang. interconnect network) wymagają jakiejś formy wyboru tras połączeń (ang. routing) dla procesorów, które nie są bezpośrednio połączone. Medium użyte do komunikacji pomiędzy procesorami zwykle ma strukturę hierarchiczną, zwłaszcza w przypadku dużej liczby procesorów.

Typy komputerów równoległych

Komputery równoległe da się podzielić ze względu na poziom, na jakim sprzęt zrównolegla operacje. Klasyfikacja w dużym stopniu odpowiada temu, jak bardzo są fizycznie oddalone od siebie poszczególne jednostki obliczeniowe. Przynależność do jednej z grup nie wyklucza jednak przynależności do pozostałych. Do wielokrotnie spotykanych kombinacji należą dla przykładu klastry wieloprocesorów symetrycznych.

Procesory wielordzeniowe

Procesor wielordzeniowy to procesor z kilkoma jednostkami wykonawczymi ("rdzeniami"). Procesory te różnią się od procesorów superskalarnych, albowiem potrafią wykonywać równocześnie instrukcje pochodzące z wielorakich ciągów instrukcji; w przeciwieństwie do tych drugich, które co prawda także potrafią w pewnych warunkach wykonywać parę instrukcji jednocześnie, ale pochodzących z jednego ciągu instrukcji (w danej chwili wykonują tylko jeden wątek). Potencjalnie każdy z rdzeni bywa jednostką superskalarną.

Wczesną formą procesorów wielordzeniowych była technologia SMT, inaczej wielowątkowość współbieżna (ang. simultaneous multithreading), którą zastosowano dla przykładu w procesorach oraz Pentium 4 (zob. Hyper-Threading). Procesor z technologią SMT ma tylko jeden rdzeń, ale kiedy jest bezczynny (ang. idle), dla przykładu z powodu konieczności odwołania poza pamięć podręczną (ang. cache miss), może go wykorzystać do wykonywania kolejnego wątku. Jako faktycznie wielordzeniowe procesory da się wymienić architektury Core oraz Cell.

Symetryczne systemy wieloprocesorowe

 Osobny artykuł: Wieloprocesorowość symetryczna.

Wieloprocesor symetryczny (SMP – ang. symmetric multiprocessor) to system komputerowy z wieloma identycznymi procesorami, które operują na wspólnej pamięci za pośrednictwem magistrali (ang. bus)^[21]. Z powodu zastosowania magistrali rozwiązanie to jest jednak słabo skalowalne, dlatego zwykle maszyny SMP posiadają nie więcej niż 32 procesory^[22]. Stosowanie dużych pamięci podręcznych, co ogranicza wykorzystanie magistrali, oraz niewielkich rozmiarów procesorów powoduje, że przy założeniu dostatecznie szybkiego dostępu do pamięci, symetryczne systemy wieloprocesorowe są bardzo wydajne przy stosunkowo niewielkich kosztach^[21].

Przetwarzanie rozproszone

 Osobny artykuł: Przetwarzanie rozproszone.

Przetwarzanie rozproszone (znane też jako wieloprocesor o rozproszonej pamięci) jest systemem komputerowym o rozproszonej pamięci, w którym elementy przetwarzające połączone są przez sieć komputerową. Komputery rozproszone są wysoce skalowalne^[23].

Przetwarzanie klastrowe

 Osobny artykuł: Klaster komputerowy.

Klaster Beowulf

Klaster jest grupą komputerów, które w pewnych aspektach bywają traktowane jako pojedynczy komputer^[24]. Klastry składają się z wielu niezależnych komputerów połączonych siecią. Podczas kiedy maszyny w klastrze nie muszą być symetryczne, równoważenie obciążenia jest trudniejsze jeśli nie są. Jednym z typów klastra jest Beowulf, który jest zaimplementowany na wielu identycznych komputerach połączonych siecią lokalną Ethernet opartą o protokół TCP/IP^[25]. Technologia Beowulf była zbudowana przez Thomasa Sterlinga oraz Donalda Beckera. Znaczna cząstka superkomputerów z listy TOP500 to klastry^[26].

Komputery masowo równoległe

 Osobny artykuł: MPP.

Masowo równoległy komputer (ang. Massively Parallel Processor) jest jednym komputerem z wieloma połączonymi ze sobą procesorami. Komputer ten ma wiele podobnych cech do klastrów, jednak jest on zwykle większy oraz ma o wiele więcej niż 100 procesorów.^[27] W komputerze masowo równoległym, "każdy procesor ma swoją własna pamięć oraz kopię systemu operacyjnego oraz aplikacji. Każdy podsystem komunikuje się z innymi poprzez szybkie łącza"^[28].

Pojedynczy rack komputera Blue Gene/L, będącego na pierwszym miejscu rankingu TOP500 – najszybszych komputerów świata.

Blue Gene/L, najszybszy wg rankingu TOP500 w 2007 roku, superkomputer na świecie jest komputerem masowo równoległym.

Obliczenia w gridach

Obliczenia w gridach to najbardziej rozproszona forma obliczeń równoległych. Mamy tu do czynienia z komputerami połączonymi siecią Internet, których zasoby używane są do rozwiązania danego problemu. Z uwagi na niewielką przepustowość oraz duże opóźnienia łączy, zwykle tylko problemy, które wymagają niewiele komunikacji są rozwiązywane w ten sposób. Wśród realizacji obliczeń gridowych da się wymienić SETI@home oraz Folding@home jako szerzej znane.

Przeważajaca ilość aplikacji wykorzystuje z warstwy pośredniej (ang. middleware) – oprogramowania, które, działając na poziomie pomiędzy system operacyjnym a aplikacjami, dostarcza usług związanych z wykorzystaniem zasobów sieciowych. Jako przykład da się wymienić system BOINC (ang. Berkeley Open Infrastructure for Network Computing), który pierwotnie powstał dla potrzeb projektu SETI@home.

Specjalistyczne urządzenia do przetwarzania równoległego

Obliczenia równoległe da się wykonywać nie tylko w komputerach ogólnego przeznaczenia, ale oraz w specjalnie zaprojektowanych urządzeniach. Rozwiązanie to zwykle opłaca się stosować do rozwiązywania nader ograniczonej klasy zagadnień równoległych.

Rekonfigurowalne Systemy Obliczeniowe

System rekonfigurowalny składa się z procesora ogólnego przeznaczenia oraz programowalnych układów logicznych FPGA (ang. field-programmable gate array).

Układy FPGA programuje się przy użyciu języków HDL (ang. Hardware Description Language) takich jak VHDL czy Verilog. Programowanie w tych językach bywa jednak monotonne oraz męczące, dlatego powstało parę narzędzi, które próbują emulować elementy składni oraz semantyki języka C, znanego większości programistów, tłumacząc je na język typu HDL. Jako przykłady takich rozwiązań da się podać: Mitrion-C, Impulse C, DIME-C oraz Handel-C.

Upublicznienie specyfikacji technologii HyperTransport przez AMD umożliwiło dostęp do wysoko wydajnych, rekonfigurowalnych obliczeń stronom trzecim^[29].

GPGPU

Karta GPGPU Tesla firmy NVIDIA Corporation

Wykonywanie obliczeń ogólnego przeznaczenia za pomocą procesora karty graficznej (GPGPU, ang. General-Purpose Computing on Graphics Processing Units) to nowy kierunek badań w inżynierii komputerowej. Procesor karty graficznej (tzw. GPU) to koprocesor zoptymalizowany do obliczeń w grafice komputerowej^[30], z których przeważajaca ilość to podlegające łatwemu urównolegleniu algebraiczne operacje macierzowe wykonywane w arytmetyce zmiennopozycyjnej. Dlatego współczesne GPU posiadają architekturę masowo równoległą z setkami rdzeni obliczeniowych, a ich teoretyczna moc obliczeniowa sięga 1 TFLOPS (bilion operacji zmiennoprzecinkowych na sekundę).

Oryginalnie w programach wykorzystujących technikę GPGPU używano standardowych interfejsów programowania aplikacji graficznych, z reguły DirectX oraz OpenGL, co było niewygodne oraz nieefektywne. Dlatego producenci kart graficznych udostępnili specjalne języki programowania oraz środowiska programistyczne dostosowane do tworzenia aplikacji w technologii GPGPU: CUDA dla procesorów firmy Nvidia oraz CTM oraz ATI Stream dla procesorów firmy AMD. Innymi środowiskami przeznaczonymi do pracy w technologii GPGPU są m.in. BrookGPU, PeakStream oraz RapidMind. Istnieje także niezależne od platformy sprzętowej oraz wspierane przez wszystkich liczących się producentów sprzętu środowisko OpenCL. Zarówno Nvidia, jak oraz AMD produkują tzw. procesory obliczeniowe, czyli dedykowane do technologii GPGPU karty graficzne: Tesla oraz FireStream.

Specjalizowane układy scalone

 Osobny artykuł: ASIC.

Specjalizowane układy scalone (ASIC ang. application-specific integrated circuit) to układy projektowane do realizacji ściśle określonego zadania^[31][32][33]. Zaletą układów ASIC, ze względu na specjalizację do określonego zadania, jest większa wydajność w porównaniu z komputerem ogólnego przeznaczenia. Jednak ze względu na wysoki koszt (stworzenie maski litograficznej może kosztować ponad milion dolarów^[34], a im mniejsze tranzystory, tym droższa maska) może się okazać, że osiągnięty zysk jest iluzoryczny. W czasie potrzebnym na przygotowanie ASIC układy ogólnego przeznaczenia, których wydajność rośnie zgodnie z prawem Moore'a, mogły osiągnąć porównywalną wydajność^[29]. Czynniki te powodują, że układy ASIC nie nadają się w większości zastosowań obliczeń równoległych. Jednym z nielicznych przykładów bywa maszyna Riken MDGRAPE-3, gdzie użyto ASIC do symulacji dynamiki molekularnej.

Procesory wektorowe

 Osobny artykuł: Procesor wektorowy.

Cray-1 jest najbardziej znanym procesorem wektorowym.

Procesor wektorowy jest procesorem albo systemem komputerowym, który wykonuje te same instrukcje na dużych zbiorach danych. "Procesory wektorowe posiadają operacje wysokiego poziomu, które działają na liniowych tablicach składających się z liczb albo wektorów. Przykładem operacji wektorowej jest gdzie A, B oraz C są 64-elementowymi wektorami złożonymi z 64-bitowych liczb zmiennoprzecinkowych"^[35]. Procesory wektorowe są przykładem architektury klasy SIMD taksonomii Flynna^[35].

Komputery Cray z procesorami wektorowymi są znane w latach 70. oraz 80. Ogólnie jednak procesory wektorowe przestały być popularne, zarówno jako CPU, jak oraz pełne systemy komputerowe, a nowoczesne maszyny używają tego typu przetwarzania danych poprzez dodatkowe zestawy rozkazów takie jak AltiVec, SSE oraz 3DNow!.

Oprogramowanie

W kwestii ułatwienia programowania komputerów równoległych stworzono specjalne: języki programowania, interfejsy oraz biblioteki. Można je podzielić ze względu na architekturę pamięci jaką zakładają: pamięć współdzieloną, pamięć rozproszoną, czy też rozproszoną pamięć dzieloną. Języki programowania oparte na pamięci dzielonej pozwalają operować na współdzielonych zmiennych, a te oparte na pamięci rozproszonej korzystają z przesyłania komunikatów (ang. message passing). POSIX Threads oraz OpenMP to dwa najczęściej używane interfejsy oparte na pamięci dzielonej, natomiast Message Passing Interface (MPI) to najczęściej używany interfejs korzystający z przesyłania komunikatów.

Zrównoleglanie automatyczne

Automatyczne zrównoleglanie sekwencyjnego programu przez kompilator jest "świętym graalem" obliczeń równoległych. Mimo wieloletnich wysiłków osób pracujących nad rozwojem kompilatorów, osiągnięto zaledwie częściowy sukces^[36].

Popularne języki programowania równoległego pozostają albo jawnie równolegle (ang. explicitily parallel), albo (w najlepszym przypadku) częściowo niejawne (ang. partially implicit), kiedy to programista podaje kompilatorowi specjalne dyrektywy sterujące zrównoleglaniem. Istnieje parę języków, w których zrównoleglanie przebiega się w pełni niejawnie: SISAL, Równoległy Haskell oraz (dla FPGA) Mitrion-C – są to jednak języki niszowe, które nie są powszechnie używane.

Mechanizm punktów kontrolnych

Wraz ze wzrostem stopnia skomplikowania komputerów rośnie także liczba występujących błędów oraz zmniejsza się średni bezawaryjny czas ich pracy. Jedną z technik zapewniania poprawności obliczeń jest zapamiętywanie, w czasie działania aplikacji, tak zwanych punktów kontrolnych (ang. application checkpointing). Innymi słowy, system co jakiś czas zapamiętuje stan działania aplikacji wraz ze wszystkimi wykorzystywanymi zasobami (ang. core dump), aby w razie wystąpienia błędu wznowić obliczenia od ostatniego punktu kontrolnego, zamiast wykonywać je wszystkie od początku. Technika ta może także ułatwić migrację procesów.

Zastosowania

Wraz z postępem w szybkości działania komputerów równoległych coraz więcej problemów, których rozwiązanie wcześniej nie było możliwe, jest w zasięgu dostępnych mocy obliczeniowych. Zastosowanie obliczeń równoległych zawiera w sobie szerokie spektrum dziedzin nauki od bioinformatyki (zob. zwijanie białka) do ekonomii (symulacje w matematyce finansowej).

Typowe problemy, gdzie bywa wykorzystane przetwarzanie równoległe obejmują^[37]:

• gęstą algebrę liniowa – metody numeryczne w algebrze liniowej, gdzie dane są macierzami albo wektorami gęstymi,
• rzadką algebrę liniową – metody numeryczne w algebrze liniowej, gdzie dane są macierzami albo wektorami rzadkimi,
• metody spektralne – dane są w dziedzinie częstotliwości (ang. Frequency domain) w przeciwieństwie do dziedziny czasu oraz przestrzeni,
• symulacje zachowania układu ciał pod wpływem oddziaływań fizycznych (ang. N-body simulation), dla przykładu symulacja Barnesa-Huta (ang. Barnes-Hut simulation),
• obliczenia z rozmieszczeniem węzłów w siatce prostokątnej (ang. regular grid problems) takich jak metoda kratowa Boltzmanna (ang. Lattice Boltzmann methods) stosowana w mechanice płynów,
• obliczenia z nieregularnym rozmieszczeniem węzłów (ang. unstructured grid problems) tak jak w analizie metodą elementów skończonych,
• symulacje metodą Monte Carlo,
• zagadnienia związane z układami kombinacyjnymi takie jak atak typu brute force,
• problemy, w których jest przeszukiwanie grafu,
• programowanie dynamiczne,
• algorytmy typu branch and bound,
• obliczenia w modelach grafowych (ang. graphical models) takie jak wykrywanie ukrytych modeli Markowa albo konstruowanie sieci bayesowskich),
• symulacja działania automatu skończonego.

Prowadzenie obliczeń równoległych na dużą skalę jest niezwykle kosztowne. Z tego powodu jednostki posiadające superkomputery (komputery równoległe o dużej mocy obliczeniowej) wyznacza się mianem centrów obliczeniowych. W Polsce są to pomiędzy innymi: ICM w Warszawie, TASK w Gdańsku, PCSS w Poznaniu oraz Cyfronet w Krakowie, a na świecie: Los Alamos National Laboratory oraz Lawrence Livermore National Laboratory w USA, EPCC w Wielkiej Brytanii oraz wiele innych.

Historia

ILLIAC IV – komputer typu SIMD ukończony w 1976 roku na Uniwersytecie Illinois. Jest otoczony złą sławą ze względu na duże koszty oraz przeciągające się terminy budowy.

Początki obliczeń równoległych łączy się z pracą Luigi Federico Menabrei pod tytułem "Sketch of the Analytic Engine Invented by Charles Babbage" z 1842 roku^[38][39]. Ponad sto lat później, w 1954 roku, IBM wprowadził na rynek komputer 704, wedle projektu, którego Gene Amdahl był jednym z głównych konstruktorów. Komputer ten stał się pierwszym urządzeniem dostępnym na rynku, które w pełni automatycznie używało rozkazów arytmetyki liczb zmiennoprzecinkowych^[40]. W 1958, naukowcy z IBM John Cocke oraz Daniel Slotnick po raz pierwszy rozważali wykorzystanie przetwarzania równoległego w obliczeniach numerycznych^[41]. Firma Burroughs w 1962 roku wprowadziła D825 – czteroprocesorowy komputer, który adresował 16 modułów pamięci przy użyciu przełącznicy krzyżowej^[42]. W 1967, Gene Amdahl opublikował artykuł, w którym sformułowane było prawo nazwane później prawem Amdahla^[43].

W 1969, Amerykański Honeywell wprowadził na rynek system Multics, który mógł zawierać do ośmiu procesorów^[41]. Z kolei C.mmp był, w latach siedemdziesiątych, systemem składającym się z szesnastu minikomputerów PDP-11 (działał w Carnegie Mellon University)^[39].

Początki komputerów typu SIMD sięgają lat siedemdziesiątych dwudziestego wieku, a motywacją ich konstruktorów była próba zamortyzowania czasu propagacji jednostki sterującej procesora przy przetwarzaniu kolejnych instrukcji^[44]. W 1964, Slotnick zaproponował zbudowanie wieloprocesorowego komputera równoległego dla Laboratoriów Lawrence'a w Livermore (Kalifornia)^[41]. Komputer ten (ILLIAC IV) stał się ufundowany przez Siły Powietrzne Stanów Zjednoczonych, co było pierwszą próbą konstrukcji komputera typu SIMD^[41]. Projekt pozwalał na wyposażenie tego komputera nawet w 256 procesorów, co umożliwiało jednoczesne przetwarzanie wielu zbiorów danych. Po jedenastu latach przedsięwzięcie, zrealizowane ostatecznie na Uniwersytecie Illinois, pochłonęło czterokrotnie więcej funduszy niż pierwotnie zakładano^[45] oraz kiedy w 1976 roku w końcu da się było go użyć, ówczesne komputery, takie jak Cray-1, były już od niego bardziej wydajne.

Koniec ery skalowania częstotliwości

Od połowy lat 80. do 2004 roku dominującym czynnikiem przyspieszającym działanie komputerów było zwiększanie częstotliwości zegara. Czas wykonywania programu jest równy liczbie instrukcji pomnożonej przez średni czas wykonywania instrukcji. Jeśli pozostałe parametry się nie zmieniają, to zwiększanie częstotliwości zegara zmniejsza średni czas jaki potrzebny jest na wykonanie instrukcji. Wzrost częstotliwości zmniejsza zatem czas wykonywania wszystkich programów, w których prędkość procesora ma dominujący wpływ na szybkość ich wykonania (ang. computation-bounded programs)^[46].

Pobór mocy danego układu scalonego wyznacza wzór gdzie P oznacza moc, C – pojemność elektryczną związaną z kondensatorami ładowanymi oraz rozładowanymi przy każdym cyklu zegara (proporcjonalna do liczby tranzystorów, których sygnały wejściowe ulegają zmianie), U napięciem a f częstotliwością procesora (liczba cykli zegara na sekundę)^[47]. Wzrost częstotliwości zwiększa energię elektryczną pobieraną przez procesor oraz zamienianą na ciepło. Powiększający się pobór energii procesorów oraz związane z tym problemy z odprowadzaniem ciepła skłoniły firmę Intel w maju 2004 do zamknięcia projektu tworzenia procesorów Tejas oraz Jayhawk. Decyzja ta jest nazywana końcem dominującej roli zwiększania częstotliwości w ulepszaniu architektury komputerów^[48].

Prawo Moore'a jest empiryczną obserwacją mówiącą, iż liczba tranzystorów w układzie scalonym podwaja się co 18-24 miesiące. Mimo problemów z poborem energii oraz częstych zapowiedzi jego końca, prawo Moore'a jest nadal aktualne. Wzrastające możliwości umieszczania w jednym układzie scalonym coraz większej liczby tranzystorów zmuszają do szukania kolejnych technik wykorzystania ich do zwiększenia szybkości obliczeń, np. budując koprocesory zrównoleglające obliczenia.

Przypisy

Sprawdź też

• Przetwarzanie współbieżne

Linki zewnętrzne

• Lawrence Livermore National Laboratory: Introduction to Parallel Computing
• Designing and Building Parallel Programs, by Ian Foster
• Internet Parallel Computing Archive
• Parallel processing topic area at IEEE Distributed Computing Online
• Parallel Computing Works Free On-line Book
• Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications