• Complex
  • Title
  • Author
  • Keyword
  • Abstract
  • Scholars
Search

Author:

Kang, Yu (Kang, Yu.) | Yan, Xiangguo (Yan, Xiangguo.) | Zheng, Chongxun (Zheng, Chongxun.) | Shen, Guangjie (Shen, Guangjie.)

Indexed by:

EI Scopus CSCD PKU

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:

Asymptotically optimal Communication latency Communication time Computation time Divisible workload Load distributions Multi-Round scheduling Network parameters

Author Community:

  • [ 1 ] [Kang, Yu;Yan, Xiangguo;Zheng, Chongxun;Shen, Guangjie]The Key Laboratory of Biomedical Information Engineering of Ministry of Education, Xi'an Jiaotong University, Xi'an 710049, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

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

FAQ| About| Online/Total:983/168836613
Address:XI'AN JIAOTONG UNIVERSITY LIBRARY(No.28, Xianning West Road, Xi'an, Shaanxi Post Code:710049) Contact Us:029-82667865
Copyright:XI'AN JIAOTONG UNIVERSITY LIBRARY Technical Support:Beijing Aegean Software Co., Ltd.