Erweiterung des Pheet Frameworks für Pipeline-Parallele Anwendungen

Abstract

In dieser Arbeit wurde eine Implementierung des parallelen Pipeline Patterns für das Task-parallele Pheet framework erstellt. Das Pipeline Pattern kann in vielen Situationen in der Praxis angewandt werden. Es teilt Eingabedaten in unabhängige Teile (chunks), die durch eine Serie von Verarbeitungsschritten gehen. Diese Verarbeitungsschritte werden üblicherweise als stages bezeichnet. Manche dieser Schritte können parallel ausgeführt werden, während in anderen Schritten manche Teile auf vorangegangene Teile warten müssen. Für die Entwicklung einer Pipeline Implementierung ist die Kenntnis von anderen existierenden Implementierungen notwendig. In dieser Arbeit wurden dafür die weitverbreitetsten Implementierungen analysiert. Für jede dieser Implementierungen wird eine technische Beschreibung und eine Analyse der Einschränkungen geliefert. Unsere Implementierung ist nicht-blockierend (lock-free) and verwendet keine zentralisierten Datenstrukturen, um die Skalierbarkeit in Mehr-CPU-Systemen zu gewährleisten. Wir verwenden C++ atomics für die Synchronisierung in unserer Implementierung. Um unsere Implementierung zu testen, wurden Benchmarks auf mehreren Systemen ausgeführt. Alle Benchmarks sind bekannte Probleme die sich gut auf eine Pipeline-Schnittstelle adaptieren lassen. Für jeden Benchmark wurde eine Referenz-Implementierung verwendet,um Eigenschaften der Benchmarks herauszufinden. Ein von uns erstellter synthetischer Benchmark misst den Mehraufwand für die Synchronisierung unserer Implementierung.Das Ergebnis lautet, dass unsere Implementierung beim synthetischen Benchmark gutskaliert. Für die anderen Benchmarks ist das Ergebnis durchwachsen und hängt von den unterschiedlichen Systemen ab.

In this thesis we provide a competitive implementation of the Parallel Pipeline pattern for the task parallel Pheet framework. The Pipeline pattern can be applied to many real world problems. The Pipeline pattern splits the input into independent chunks which go through a series of computation steps called stages. Some stages may run in parallel while others have to wait for preceding input chunks to finish. To develop a new Pipeline implementation deep knowledge of existing implementations is required. Therefore this thesis analyzes common existing Pipeline implementations. A technical description of the implementations and their limitations is given. Our implementation is designed to be lock-free and without central data structures to allow good scalability for many core systems. We use C++ atomics to perform non-blocking synchronization. To evaluate our implementation, a set of benchmarks has been executed on different benchmark systems, each featuring a different architecture. The benchmarks contain popular problems which can be modeled efficiently with the Pipeline pattern. Foreach benchmark a reference implementation is used as baseline to compare our results. Additionally a synthetic benchmark is proposed to measure the synchronization overhead of our implementation. We show that our implementation scales well using our synthetic benchmark. The other benchmarks yield very different results on our different test systems.