Algorytm równoległy
Algorytm równoległy to taki, który umożliwia jednoczesne wykonywanie wielu operacji.
Algorytmy równoległe są istotne, ponieważ pozwalają na szybsze obliczenia w porównaniu do tradycyjnych algorytmów działających na pojedynczym procesorze. W obecnym etapie rozwoju procesorów, znacznie łatwiej jest zintegrować kilka mniej wydajnych procesorów, niż stworzyć jeden o podobnej mocy obliczeniowej.
Koszt algorytmów ocenia się na podstawie wykonanej pracy (liczby cykli wszystkich procesorów), czasu działania oraz pamięci wymaganej do ich działania.
W odpowiednich modelach analizowane są również problemy związane z jednoczesnym odczytem i zapisem do wspólnej pamięci.
Wiele algorytmów używanych do obliczania liczby pi (π) nie jest łatwo dzielić na równoległe fragmenty. Wymagają one uzyskania wyników z wcześniejszych kroków, aby kontynuować obliczenia w następnych etapach. Takie problemy określa się jako szeregowe. Przykłady algorytmów szeregowych to iteracyjne analizy numeryczne, takie jak Metoda Newtona czy problem trzech ciał. Niektóre z nich, mimo że są rekurencyjne, są trudne do zrównoleglania, jak na przykład algorytm przeszukiwania w głąb dla grafów.
Algorytmy równoległe są niezwykle wartościowe, ponieważ wprowadzają istotne ulepszenia w systemach wieloprocesorowych oraz rozwijają technologię procesorów wielordzeniowych. Zasadniczo łatwiej jest skonstruować komputer z jednym szybkim procesorem niż z wieloma wolniejszymi przy tej samej wydajności. Niemniej jednak, zwiększenie prędkości procesora następuje głównie poprzez miniaturyzację układów elektrycznych. Współczesne procesory ciągle osiągają granice fizycznych rozmiarów oraz generowanego ciepła. Te czynniki spowodowały zmianę w podejściu do wydajności, co skłoniło rozwój technologiczny w kierunku budowania systemów wieloprocesorowych, nawet w komputerach osobistych.
Koszt lub złożoność algorytmów szeregowych ocenia się na podstawie zajmowanej przestrzeni (pamięci) oraz czasu (cykli procesora). Algorytmy równoległe, aby zostały zoptymalizowane, wymagają dodatkowego elementu – komunikacji pomiędzy różnymi procesorami. Istnieją dwa główne sposoby komunikacji: pamięć dzielona oraz przesyłanie komunikatów.
Korzystanie z pamięci dzielonej wiąże się z koniecznością blokowania danych, co zwiększa ogólny koszt o dodatkowy procesor oraz cykle magistrali, a także prowadzi do szeregowania części algorytmu.
Przesyłanie komunikatów zwiększa koszty związane z magistralą oraz wymaga dodatkowej pamięci do kolejkowania i przechowywania komunikatów. Projekty procesorów równoległych wykorzystują specjalne magistrale krzyżowe, co zmniejsza koszty, lecz decyzje dotyczące natężenia przepływu danych podejmuje algorytm równoległy.
Innym wyzwaniem związanym z algorytmami równoległymi jest efektywne rozłożenie obliczeń. Na przykład, sprawdzanie, czy liczby od 1 do 100 000 są liczbami pierwszymi, jest łatwe do podziału między procesory, jednak niektóre z nich mogą otrzymać więcej zadań niż inne, co prowadzi do bezczynności tych, które mają mniej pracy, podczas gdy czekają na zakończenie obliczeń przez bardziej obciążone procesory.
Algorytmy dystrybucyjne, będące podtypem algorytmów równoległych, zostały zaprojektowane do pracy w klastrach oraz w środowiskach obliczeń rozproszonych, gdzie przewyższają możliwości tradycyjnych algorytmów równoległych.
Zobacz też:
Przypisy:
Bibliografia:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.
