Scheduling Data-Parallel Computations on Heterogeneous and Time-Shared Environments

This paper addresses the problem of load balancing data-parallel computations on heterogeneous and time-shared parallel computing environments. Load imbalance in these environments may be introduced by the different capacities of processors populating a computer, or by the sharing of the same computational resources among several users. A evenly partitioned code, which on a homogeneous system runs with a perfect load balance, may perform poorly if the processors have different speeds or loads. To solve this problem for data-parallel computations, we propose a run-time support for parallel loops based upon a hybrid (static + dynamic) scheduling strategy. Our support balances the processor workloads by dynamically migrating computations from slower to faster processors without requiring a priori knowledge of their relative speeds. The results obtained on many experiments conducted on SGI/Cray T3E and IBM SP2 systems show that our hybrid scheduling strategy which first allocates the sa..