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

Efficient Task-Based Execution of Irregular Applications with Adaptive Load Balancing

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 ApplikZur 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.show moreshow less
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 tasThis 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.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Institutes:Informatik
Author: Ralf Hoffmann
Advisor:Prof. Dr. Thomas Rauber
Granting Institution:Universität Bayreuth,Fakultät für Mathematik, Physik und Informatik
Date of final exam:04.05.2009
Year of Completion:2009
SWD-Keyword:Dynamische Lastteilung; Gemeinsamer Speicher; Parallelverarbeitung; Task; Thread
Tag:Adaptive Lastbalancierung; Feingranulare Taskverarbeitung
adaptive; dynamic; fine-grained tasks; load balancing
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
URN:urn:nbn:de:bvb:703-opus-5579
Document Type:Doctoral Thesis
Language:German
Date of Publication (online):20.05.2009