Parallele Algorithmen und ihre Komplexität

6.1 Parallele Algorithmen.

Parallele Algorithmen sind für die Ausführung auf Mehrprozessor- oder Multithreading-Systemen vorgesehen, um die Berechnungen zu beschleunigen. Sie teilen die Aufgabe in unabhängige Teilaufgaben, die gleichzeitig ausgeführt werden. Die Analyse der Komplexität paralleler Algorithmen erfordert die Berücksichtigung sowohl der zeitlichen als auch der räumlichen Komplexität sowie Faktoren wie Beschleunigung, Effizienz und Skalierbarkeit.

Grundkonzepte paralleler Algorithmen

• Parallelismus: Aufteilung der Aufgabe in mehrere Teilaufgaben, die gleichzeitig ausgeführt werden können.
• Beschleunigung (Speedup): Das Verhältnis der Ausführungszeit des sequentiellen Algorithmus zur Ausführungszeit des parallelen Algorithmus.
• Effizienz (Efficiency): Das Verhältnis der Beschleunigung zur Anzahl der Prozessoren.
• Skalierbarkeit (Scalability): Die Fähigkeit des parallelen Algorithmus, eine zunehmende Anzahl von Prozessoren effektiv zu nutzen.

Vorteile paralleler Algorithmen:

• Schnellere Ausführung: Schnellere Ausführung von Aufgaben durch Parallelisierung der Arbeit.
• Effiziente Ressourcennutzung: Optimierung der Nutzung von Prozessoren und Kernen.
• Lösung großer Aufgaben: Die Möglichkeit, große Datenmengen und komplexe Berechnungen zu bearbeiten, die auf einem Prozessor unmöglich oder sehr langsam wären.

Zeitliche Komplexität paralleler Algorithmen

Die zeitliche Komplexität paralleler Algorithmen wird gemessen, indem die Zeit berücksichtigt wird, die für die Ausführung aller parallelen Teilaufgaben und die Synchronisation zwischen ihnen benötigt wird. Sie umfasst:

• Theoretische zeitliche Komplexität: Ideale Ausführungszeit bei einer unbegrenzten Anzahl von Prozessoren.
• Reale zeitliche Komplexität: Ausführungszeit unter Berücksichtigung der Beschränkungen der Anzahl der Prozessoren und des Synchronisationsaufwands.

Räumliche Komplexität paralleler Algorithmen

Die räumliche Komplexität paralleler Algorithmen berücksichtigt den Speicherbedarf zur Speicherung der Daten und des Kontextes jedes parallelen Prozesses. Es ist auch wichtig, den Kommunikationsaufwand zwischen den Prozessoren zu berücksichtigen.

6.2 Beispiel eines parallelen Algorithmus

Paralleler Mergesort (Parallel Merge Sort):

Teilt das Array in Teilarrays, sortiert sie parallel und fügt sie dann zusammen.

Zeitliche Komplexität: O(n*log(n)/p), wobei n die Größe des Arrays ist und p die Anzahl der Prozessoren.

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
            
# Beispiel der Nutzung
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Aber uns interessiert nicht der Algorithmus selbst, sondern die Analyse seiner „Effizienz“.

6.3 Analyse paralleler Algorithmen

Grundlegende Konzepte:

1. Analyse der Beschleunigung (Speedup):
   • Das Verhältnis der Ausführungszeit des sequentiellen Algorithmus zur Ausführungszeit des parallelen Algorithmus.
   • Speedup = T_seq / T_par, wobei T_seq die Ausführungszeit des sequentiellen Algorithmus ist, T_par die Ausführungszeit des parallelen Algorithmus.
2. Effizienz (Efficiency):
   • Bewertung der Effizienz der Prozessorennutzung.
   • Efficiency = Speedup / P, wobei P die Anzahl der Prozessoren ist.
3. Amdahl's Law:
   • Bestimmt die maximale Beschleunigung, die bei der Parallelisierung einer Aufgabe erreicht werden kann.
   • Speedup_max = 1 / (S + (1 - S) / P), wobei S der Anteil des sequentiellen Teils der Aufgabe ist und P die Anzahl der Prozessoren.
