A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing

YAO Yu; SONG Yukun; YANG Guowei; HUANG Ying; ZHANG Duoli

doi:10.11999/JEIT211150

Volume 45 Issue 1

Jan. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(1): 125-133

YAO Yu, SONG Yukun, YANG Guowei, HUANG Ying, ZHANG Duoli. A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing[J]. Journal of Electronics & Information Technology, 2023, 45(1): 125-133. doi: 10.11999/JEIT211150

Citation:

YAO Yu, SONG Yukun, YANG Guowei, HUANG Ying, ZHANG Duoli. A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing[J]. Journal of Electronics & Information Technology, 2023, 45(1): 125-133. doi: 10.11999/JEIT211150

Citation:

YAO Yu, SONG Yukun, YANG Guowei, HUANG Ying, ZHANG Duoli. A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing[J]. Journal of Electronics & Information Technology, 2023, 45(1): 125-133. doi: 10.11999/JEIT211150

PDF( 4843 KB)

A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing

doi: 10.11999/JEIT211150

School of Microelectronics, Hefei University of Technology, Hefei 230601, China

Funds: The University Synergy Innovation Program of Anhui Province (GXXT-2019-030)

Received Date: 2021-10-21
Accepted Date: 2022-01-20
Rev Recd Date: 2022-01-12

Available Online: 2022-02-03

Publish Date: 2023-01-17

Abstract

Abstract

The improvement of application efficiency of heterogeneous computing systems is highly dependent on effective scheduling algorithms. A new list scheduling algorithm called Improved Predict Priority and Optimistic processor Selection Scheduling (IPPOSS) is proposed by this paper. By introducing the backward prediction cost of tasks in task prioritizing phase, the scheduling length is reduced. Compared with the existing work, an Improved Predict Cost Matrix (IPCM) is adopted to prioritize tasks more reasonably and a better solution in processor selection phase when keeping quadratic time complexity is obtain. IPCM, which considers various calculation and communication factors in the task prioritization stage, is easier to obtain a reasonable priority list than Predict Cost Matrix (PCM) proposed by Predict Priority Task Scheduling (PPTS). That the performance of IPPOSS is better than related algorithms is shown by the analysis of the experimental results of randomly generated application Directed Acyclic Graphs (DAGs) and real-world application DAGs.
- Heterogeneous systems,
- Parallel computing,
- List scheduling,
- Static scheduling

FullText(HTML)

References(26)

References

