Adaptive Dynamic Process Scheduling on Distributed Memory Parallel Computers

Issue title: Operating system Support for Massively Parallel Computer Architectures

Article type: Research Article

Authors: Shu, Wei

Affiliations: Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260

Abstract: One of the challenges in programming distributed memory parallel machines is deciding how to allocate work to processors. This problem is particularly important for computations with unpredictable dynamic behaviors or irregular structures. 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. It deals with dynamic and unpredictable creation of processes and adapts to different systems. The scheme is described and contrasted with two other schemes that have been proposed in this context, namely the randomized allocation and the gradient model. The performance of the three schemes on an Intel iPSC/2 hypercube is presented and analyzed. The experimental results show that even though the ACWN algorithm incurs somewhat larger overhead than the randomized allocation, it achieves better performance in most cases due to its adaptiveness. Its feature of quickly spreading the work helps it outperform the gradient model in performance and scalability.

Journal: Scientific Programming, vol. 3, no. 4, pp. 341-352, 1994