Eine generische Schedulingkomponente für Multiprozessortask-Programmierung
Final Report Abstract
Schedulingkomponente SEParAT: Das im Projekt entwickelte Softwarewerkzeug SEParAT (Scheduling Support Environment for Parallel Application Jask Graphs) stellt eine einheitliche Schnittstelle für Schedulingalgorithmen homogener und heterogener Zielplattformen zur Verfügung. Das Werkzeug kann über die Kommandozeile und eine integrierte grafische Benutzeroberfläche (GUI) gesteuert werden. Die GUI unterstützt den Anwender bei der Entwicklung von Schedulingalgorithmen, indem sie die während des Schedulingprozesses erzeugten Zwischenergebnisse visualisiert und den Leistungsvergleich von Schedulingalgorithmen anhand vorgegebener Metriken ermöglicht. In SEParAT wurden 18 Schedulingalgorithmen für homogene und 6 Algorithmen für heterogene Plattformen implementiert. Die einzelnen Algorithmenschritte sind als wiederverwendbare Codefragmente realisiert, die sich durch die GUI zu neuen Schedulingalgorithmen rekombinieren lassen. Zusätzlich sind verschiedene Optimierungen für den Schedulingprozess zuschaltbar. Mit Hilfe von SEParAT wurden die implementierten Algorithmen detailliert untersucht und es wurden Richtlinien erarbeitet, welcher Algorithmus in welcher Situation zu bevorzugen ist. Optimierung des schichtenbasierten Schedulings: Ein Ansatz für das Scheduling von M-Tasks mit Abhängigkeiten sind schichtenbasierte Algorithmen, die zunächst Schichten unabhängiger M-Tasks erzeugen und anschließend für jede Schicht getrennt einen Schedule bestimmen. Im Rahmen des Projekts wurde der Optimierungsalgorithmus Move-Blocks entwickelt, der die Schedules der einzelnen Schichten zusammensetzt und dabei eine geringe Überlappung erlaubt. Dadurch wird die ungenutzte Prozessorzeit verringert, was zu einer deutlichen Reduktion der Anwendungslaufzeiten bei nur geringfügig höherer Schedulingzeit führte. Die besondere Herausforderung war die korrektheitserhaltende Optimierung der M-Task-Schedules hinsichtlich der Daten- und Kontrollabhängigkeiten. Zur Unterstützung heterogener Cluster-of-Clusters-Zielplattformen wurden schichtenbasierte Schedulingalgorithmen um eine zusätzliche Phase erweitert, die für die Zuordnung der M-Tasks einer Schicht zu den einzelnen Teilclustern der Plattform verantwortlich ist. Experimente mit verschiedenen Anwendungen und synthetischen Schedulingproblemen haben gezeigt, dass dieser Ansatz in vielen Fällen bessere Schedules als bereits vorhandene Schedulingalgorithmen liefert. Semi-dynamisches Scheduling für heterogene Plattformen: Semi-dynamisches Scheduling, also die Kombination von statischem Scheduling und dynamischer Lastbalancierung, hat sich für heterogene Plattformen vor allem dann als sinnvoll herausgestellt, wenn keine exakten Laufzeitvorhersagen existieren. Die erfolgreiche Anwendung des semi-dynamischen Schedulings wurde für die Ausführung verschiedener Löser für Systeme gewöhnlicher Differentialgleichungen auf einem heterogenen Cluster demonstriert. Die dynamische Verteilung von Rechenlast wurde auch für eine Anwendung aus dem Bereich der Finite-Elemente-Methoden untersucht. Die heterogene Zielplattform war eine Multicore-Plattform mit einem zusätzlichen Grafikprozessor (GPU). Es wurde gezeigt, dass durch eine dynamische Zuweisung der Berechnungen an die verfügbaren Ausführungseinheiten (CPUs und GPU) die Anwendungslaufzeit deutlich verringert werden kann.
Publications
- A Compar/son of Scheduling Algorithms for Multiprocessor-tasks with Precedence Constraints. In: Proc. of 2007 High Performance Computing & Simulation Conf (HPCS2007), Seiten 663-669. ECMS, 2007
Dümmler, J., R. Kunis und G. Rünger
- A Scheduling Toolkit for Multiprocessor-Task Programming with Dependencies. In: Proc. of 13th Int. Euro-Par Conf, Band 4641 der Reihe LNCS, Seiten 23-32. Springer, 2007
Dümmler, J., R. Kunis und G. Rünger
- Layer-Based Scheduling Algorithms for Multiprocessor-Tasks with Precedence Constraints. In: Parallel Computing: Architectures, Algorithms ond Applications: Proc. of Int. Conf. ParCo 2007, Band 15 der Reihe Advances in Parallel Computing, Seiten 321-328. lOS Press, 2007
Dümmler, J., R. Kunis und G. Rünger
- Optimization of Layer-based Scheduling Algorithms far Mixed Parallel Applications with Precedence Constraints Using Move-blocks. In: Proc. of 17th Euramicro Int. Conf. on Parallel, Distr. and Network-Based Processing (PDP2009), Seiten 70-77. IEEE Comp. Society, 2009
Kunis, R. und G. Rünger
- Task-Block Identification and Movement for Layer-based Scheduling Algorithms. In: Smari, W. (Herausgeber): Proc. of 2010 Int. Conf on High Performance Computing & Simulation Conf (HPCS20W), Seiten 132 -139. IEEE, 2010
Kunis, R. und G. Rünger
- Optimizing Layer-based Scheduling Algorithms for Parallel Tasks with Dependencies. Concurrency and Computation: Practice and Experience, 23(8):827-849,2011
Kunis, R. und G. Rünger
- SEParAT: Scheduling Support Environment for Parallel Application Task Graphs. Cluster Computing, 15(3):223-238,2012
Dümmler, J., R. Kunis und G. Rünger
(See online at https://doi.org/10.1007/s10586-012-0211-1) - Programming Support and Scheduling for Communicating Parallel Tasks. Journal of Parallel and Distributed Computing, 73(2):220-234,2013
Dümmler, J.,T. Rauber und G. Rünger
