Dynamic scheduling strategy for the Chare-Kernel system

One of the challenges in programming distributed memory parallel machines is deciding how to allocate work to processors. This problem is particularly acute for computations with unpredictable dynamic behavior or irregular structure. The authors present a scheme for dynamic scheduling of medium-grained processes that is useful in this context. Adaptive contracting within neighborhood (ACWN) is a dynamic, distributed, self-adaptive, and scalable scheme. The basic scheme and its adaptive extensions are described and contrasted with other schemes that have been proposed in this context. The performance of all the three schemes on an iPSC/2 hypercube is presented and analyzed. The experimental results show that the ACWN algorithm achieves better performance in most cases than randomized allocation. Its agility in spreading the work helps it outperform the gradient model in performance and scalability.