Title: Erweiterung des Pheet Frameworks für Pipeline-Parallele Anwendungen
Other Titles: Extending the pheet framework for parallel pipelined applications
Language: English
Authors: Redl, Bernhard 
Qualification level: Diploma
Keywords: Pipeline; lock-free; Pheet framework; multicore
Advisor: Träff, Jesper Larsson  
Issue Date: 2016
Number of Pages: 143
Qualification level: Diploma
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-7097
http://hdl.handle.net/20.500.12708/3330
Library ID: AC13351651
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

36
checked on Feb 18, 2021

Download(s)

67
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.