[Back]

L. Haselsteiner:
"Adaptive Work-Stealing Techniques";
Supervisor: J. Träff, M. Wimmer; Institut für Informationssysteme, Parallel Computing Group, 2015; final examination: 2015-06-03.

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. However, the parallelism of an application is seldom stable but often changes over the application´s lifetime. This may decrease performance or waste resources, especially when multiple applications are running in parallel. 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 a backoff. Backoffs are often used in computer networks to throttle senders when there exists a collision, because two or more computers try to send data at the same time. 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. We found out that it is crucial to select good parameter values for the backoffs, since some of them significantly influence the overall performance. The results are quite promising and our optimized backoffs improved the performance in our
benchmarks notably. It was also interesting to see that in the end all different types of backoffs provide similar performance.
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. We named our algorithm "dynamic quanta algorithm" and tested the performance of the adaptive scheduler. Our algorithm performed better than the existing work-stealing scheduler, we compared our algorithms with. However, one surprising result is that in our benchmarks using an optimized backoff is at least as good.