Embracing Explicit Communication in Work-Stealing Runtime Systems

Titelangaben

Prell, Andreas:
Embracing Explicit Communication in Work-Stealing Runtime Systems.
Bayreuth , 2016 . - XIX, 176 S.
( Dissertation, 2016 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Angaben zu Projekten

Abstract

Parallel computers are commonplace. The trend of increasing the number of processor cores highlights the importance of parallel computing: a single-threaded program uses a fraction of a modern processor's resources and potential, and that fraction will only decrease over the coming processor generations.

Existing abstractions for writing parallel programs, such as threads and mutual exclusion locks, are difficult to understand, use, and reason about, making them a poor choice for mainstream parallel programming. Higher-level abstractions aim to achieve a more favorable division of labor between programmers and compilers/runtime systems, with programmers expressing and exposing parallelism and compilers/runtime systems managing parallel execution.

A popular and effective abstraction is that of a task, a piece of work, usually a function or a closure, that is safe to execute in parallel with other tasks. Scheduling decisions, including the mapping of tasks to threads, are made by the runtime system and are not imposed on the programmer.

Tasks are well-suited to express fine-grained parallelism, but whether fine-grained parallelism brings performance gains depends on the runtime system and its implementation. State-of-the-art runtime systems employ the scheduling and load balancing technique of work stealing, which is known to be efficient, both in theory and practice. In work stealing, idle workers, called thieves, request tasks from busy workers, called victims, thereby balancing the load. Most implementations of work stealing take advantage of shared memory by letting thieves "steal" tasks from the double-ended queues (deques) of their victims.

Modern multiprocessors feature increasingly complex architectures that make it challenging to implement efficient yet flexible work-stealing schedulers. Future manycore processors may have limited support for shared memory, or may rely on message passing for scalable inter-core communication, such as Intel's SCC research processor, a recent example of a "cluster-on-a-chip".

This thesis aims to put work stealing based on message passing on a better, more practical foundation, developing techniques to rival the performance of concurrent deque-based implementations, while remaining more flexible. Work stealing based on message passing has been studied before, notably in the context of distributed systems, where MPI still dominates. We present a work-stealing scheduler in which workers communicate with each other through channels, a lightweight message passing abstraction that goes back to Hoare's Communicating Sequential Processes (CSP). Channels feature prominently in modern programming languages such as Go and Rust, which advocate messages to communicate, synchronize, and share state between threads. The advantage of using channels, as opposed to using low-level synchronization primitives, is that channels decouple the scheduler from processor-specific features, thereby increasing its flexibility. Large parts of this thesis are dedicated to making channel-based work stealing perform well on modern shared-memory multiprocessors.

We describe an implementation in which workers exchange asynchronous steal requests and tasks by passing messages over channels. Termination is detected as a consequence of forwarding steal requests instead of requiring additional control messages to be passed between workers. Dependencies between tasks, most importantly, between parent and child tasks, are expressed with futures, which can be implemented efficiently in terms of channels.

Private task queues are more flexible than concurrent ones. We show a simple extension that provides support for adaptive stealing---the ability to switch the stealing strategy at runtime. Fine-grained parallelism requires not only efficient work stealing, but also granularity control to overcome the overhead of task creation and scheduling. Similar tasks, such as iterations of a parallel loop, can be combined into a single task ready to split whenever parallelism is needed. We extend previous work on lazy splitting, integrate it with channel-based work stealing, and demonstrate performance comparable to dedicated loop schedulers in OpenMP. Finally, we provide experimental evidence that channel-based work stealing performs on par with runtime systems based on concurrent deques.

Abstract in weiterer Sprache

Parallelrechner auf Basis von Mehrkernprozessoren sind heutzutage allgegenwärtig. Da anzunehmen ist, dass die Anzahl der Prozessorkerne, die auf einem Chip Platz finden, weiter steigen wird, besteht Handlungsbedarf. Ohne Parallelverarbeitung bleibt das Potenzial eines modernen Rechners zunehmend ungenutzt. Aus diesem Grund gewinnen Techniken der parallelen Programmierung mehr und mehr an Relevanz.

Die klassische Thread-Programmierung gilt als zu diffizil, um ein geeignetes Programmiermodell zu bieten, das auch von Nicht-Experten effektiv eingesetzt werden kann. Eine vielversprechende Alternative ist die Benutzung von Tasks anstelle von Threads. Ein Task bezeichnet eine beliebige Berechnung innerhalb eines Programms, die unabhängig von anderen Berechnungen und damit parallel ausgeführt werden kann. Der Programmierer hat die Aufgabe, Tasks zu spezifizieren, während das Laufzeitsystem für deren Ausführung sorgt. Dabei übernimmt das Laufzeitsystem viele kritische Funktionen einschließlich der Verwaltung von Threads, der Zuweisung von Tasks an Threads und der Lastverteilung.

Tasks sind leichtgewichtiger als Threads und somit einfach zu erzeugen, selbst für relativ feingranulare Aufgaben. Task-parallele Programme generieren in der Regel eine Vielzahl von Tasks, mit dem Ziel, diese möglichst gleichmäßig an die ausführenden Worker Threads zu verteilen. Wie feingranular die Tasks dabei sein dürfen, hängt von der Effizienz des Laufzeitsystems ab.

Von besonderer Bedeutung ist das Work Stealing, eine Scheduling-Technik, bei der Worker Threads, die keine Tasks mehr haben, anderen Worker Threads durch Stehlen Arbeit abnehmen, wodurch eine dynamische Lastverteilung erzielt wird. Üblicherweise besitzt jeder Worker Thread eine eigene Queue-Datenstruktur (Deque), in die Tasks abgelegt und zur Ausführung entnommen werden, und die von anderen Worker Threads zugegriffen werden kann, um Stehlen zu ermöglichen. Solche Implementierungen sind oft aus Effizienzgründen auf eine bestimmte Hardware-Architektur zugeschnitten. Da die Zukunft Cluster-ähnlichen Vielkernprozessoren gehören dürfte, ist davon auszugehen, dass Work Stealing Scheduler an diesen Umstand angepasst werden müssen. Eine zu starke Plattformabhängigkeit, was zum Beispiel das Vorhandensein bestimmter Synchronisationsoperationen betrifft, kann auf lange Sicht eine Portierung erschweren.

Die vorliegende Arbeit verfolgt das Ziel, eine effiziente und gleichzeitig flexible Alternative zum klassischen Work Stealing im gemeinsamen Adressraum zu entwickeln. Zu diesem Zweck wird ein Laufzeitsystem entworfen, in dem Worker Threads ausschließlich über Channels miteinander kommunizieren. Direktes Stehlen ist nicht mehr möglich: Worker Threads senden Steal Requests, die mit Tasks beantwortet oder abgelehnt werden.

Channels bieten ein einfaches Interface für den Nachrichtenaustausch zwischen Threads, das von der Hardware-Architektur abstrahiert und effizient implementiert werden kann. Gepufferte Channels ermöglichen asynchrone Kommunikation, so dass Worker Threads in der Lage sind, Steal Requests untereinander auszutauschen, ohne Antworten abwarten zu müssen. Das Senden eines Steal Requests ist dadurch vergleichbar mit einem asynchronen Aufruf, der eventuell einen Task über einen separaten Channel zurückliefert. Die Terminierung einer task-parallelen Berechnung kann aus Steal Requests abgeleitet werden und erfordert kein verteiltes Protokoll mit zusätzlichem Nachrichtenaustausch. Taskabhängigkeiten, zum Beispiel zwischen Eltern- und Kindtasks, werden durch Futures ausgedrückt, welche eng mit Channels korrespondieren.

Worker Threads verwalten Tasks in privaten Deques. Dies vereinfacht die Realisierung flexibler Strategien wie zum Beispiel adaptives Stehlen, bei dem jeder Worker Thread selbst entscheidet, wieviele Tasks gestohlen werden sollen.

Im Mittelpunkt der Arbeit steht die effiziente Ausführung feingranularer Tasks. Um den Overhead der Taskverwaltung zu reduzieren, ist es möglich, ähnliche Tasks, insbesondere Iterationen paralleler Schleifen, so zusammenzufassen, dass weitere Tasks nur nach Bedarf erzeugt werden. Überschüssige Tasks werden automatisch sequentialisiert und verursachen keinen Overhead. Das vorgestellte Laufzeitsystem implementiert und erweitert das sogenannte Lazy Splitting, welches ermöglicht, parallele Schleifen ähnlich effizient auszuführen wie mit OpenMP, ohne auf die Unterstützung eines Loop Schedulers angewiesen zu sein.

Mithilfe der entwickelten Techniken lässt sich trotz expliziter Kommunikation gute Performance erzielen. Bei einem Vergleich auf drei unterschiedlichen Systemen landet das vorgestellte Laufzeitsystem vor Cilk Plus und Intel OpenMP und nur knapp hinter einer Variante mit Chase-Lev Deques.