Dynamic mapping of cooperating tasks to nodes in a distributed system

Networks of workstations (NOWs) are a low-cost and widespread platform for parallel computing. This paper focuses on the dynamic task-scheduling problem in NOW environments. The aim is to minimize the completion time of parallel programs by distributing cooperating concurrent tasks to homogeneous networked nodes. Cooperation dependencies as well as creation and termination dependencies between tasks are taken into account. An event lattice model is introduced to describe past, actual and future behavior of a parallel program in execution. Based on this model an algorithm is presented to dynamically assign tasks to the nodes of a dedicated distributed system. Crucial for the efficiency of this approach is a top-down construction of all operating system entities involved in distributed resource management, particularly the close cooperation of the compiler and runtime system, which allows the creation of event lattice clippings at runtime.