Parallel Computing; Adaptive Load-Balancing; Shared Memory Systems
en
Abstract:
Eine oft genutzte Technik für die Programmierung nebenläufiger Programme ist die Aufteilung der Arbeit in kleine Tasks, welche parallel ausgeführt werden können. Die Verteilung der Tasks zwischen den Threads ist nicht trivial, ein dafür oft genutzter Ansatz ist Work-Stealing. Beim Work-Stealing Algorithmus ist die Anzahl der Worker-Threads während der Ausführung der Tasks fixiert. In Situationen, wo nicht genug Tasks vorhanden sind um alle verfügbaren Prozessoren auszunutzen, verschwenden nicht genutzte Worker Prozessorressourcen und können die Ausführungszeit der Anwendung vergrößern. Ein Ansatz dieses Problem zu lösen ist adaptives Work-Stealing. Dieser Algorithmus passt die Anzahl der Threads, die für die Ausführung der Tasks genutzt werden, zur Laufzeit dynamisch an. Es wird versucht die Anzahl der Worker-Threads, die genutzt werden können, abzuschätzen. Darauf basierend können Threads, die nicht benötigt werden, in einen Schlafzustand versetzt. Existierende Ansätze zu adaptivem Work-Stealing teilen die Ausführung der Anwendung meist in so genannte Quanten auf. Zwischen 2 Quanten wird überprüft wieviel Zeit die Threads für das Stehlen von Tasks verwendet haben und wieviel für die Ausführung von Tasks. Anhand dieser Klassifikation werden Threads zur Anwendung hinzugefügt oder entfernt. Eine einfache Technik, um Worker-Threads, die gerade nicht genutzt werden, zu pausieren, ist der Einsatz von sogenannten Backoffs. In dieser Arbeit wird untersucht, inwiefern sich Backoffs auch in Work-Stealing Schedulern verwenden lassen. Daneben wird ein neuer adaptiver Work-Stealing Algorithmus entwickelt. Der Algorithmus verwendet ebenso das Konzept der Quanten, unterbricht Worker aber niemals, wenn sie selbst noch genug Tasks zum Ausführen haben. Deshalb verursacht dieser Ansatz nur einen sehr kleinen Mehraufwand, solange genug Arbeit vorhanden ist. Kleine Benchmarks werden genutzt, um die Performance der neuen Algorithmen zu testen und mit anderen Techniken zu vergleichen.
de
This thesis provides an in-depth discussion of improving the widely used work-stealing algorithm in situations where not all cores can be utilized. In the standard work-stealing algorithm, the number of active workers is kept fixed during the execution of the tasks. When there are not enough tasks available to utilize all available processors, the unneeded workers waste processor resources and could slow down the whole application. An approach to solve this problem is adaptive work-stealing. Adaptive work-stealing schedulers dynamically adjust the number of threads that are used to execute the tasks of an application. Such schedulers try to estimate the number of workers that can be utilized. Most of these schedulers split the execution of the application in so called quanta. Between two quanta it is checked how much time the workers spent stealing and how much time was spent working. Based on this classification workers are added or removed to process tasks in the next quantum. A simple possibility to block workers that are currently under-utilized is the usage of so called backoffs. This work analyzes the usage of backoffs in work-stealing schedulers. We implemented and tested several different types of backoffs in the context of this work. As a second main part, a new adaptive work-stealing algorithm is designed and implemented. It also uses the concept of quanta, but does not interrupt workers as long as they do not need to steal tasks. Therefore the approach has only a small overhead as long as there is enough work to process. Small benchmarks are used to test the performance of our new algorithms and to compare it with other techniques.