[1]	SINNEN O and SOUSA L A. Communication contention in task scheduling[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(6): 503–515. doi: 10.1109/TPDS.2005.64
[2]	GAREY M R, JOHNSON D S, and STOCKMEYER L. Some simplified NP-complete problems[C]. The 6th Annual ACM Symposium on Theory of Computing, Seattle, USA, 1974: 47–63.
[3]	ULLMAN J D. NP-complete scheduling problems[J]. Journal of Computer and System Sciences, 1975, 10(3): 384–393. doi: 10.1016/S0022-0000(75)80008-0
[4]	PAPADIMITRIOU C H and YANNAKAKIS M. Scheduling interval-ordered tasks[J]. SIAM Journal on Computing, 1979, 8(3): 405–409. doi: 10.1137/0208031
[5]	AGUILAR J and GELENBE E. Task assignment and transaction clustering heuristics for distributed systems[J]. Information Sciences, 1997, 97(1/2): 199–219. doi: 10.1016/S0020-0255(96)00178-8
[6]	HUANG Kuochan, GU D S, LIU H C, et al. Task clustering heuristics for efficient execution time reduction in workflow scheduling[J]. Journal of Computers, 2017, 28(1): 43–56. doi: 10.3966/199115592017022801004
[7]	TIAN Qiao, LI Jingmei, XUE Di, et al. A hybrid task scheduling algorithm based on task clustering[J]. Mobile Networks and Applications, 2020, 25(4): 1518–1527. doi: 10.1007/s11036-019-01356-x
[8]	SULAIMAN M, HALIM Z, WAQAS M, et al. A hybrid list-based task scheduling scheme for heterogeneous computing[J]. The Journal of Supercomputing, 2021, 77(9): 10252–10288. doi: 10.1007/s11227-021-03685-9
[9]	AHMAD W and ALAM B. An efficient list scheduling algorithm with task duplication for scientific big data workflow in heterogeneous computing environments[J]. Concurrency and Computation:Practice and Experience, 2021, 33(5): e5987. doi: 10.1002/cpe.5987
[10]	HAGRAS T, ATEF A, and MAHDY Y B. Greening duplication-based dependent-tasks scheduling on heterogeneous large-scale computing platforms[J]. Journal of Grid Computing, 2021, 19(1): 13. doi: 10.1007/s10723-021-09554-2
[11]	TOPCUOGLU H, HARIRI S, and WU Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260–274. doi: 10.1109/71.993206
[12]	BITTENCOURT L F, SAKELLARIOU R, and MADEIRA E R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[C]. The 2010 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, Pisa, Italy, 2010: 27–34.
[13]	ARABNEJAD H and BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682–694. doi: 10.1109/TPDS.2013.57
[14]	DJIGAL H, FENG Jun, and LU Jiamin. Task scheduling for heterogeneous computing using a predict cost matrix[C]. The 48th International Conference on Parallel Processing: Workshops, Kyoto, Japan, 2019: 25.
[15]	ZHAO Yi, CAO Suzhi, and YAN Lei. List scheduling algorithm based on pre-scheduling for heterogeneous computing[C]. 2019 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking, Xiamen, China, 2019: 588–595.
[16]	IJAZ S and MUNIR E U. MOPT: List-based heuristic for scheduling workflows in cloud environment[J]. The Journal of Supercomputing, 2019, 75(7): 3740–3768. doi: 10.1007/s11227-018-2726-6
[17]	DOROSTKAR F and MIRZAKUCHAKI S. List scheduling for heterogeneous computing systems introducing a performance-effective definition for critical path[C]. The 2019 9th International Conference on Computer and Knowledge Engineering, Mashhad, Iran, 2019: 356–362.
[18]	JIANG Chao, WANG Jinlin, and YE Xiaozhou. PVBTS: A novel task scheduling algorithm for heterogeneous computing platforms[J]. International Journal of Innovative Computing, Information and Control, 2020, 16(2): 701–713. doi: 10.24507/ijicic.16.02.701
[19]	GHOLAMI H and ZAKERIAN R. A list-based heuristic algorithm for static task scheduling in heterogeneous distributed computing systems[C]. The 2020 6th International Conference on Web Research, Tehran, Iran, 2020: 21–26.
[20]	HU Wei, GAN Yu, LV Xiangyu, et al. A improved list heuristic scheduling algorithm for heterogeneous computing systems[C]. 2020 IEEE International Conference on Systems, Man, and Cybernetics, Toronto, Canada, 2020: 1111–1116.
[21]	HU Wei, GAN Yu, WEN Yuan, et al. An improved heterogeneous dynamic list schedule algorithm[C]. The 20th International Conference on Algorithms and Architectures for Parallel Processing, New York City, USA, 2020: 159–173.
[22]	DJIGAL H, FENG Jun, LU Jiamin, et al. IPPTS: An efficient algorithm for scientific workflow scheduling in heterogeneous computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(5): 1057–1071. doi: 10.1109/TPDS.2020.3041829
[23]	SHI Zhiao, JEANNOT E, and DONGARRA J J. Robust task scheduling in non-deterministic heterogeneous computing systems[C]. 2006 IEEE International Conference on Cluster Computing, Barcelona, Spain, 2006: 1–10.
[24]	frs69wq. DAGGEN: A synthetic task graph generator[EB/OL].https://github.com/frs69wq/daggen, 2021.
[25]	AMOURA A K, BAMPIS E, and KONIG J C. Scheduling algorithms for parallel Gaussian elimination with communication costs[J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(7): 679–686. doi: 10.1109/71.707547
[26]	JIANG Qingye, LEE Y C, ARENAZ M, et al. Optimizing scientific workflows in the cloud: A montage example[C]. The 2014 IEEE/ACM 7th International Conference on Utility and Cloud Computing, London, UK, 2014: 517–522.