Title: Decentralised hybrid workflow scheduling algorithm for minimum end-to-end delay in heterogeneous computing environment

Authors: Fei Cao; Michelle Mengxia Zhu

Addresses: Department of Mathematics and Computer Science, University of Central Missouri, Warrensburg, MO, USA ' Department of Computer Science, Southern Illinois University Carbondale, Carbondale, IL, USA

Abstract: This paper considers a decentralised hybrid algorithm for scheduling scientific workflow applications onto an underlying distributed computing environment with heterogeneous resources for minimum end-to-end delay (EED). Distributed scientific workflow applications modelled as directed acyclic graphs (DAGs) are widely applied to various research areas to enable efficient knowledge discovery by automated data processing. Owing to the NP-hardness of this problem, heuristic algorithms are commonly proposed to achieve the EED. Our algorithm combines iterative critical path search and layer-based priority techniques (HICPP) to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HICPP. Our simulation results illustrate that HICPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.

Keywords: decentralised hybrid algorithms; directed acyclic graph; DAG; distributed computing; minimum EED; end-to-end delay; workflow mapping; workflow scheduling; heterogeneous computing; scientific workflow; iterative critical path search; layer-based priority techniques; HICPP; simulation.

DOI: 10.1504/IJHPCN.2015.072783

International Journal of High Performance Computing and Networking, 2015 Vol.8 No.4, pp.324 - 336

Accepted: 07 Oct 2014
Published online: 03 Nov 2015 *

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