Load Balancing Using Work-stealing for Pipeline Parallelism in Emerging Applications

Parallel programming is a requirement in the multi-core era. One of the most promising techniques to make parallel programming available for the general users is the use of parallel programming patterns. Functional pipeline parallelism 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 develop an analytical model for pipeline parallelism based on queueing theory. The model is useful to both characterize the performance and eciency of existing implementations and to guide the design of new pipeline algorithms.

We demonstrate how we used the model to characterize and optimize two of the PARSEC benchmarks, ferret and dedup. We identi ed two issues with these codes: load imbalance and I/O bottlenecks. We propose to address the I/O bottleneck using parallel I/O. We addressed load imbalance using two techniques: i) parallel pipeline stage collapsing; and ii) work-stealing. We implemented these optimizations using Pthreads and the Threading Building Blocks (TBB) libraries. We compare the performance of different alternatives and we note that the TBB implementation outperforms all other variants. However, the current pipeline template supported by TBB is restrictive and we discuss extensions that will allow more exible pipeline designs using this library.

By: Angeles Navarro; Rafael Asenjo; Siham Tabik; Calin Cascaval

Published in: RC24732 in 2009


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .