Automatische Parallelisierung von rekursiven Programmen auf Vielkernrechnern mittels spekulativer Ausführung

BearbeiterIn:Frederik Simon
Titel:Automatische Parallelisierung von rekursiven Programmen auf Vielkernrechnern mittels spekulativer Ausführung
Typ:masters thesis
Betreuer:Philippsen, M.; Werth, T.
Status:abgeschlossen am 1. Juni 2016
Vorausetzungen:
Thema:

Der XeonPhi-Prozessor (Intel MIC Architektur) stellt mit seiner Vielzahl an Kernen und der großen Registerbreite (und der damit verbundenen Vektorisierbarkeit) neue Herausforderungen an den Programmierer, die vorhandene Rechenleistung effizient zu nutzen.

Cilk erweitert die Programmiersprache C um wenige Schlüsselworte, die zur Erzeugung und Kontrolle von rechenbetonten Kontrollfäden dienen. In Vergleichen mit anderen Programmiermodellen überzeugt Cilk sowohl mit einem hohen Grad an Abstraktion für den Programmierer als auch guten Laufzeiten bei paralleler Ausführung.
Das bestehende Lastverteilungsverfahren für Mehrkernarchitekturen mit gemeinsamem Speicher ist mittels Arbeitsdiebstahl realisiert. Dabei wählt der untätige Arbeiter zufällig ein 110pferu aus, aus deren Warteschlange Arbeitspakete gestohlen werden.
Der Cilk-Programmierer muss Nebenläufigkeiten mittels spawn und Barrieren mittels sync im Programm explizit angeben. Dies ist sowohl aufwändig als auch fehleranfällig. Um ein sequentielles C-Programm korrekt in ein Cilk-Programm zu übersetzen, könnte man einfach jeden (rekursiven) Funktionsaufruf mit spawn annotieren und direkt danach eine Barriere (sync) setzen.

Im Rahmen der Arbeit sollen möglichst viele Barrieren entfernt werden. Dies kann zum einen durch Übersetzertechniken geschehen, die analysieren, dass eine Barriere entweder nie notwendig ist (Fall A), immer notwendig ist (Fall B, z.B. durch triviale Datenabhängigkeiten) oder es nicht statisch entschieden werden kann (Fall C). Die zusätzlich vorhandene Rechenkapazität der vielen Kerne der XeonPhi-Architektur erlaubt es, im Fall C sowohl die sequentielle Berechnung als auch eine spekulativ parallele Berechnung anzustoßen. Sollte sich in der parallelen Berechnung herausstellen, dass eine Wettlauf­ situation eingetreten ist, wird das Ergebnis der sequentiellen Berechnung verwendet.

Im MIT-Cilk-Projekt wurde ein Werkzeug (sog. Nondeterminator) entwickelt, um Nebenläufigkeitsprobleme wie Wettlaufsituationen in Cilk-Programmen während um des Programmablaufs erkennen und melden zu können. Der Nondeterminator prüft dabei für ein gegebenes Eingabeset, ob es im Programmablauf zu solchen Situationen gekommen ist, indem Datenzugriffe instrumentiert und im weiteren Verlauf untersucht werden.
Im Fall C sollen ähnliche Algorithmen wie im Nondeterminator eingesetzt werden, und die Prorgammausführung an den entsprechenden Barrieren spekulativ fortgesetzt werden. Falls sich das sync als notwendig herausstellt, wird es entsprechend markiert und in Zukunft nicht als Fall B betrachtet.

Eine weitere Alternative ist die Verwendung von Software Transactional Memory, in der die verschiedenen Kontrollfäden ihre Arbeitspakete im Rahmen einer Transaktion ausführen. Falls eine Transaktion abgebrochen werden muss, muss die entsprechende Barriere (zumindest für diese Eingabe) ergänzt werden.

Folgende Schritte sind für die Arbeit vorgeschlagen:

  • Einarbeitung in XeonPhi-Architektur
  • Einarbeitung in taskparallele Programmierung mit Cilk
  • Einarbeitung in den LLVM-Übersetzungsvorgang und die Cilk-Laufzeitbibliothek
  • Sichten der relevanten Literatur
  • Implementierung der notwendigen Analysen und Spracherweiterungen im Übersetzer
  • Implementierung einer spekulativen Ausführung inkl. Möglichkeit des Rollbacks
  • Implementierung mehrerer Beispielanwendungen und Evaluation
  • Optional: theoretischer Beweis der Effizienz und Korrektheit des Ausführungsmodells
  • Ausarbeitung
watermark seal