OpenMP-Parallelisierung ohne parallel for: Leistungsoptimierung für Cosc407 A3

OpenMP-Parallelisierung ohne parallel for: Leistungsoptimierung für Cosc407 A3

In dieser Anleitung lernst du, wie du die Aufgabenstellung der Cosc407 A3 (20 Punkte) meisterst, ohne #pragma omp parallel for oder #pragma omp for zu verwenden. Stattdessen setzt du manuelle Thread-Aufteilung mit omp_get_thread_num() und omp_get_num_threads() ein. Dies ist eine typische Anforderung in Hochschulkursen wie Cosc407, um ein tiefes Verständnis für parallele Programmierung zu entwickeln.

Warum OpenMP ohne parallel for?

Viele Studierende greifen automatisch zu #pragma omp parallel for, aber die Aufgabe verbietet dies bewusst. Du sollst lernen, wie die Arbeit manuell aufgeteilt wird – ähnlich wie bei einem Projektmanagement in agilen Teams: Statt einer automatischen Aufgabenverteilung weist du jedem Thread explizit einen Bereich zu. Dies ist besonders relevant für Bildverarbeitungsalgorithmen, bei denen die Laufzeit entscheidend ist. Aktuelle Trends wie KI-gestützte Bildbearbeitung in Apps wie Canva oder Photoshop nutzen ähnliche Parallelisierungskonzepte, um Filter in Echtzeit anzuwenden.

Schritt 1: Projekt einrichten und Code verstehen

Lade die ZIP-Datei von Canvas herunter und entpacke sie in ein neues C-Projekt. Lies die readme.txt für Copyright-Hinweise und Hintergrund zur verwendeten Bibliothek. Die ersten drei Anweisungen in main() definieren Eingabe- und Ausgabebilder sowie die erforderliche Verarbeitung. Experimentiere mit den Konstanten, um die Ausgabe zu verstehen. Dein Ziel ist es, die Verarbeitungszeit zu reduzieren, indem du die Arbeit auf mehrere Threads (z. B. 4) verteilst.

// Beispiel für die ersten drei Anweisungen
char* inputFile = "input.png";
char* outputFile = "output.png";
int filterType = 1; // 1 = Weichzeichner, 2 = Kantenerkennung

Schritt 2: Manuelle Thread-Aufteilung mit OpenMP

Ohne parallel for musst du die Schleifen selbst aufteilen. Verwende #pragma omp parallel und teile die Iterationen manuell auf. Ein gängiges Muster ist die Blockaufteilung (block distribution), bei der jeder Thread einen zusammenhängenden Block von Zeilen oder Pixeln bearbeitet.

#pragma omp parallel num_threads(4)
{
    int tid = omp_get_thread_num();
    int num_threads = omp_get_num_threads();
    int chunk = height / num_threads;
    int start = tid * chunk;
    int end = (tid == num_threads - 1) ? height : start + chunk;
    for (int y = start; y < end; y++) {
        for (int x = 0; x < width; x++) {
            // Bildverarbeitung
        }
    }
}

Diese Methode ähnelt der Datenparallelität in GPUs, wie sie in modernen KI-Modellen (z. B. Stable Diffusion) verwendet wird. Jeder Thread arbeitet unabhängig an einem Teil des Bildes.

Schritt 3: Zeitmessung mit omp_get_wtime()

Um die Leistung zu vergleichen, misst du die Zeit vor und nach dem parallelen Block. Die Funktion omp_get_wtime() gibt die vergangenen Sekunden seit einem Referenzpunkt zurück. Platziere die Messung wie folgt:

double start = omp_get_wtime();
// Paralleler Block
#pragma omp parallel num_threads(4)
{
    // ...
}
double end = omp_get_wtime();
printf("Zeit mit %d Threads: %f Sekunden\n", num_threads, end - start);

Notiere die Zeiten für 2, 4, 8 und 16 Threads als Kommentar im Code. Diese Messungen sind entscheidend für die Bewertung der Skalierbarkeit deiner Lösung. Ein typisches Ergebnis könnte sein:

// Zeiten:
// 2 Threads: 12.34 s
// 4 Threads: 6.78 s
// 8 Threads: 4.12 s
// 16 Threads: 3.89 s

Schritt 4: Korrektheit prüfen und Ausgabe vergleichen

Vergleiche das Ausgabebild mit der seriellen Version. Die Pixelwerte müssen identisch sein. Verwende ein Tool wie diff oder visuellen Vergleich. Bei Abweichungen prüfe die Randbedingungen – oft entstehen Fehler durch falsche Indexberechnung am Ende der Blöcke.

Häufige Fehler und Lösungen

• Datenrennen (Race Conditions): Wenn mehrere Threads auf dieselbe Speicherstelle schreiben, verwende #pragma omp critical oder atomare Operationen. In der Bildverarbeitung tritt dies selten auf, da jeder Thread exklusive Pixelbereiche hat.
• Falsche Chunk-Größe: Bei ungleicher Teilung kann ein Thread übermäßig viel Arbeit haben. Verwende eine dynamische Aufteilung oder runde die Chunk-Größe geschickt.
• Vergessene omp_get_wtime() Initialisierung: Stelle sicher, dass die Zeitmessung vor dem parallelen Block beginnt und danach endet.

Bezug zu aktuellen Trends

Die manuelle Thread-Aufteilung ist nicht nur akademisch relevant. In der Spieleentwicklung (z. B. Unreal Engine 5) werden ähnliche Techniken verwendet, um Render-Aufgaben auf mehrere Kerne zu verteilen. Auch in Finanzalgorithmen für den Hochfrequenzhandel werden Berechnungen manuell partitioniert, um Latenzen zu minimieren. Ein weiteres Beispiel ist die Echtzeit-Videobearbeitung in Apps wie TikTok, wo Filter auf mehrere Threads verteilt werden, um flüssige Vorschauen zu gewährleisten.

Erweiterte Optimierung: Lastverteilung verbessern

Falls die Bildverarbeitung unterschiedlich komplex ist (z. B. Kantenerkennung in bestimmten Bereichen), kann eine dynamische Aufteilung sinnvoll sein. Verwende eine Aufgabenwarteschlange, bei der Threads sich die nächste Aufgabe holen. Dies erfordert jedoch omp_lock oder atomare Inkremente. Ein einfacherer Ansatz ist die Verwendung einer zyklischen Verteilung (cyclic distribution), bei der jeder Thread jede num_threads-te Zeile bearbeitet.

#pragma omp parallel num_threads(4)
{
    int tid = omp_get_thread_num();
    for (int y = tid; y < height; y += num_threads) {
        for (int x = 0; x < width; x++) {
            // Verarbeitung
        }
    }
}

Diese Methode kann die Last besser ausgleichen, wenn die Verarbeitungszeit pro Zeile variiert.

Zusammenfassung und nächste Schritte

Du hast gelernt, wie du OpenMP ohne parallel for einsetzt, um Bildverarbeitung zu parallelisieren. Teste deine Implementierung mit verschiedenen Thread-Anzahlen und dokumentiere die Zeiten. Für die Abgabe in Cosc407 sind die kommentierten Zeiten und der korrekte Output entscheidend. Viel Erfolg bei deiner Assignment-Abgabe!

Hinweis: Achte darauf, dass du die neueste Version deines Codes abgibst, da erneute Abgaben alte Versionen überschreiben. Verwende Eclipse oder die Kommandozeile, um Argumente zu übergeben (siehe omp_trap_1.c).