Algorytm równoległy

Algorytm równoległy – algorytm, który w danej chwili pozwala na wykonywanie wielu operacji.

Równoległe algorytmy są cenne ze względu na możliwość szybszego (w stosunku do jednego procesora) obliczania różnego typu zagadnień. Przy aktualnym stanie rozwoju procesorów dużo łatwiejsze jest połączenie wielu słabszych procesorów od stworzenia nowego o podobnej mocy obliczeniowej.

Koszt algorytmów obliczany jest na podstawie wykonanej pracy (ilości cykli wszystkich procesorów), czasu działania i pamięci potrzebnej do działania.

W odpowiednich modelach rozważane są także problemy jednoczesnego odczytu czy zapisu do pamięci wspólnej.

Większość dostępnych algorytmów obliczających liczbę pi (π) nie mają możliwości zbyt łatwego podziału obliczeń na równoległe porcje danych. Wymagają one wyników z poprzedzającego kroku do faktycznego kontynuowania obliczeń w następnym kroku. Problemy takie nazywane są właściwie szeregowymi. Iteracyjne analizy numeryczne, takie jak Metoda Newtona czy problem trzech ciał, są również algorytmami szeregowymi. Niektóre z nich są bardzo trudne do zrównoleglenia, aczkolwiek są one rekurencyjne. Jednym z przykładów jest algorytm przeszukiwania w głąb dla grafów.

Algorytmy równoległe są wartościowe, z uwagi na wprowadzenie znaczących ulepszeń w systemach wieloprocesorowych oraz postęp w dziedzinie procesorów wielordzeniowych. Generalnie prościej jest skonstruować komputer z jednym szybkim procesorem niż taki, który posiadać będzie wiele wolniejszych procesorów przy tej samej przepustowości maszyny. Jednak prędkość procesora wzrasta głównie poprzez zmniejszanie układów elektrycznych. Współczesne procesory ciągle naciskają limity fizycznego rozmiaru i wytwarzanego podczas pracy ciepła. Te czynniki spowodowały odwrócenie równania wydajności i sprawiły, że rozwój technologiczny kierunkuje się na tworzenie wieloprocesorowych systemów, nawet w komputerach osobistych.

Koszt lub złożoność algorytmów szeregowych jest szacowany w oparciu o przestrzeń (pamięć) i czas (cykle procesora), które one zajmują. Algorytmy równoległe, w celu optymalizacji potrzebują jeszcze czegoś więcej – jest to komunikacja pomiędzy różnymi procesorami. Istnieją dwa sposoby takiej komunikacji: pamięć dzielona i przesyłanie komunikatów.

Wykorzystywanie pamięci dzielonej wymaga dodatkowo blokowania danych, co zwiększa ogólny koszt o dodatkowy procesor i cykle magistrali, jak również szereguje część algorytmu.

Przesyłanie komunikatów podnosi koszt na magistrali oraz dodatkowej pamięci do kolejkowania i przechowywania komunikatów. Projekty procesorów równoległych wykorzystują specjalne magistrale krzyżowe co zmniejsza koszty, ale to algorytm równoległy decyduje o rozmiarze natężenia przepływu danych.

Innym problemem związanym z algorytmami równoległymi jest właściwe rozłożenie obliczeń. Np. sprawdzanie każdej liczby od 1 do 100 000 czy jest liczbą pierwszą jest proste do podzielenia pomiędzy procesory, aczkolwiek niektóre procesory dostaną więcej pracy niż inne, co spowoduje ich bezczynne oczekiwanie na zakończenie pracy tych bardziej obłożonych.

Algorytmy dystrybucyjne - podtyp algorytmów równoległych – są zaprojektowane do pracy na klastrach i w środowiskach obliczeń rozproszonych, gdzie przekraczają możliwości klasycznych algorytmów równoległych.

Zobacz też

• Obliczenia równoległe
• Message Passing Interface (MPI)

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.