Optimal algorithm for scheduling large divisible workload on heterogeneous system |
| |
Authors: | Shang Mingsheng |
| |
Institution: | School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, PR China |
| |
Abstract: | Optimal algorithms for scheduling divisible load on heterogeneous system are considered in this paper. The platform model we use is general and realistic, in which the mode of communication is non-blocking message receiving, and processors and communication links may have different speeds and arbitrary start-up overheads. The objective is to minimize the processing time of the entire workload. The main contributions are: (1) closed-form expressions for the processing time and the fraction of workload for each processor are derived; (2) the influence of start-up overheads on the optimal processing time is analyzed; (3) for system of bounded number of processors and large workload, optimal sequence and algorithm for workload distribution are proposed. Moreover, some numerical examples are presented to illustrate the analysis. |
| |
Keywords: | Heterogeneous computing Divisible load theory Non-blocking mode of communication Start-up overheads Optimal scheduling sequence |
本文献已被 ScienceDirect 等数据库收录! |
|