Divisible load scheduling strategies on distributed multi-level tree networks with communication delays and buffer constraints

Abstract

In this paper, the problem of scheduling divisible loads on arbitrary tree networks is considered, with the objective to minimize the total processing time of the entire load. We consider an arbitrary tree network comprising heterogeneous processors interconnected via heterogeneous links. The divisible load is assumed to originate at the root processor in the network and the processors in the system are assumed to render only a finite amount of buffer space (capacity constraint) for processing the divisible load. For a special case of the problem instance wherein when all the processor-link pairs in the tree network can be utilized, we design an algorithm referred to as pull-push optimal load distribution algorithm to obtain an optimal solution. For the generic case, when the network has any redundant processor-link pairs (those pairs whose consideration in scheduling the load will penalize the performance) we propose three heuristic strategies to obtain the best possible time performance. These heuristics are based on applying systematic procedures to eliminate any redundant-link pairs and also using the optimal sequencing theorem proposed in the literature for single-level tree networks. We derive the worst and the best case complexities for all the algorithms proposed and present a discussion on the applicability of the algorithms on a wide range of network scenarios. We demonstrate all the above strategies with illustrative examples and evaluate their performance. © 2003 Elsevier B.V. All rights reserved.