Algorytmy równoległe i ich złożoność

6.1 Algorytmy równoległe.

Algorytmy równoległe są przeznaczone do wykonywania na systemach wieloprocesorowych lub wielowątkowych w celu przyspieszenia obliczeń. Dzielą zadanie na niezależne podzadania, które są wykonywane jednocześnie. Analiza złożoności algorytmów równoległych wymaga uwzględnienia zarówno złożoności czasowej, jak i przestrzennej, a także takich czynników jak przyspieszenie, efektywność i skalowalność.

Podstawowe koncepcje algorytmów równoległych

• Równoległość: Podział zadania na kilka podzadań, które mogą być wykonywane jednocześnie.
• Przyspieszenie (Speedup): Stosunek czasu wykonania algorytmu sekwencyjnego do czasu wykonania algorytmu równoległego.
• Efektywność (Efficiency): Stosunek przyspieszenia do liczby procesorów.
• Skalowalność (Scalability): Zdolność algorytmu równoległego do efektywnego wykorzystania rosnącej liczby procesorów.

Zalety algorytmów równoległych:

• Przyspieszenie wykonania: Szybsze wykonywanie zadań dzięki równoległemu przetwarzaniu.
• Efektywne wykorzystanie zasobów: Optymalizacja wykorzystania procesorów i rdzeni.
• Rozwiązywanie dużych zadań: Możliwość przetwarzania dużych ilości danych i skomplikowanych obliczeń, które są niemożliwe lub bardzo wolne na jednym procesorze.

Złożoność czasowa algorytmów równoległych

Złożoność czasowa algorytmów równoległych mierzona jest z uwzględnieniem czasu potrzebnego na wykonanie wszystkich równoległych podzadań i synchronizację między nimi. Obejmuje ona:

• Teoretyczna złożoność czasowa: Idealny czas wykonania na nieskończonej liczbie procesorów.
• Rzeczywista złożoność czasowa: Czas wykonania z uwzględnieniem ograniczeń co do liczby procesorów i kosztów synchronizacji.

Złożoność przestrzenna algorytmów równoległych

Złożoność przestrzenna algorytmów równoległych uwzględnia ilość pamięci potrzebnej do przechowywania danych i kontekstu każdego równoległego procesu. Ważne jest także uwzględnienie kosztów komunikacji między procesorami.

6.2 Przykład algorytmu równoległego

Równoległe sortowanie przez scalanie (Parallel Merge Sort):

Dzieli tablicę na podtablice, sortuje je równolegle i następnie scala.

Złożoność czasowa: O(n*log(n)/p), gdzie n — rozmiar tablicy, p — liczba procesorów.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# Przykład użycia
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Ale interesujący będzie dla nas nie sam algorytm, lecz analiza jego „efektywności”.

6.3 Analiza algorytmów równoległych

Podstawowe koncepcje:

1. Analiza przyspieszenia (Speedup):
   • Stosunek czasu wykonania algorytmu sekwencyjnego do czasu wykonania algorytmu równoległego.
   • Speedup = T_seq / T_par, gdzie T_seq — czas wykonania algorytmu sekwencyjnego, T_par — czas wykonania algorytmu równoległego.
2. Efektywność (Efficiency):
   • Ocena efektywności wykorzystania procesorów.
   • Efficiency = Speedup / P, gdzie P — liczba procesorów.
3. Prawo Amdahla (Amdahl's Law):
   • Określa maksymalne przyspieszenie, jakie można osiągnąć przy równolegleniu zadania.
   • Speedup_max = 1 / (S + (1 - S) / P), gdzie S — udział części sekwencyjnej zadania, P — liczba procesorów.
4. Prawo Gustafsona (Gustafson's Law):
   • Określa przyspieszenie z uwzględnieniem zmiany rozmiaru zadania przy zwiększaniu liczby procesorów.
   • Speedup = P - α * (P - 1), gdzie P — liczba procesorów, α — udział części sekwencyjnej zadania.

6.4 Przykłady algorytmów równoległych i ich złożoność

Przykład 1: Równoległe sortowanie przez scalanie (Parallel Merge Sort)

Opis: Równoległe sortowanie przez scalanie dzieli tablicę na podtablice, sortuje każdą podtablicę równolegle, a następnie scala posortowane podtablice.

Analiza złożoności:

• Złożoność czasowa: O((n log n) / P), gdzie P — liczba procesorów.
• Złożoność przestrzenna: O(n) dla przechowywania danych pośrednich.

Przykład 2: Równoległe wyszukiwanie w tablicy (Parallel Search)

Opis: Zadanie wyszukiwania elementu w tablicy dzieli się na kilka podzadań, z których każde wykonywane jest równolegle na osobnym procesorze.

Analiza złożoności:

• Złożoność czasowa: O(n / P), gdzie P — liczba procesorów.
• Złożoność przestrzenna: O(1), jeśli używana jest ta sama tablica.

Przykład 3: Równoległe mnożenie macierzy (Parallel Matrix Multiplication)

Opis: Macierze są dzielone na bloki, a każda para bloków jest mnożona równolegle na różnych procesorach.

Analiza złożoności:

• Złożoność czasowa: O(n^3 / P), gdzie P — liczba procesorów.
• Złożoność przestrzenna: O(n^2) dla przechowywania wyników pośrednich.

6.5 Implementacja algorytmów równoległych

Narzędzia i biblioteki:

1. OpenMP:
   • Biblioteka dla C, C++ i Fortran, dostarczająca narzędzi do tworzenia aplikacji wielowątkowych.
2. MPI (Message Passing Interface):
   • Standard do programowania równoległego na systemach rozproszonych, wspierający wymianę komunikatów między procesami.
3. CUDA:
   • Platforma i API od NVIDIA do tworzenia programów równoległych wykorzystujących procesory graficzne (GPU).
4. Threading i multiprocessing w Python:
   • Moduły do tworzenia aplikacji wielowątkowych i wieloprocesowych w Python.

Algorytmy równoległe pozwalają na znaczne przyspieszenie obliczeń poprzez dzielenie zadań na kilka procesorów lub rdzeni. Analiza złożoności algorytmów równoległych obejmuje ocenę przyspieszenia, efektywności oraz wykorzystanie praw Amdahla i Gustafsona do zrozumienia maksymalnego przyspieszenia osiągalnego przy równolegleniu.

Algorytmy równoległe znajdują zastosowanie w różnych dziedzinach, od sortowania i wyszukiwania po skomplikowane obliczenia matematyczne, i wymagają użycia specjalistycznych narzędzi i bibliotek do ich implementacji.

Ważne! Nie musisz przesadzać z algorytmami równoległymi. Po pierwsze, ze względu na prawo Amdahla, nie są one aż tak efektywne, jak się wydaje. Po drugie, obecnie serwery z 30 procesorami obsługują po 3000 zapytań na minutę i nadal mamy n zadań na 1 procesor, a nie 1 zadanie dla n procesorów.

Po trzecie, realne zadania, które trzeba przyspieszyć dzięki wieloprocesorowości, przeszły na GPU (karty graficzne) i ich kod pisze się w językach niskopoziomowych takich jak C.