2004 HIPS S. MacDonald, D. Szafron, and J. Schaeffer, Rethinking the Pipeline as Object–Oriented States withTransformations, 9th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS'2004) at IPDPS, April 2004, Santa Fe, U.S., pp. 12-21, abstract or pdf.

The pipeline is a simple and intuitive structure to speed up many kinds of problems. Novice parallel programmers are usually taught this structure early on. However, expert parallel programmers typically eschew using the pipeline in coarse­grained applications because it has two serious problems that make it difficult to implement efficiently in practice. First, load balancing is crucial to obtaining good speedup. Second, processors will idle when the pipeline is not full, notably at the beginning and end of the program. Instead, experts recast the problem as a master/slave structure which doesn’t suffer from these problems. A further problem with pipelines is that it is difficult to incrementally incorporate additional processors into an existing pipeline. This paper details a transformation that allows programs written using a pipeline style to execute using the more efficient master/slave structure. Parallel programmers can benefit from both the intuitive simplicity of the pipeline and the efficient execution of a master/slave structure. This is demonstrated by performance results from a parallel JPEG encoder.