Dynamic scheduling of medium-grained processes on distributed memory computers

One of the challenges in programming distributed memory parallel machines is how to allocate work to processors. We present a scheme for dynamic scheduling of medium-grained processes that is useful in this context. The Adaptive Contracting Within Neighborhood (ACWN) is a dynamic, distributed, load-dependent, and scalable scheme. The scheme is described, contrasted with two other schemes that have been proposed in this context. The performance of all the three schemes on a 32 processor iPSC/2 hypercube is presented and analyzed. The experimental results show that even though ACWN algorithm incurs larger overhead than randomized allocation, it achieves better performance in most cases due to its adaptiveness. Its feature of fast spreading the work helps it outperform the gradient model in performance and scalability.<>