Resource-Constrained Heterogeneous Workflow Scheduling Algorithm for Heterogeneous Computing Clusters

Authors: Lei Wang, Jiahao Zhou

Abstract:

The development of heterogeneous computing clusters provides robust computational support for large-scale workflows, commonly seen in domains such as scientific computing and artificial intelligence. However, the tasks within these large-scale workflows are increasingly heterogeneous, exhibiting varying demands on computing resources. This shift necessitates the integration of resource-constrained considerations into the workflow scheduling problem on heterogeneous computing platforms. In this study, we propose a scheduling algorithm designed to minimize the makespan under heterogeneous constraints, employing a greedy strategy to effectively address the scheduling challenges posed by heterogeneous workflows. We evaluate the performance of the proposed algorithm using randomly generated heterogeneous workflows and a corresponding heterogeneous computing platform. The experimental results demonstrate a 15.2% improvement in performance compared to existing state-of-the-art methods.

Keywords: Heterogeneous Computing, Workflow Scheduling, Constrained Resources, Minimal Makespan.

References:

[1] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260–274, Mar. 2002.
[2] H. Arabnejad and J. G. Barbosa, “List scheduling algorithm for heterogeneous systems by an optimistic cost table,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 3, pp. 682–694, Mar. 2014.
[3] K. He, X. Meng, Z. Pan, L. Yuan and P. Zhou, “A Novel Task-Duplication Based Clustering Algorithm for Heterogeneous Computing Environments,” in IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 1, pp. 2-14, 1 Jan. 2019.
[4] Paraskevas, Kyriakos. “Enabling Direct-Access Global Shared Memory for Distributed Heterogeneous Computing.” (2023).
[5] Lawley, Jason. “Understanding Performance of PCI Express Systems.” WP350 (v1. 2). **linx 97 2014.
[6] Dongarra, Jack, and Alexey L. Lastovetsky. “High performance heterogeneous computing.” John Wiley & Sons, 2009.
[7] Mittal, S. and Vetter, J.S., 2015. “A survey of CPU-GPU heterogeneous computing techniques.” ACM Computing Surveys (CSUR), 47(4), pp.1-35.
[8] L. Wu et al., “DOT: Decentralized Offloading of Tasks in OFDMA-Based Heterogeneous Computing Networks,” in IEEE Internet of Things Journal, vol. 9, no. 20, pp. 20071-20082, 15 Oct.15, 2022.
[9] A. Reisizadeh, S. Prakash, R. Pedarsani and A. S. Avestimehr, “Coded Computation Over Heterogeneous Clusters,” in IEEE Transactions on Information Theory, vol. 65, no. 7, pp. 4227-4242, July 2019.
[10] J. Kim, S. Lee, B. Johnston and J. S. Vetter, “IRIS: A Performance-Portable Framework for Cross-Platform Heterogeneous Computing,” in IEEE Transactions on Parallel and Distributed Systems, vol. 35, no. 10, pp. 1796-1809, Oct. 2024.
[11] M. I. Daoud and N. Kharma, “A high performance algorithm for static task scheduling in heterogeneous distributed computing systems,” J. Parallel Distrib. Comput., vol. 68, no. 4, pp. 399–409, 2008.
[12] C. -W. Tsai, W. -C. Huang, M. -H. Chiang, M. -C. Chiang and C. -S. Yang, “A Hyper-Heuristic Scheduling Algorithm for Cloud,” in IEEE Transactions on Cloud Computing, vol. 2, no. 2, pp. 236-250, 1 April-June 2014.
[13] M¨onch, Lars, Hari Balasubramanian, John W. Fowler, and Michele E. Pfund. “Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times.” Computers & Operations Research 32, no. 11 (2005): 2731-2750.