Analytical modeling of pipeline parallelism

Parallel programming is a requirement in the multi-core era. One of the most promising techniques to make paral-lel programming available for the general users is the use of parallel programming patterns. Functional pipeline par-allelism is a pattern that is well suited for many emerging applications, such as streaming and “Recognition, Mining and Synthesis ” (RMS) workloads. In this paper we de-velop an analytical model for pipeline parallelism based on queueing theory. The model is useful to both characterize the performance and efficiency of existing implementations and to guide the design of new pipeline algorithms. We demonstrate the usefulness of the model by charac-terizing and optimizing two of the PARSEC benchmarks, ferret and dedup. We identified two issues with these codes: load imbalance and I/O bottlenecks. We addressed load imbalance using two techniques: i) parallel pipeline stage collapsing; and ii) dynamic scheduling. We imple-mented these optimizations using Pthreads and the Thread-ing Building Blocks (TBB) libraries. We compare the per-formance of different alternatives and we note that the TBB implementation based on work stealing outperforms all other variants.