Abstract |
Task-based programming models are becoming the most efficient mechanism to achieve performance and programmability on parallel applications. However, the construction of parallel pipelined applications with the use of the state of the art task dataflow programming models still remains hard.
In this thesis we designed and implemented hyperqueues, a programming abstraction of queues that allows different pipeline stages of a parallel application to exchange data with flexibility. Hyperqueues are types of Cilk++ hyperobjects that allow different code paths in a multi-threaded program to maintain coherent local views of the same shared variable. Our design enables shared concurrent views among threads and guarantees the correct execution path by labeling the access type of each thread. We define the semantics of this programming abstraction and describe its implementation on a work stealing Cilk-like scheduler. The main contribution of hyperqueues is the abstraction they offer in the construction of parallel irregular pipelines. We performed an experimental evaluation on the PARSEC benchmarks that can be expressed with pipeline parallelism and we find that hyperqueues overcome the programmability limitations of the state-of-the-art task dataflow models while they achieve performance better than POSIX threads, by a factor of 1.85×, and same as Intel’s Threading Building Blocks, with 50% and 10% less code effort (lines of code) respectively. The improvement of hyperqueues on Swan scheduler is demonstrated by a factor of 2.02× over the baseline.
|