HIERARCHICAL SCHEDULING OF DYNAMIC PARALLEL COMPUTATIONS ON HYPERCUBEMULTICOMPUTERS

In this paper a hierarchical task scheduling strategy for assigning pa rallel computations with dynamic structures to large hypercube multico mputers is proposed. Such computations represent a wide range of recur sive and divide/conquer algorithms for which structure of the problem varies dynamically. To achieve load balancing and reduce processor con tentions, the system is divided into multiple regions of processors fo r which the first level of scheduling is done by the host computer tha t spreads out the initial computations into these regions. The second level scheduling is done by a set of median processors of these region s which enable the processors of their regions to optimally balance th e dynamically created load and to communicate with each other with red uced overhead. The results of an extensive simulation study are presen ted that exhibit the performance of the proposed strategy under differ ent loading conditions, varying degrees of depth and parallelism, and communication costs. The proposed dual-level hierarchical scheduling i s shown to outperform a well known distributed scheduling strategy. (C ) 1994 Academic Press, Inc.