Berechnungsverteilung auf heteogene, vernetzte Rechnerarchitekturen
Final Report Abstract
In den beiden Projektphasen wurde in mehreren Schritten ein Übersetzer-Prototyp entwickelt, mit dem es möglich ist, einfeche Schleifenprogramme automatisch zu parallellsieren und in einer heterogenen Netzwerkumgebung wie dem Grid automatisch auszuführen. Im Verlauf des Projektes stellte es sich heraus, dass ein rein statisches Ausführungsmodell mit fest vorgegebenen Ausführungszeitpunkten in einer stark heterogenen Umgebung nicht praktikabel ist. Insbesondere kompliziert eine statische Ausführung die Zielcodegenerierung, da alle Berechnungs- und Kommunikationsstatements gemeinsam für die Schleifengenerierung berücksichtigt werden müssen, was zu sehr großem und komplexen Zielcode führt. Stattdessen bewährte sich der von uns realisierte dynamische Ansatz, möglichst viel Freiheiten bei der Ausführung des parallelisierten Programms zur Laufzeit zu erlauben. Dies wurde durch die Verwendung eines Taskgraphen erreicht, der dynamisch von einem Scheduler zur Laufzeit abgearbeitet wird und so die Ausführungsreihenfolge der Tasks anhand der erfüllten Abhängigkeiten im Taskgraphen bestimmt. Auch die Verteilung von Berechnungen auf Prozessoren erfolgt dynamisch, wobei durch geeignete Kachelung mit fester Kachelgröße immer genug Tasks zur Auswahl stehen, um alle Realprozessoren auszulasten. Weiterhin stellten wir fest, dass die Zustandslosigkeit, die wir mit der Speichersparmethode eingeführt haben, einige Vorteile bringt So erieichtert sie den Entwurf von komplizierteren Ausführungsmodellen, wie hierarchische Enweiterungen oder die Anbindung an Grid-Bibliotheken. Durch die häufig auftretenden Probleme bei der Codegenerierung hinsichtlich der Größe und Komplexität des Zielcodes, sowie der Laufzeit der Generierung, gab es eine intensive und stetige Zusammenarbeit mit den Entwicklergruppen rund um die verwendeten Bibliotheken. So wurden aufgrund unserer Anregungen einige Optimierungen und Erweiterungen in diesen Bibliotheken erreicht. Insbesondere arbeiteten wir eng mit der Entwicklergruppe um die Bibliotheken CLooG und Barvinok zusammen, was zur Ausbesserung einiger Fehler und Hinzufügung neuer Features (z.B. für Codegenerierung) führte. Dabei hat es sich mehrfach bewährt, einen allgemeinen Ansatz zu wählen, der eine elegante mathematische Beschreibung erlaubt, auch wenn er zunächst zu Problemen bei der Codegenerierung führt. Durch Betrachtung geeigneter Beispiele ist es dann oft möglich, mit Spezialisierungen und Optimierungen für eine ganze Klasse von Beispielen doch zu praktikablen Resultaten zu gelangen. So lässt sich z.B. die Speichersparmethode in der Klasse der Programme mit ausschließlich uniformen Abhängigkeiten effizient umsetzen. Nicht alle Komplexitätsprobleme können jedoch durch Spezialisierung beseitigt werden. Ein Grund für die verbleibenden Probleme bei der Codegenerierung sind die zur Übersetzungszeit noch unbekannten Parameter (z. B. die Problemgröße und die aktuelle Taskzahl). Die Berechnungen zur Übersetzungszeit müssen in Abhängigkeit von diesen Parametern durchgeführt werden. Ein weiterer Ansatz zur Reduzierung der Komplexität ist, die Codegenerierung zur Laufzeit durchzuführen. Da Parameter (z.B. die Problemgröße oder die Taskzahl) zur Laufzeit bekannt sind, wird die Codegenerierung deutlich vereinfacht. Einige unserer Experimente deuten darauf hin, dass die benötigte Zeit für die Codegenerierung so gering ist, dass sie die Gesamtlaufzeit des Programms nicht wesentlich verlängert; andererseits ist der erzeugte Code auch kleiner (und daher schneller) als der statisch erzeugte, parametrisierte Code. Wir wollen uns daher in Zukunft der Untersuchung von dynamischen Optimierungen im Polyedermodell widmen. Entgegen ursprünglichen Erwartungen zum Projektstart hat sich kein kommerzieller Markt von Grid-Umgebungen ergeben, die z.B. auf Globus basiert sind. Nach unserer Erfahrung werden praktisch alle verfügbaren Grid-Systeme von Zweckverbänden bereitgestellt. In ihrem Betrieb gibt es kaum Gemeinsamkeiten und es ist auch kein allgemeiner Standard von Grid-Umgebungen auszumachen. Globus hatte eigentlich diesen Anspruch erhoben. Durch Verwendung von Bibliotheken wie IPL und JavaGAT ist es jedoch möglich, von den Unterschieden dieser Grid-Umgebungen zu abstrahieren.
Publications
-
Automatic code generation for distributed memory architectures in the polytope model. In: 11th Int. Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS) in 20th IEEE Int Symp. on Parallel and Distributed Processing (IPDPS), April 2006
Michael Claßen and Martin Griebl
-
Loop parallelization for a GRID master-worker framework. In: Proc. CoreGRID Workshop on Grid Programming Model, number TR-0080 in CoreGRID Technical Reports, pages 516- 527, June 2007
Eduardo Argollo, Michael Claßen, Philipp Claßen, and Martin Griebl
-
Adapting loop parallelization to the Grid. In: Proceedings of the Programming Model Institute Technical Meeting 2008, number TR-0138 In CoreGRID Technical Reports, pages 4-10, 2008
Michael Claßen, Philipp Claßen, Christian Lengauer, Jan Dünnweber, and Sergei Gorlatch
-
Extending loop parallelization for the Grid lo largely decentralized communication. In: Sergei Gorlatch, Paraskevi Fragopoulou, and Thierry Priol, editors. Integrated Research in Grid Computing, Core-GRID Integration Workshop, pages 287-298. Crete University Press, 2008
Michael Claßen, Philipp Claßen, and Christian Lengauer
-
LooPo-HOC: A Grid component with embedded loop parallelization. In: Sergei Gorlatch, Paraskevi Fragopoulou, and Thierry Priol, editors. Grid Computing: Achievements and Prospects, pages 261-274. Springer-Verlag, 2008
Johannes Tomasoni, Jan Dünnweber, Sergei Gorlatch, Michael Claßen, Philipp Claßen, and Christian Lengauer
