Optimum divisible load scheduling on heterogeneous stars with limited memory

Optimum divisible load scheduling on heterogeneous stars with limited memory

0.00 Avg rating0 Votes
Article ID: iaor20083736
Country: Netherlands
Volume: 172
Issue: 2
Start Page Number: 545
End Page Number: 559
Publication Date: Jul 2006
Journal: European Journal of Operational Research
Authors: ,
Abstract:

Scheduling divisible application on a set of heterogeneous processors with limited memory sizes is analyzed in this paper. Divisible loads are computations which allow for dividing computations into several parts of arbitrary sizes, and the parts can be processed independently in parallel. Though the model originated in the parallel computing context, it has strong links with other applications of operations research. A star communication network is assumed. Each processing element of the network is characterized by the processing speed, memory size, speed and startup time of its communication link. The goal is to find a distribution of the load whose schedule length is minimum. The problem is established to be computationally hard. Therefore, two types of algorithms are proposed, and evaluated: an exact algorithm whose execution time may be exponential, and polynomial-time heuristics.

Reviews

Required fields are marked *. Your email address will not be published.