4. Gustafson's Law:
   • Bestimmt die Beschleunigung unter Berücksichtigung der Änderung der Aufgabenmenge bei Erhöhung der Prozessoranzahl.
   • Speedup = P - α * (P - 1), wobei P die Anzahl der Prozessoren ist und α der Anteil des sequentiellen Teils der Aufgabe.

6.4 Beispiele paralleler Algorithmen und ihre Komplexität

Beispiel 1: Paralleler Mergesort (Parallel Merge Sort)

Beschreibung: Der parallele Mergesort teilt ein Array in Teilarrays, sortiert jedes Teilarray parallel und fügt dann die sortierten Teilarrays zusammen.

Analyse der Komplexität:

• Zeitliche Komplexität: O((n log n) / P), wobei P die Anzahl der Prozessoren ist.
• Räumliche Komplexität: O(n) zur Speicherung von Zwischendaten.

Beispiel 2: Parallele Suche im Array (Parallel Search)

Beschreibung: Die Aufgabe, ein Element in einem Array zu suchen, wird in mehrere Teilaufgaben aufgeteilt, von denen jede parallel auf einem separaten Prozessor ausgeführt wird.

Analyse der Komplexität:

• Zeitliche Komplexität: O(n / P), wobei P die Anzahl der Prozessoren ist.
• Räumliche Komplexität: O(1), wenn dasselbe Array verwendet wird.

Beispiel 3: Parallele Matrizenmultiplikation (Parallel Matrix Multiplication)

Beschreibung: Matrizen werden in Blöcke aufgeteilt und jedes Paar Blöcke wird parallel auf verschiedenen Prozessoren multipliziert.

Analyse der Komplexität:

• Zeitliche Komplexität: O(n^3 / P), wobei P die Anzahl der Prozessoren ist.
• Räumliche Komplexität: O(n^2) zur Speicherung der Zwischenergebnisse.

6.5 Implementierung paralleler Algorithmen

Werkzeuge und Bibliotheken:

1. OpenMP:
   • Bibliothek für C, C++ und Fortran, die Werkzeuge zur Entwicklung von Multithreading-Anwendungen bietet.
2. MPI (Message Passing Interface):
   • Standard für paralleles Programmieren auf verteilten Systemen, unterstützt den Nachrichtenaustausch zwischen Prozessen.
3. CUDA:
   • Plattform und API von NVIDIA zur Entwicklung paralleler Programme, die Grafikprozessoren (GPU) nutzen.
4. Threading und Multiprocessing in Python:
   • Module für die Erstellung von Multithreading- und Multiprocessing-Programmen in Python.

Parallele Algorithmen ermöglichen es, die Berechnungen erheblich zu beschleunigen, indem Aufgaben auf mehrere Prozessoren oder Kerne aufgeteilt werden. Die Analyse der Komplexität paralleler Algorithmen umfasst die Bewertung von Beschleunigung, Effizienz und die Nutzung von Amdahl's und Gustafson's Gesetzen, um das maximale Beschleunigungspotential bei der Parallelisierung zu verstehen.

Parallele Algorithmen finden Anwendung in verschiedenen Bereichen, von Sortierung und Suche bis hin zu komplexen mathematischen Berechnungen, und erfordern den Einsatz spezialisierter Werkzeuge und Bibliotheken für ihre Implementierung.

Wichtig! Du musst dich nicht zu sehr für parallele Algorithmen begeistern. Erstens, wegen Amdahl's Law, sind sie nicht so effizient, wie es scheint. Zweitens, heutzutage bearbeiten Server mit 30 Prozessoren 3000 Anfragen pro Minute und wir haben immer noch n Aufgaben auf 1 Prozessor, nicht 1 Aufgabe für n Prozessoren.

Drittens sind reale Aufgaben, die durch Mehrprozessornutzung beschleunigt werden müssen, auf die GPU (Grafikkarten) umgezogen und ihr Code wird in low-level Sprachen wie C geschrieben.