Algorytm równoległy - Parallel algorithm

W informatyce , a algorytm równoległy , w przeciwieństwie do tradycyjnego algorytmu szeregowego , to algorytm , który może zrobić wiele operacji w danym czasie. Tradycją informatyki było opisywanie algorytmów szeregowych w abstrakcyjnych modelach maszyn , często znanych jako maszyny o dostępie swobodnym . Podobnie, wielu badaczy informatyki używało tak zwanej równoległej maszyny o dostępie swobodnym (PRAM) jako równoległej maszyny abstrakcyjnej (pamięć współdzielona).

Wiele algorytmów równoległych jest wykonywanych jednocześnie – chociaż ogólnie algorytmy współbieżne są odrębnym pojęciem – i dlatego te pojęcia są często utożsamiane, z którym aspekt algorytmu jest równoległy, a który współbieżny nie jest wyraźnie rozróżniany. Ponadto, nierównoległe, niewspółbieżne algorytmy są często określane jako „ algorytmy sekwencyjne ”, w przeciwieństwie do algorytmów współbieżnych.

Paralelizowalność

Algorytmy różnią się znacznie pod względem tego, jak są paralelizowalne, od łatwo paralelizowalnych do całkowicie nierównoległych. Ponadto dany problem może uwzględniać różne algorytmy, które mogą być mniej lub bardziej równoległe.

Niektóre problemy można w ten sposób łatwo podzielić na części – nazywa się je kłopotliwie równoległymi problemami. Przykłady obejmują wiele algorytmów do rozwiązywania kostek Rubika i znajdowania wartości, które dają w wyniku dany hash .

Niektórych problemów nie można podzielić na równoległe części, ponieważ wymagają one wyników z poprzedniego kroku, aby skutecznie przejść do następnego kroku – są to tzw. Problem natury seryjny s. Przykłady obejmują iteracyjnemetody numeryczne, takie jakmetoda Newtona, iteracyjne rozwiązania problemutrzech ciałoraz większość dostępnych algorytmów do obliczaniapi(π). Niektóre algorytmy sekwencyjne można przekształcić w algorytmy równoległe przy użyciuautomatycznej równoległości.

Motywacja

Algorytmy równoległe na poszczególnych urządzeniach stały się bardziej powszechne od początku XXI wieku ze względu na znaczne ulepszenia systemów wieloprocesorowych i wzrost liczby procesorów wielordzeniowych . Do końca 2004 r. wydajność procesorów jednordzeniowych gwałtownie rosła dzięki skalowaniu częstotliwości , dlatego łatwiej było skonstruować komputer z jednym szybkim rdzeniem niż z wieloma wolniejszymi rdzeniami o tej samej przepustowości , więc systemy wielordzeniowe były bardziej ograniczone. posługiwać się. Jednak od 2004 r. skalowanie częstotliwości uderzyło w ścianę, a tym samym systemy wielordzeniowe stały się bardziej rozpowszechnione, czyniąc algorytmy równoległe bardziej ogólne.

Kwestie

Komunikacja

Koszt lub złożoność algorytmów szeregowych szacowany jest pod względem zajmowanej przez nie przestrzeni (pamięć) i czasu (cykle procesora). Algorytmy równoległe muszą zoptymalizować jeszcze jeden zasób, komunikację między różnymi procesorami. Istnieją dwa sposoby komunikowania się procesorów równoległych: pamięć współdzielona lub przekazywanie komunikatów.

Przetwarzanie pamięci współdzielonej wymaga dodatkowego blokowania danych, narzuca dodatkowe cykle procesora i magistrali, a także serializuje pewną część algorytmu.

Przetwarzanie z przekazywaniem wiadomości wykorzystuje kanały i skrzynki wiadomości, ale ta komunikacja zwiększa obciążenie dla transferu w magistrali, wymaga dodatkowej pamięci dla kolejek i skrzynek wiadomości oraz opóźnienia w wiadomościach. Konstrukcje procesorów równoległych wykorzystują specjalne magistrale, takie jak crossbar, dzięki czemu narzut komunikacji będzie niewielki, ale to algorytm równoległy decyduje o wielkości ruchu.

Jeśli obciążenie komunikacyjne dodatkowych procesorów przeważa nad korzyścią z dodania kolejnego procesora, pojawia się spowolnienie równoległe .

Równoważenie obciążenia

Innym problemem związanym z algorytmami równoległymi jest zapewnienie, że są one odpowiednio zbilansowane pod względem obciążenia , poprzez zapewnienie, że obciążenie (ogólna praca) jest zbalansowane, a nie rozmiar wejściowy. Na przykład sprawdzanie pierwszości wszystkich liczb od jednego do stu tysięcy jest łatwe do podziału między procesory; jeśli jednak liczby zostaną po prostu podzielone równo (1–1000, 1001–2000 itd.), nakład pracy będzie niezrównoważony, ponieważ mniejsze liczby są łatwiejsze do przetworzenia za pomocą tego algorytmu (łatwiejsze do przetestowania pod kątem pierwszości) oraz w ten sposób niektóre procesory będą miały więcej pracy niż inne, które pozostaną bezczynne, dopóki załadowane procesory nie skończą.

Algorytmy rozproszone

Podtyp algorytmów równoległych, algorytmy rozproszone , to algorytmy zaprojektowane do pracy w środowiskach obliczeniowych klastrowych i rozproszonych , w których należy rozwiązać dodatkowe problemy wykraczające poza zakres „klasycznych” algorytmów równoległych.

Zobacz też

• System wieloagentowy (MAS)
• Równoległe algorytmy mnożenia macierzy
• Algorytmy równoległe dla minimalnych drzew opinających
• Równoległe obliczenia
• Parareal

Bibliografia

Linki zewnętrzne

• Projektowanie i budowa programów równoległych , US Argonne National Laboratory