Scheduling Non-Uniform Parallel Loops on Highly Parallel Multicomputers

We consider the problem of scheduling parallel loops that are characterized by highly varying execution times (non-uniform parallel loops), and whose iterations operate on large data structures. A general parallel loop implementation template for messagepassing multicomputers is presented. It exploits a partial static replication of the data and a two-phase scheduling strategy. While the first phase of the strategy is static, the second one is dynamic, and only starts when processor loads are estimated to be lower than a given threshold. The static knowledge of the data distribution strategy, which randomly replicates blocks on a fixed set of partner processors, is successfully exploited by the dynamic scheduling phase of our technique. The main advantages of the approach are low-cost scheduling decisions (mainly based on local information) and high scalability, since communications to request further work are overlapped with computations. A simple analytical model of load imbalance, ..