Paralleles Merge Sort in C++: Tutorial für Cscn73000 Assignment 2

Einleitung: Warum parallele Sortierung?

Daten sind das Herzstück der modernen Informatik. Ob in der Finanzwelt, bei Gaming-Plattformen oder in KI-gestützten Apps – riesige Datenmengen müssen effizient sortiert werden. Der klassische Merge-Sort-Algorithmus ist zwar effektiv, aber in einer sequenziellen Version nutzt er nur einen Kern. In Zeiten von Multi-Core-Prozessoren und parallelen Architekturen ist es essenziell, diese Algorithmen für Parallelverarbeitung zu optimieren. In diesem Tutorial zeigen wir dir, wie du einen sequenziellen Merge Sort in C++ in eine parallele Version umwandelst – genau wie in der Aufgabenstellung Cscn73000 Assignment 2.

Stell dir vor, du organisierst ein großes Gaming-Turnier mit Tausenden von Spielern. Ein einzelner Schiedsrichter würde ewig brauchen, um die Rangliste zu sortieren. Aber wenn du mehrere Helfer einsetzt, die jeweils einen Teil der Liste sortieren, geht es viel schneller. Genau das macht paralleles Merge Sort: Es teilt die Daten auf mehrere Threads auf, die gleichzeitig arbeiten.

Grundlagen: Merge Sort verstehen

Bevor wir parallelisieren, müssen wir den sequenziellen Merge Sort verstehen. Der Algorithmus folgt dem Teile-und-Herrsche-Prinzip:

Teile: Das Array wird rekursiv in zwei Hälften geteilt, bis nur noch ein Element übrig ist.
Herrsche: Die sortierten Teillisten werden durch Merge wieder zusammengeführt.

Hier ein einfacher C++-Code für den sequenziellen Merge Sort (Startpunkt für die Aufgabe):

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Dieser Code arbeitet sequenziell: Ein Thread führt alle Rekursionen aus. Für kleine Arrays (z.B. N=10) ist das in Ordnung, aber bei 100.000 Elementen wird die Wartezeit spürbar.

Paralleles Merge Sort: Die Idee

Die parallele Version nutzt mehrere Threads, um die Rekursionsbäume gleichzeitig zu durchlaufen. Statt die linke und rechte Hälfte nacheinander zu sortieren, starten wir für jede Hälfte einen neuen Thread. Wichtig ist, dass die Anzahl der Threads begrenzt ist, um Overhead zu vermeiden. Eine typische Strategie ist es, bis zu einer bestimmten Tiefe (z.B. 4 Threads) parallel zu arbeiten und dann sequenziell fortzufahren.

In der Aufgabe Cscn73000 sollst du eine neue Funktion Parallel_Merge_Sort erstellen. Diese Funktion teilt das Array in Segmente auf und verteilt sie an Threads. Jeder Thread sortiert sein Segment mit dem sequenziellen Merge Sort. Anschließend werden die sortierten Segmente durch Merge-Schritte zusammengeführt.

Implementierung der parallelen Version

Wir verwenden std::thread aus C++11. Hier ein Grundgerüst:

#include <iostream>
#include <thread>
#include <vector>
#include <algorithm>
#include <chrono>

void merge(int arr[], int left, int mid, int right) { /* wie oben */ }

void mergeSortSeq(int arr[], int left, int right) { /* wie oben */ }

void parallelMergeSort(int arr[], int left, int right, int depth) {
    if (depth <= 0 || left >= right) {
        mergeSortSeq(arr, left, right);
        return;
    }
    int mid = left + (right - left) / 2;
    std::thread leftThread(parallelMergeSort, arr, left, mid, depth - 1);
    std::thread rightThread(parallelMergeSort, arr, mid + 1, right, depth - 1);
    leftThread.join();
    rightThread.join();
    merge(arr, left, mid, right);
}

void Parallel_Merge_Sort(int arr[], int n) {
    int maxThreads = std::thread::hardware_concurrency();
    int depth = (int)log2(maxThreads);
    parallelMergeSort(arr, 0, n - 1, depth);
}

Erklärung: depth steuert, wie viele Rekursionsebenen parallel ausgeführt werden. Mit hardware_concurrency() ermitteln wir die Anzahl der verfügbaren Kerne. Jeder Thread ruft rekursiv parallelMergeSort auf, bis die Tiefe erreicht ist – dann wird sequenziell sortiert.

Kritische Abschnitte und Thread-Sicherheit

