Run-time selection of block size in pipelined parallel programs

Parallelizing compiler technology has improved in re-cent years. One area in which compilers have made progress is in handling DOACROSS loops, where cross-processor data dependencies can inhibit ecient par-allelization. In regular DOACROSS loops, where depen-dencies can be determined at compile time, a useful parallelization technique is pipelining, where each pro-cessor (node) performs its computation in blocks; af-ter each, it sends data to the next processor in the pipeline. The amount of computation before sending a message is called the block size; its choice, although dicult for a compiler to make, is critical to the e-ciency of the program. Compilers typically use a static estimation of workload, which cannot always produce an eective block size. This paper describes a exi-ble run-time approach to choosing the block size. Our system takes measurements during the rst iteration of the program and then uses the results to build an execution model and choose an appropriate block size which, unlike those chosen by compiler analysis, may be nonuniform. Performance on a network of work-stations shows that programs using our run-time anal-ysis outperform those that use static block sizes when the workload is either unbalanced or unanalyzable. On more regular programs, our programs are competitive with their static counterparts. 1