Title: Communication-aware task scheduling algorithm for heterogeneous computing

Authors: Tehui Huang; Tao Li; Qiankun Dong; Kezhao Zhao; Wenjing Ma; Yulu Yang

Addresses: College of Computer and Control Engineering, Nankai University, Tianjin, 300350, China ' College of Computer and Control Engineering, Nankai University, Tianjin, 300350, China ' College of Computer and Control Engineering, Nankai University, Tianjin, 300350, China ' College of Computer and Control Engineering, Nankai University, Tianjin, 300350, China ' Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China ' College of Computer and Control Engineering, Nankai University, Tianjin, 300350, China

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² • 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.

Keywords: list scheduling; task duplication; heterogeneous computing; communication ratio.

DOI: 10.1504/IJHPCN.2017.086534

International Journal of High Performance Computing and Networking, 2017 Vol.10 No.4/5, pp.298 - 309

Received: 27 Sep 2015
Accepted: 26 Nov 2015
Published online: 12 Sep 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article