Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

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

Title data

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

Official URL: Volltext

Abstract in another language

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 another language

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.

Further data

Item Type: Doctoral thesis
Keywords: Parallelverarbeitung; Dynamische Lastteilung; Gemeinsamer Speicher; Task; Thread; Adaptive Lastbalancierung; Feingranulare Taskverarbeitung; load balancing; dynamic; adaptive; fine-grained tasks
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
Date Deposited: 01 May 2015 10:59
Last Modified: 01 May 2015 10:59
URI: https://eref.uni-bayreuth.de/id/eprint/12388