Automatische Optimierung der Granularität von rekursiven task-parallelen Programmen auf Vielkernrechnern

BearbeiterIn:Daniel Schmidt
Titel:Automatische Optimierung der Granularität von rekursiven task-parallelen Programmen auf Vielkernrechnern
Typ:masters thesis
Betreuer:Philippsen, M.; Werth, T.
Status:abgeschlossen am 2. Mai 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 Lastverteilungsverfahren für Mehrkernarchitekturen mit gemeinsamem Speicher ist mittels Arbeitsdiebstahl realisiert. Dabei wählt der untätige Arbeiter zufällig ein „Opfer" aus, aus deren Warteschlange Arbeitspakete gestohlen werden.

Damit dieser Arbeitsdiebstahl möglich ist, muss der „erste" Arbeiter zusätzliche Daten in seinem Stackframe aufsetzen und den Zustand abspeichern, bevor er ein neues Arbeitspaket beginnt, das parallel ausgeführt werden darf. Dieser Zustand kann dann von einem untätigen Arbeiter geladen werden, wodurch dieses parallel zum ersten Arbeiter ausgeführt wird. Dieser Mehraufwand für den ersten Arbeiter fällt umso deutlicher ins Gewicht, je kleiner die einzelnen Arbeitspakete sind.

Die Größe eines Arbeitspakets hängt (nach einer initialen Aufteilung) meist vom Basisfall der rekursiven Funktion ab. Wählt man die Granularität des Basisfalls zu klein, ist die parallele Ausführung durch den Mehraufwand evtl. langsamer als die sequentielle Ausführung. Wählt man die Granularität des Basisfalls zu groß, werden die vorhandenen parallelen Recheneinheiten evtl. nicht optimal ausgenutzt. Die optimale Granularität hängt ggf. auch von der Phase des Programms und der aktuellen Auslastung der anderen Rechenkerne ab.

Im Rahmen der Arbeit sollen verschiedene Techniken ausprobiert werden, um die Granularität des Basisfalls automatisch zu optimieren. Zum einen sollen in der Codeerzeugung verschiedene Varianten mit unterschiedlicher Basisfallgröße generiert werden, die dann automatisch zur Laufzeit des Programms ausgetauscht werden. Dies kann z.B. auf Grund von Heuristiken (z.B. Füllstände der Warteschlangen) oder gesammelter Profiling-Informationen geschehen. Eine weitere Möglichkeit, für gröbere Granularität zu sorgen, ist das Einbetten der rekursiven Funktion in sich selbst. Dabei ist darauf zu achten, dass die Codegröße gering gehalten wird und im rekursiven Aufruf auf eingebettete Funktionen niedrigerer und höherer Ordnung umgestiegen werden können muss.

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 im Übersetzer zur Erkennung des rekursiven Basisfalls
  • Implementierung einer Code-Transformation zur Erzeugung eines "größeren" Basisfalls
  • Implementierung der Techniken, um zur Laufzeit zwischen verschiedenen Funktionsvarianten zu wechseln
  • Implementierung einer Code-Transformation zur Einbettung von rekursiven, task-parallelen Funktionen
  • Vergleich mehrerer Heuristiken und Profilingschritte
  • Implementierung mehrerer Beispielanwendungen und Evaluation
  • Ausarbeitung
watermark seal