Pipelined Parallelism in a Work-Stealing Scheduler

A pipeline is a particular type of parallel program structure, often used to represent loops with cross-iteration dependencies. Pipelines cannot be expressed with the typical parallel language constructs offered by most environments. Therefore, in order to run pipelines, it is necessary to write a parallel language and scheduler with specialized support for them. Some such schedulers are written exclusively for pipelines and unable to run any other type of program, which allows for certain optimizations that take advantage of the pipeline structure. Other schedulers implement support for pipelines on top of a general-purpose scheduling algorithm. One example of such an algorithm is work stealing, a paradigm used by many popular parallel environments. The benefit of this approach is that it allows the user to arbitrarily combine pipeline and non-pipeline structures in their programs. This article is concerned with implementing support for pipelines in a work-stealing scheduler, and then attempting to optimize the scheduler in such a way that takes advantage of the pipeline structure, despite running in a general-purpose environment