Indexed by:
Abstract:
A multi-round scheduling algorithm, data-collection multi-round (DCMR), is presented to minimize the makespan of divisible workloads in parallel computing. A three-stage model is proposed and takes communication latency and computation start-up time into consideration. The algorithm provides a method to generate a near-optimal number of scheduling rounds. Close-form equations are given through analyzing a specific time sequence of load distribution, and then the bisection method, combined with back-forward adjustment, is used to get an asymptotically optimal number of scheduling rounds, which make the computation time overlap the communication time as much as possible and reduce the makespan. Simulation results show that the algorithm can find a near-optimal number of scheduling rounds under different network parameters. Compared with the classical algorithms such as FIFO and LIFO, the DCMR has higher adaptability. When the computation time dominates the communication time, the algorithm can keep the makespan at a rather low level which is about 1.1 times of the ideal time.
Keyword:
Reprint Author's Address:
Source :
Hsi-An Chiao Tung Ta Hsueh/Journal of Xi'an Jiaotong University
ISSN: 0253-987X
Year: 2009
Issue: 8
Volume: 43
Page: 125-129
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 7
Affiliated Colleges: