Analiza algorytmów równoległych - Analysis of parallel algorithms

W informatyce analiza algorytmów równoległych to proces znajdowania złożoności obliczeniowej algorytmów wykonywanych równolegle – ilości czasu, pamięci lub innych zasobów potrzebnych do ich wykonania. Pod wieloma względami analiza algorytmów równoległych jest podobna do analizy algorytmów sekwencyjnych , ale generalnie jest bardziej zaangażowana, ponieważ należy uzasadnić zachowanie wielu współpracujących wątków wykonania. Jednym z głównych celów analizy równoległej jest zrozumienie, w jaki sposób wykorzystanie zasobów przez algorytm równoległy (szybkość, przestrzeń itp.) zmienia się wraz ze zmianą liczby procesorów.

Tło

Tak zwany framework czasu pracy (WT) (czasami nazywany work-depth lub work-span) został pierwotnie wprowadzony przez Shiloacha i Vishkina do konceptualizacji i opisywania algorytmów równoległych. W ramach WT algorytm równoległy jest po raz pierwszy opisany w kategoriach równoległych rund. Dla każdej rundy scharakteryzowano operacje do wykonania, ale można pominąć kilka kwestii. Na przykład liczba operacji w każdej rundzie nie musi być jasna, procesory nie muszą być wymieniane, a wszelkie informacje, które mogą pomóc w przypisaniu procesorów do zadań, nie muszą być uwzględniane. Po drugie, dostarczane są tłumione informacje. Włączenie wytłumionych informacji jest prowadzone na podstawie dowodu twierdzenia o szeregowaniu ze względu na Brenta, co wyjaśniono w dalszej części tego artykułu. Struktura WT jest przydatna, ponieważ chociaż może znacznie uprościć wstępny opis równoległego algorytmu, wstawienie szczegółów tłumionych przez ten wstępny opis często nie jest zbyt trudne. Na przykład struktura WT została przyjęta jako podstawowa struktura prezentacji w książkach o algorytmach równoległych (dla modelu PRAM maszyny o dostępie swobodnym Parallel ) oraz w notatkach klasowych. Poniższy przegląd wyjaśnia, w jaki sposób ramy WT można wykorzystać do analizy bardziej ogólnych algorytmów równoległych, nawet jeśli ich opis nie jest dostępny w ramach WT.

Definicje

Załóżmy, że obliczenia są wykonywane na maszynie, która ma p procesorów. Niech T _p oznacza czas, który upływa między rozpoczęciem obliczenia a jego końcem. Analiza obliczeń w czasie trwania koncentruje się na następujących pojęć:

• Praca z obliczeń wykonanych przez p procesorów jest całkowita liczba pierwotnych operacji, które procesory wykonują. Ignorując narzut komunikacyjny związany z synchronizacją procesorów, jest to czas potrzebny na wykonanie obliczeń na pojedynczym procesorze, oznaczonym jako T ₁ .
• Głębokość lub rozpiętość ma długość najdłuższej serii operacji, które mają być wykonywane kolejno w wyniku zależności danych (stanowiącego ścieżkę krytyczną ). Głębokość można również nazwać krytyczną długością ścieżki obliczeń. Minimalizacja głębokości/rozpiętości jest ważna przy projektowaniu algorytmów równoległych, ponieważ głębokość/rozpiętość określa najkrótszy możliwy czas wykonania. Alternatywnie, zakres może być zdefiniowany jako czas T _∞ zużytego obliczenie za pomocą urządzenia z wyidealizowanym nieskończoną liczbę procesorów.
• Koszt od obliczeń jest ilość pT _p . Wyraża to całkowity czas spędzony przez wszystkie procesory zarówno na obliczeniach, jak i na oczekiwaniu.

Z definicji pracy, zakresu i kosztów wynika kilka użytecznych wyników:

• Prawo pracy . Kosztem jest zawsze co najmniej praca: pT _p ≥ T ₁ . Wynika to z faktu, że p procesorów może wykonywać co najwyżej p operacji równolegle.
• Prawo przęseł . Skończona liczba p procesorów nie może przewyższyć nieskończonej liczby, tak że T _p ≥ T _∞ .

Korzystając z tych definicji i przepisów, można podać następujące miary wydajności:

• Przyspieszenie to przyrost prędkości uzyskany przez wykonywanie równoległe w porównaniu z wykonywaniem sekwencyjnym: S _p = T ₁ ∕ T _p . Gdy przyspieszenie wynosi Ω( n ) dla wielkości wejściowej n (przy użyciu dużego notacji O ), przyspieszenie jest liniowe, co jest optymalne w prostych modelach obliczeń, ponieważ prawo pracy implikuje, że T ₁ ∕ T _p ≤ p ( przyspieszenie superliniowe w praktyce może wystąpić z powoduefektów hierarchii pamięci ). Sytuację T ₁ ∕ T _p = p nazywamy doskonałym przyspieszeniem liniowym. Mówi się, że algorytm, który wykazuje przyspieszenie liniowe, jest skalowalny .
• Wydajność to przyspieszenie na procesor, S _p ∕ p .
• Równoległość jest stosunkiem T ₁ ∕ T _∞ . Reprezentuje maksymalne możliwe przyspieszenie na dowolnej liczbie procesorów. Zgodnie z prawem rozpiętości, równoległość ogranicza przyspieszenie: jeśli p > T ₁ ∕ T _∞ , to:

${\displaystyle {\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty}}}<p}$ .

• Rozprężenie jest T ₁ / ( pT _∞ ) . Slackness mniejszy niż jeden implikuje (zgodnie z prawem span), że idealne przyspieszenie liniowe jest niemożliwe na p procesorach.

Wykonanie na ograniczonej liczbie procesorów

Analiza algorytmów równoległych jest zwykle przeprowadzana przy założeniu, że dostępna jest nieograniczona liczba procesorów. Jest to nierealistyczne, ale nie stanowi problemu, ponieważ wszelkie obliczenia, które mogą działać równolegle na N procesorach, można wykonać na p < N procesorach, pozwalając każdemu procesorowi na wykonanie wielu jednostek pracy. Wynik zwane prawa Brent stany, które można wykonać taką „Symulacja” na czas T _p , ograniczony przez

${\ Displaystyle T_ {p} \ leq T_ {N} + {\ Frac {T_ {1}-T_ {N}} {p}},}$

lub mniej precyzyjnie

${\ Displaystyle T_ {p} = O \ lewo (T_ {N} + {\ Frac {T_ {1}} {p}} \ po prawej).}$

Alternatywne stwierdzenie prawa ogranicza T _p powyżej i poniżej przez

${\displaystyle {\frac {T_{1}}{p}}\leq T_ {p}\leq {\frac {T_{1}}{p}}+T_{\infty}}$.

pokazując, że rozpiętość (głębokość) T _∞ i praca T ₁ razem zapewniają rozsądne ograniczenia czasu obliczeń.

Bibliografia