Paralleles Datenverarbeitungs-Design-Sprint: Hamlet-Wortzählung mit C++ und Thread-Pools

Einführung in den parallelen Design-Sprint

Der CSCN73000 Assignment 3 fordert dich heraus, ein paralleles Programm zu entwerfen, das eine große Textdatei (Hamlet.txt) analysiert. Deine Lösung muss die Vorkommen bestimmter Wörter zählen und die Gesamtwortanzahl ermitteln – und das alles parallel. In diesem Tutorial zeigen wir dir, wie du einen Thread-Pool einsetzt, um die Anforderungen zu erfüllen, und wie du Execution Time, Latency, Speedup und Efficiency misst. Der Fokus liegt auf dem parallelen Design, nicht auf sequenzieller Implementierung.

Warum parallele Verarbeitung? Ein Beispiel aus der Gaming-Welt

Stell dir vor, du entwickelst eine KI für ein Battle-Royale-Spiel wie Fortnite. Die KI muss gleichzeitig Gegner erkennen, die Karte scannen und Entscheidungen treffen – alles in Echtzeit. Genauso wie dein Hamlet-Wortzähler mehrere Wörter parallel zählen muss, nutzt die Spieleentwicklung Multithreading, um flüssige 60 FPS zu erreichen. Ohne parallele Verarbeitung wäre das Spiel ruckelig und unspielbar.

Anforderung 1: Parallele Wortzählung (Horatio, and, Hamlet, God)

Dein Programm muss die Vorkommen von Horatio, and, Hamlet und God (case-insensitive) zählen. Du kannst die Datei in Blöcke aufteilen und jeden Block von einem Thread verarbeiten lassen. Jeder Thread aktualisiert einen gemeinsamen Zähler – aber Achtung: Race Conditions! Verwende Mutexes oder atomare Operationen, um die Zähler sicher zu inkrementieren. Hier ein Codeausschnitt:

std::atomic<int> horatioCount{0};
std::atomic<int> andCount{0};
// ... weitere Zähler

// Thread-Funktion
void countWords(const std::string& chunk) {
    // Tokenisierung und Zählung
    if (word == "horatio") horatioCount++;
    // ...
}

Anforderung 2 und 4: Gesamtwortzählung mit Thread-Pool

Die Gesamtwortanzahl muss mit einem Thread-Pool berechnet werden. Ein Thread-Pool verwaltet eine feste Anzahl von Worker-Threads, die Aufgaben aus einer Warteschlange abarbeiten. Das ist effizienter als ständig neue Threads zu erstellen. Du kannst die Datei in kleinere Teile zerlegen und jedes Teil als Aufgabe an den Pool übergeben. Die Ergebnisse werden aufsummiert.

ThreadPool pool(4); // 4 Worker-Threads
std::vector<std::future<int>> futures;
for (auto& chunk : chunks) {
    futures.push_back(pool.enqueue([chunk]() {
        return countTotalWords(chunk);
    }));
}
int totalWords = 0;
for (auto& f : futures) totalWords += f.get();

Warum 4 Threads? Das hängt von deiner CPU ab. Ein guter Richtwert ist die Anzahl der physischen Kerne. Du kannst auch die optimale Anzahl durch Experimente ermitteln – das ist Teil des Design Sprints.

Anforderung 3: Sequenzielle Abhängigkeit – Wortzählung vor Gesamtzahl

Die spezifischen Wortzählungen (Anforderung 1) müssen abgeschlossen sein, bevor die Gesamtwortzählung (Anforderung 2) beginnt. Dies erreichst du durch Barrieren oder std::future. Starte zuerst die Threads für die Wortzählung, warte mit future.get() auf ihre Ergebnisse, und starte dann den Thread-Pool für die Gesamtzählung. Ein einfacher std::promise kann ebenfalls verwendet werden.

// Phase 1: Wortzählung parallel
std::vector<std::thread> wordThreads;
// ... Threads starten
for (auto& t : wordThreads) t.join();

// Phase 2: Gesamtwortzählung mit Thread-Pool
// ... wie oben

Leistungsmessung: Execution Time, Latency, Speedup, Efficiency

Deine parallele Lösung muss messen, wie schnell sie ist. Verwende std::chrono::high_resolution_clock für präzise Zeitmessung. Execution Time ist die Gesamtzeit von Start bis Ende. Startup Latency ist die Zeit bis zum Beginn der ersten Berechnung. Speedup = sequenzielle Zeit / parallele Zeit. Efficiency = Speedup / Anzahl der Threads. Notiere diese Werte in deiner Abgabe.

auto start = std::chrono::high_resolution_clock::now();
// parallele Arbeit
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = end - start;
std::cout << "Execution Time: " << elapsed.count() << " s\n";

Typische Fehler und wie du sie vermeidest

• Race Conditions: Verwende atomare Variablen oder Mutexes, wenn mehrere Threads auf gemeinsame Daten zugreifen.
• Deadlocks: Achte auf die Reihenfolge, in der du Mutexes sperrst.
• Zu viele Threads: Mehr Threads als Kerne führen zu Kontextwechsel-Overhead. Nutze einen Thread-Pool mit begrenzter Größe.
• Sequenzielle Engpässe: Stelle sicher, dass die Datei parallel gelesen wird (z.B. mit mmap oder mehreren ifstream-Streams an verschiedenen Positionen).

Trend-Inspiration: KI und große Textmengen

In Zeiten von Large Language Models (LLMs) wie ChatGPT ist die parallele Verarbeitung von Textdaten aktueller denn je. Wenn du Texte für das Training einer KI aufbereitest, musst du riesige Dateien parallel parsen – ähnlich wie in deinem Assignment. Das Verständnis von Thread-Pools und parallelen Algorithmen hilft dir, effiziente Datenpipelines für KI-Anwendungen zu bauen.

Zusammenfassung und nächste Schritte

Dein paralleler Hamlet-Wortzähler ist ein hervorragendes Beispiel für Parallel Data Processing. Du hast gelernt, wie man eine Datei in Blöcke aufteilt, Threads synchronisiert und Leistung misst. Experimentiere mit verschiedenen Thread-Anzahlen und vergleiche die Ergebnisse. Dokumentiere deinen Designprozess für die Abgabe – der Professor bewertet die Qualität des parallelen Designs, nicht nur die Korrektheit.

Viel Erfolg bei deinem CSCN73000 Design Sprint!