Demian Hespe, Lukas Hübner, Peter Sanders

Charel Mercatoris

Mit der Zunahme von parallelen Rechenknoten in Hochleistungsrechnersystemen steigt die Wahrscheinlichkeit von Hardwareausfällen für Anwendungen, welche auf Millionen von Knoten laufen. Aus diesem Grund müssen zukünftige Anwendungen Knotenausfälle erwarten, erkennen und behandeln. Im Ramen dieser Arbeit entwickeln wir ein dezentrales, fehlertolerantes MapReduce Framework für iterative Algorithmen, das mit Knotenausfall umgehen kann. Unser Framework folgt dem Bulk Synchronous Parallel Modell (BSP) und verwendet eine zufällige statische Lastverteilung während der Shuffle Phase. Wir stellen einen Fehlertoleranzmechanismus vor, welcher während der Shuffle Phase zusätzliche Selbstnachrichten austauscht und im Speicher ablegt. Im Gegensatz zu bisherigen Ansätzen speichern wir keine Checkpoints auf einem fehlertoleranten Dateisystem. Darüber hinaus stellen wir ein rein MPI basiertes MapReduce Framework, sowie eine hybride Parallelisierung mit mehreren OpenMP Threads pro Prozess vor. Wir beweisen die erwartete Laufzeit der verschiedenen MapReduce Phasen und Fehlertoleranzmechanismen. Wir implementieren die "Word Count", "Page Rank", "Connected Component" und R-Mat Algorithmen in unserem Framework und führen Laufzeitexperimente durch. Wir beobachten einen superlineare Speedup für das Abspeichern und Senden der Selbstnachrichten. Die anderen Phasen, außer die Shuffle Phase, haben optimale Speedups, wenn die Eingabe im Vergleich zu der Anzahl an Prozessen und der Flaschenhals Last groß genug ist.