Variations on task scheduling for shared memory systems

Abstract

Diese Arbeit beschäftigt sich mit dem Problem des Task-Scheduling, der Ablaufplanung für parallel ausführbare Aufgaben, auf parallelen Systemen mit gemeinsamen Speicher. Für den Aufbau der Arbeit wurde ein vertikaler Ansatz gewählt, bei dem das Thema auf allen Ebenen diskutiert wird. Begonnen wird auf der Ebene der Programmiermodelle mit einer Beschreibung existierender Modelle, sowie von Entwurfsmustern für task-parallele Programme. Diese Modelle und Entwurfsmuster werden in Folge erweitert. Eine dieser Erweiterungen baut auf sogenannten Strategien auf, einem Konstrukt das eine engere Interaktion zwischen task-parallelen Programmen und dem Task-Scheduler ermöglicht. Der Einsatz von Strategien zielt darauf ab, die Brücke zwischen generischen Task-Schedulern und spezialisierten, auf eine bestimmte Applikation optimierten Task-Schedulern zu schließen. Task-parallele Programmiermodelle bedingen den Einsatz von Task-Schedulern die sowohl theoretisch als auch praktisch effizient sind. Diese Effizienz wurde für Work-Stealing, einen weit verbreiteten Ansatz zum Task-Scheduling, bewiesen, doch viele der in dieser Arbeit gezeigten Erweiterungen des task-parallelen Programmiermodells benötigen Task-Scheduler die über Work-Stealing hinausgehen. Das Primärziel hierbei ist die Ausführungszeit und den Speicherverbrauch einer task-parallelen Applikation zu beschränken, und dabei die Kommunikation zwischen Prozessoren klein zu halten. In einem weiteren Teil dieser Arbeit werden Ansätze zur Synchronisation, sowie Datenstrukturen die parallele Zugriffe erlauben, diskutiert. Diese sind für die Implementierung von effizienten Task-Schedulern notwendig, sowie als Unterstützung der in dieser Arbeit diskutierten Entwurfsmuster. Der Fokus dieser Arbeit liegt auf Ansätzen die Fortschrittsgarantien für Synchronisation geben können. Die meisten der vorgestellten Synchronisationsalgorithmen und Datenstrukturen sind lock-free, was den Fortschritt zumindest eines Synchronisationsteilnehmers in einer beschränkten Anzahl an Schritten garantiert. Manche der vorgestellten Algorithmen sind auch wait-free, und garantieren somit den Fortschritt für alle Teilnehmer. Die vorgestellten Algorithmen und Techniken wurden genutzt, um eine Programmierbibliothek namens Pheet zu implementieren. Pheet wurde ursprünglich als Plattform entwickelt, die es erlaubt, schnell neue Task-Scheduler und Synchronisationsalgorithmen zu entwickeln und mit anderen zu vergleichen. Um dies zu ermöglichen, setzt Pheet auf einer Plug-In-Architektur auf, die auf C++ Template-Metaprogrammierung basiert. Durch diese Architektur ist es möglich, einen großen Teil der Komponenten von Pheet auszutauschen, ohne die restliche Konfiguration zu verändern. Dies ermöglicht den direkten Vergleich mehrerer Implementierungen einer Komponente. Um diesen Vergleich zu vereinfachen, enthält Pheet eine Reihe von kleinen Benchmark-Applikationen über die verschiedene Implementierungen verglichen werden können. Pheet war ursprünglich als Forschungs- und Unterrichtswerkzeug gedacht, ist aber in Zwischenzeit zu einer vollwertigen Programmierbibliothek zur Entwicklung von task-parallelen Applikationen angewachsen und ist als Quelloffene Software öffentlich verfügbar.

This thesis provides an in-depth discussion of task scheduling for shared memory systems. The topic is approached in a vertical manner, starting with high-level programming model aspects, and moving down to low-level implementation details. On the programming model level existing task-parallel programming models are discussed, as well as programming patterns that can be used on top of task parallel models. This is supplemented by extensions to these models and patterns developed in the context of this work. One such extension is strategy scheduling, which allows for tighter interaction between a task-parallel program and the scheduling system. Strategy scheduling is intended to bridge the gap between specialized scheduling systems, optimized for specific applications, and generic task schedulers. Theoretically and practically efficient run-time systems are required to support task scheduling. While work-stealing has been proven to be an efficient approach for general task scheduling, more complex techniques are required to support the presented extensions to the task parallel model. The main goal here is to provide good load balancing, while at the same time reducing communication to increase the scalability of applications. Another concern in task scheduling is memory usage. For a large class of task parallel applications efficient greedy schedules exist that will only use the same space per processor as a space-efficient execution on one processor. Both the run-time system and programming patterns require supporting concurrent data structures. Such data structures have been developed in the context of this work and are discussed in detail. To enable good scalability, the concurrent data structures in this work all provide strong progress guarantees. Most are lock-free, which guarantees that at least one participant will progress in a bounded number of steps. Some data structures presented in this work are wait-free, guaranteeing progress for all participants. The techniques presented in this work have been used to create a task scheduling framework called Pheet. Pheet was originally designed as a vehicle for evaluation of new scheduling techniques, and therefore has a highly flexible plug-in architecture based on C++ template meta-programming. This allows to replace any single component in the task scheduling system, while keeping the rest of a configuration the same, in order to enable direct (performance) comparison between different implementations of a specific component. Pheet is accompanied by the Pheet benchmark suite containing a variety of task parallel micro benchmarks. The Pheet benchmark suite is used to evaluate the performance of Pheet components. While Pheet was originally developed as a tool for research and teaching on task parallel programming, it has developed into a fully fledged scheduling framework, which has been released as open source software.