Assignment Chef icon Assignment Chef
All German tutorials

Programming lesson

Parallele Matrixmultiplikation in C++: Ein Tutorial mit std::thread, Mutex und Shared Mutex

Lerne, wie du die traditionelle Matrixmultiplikation mit std::thread parallelisierst, kritische Abschnitte mit Mutex und Shared Mutex schützt und die Effizienz deines parallelen Codes analysierst. Inklusive praktischer Tipps für die Cscn73000 Aufgabe.

parallele Matrixmultiplikation C++ Cscn73000 assignment 1 std::thread Matrixmultiplikation std::mutex Beispiel std::shared_mutex Tutorial C++ Parallelisierung Übung Effizienz paralleler Algorithmen Matrixmultiplikation Threads kritische Abschnitte C++ Multithreading C++ Beispiel C++ Performance Optimierung parallele Programmierung Studium C++ Thread Synchronisation Matrixmultiplikation parallelisieren C++ Chrono Zeitmessung C++ Vektor Matrix

Einführung: Warum parallele Matrixmultiplikation?

Matrixmultiplikation ist ein klassisches Beispiel für Parallelisierung – und perfekt für deine Cscn73000 Aufgabe. Stell dir vor, du berechnest die Punktzahlen für ein eSport-Turnier mit tausend Teams: Jedes Spielergebnis hängt von vielen Faktoren ab. Wenn du das sequenziell machst, dauert es ewig. Mit parallelen Threads kannst du die Arbeit auf mehrere Kerne verteilen, so wie ein Turnier mehrere Spiele gleichzeitig austrägt. In diesem Tutorial zeige ich dir, wie du mit std::thread, std::mutex und std::shared_mutex eine effiziente parallele Matrixmultiplikation implementierst – genau das, was in der Cscn73000 assignment 1 gefordert wird.

Grundlagen der Matrixmultiplikation auffrischen

Bevor wir parallelisieren, müssen wir die sequenzielle Version verstehen. Gegeben zwei Matrizen A (Größe m×n) und B (Größe n×p), ist das Ergebnis C (m×p) definiert als:

