Pipelined Data-Parallel Algorithms: Part II—Design

In part I of this paper [9], we introduced the basic concept of pipelined data parallel algorithms and discussed the modeling of such algorithms on distributed-memory multicomputers. In this paper, a methodology for designing pipelined data-parallel algorithms on multicomputers is studied. The design procedure starts with a sequential algorithm which can be expressed as a nested loop with constant loop-carried dependencies. The main focus of the procedure is on partitioning the loop by grouping related iterations together. Grouping is necessary to balance the communication overhead with the available parallelism and to produce pipelined execution patterns, which result in pipelined data parallel computation. The grouping should satisfy dependence relationships among the iterations and also allow the granularity to be controlled. Various properties of grouping are studied, and methods for generating communication efficient grouping are given. Given a grouping and an assignment of the groups to the processors, we then combine the analytic model introduced in [9] with the grouping results to describe the behavior and to estimate the performance of the resultant parallel program. Expressions characterizing the performance are derived, and from the modeling the optimal grouping schemes can be obtained.