Beim Mergen greifen mehrere Threads auf das globale Array zu. Da wir das Array jedoch in disjunkte Segmente aufteilen, entstehen keine Datenkonflikte – solange wir sicherstellen, dass sich die Bereiche nicht überschneiden. In der Aufgabenstellung wird zusätzlich verlangt, eine globale Vektor von Thread-IDs zu führen, die bei jedem kritischen Abschnitt aktualisiert wird. Ein kritischer Abschnitt ist hier der Merge-Schritt, da er auf gemeinsame Daten zugreift. Wir schützen ihn mit einem std::mutex:

#include <mutex>
std::vector<std::thread::id> threadIDs;
std::mutex mtx;

void merge(int arr[], int left, int mid, int right) {
    // ... Merge-Logik ...
    // Kritischer Abschnitt: Thread-ID speichern
    {
        std::lock_guard<std::mutex> lock(mtx);
        threadIDs.push_back(std::this_thread::get_id());
    }
}

So protokollieren wir, welche Threads den Merge ausführen. Das ist nützlich, um die Parallelität zu überprüfen.

Leistungsanalyse: Sequenziell vs. Parallel

Nach der Implementierung müssen wir die Laufzeiten messen. Verwende std::chrono::high_resolution_clock:

auto start = std::chrono::high_resolution_clock::now();
mergeSortSeq(arr, 0, N-1);
auto end = std::chrono::high_resolution_clock::now();
auto seqTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

// Für parallele Version: Array zurücksetzen und erneut messen
start = std::chrono::high_resolution_clock::now();
Parallel_Merge_Sort(arr, N);
end = std::chrono::high_resolution_clock::now();
auto parTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

std::cout << "Sequenzielle Zeit: " << seqTime << " ms\n";
std::cout << "Parallele Zeit: " << parTime << " ms\n";
std::cout << "Speedup: " << (double)seqTime / parTime << "\n";

Teste mit N=10 (klein) und dann mit N=100000 oder mehr. Bei großen Arrays sollte die parallele Version deutlich schneller sein – vorausgesetzt, die Thread-Anzahl ist optimal. Ein Speedup von 2-4 auf einem Quad-Core ist typisch.

Praktische Tipps aus der Aufgabenstellung

Konstante N: Beginne mit N=10, um die Korrektheit zu prüfen. Erhöhe dann schrittweise.
Kommentiere Ausgaben aus: Bei großen Arrays solltest du die Druckbefehle auskommentieren, da sie die Messung verfälschen.
Thread-IDs: Der globale Vektor mit Thread-IDs hilft, die Parallelität zu visualisieren. Gib ihn nach der Sortierung aus.
Parallelisierungstiefe: Experimentiere mit verschiedenen Tiefen. Zu viele Threads können Overhead erzeugen.

Häufige Fehler und wie du sie vermeidest

Race Conditions: Wenn Threads gleichzeitig auf dasselbe Array-Element zugreifen, kann es zu inkorrekten Ergebnissen kommen. Stelle sicher, dass die Segmente disjunkt sind.
Deadlocks: Verwende lock_guard oder unique_lock, um Mutexe sicher zu handhaben.
Zu viele Threads: Mehr Threads als Kerne bringen keinen Vorteil. Begrenze die Anzahl mit hardware_concurrency().
Vergessene Thread-Joins: Jeder gestartete Thread muss gejoined werden, sonst terminiert das Programm möglicherweise nicht richtig.

Trend-Beispiel: Paralleles Sortieren in der Praxis

Stell dir vor, du arbeitest an einer KI-gestützten App, die Echtzeit-Sportdaten verarbeitet. Während eines Fußballspiels werden ständig neue Spielerstatistiken generiert. Ein paralleler Sortieralgorithmus kann diese Daten in Millisekunden ordnen und sofort für Analysen bereitstellen. Ohne Parallelisierung würde die App bei 100.000 Datensätzen mehrere Sekunden brauchen – ein No-Go für Live-Ergebnisse. Genau solche Anwendungen motivieren die Arbeit an parallelen Algorithmen.

Zusammenfassung

In diesem Tutorial hast du gelernt, wie du einen sequenziellen Merge Sort in eine parallele Version umwandelst. Du hast die Grundlagen von std::thread, kritischen Abschnitten und Leistungsmessung kennengelernt. Die Implementierung einer Parallel_Merge_Sort-Funktion ist der Kern der Aufgabe Cscn73000 Assignment 2. Mit diesem Wissen kannst du große Datenmengen effizient sortieren und die Vorteile der Parallelverarbeitung nutzen. Viel Erfolg bei deiner Abgabe!