for (int i = 0; i < m; i++) {
    for (int j = 0; j < p; j++) {
        C[i][j] = 0;
        for (int k = 0; k < n; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Die äußeren Schleifen über i und j sind unabhängig – jede Zelle von C kann separat berechnet werden. Das ist der Schlüssel zur Parallelisierung.

Design der parallelen Version

Für deine parallele Matrixmultiplikation C++ Aufgabe musst du zwei Funktionen schreiben:

  • parallel_matrix_multiply(): Verteilt die Arbeit auf Threads.
  • parallel_helper(): Führt die eigentliche Berechnung für einen Teil der Matrix aus.

Überlege dir: Wie viele Threads? Welche Daten teilen sie? Die Ergebnis-Matrix C wird von allen Threads beschrieben – das ist ein kritischer Abschnitt. Ohne Synchronisation gibts Datenrennen. Später wirst du std::mutex und std::shared_mutex einsetzen, um das zu schützen.

Schritt 1: Sequenzielle Version als Ausgangspunkt

Lade die Datei A1_StartingPoint.cpp von eConestoga herunter. Sie enthält eine funktionierende sequenzielle Matrixmultiplikation. Kompiliere sie in Visual Studio und stelle sicher, dass sie läuft. Nutze kleine Matrizen (z.B. 10×10) mit der DisplayArray-Funktion zum Debuggen.

Schritt 2: Parallele Implementierung mit std::thread

Wir teilen die Zeilen der Ergebnis-Matrix gleichmäßig auf die Threads auf. Angenommen, wir haben 4 Threads und 1000 Zeilen: Thread 0 bekommt Zeilen 0-249, Thread 1 Zeilen 250-499, usw. So vermeiden wir Konflikte – jeder Thread schreibt in seinen eigenen Bereich.

void parallel_helper(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int start_row, int end_row) {
    int n = A[0].size();
    int p = B[0].size();
    for (int i = start_row; i < end_row; i++) {
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

Die Hauptfunktion erstellt Threads und misst die Zeit:

void parallel_matrix_multiply(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int num_threads) {
    int m = A.size();
    int rows_per_thread = m / num_threads;
    vector<thread> threads;
    for (int t = 0; t < num_threads; t++) {
        int start = t * rows_per_thread;
        int end = (t == num_threads - 1) ? m : start + rows_per_thread;
        threads.emplace_back(parallel_helper, ref(A), ref(B), ref(C), start, end);
    }
    for (auto& th : threads) th.join();
}

Schritt 3: Zeitmessung und Effizienz

Miss die Zeit für sequenzielle und parallele Ausführung mit std::chrono. Berechne die Effizienz:

Effizienz = (Sequenzielle_Zeit / Parallele_Zeit) / Anzahl_Threads

Beispiel: Sequenziell 10s, parallel mit 4 Threads 3s => Effizienz = (10/3)/4 ≈ 0,83. Werte unter 1 sind normal wegen Overhead. Probiere verschiedene Threadzahlen (1, 2, 4, 8) und beobachte die Effizienz. Warum sinkt sie bei vielen Threads? Wegen Thread-Erstellungs-Overhead und Speicherkonflikten. Dein Laptop hat vielleicht 4 oder 8 Kerne – schau im Task-Manager nach.

Schritt 4: Kritische Abschnitte mit std::mutex

Bisher haben wir keine Synchronisation gebraucht, weil jeder Thread exklusive Zeilen bearbeitet. Aber die Aufgabenstellung verlangt, einen std::mutex um die gesamte Ergebnis-Matrix zu legen – auch wenn das ineffizient ist. Modifiziere parallel_helper so, dass jeder Zugriff auf C durch einen Mutex geschützt wird:

std::mutex mtx;
void parallel_helper_mutex(...) {
    for (int i = start_row; i < end_row; i++) {
        for (int j = 0; j < p; j++) {
            int sum = 0;
            for (int k = 0; k < n; k++) {
                sum += A[i][k] * B[k][j];
            }
            mtx.lock();
            C[i][j] = sum;
            mtx.unlock();
        }
    }
}

Führe das Programm 10 Mal mit Matrixgröße 1000×1000 aus. Notiere Effizienz und Ausführungszeit. Der Mutex wird zum Flaschenhals – die Effizienz wird stark sinken. Berechne den Durchschnitt.

Schritt 5: Verbesserung mit std::shared_mutex

Ein std::shared_mutex erlaubt mehreren Threads gleichzeitiges Lesen, aber nur einem Schreiben. Da wir nur schreiben (und nie lesen während der Berechnung), bringt das hier kaum Vorteil – aber es ist eine Übung. Ersetze den Mutex durch einen Shared Mutex:

std::shared_mutex sh_mtx;
void parallel_helper_shared(...) {
    for (int i = start_row; i < end_row; i++) {
        for (int j = 0; j < p; j++) {
            int sum = 0;
            for (int k = 0; k < n; k++) {
                sum += A[i][k] * B[k][j];
            }
            sh_mtx.lock();
            C[i][j] = sum;
            sh_mtx.unlock();
        }
    }
}

Führe wieder 10 Läufe durch. Du wirst ähnliche Zeiten sehen, da der Exklusivzugriff dominant ist. Der Vorteil von Shared Mutex zeigt sich erst bei Lese-lastigen Szenarien.

Schritt 6: Optimierung – eigener Ansatz

Die Aufgabenstellung fordert dich auf, eine schnellere Lösung zu entwerfen. Idee: Vermeide die globale Synchronisation komplett, indem du jeder Thread seine eigene lokale Kopie der Ergebniszeilen berechnen lässt und erst am Ende zusammenführst. Oder nutze atomare Operationen? Aber für Matrizen ist das schwierig. Einfacher: Teile die Arbeit so auf, dass jeder Thread exklusiv auf seinen Bereich schreibt – wie in Schritt 2. Das ist die effizienteste Methode. Vergleiche die Effizienz mit und ohne Mutex. Dokumentiere deine Ergebnisse.

Zusammenfassung und Ausblick

Du hast gelernt, wie man Matrixmultiplikation parallelisiert, kritische Abschnitte mit std::mutex und std::shared_mutex schützt und die Effizienz misst. Diese Konzepte sind grundlegend für parallele Programmierung in C++ und tauchen in vielen Bereichen auf – von KI-Algorithmen bis zu Echtzeit-Rendering. Für deine Cscn73000 assignment hast du jetzt das Rüstzeug. Vergiss nicht, die geforderten Ergebnisse (Effizienz, Zeiten) in das Textfeld zu kopieren und deine Erkenntnisse zu erklären. Viel Erfolg!