Communication-aware task scheduling algorithm for heterogeneous computing. (2017) - Huang, Tehui; Li, Tao; Dong, Qiankun; Zhao, Kezhao; Ma, Wenjing; Yang, Yulu
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.