Effiziente taskbasierte Programmausführung irregulärer Applikationen mit adaptiver Lastbalancierung

Titelangaben

Hoffmann, Ralf:
Effiziente taskbasierte Programmausführung irregulärer Applikationen mit adaptiver Lastbalancierung.
Bayreuth , 2009
( Dissertation, 2009 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

Zur parallelen Ausführung irregulärer Applikationen auf Parallelrechnern mit gemeinsamem Speicher eignet sich ein taskbasierter Ansatz, da durch eine dynamische Lastverteilung einzelner Tasks geeignet auf die irreguläre Abarbeitungsstruktur der Applikation reagiert werden kann. In dieser Arbeit wird das KOALA-Framework zur Abarbeitung feingranularer Tasks paralleler Programme vorgestellt. Es wird ein adaptiver Taskpool beschrieben, der effizient auf wechselnde Lastzustände innerhalb einer Applikation reagieren kann. Durch adaptiv angepasste Taskblöcke kann der adaptive Taskpool auch bei einer sehr großen Anzahl von ausführungsbereiten Tasks mit nur wenigen Operationen Taskumverteilungen durchführen, um die Berechnungen möglichst gleichmäßig auf die Prozessoren zu verteilen. Verschiedene irreguläre Applikationen werden getestet, um die unterschiedlichen Taskpool-Implementierungen zu vergleichen. Dabei erzielen die adaptiven Taskpools im Gegensatz zu konventionellen Taskpools bei allen untersuchten Applikationen gute Ergebnisse. Die einzelnen funktionalen Bestandteile des KOALA-Frameworks können ohne Änderungen in der Applikation ausgetauscht werden. Eine spezielle Implementierung der Lock-Komponente erlaubt so die Nutzung von Hardware-Operationen zur effizienten Synchronisation der beteiligten Threads. Weiterhin wird eine Profiling-Komponente vorgestellt, mit der die Taskstruktur einer Applikation analysiert werden kann. An einem Fallbeispiel werden Engstellen in einer Applikation identifiziert, durch deren Behebung eine erhebliche Verbesserung der Laufzeit erreicht werden konnte.

Abstract in weiterer Sprache

This thesis considers the execution of irregular applications on shared-memory machines with many processor cores. A task-based approach with dynamic load balancing can be used to handle the irregular execution scheme of such applications. The KOALA framework presented in this thesis is used to execute fine-grained tasks of arbitrary task-based applications. An adaptive task pool is developed which is able to handle a large amount of tasks efficiently. By using dynamically adjusted blocks of tasks the adaptive task pool is able to balance the work between processors almost independently from the actual number of tasks involved. The task pool implementations are compared using several irregular applications. In contrast to conventional task pool implementations, the adaptive task pools have shown good performance for all applications. The KOALA framework is divided into several components to enable the use of different implementations. A specific implementation of the lock component uses hardware operations for efficient synchronization. Additionally, a profiling component is presented which can be used to analyze the task structure of a given application. Bottlenecks of task-based applications are identified in a case study. After improving the performance critical parts of the application, a significant runtime improvement could be achieved.