On-the-Fly Pipeline Parallelism

Pipeline parallelism organizes a parallel program as a linear se-quence of s stages. Each stage processes elements of a data stream, passing each processed data element to the next stage, and then taking on a new element before the subsequent stages have nec-essarily completed their processing. Pipeline parallelism is used especially in streaming applications that perform video, audio, and digital signal processing. Three out of 13 benchmarks in PARSEC, a popular software benchmark suite designed for shared-memory multiprocessors, can be expressed as pipeline parallelism. Whereas most concurrency platforms that support pipeline par-allelism use a “construct-and-run ” approach, this paper investi-gates “on-the-fly ” pipeline parallelism, where the structure of the pipeline emerges as the program executes rather than being spec-ified a priori. On-the-fly pipeline parallelism allows the num