A light-weight parallel execution layer for shared-memory stream processing

Abstract

In den letzten Jahren haben sich zunehmend Mehrkernprozessoren im Bereich der Universalrechner etabliert. Um die Vorteile der zunehmend ansteigenden Anzahl von Rechenkernen nutzen zu können, sind Programmierparadigmen notwendig, welche die Ableitung von Nebenläufigkeiten erleichtern bzw. erst ermöglichen.<br />S-Net ist eine deklarative Koordinationssprache, deren Ziel es ist, die Programmierung von Nebenläufigkeit und die Programmierung von Programmlogik zu trennen. Es wird die Koordination von Netzen bestehend aus asynchronen, zustandslosen Komponenten, sogenannten "Boxen", die mittels typisierter Datenströme verbunden sind, definiert. Boxen werden in einer konventionellen Programmiersprache geschrieben und haben einen einzigen Eingangs- und einen einzigen Ausgangsdatenstrom. Netzwerke werden in SNet durch algebraische Formeln ausgedrückt, bestehend aus vier Kombinatoren, nämlich serieller und paralleler Komposition, sowie serieller und paralleler Replikation.<br />Das Ziel dieser Arbeit ist es, das bestehende Laufzeitsystem dahingehend zu erweitern, dass es zwei Anforderungen genügt. Erstens soll es ermöglicht werden, Informationen über die Ausführungszeiten der Laufzeitkomponenten oder die Auslastung der Kommunikationskanäle zu sammeln. Zweitens soll es die Möglichkeit zur Kontrolle des Schedulings der Komponenten geben.<br />Durch Recherche von bestehenden Systemen, welche auf Datenstromverarbeitung basieren, und insbesondere deren Laufzeitsystemen, wurden Konzepte für eine neue Ausführungsschicht erarbeitet. Ein Light-weight Parallel Execution Layer (LPEL), d.h. eine leichtgewichtige parallele Ausführungsschicht, wurde entwickelt, welche Komponenten, die mittels gerichteter und gepufferter Datenströme kommunizieren, auf User-Ebene verwaltet, wobei besonderes Augenmerk auf die Anforderungen des S-Net Modells gelegt werden musste.<br />Mechanismen, die dem Stand der Technik entsprechen, z.B. nebenläufige Datenstrukturen und Lock-free Algorithmen, wurden bei der Umsetzung verwendet.<br />Um die Konzepttauglichkeit nachzuweisen, wurde die Ausführungsschicht als Programmbibliothek in der Programmiersprache C entwickelt, und das bestehende S-Net Laufzeitsystem darauf portiert. Experimente mit der neuen Schicht zeigen eine effiziente Ressourcennutzung selbst bei vielen zu verwaltenden Komponenten. Die zur Laufzeit gewonnene Information kann erfolgreich verwendet werden, um den erforderlichen Rechenaufwand der Komponenten zu ermitteln, sowie um anwendungsspezifische Scheduling- und Platzierungsstrategien abzuleiten.<br />

In recent years, multicore technology became prevalent in the area of general-purpose computing. In order to facilitate the benefits of the steadily increasing number of cores, programming paradigms are necessary that support or even enable the derivation of concurrency. S-Net is a declarative coordination language which aims to separate the concerns of computation and organisation of concurrent execution by defining the coordination behaviour of networks of asynchronous, stateless components (called "boxes") and their orderly interconnection via typed streams. Boxes are written in any conventional language, connected to the streaming network with a single input and a single output stream. Streaming networks are expressed in S-Net itself as algebraic formulae built out of four network combinators, namely serial and parallel composition, and serial and parallel replication.<br />The aim of this thesis is to extend the multi-threaded S-Net runtime system to fulfil two requirements. First, to enable the collection of monitoring information such as execution time of components, or buffer usage along communication paths. Second, to provide a way to control scheduling of components.<br />By analysing existing stream-processing frameworks with respect to their runtime system implementations, concepts for a new execution layer were devised. A Light-weight Parallel Execution Layer (LPEL) has been developed, which manages tasks communicating via unidirectional single-producer single-consumer buffered streams in user-space, with special focus on the requirements imposed by the S-Net model. State-of-the-art techniques, like concurrent data structures and lock-free algorithms, have been employed.<br />As a proof of concept, the layer is implemented as a separate library in the C programming language, and S-Net is ported onto it. Experiments with the new layer show efficient resource utilisation when having to handle many components. The profiling information can be used to calculate computational costs of components as well as to derive application-specific scheduling and placement strategies.