Load-balancing for load-imbalanced fine-grained linear pipelines

Pipelining is a well-known technique to overlap loop iterations by partitioning the loop body into a sequence of stages. A large class of programs can be expressed as linear pipelines if data dependences only flow from earlier to later stages. Various pipelining techniques have been explored but reconciling load-balancing and efficient execution is still a challenge for two main reasons. First, partitioning of the loop body into stages that lead to load-balancing may depend on the data set as well as system properties, e.g., number of cores. Second, the configuration of the runtime system is far from obvious. In this article, we present Pipelight, a technique that achieves load-balancing for linear pipelines. Pipelight relies on a way of mapping stages onto threads that simplifies partitioning and enables the design of a lightweight algorithm for dynamic scheduling. Furthermore, Pipelight introduces a concurrent data structure that exploits the properties of data dependences presented in linear pipelines to provide efficient communication and synchronization. This data structure simplifies the configuration of the runtime system and makes Pipelight a practical solution. The evaluation on a 44-core system shows the efficiency of Pipelight for a set of programs selected from widely-used collections. Although Pipelight simplifies parallelization of linear pipelines, it performs similarly to the most efficient properly configured state-of-the-art technique. The price paid for the benefits of Pipelight is additional overhead for fine-grained loops. However, this overhead can be amortized successfully with chunking. To make Pipelight a promising solution, we propose a directive-based transformation for Pipelight, which is developed in a prototype source-to-source compiler. Consequently, Pipelight is an efficient and practical solution to achieve load-balancing for fine-grained linear pipelines.