Communication-aware task scheduling algorithm for heterogeneous computing. (2017)

• Record Type: Journal Article
• Authors: Huang, Tehui; Li, Tao; Dong, Qiankun; Zhao, Kezhao; Ma, Wenjing; Yang, Yulu
• Is Part Of: International journal of high performance computing and networking. Volume 10:Number 4/5(2017)
• Page Start: 298
• Page End: 309
• Publication Date: 2017
• Subjects: list scheduling -- task duplication -- heterogeneous computing -- communication ratio; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

Abstract

In this paper, we propose a new task scheduling algorithm for heterogeneous computing platforms, called communication-aware earliest finish time (CEFT). It combines the features of list-scheduling and task-duplication, where task priority is assigned according to communication ratio (CR), a notion defined to represent communication cost. We also present a duplication mechanism, which cooperates with CR to reduce the communication overhead. The time complexity of the algorithm is O( v 2 • p ), for v tasks and p processors. The experiment results show that CEFT algorithm improves performance by 11% compared with the state-of-the-art list-based algorithm PEFT, and 15.6% compared with duplication-based algorithm HDCPD, in terms of scheduling length ratio. CEFT is the best algorithm compared with PEFT, HDCPD and HEFT regarding to efficiency and average surplus time as well.