[Back]

B. Redl:
"Extending the Pheet framework for Parallel Pipelined Applications";
Supervisor: J. Träff; Institute of Information Systems, Parallel Computing Group, 2016; final examination: 2016-10-04.

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.