一种多核系统改进型列表调度算法

doi:10.16180/j.cnki.issn1007-7820.2020.06.010

摘要/Abstract

摘要：

在任务调度领域,基于列表的任务调度算法被广泛应用。经典列表调度算法在节点排序阶段会对权值一致的任务节点进行随机排序,但这种节点排序方式过于粗糙,难以取得较好效果。针对这一缺陷,文中提出了一种改进型列表调度算法,通过特殊列表片段将权值一致的任务整合到一起,并对特殊列表片段的调度解空间进行遍历,以迭代产生更优的调度列表获得更好的调度效果。随机DAG图测试结果表明,提出的算法调度效果优异,算法平均增强比最高可达15.3%,不仅适用于多种任务图规模,且在CCR和平均出入度较高的情况下有更好的调度性能。

关键词: 调度算法, 节点排序, 任务权值, 权值一致排序困境, 特殊列表片段, 调度空间

Abstract:

The list-based task scheduling algorithm has been widely used in the field of task scheduling. The classic list scheduling algorithm randomly sorts the task nodes with the same weight in the node sorting stage. But the sorting method is rough and difficult to achieve better results. In view of this defect, this study proposed an improved list scheduling algorithm. This algorithm integrated tasks with consistent weights through special list fragments, and traversed the scheduling solution space of special list fragments to iteratively generate better scheduling lists to obtain a better scheduling results. The results of random DAG graph test showed that the proposed algorithm had excellent scheduling effect, and the average algorithm enhancement ratio was up to 15.3%, indicating the proposed method was not only suitable for multiple task map scales, but also had better scheduling performance under the condition of higher CCR and higher average access.

Key words: scheduling algorithm, sort nodes, task weigh, weighted consistent ordering dilemma, special list fragment, scheduling space

中图分类号:

TN401

罗乐,王春华,张多利,宋宇鲲. 一种多核系统改进型列表调度算法[J]. 电子科技, 2020, 33(6): 52-57.

LUO Le,WANG Chunhua,ZHANG Duoli,SONG Yukun. A Multicore System Improved List Scheduling Algorithm[J]. Electronic Science and Technology, 2020, 33(6): 52-57.

图/表 13

图1

算法1

算法2

表1

算法3

图2

Table 2

表3

图3

图4

图5

图6

图7

参考文献 16

[1]	Ullman J D . NP-Complete scheduling problems[J]. Journal of Computer and System Sciences, 1975,10(3):384-393.
[2]	Michael R Garey, David S Johnson . Computers and intractability: a guide to the theory NP-Completeness[M]. San Francisco:W. H. Freeman and Company, 1990.
[3]	Oliver Sinnen . Task schedule for parallel system[M]. New Jersey:John Wiley & Sons,Inc., 2007.
[4]	Topcuoglu H, Hariri S, Wu M Y . Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002,13(3):260-274.
[5]	He Kun, Zhao Yong, Chen Yang . Analysis and solutions for multitasks scheduling in distributed environments[J]. Systems Engineering-Theory and Practice, 2007,27(5):119-125.
[6]	周双娥, 袁由光, 熊兵周 , 等. 基于任务复制的处理器预分配算法[J]. 计算机学报, 2004,27(2):216-223.
	Zhou Shuange, Yuan Youguang, Xiong Bingzhou , et al. Processor pre-allocation algorithm based on task replication[J]. Chinese Journal of Computers, 2004,27(2):216-223.
[7]	谢志强, 韩英杰, 齐永红 , 等. 基于关键路径和任务复制的多核调度算法[J]. 国防科技大学学报, 2014,36(1):172-177.
	Xie Zhiqiang, Han Yingjie, Qi Yonghong , et al. Multi-core scheduling algorithm based on critical path and task replication[J]. Journal of National University of Defense Technology, 2014,36(1):172-177.
[8]	Tabak E K, Cambazoglu B B, Aykanat C . Improving the performance of independent task assignment heuristics minmin, maxmin and sufferage[J]. IEEE Transactionson Parallel and Distributed Systems, 2014,25(5):1244-1256.
[9]	李静梅, 张博, 王雪 . 基于粒子群优化的异构多处理器任务调度算法[J]. 计算机应用研究, 2012,29(10):3621-3624.
	Li Jingmei, Zhang Bo, Wang Xue . Heterogeneous multiprocessor task scheduling algorithm based on particle swarm optimization[J]. Journal of Computer Applications, 2012,29(10):3621-3624.
[10]	Faragardi H R, Shojaee R, Yazdani N. Reliability-aware task allocation in distributed computing systems using hybrid simulated annealing and tabu search[C]. Liverpool:IEEE 14 ^th International Conference on High Performance Computing and Communication & IEEE 9 ^th International Conference on Embedded Software and Systems , 2012.
[11]	高曙, 郑德 . 一种基于蚁群算法的任务调度方法[J]. 微计算机信息, 2007,23(6):191-192.
	Gao Shu, Zheng De . Atask scheduling method based on ant colony algorithm[J]. Journal of Microcomputer, 2007,23(6):191-192.
[12]	姚英彪, 王璇 . 面向多核任务调度的混合遗传算法[J]. 系统工程与电子技术, 2010,37(8):1928-1935.
	Yao Yingbiao, Wang Xuan . Hybrid genetic algorithm for multi-core task scheduling[J]. Systems Engineering and Electronics, 2010,37(8):1928-1935.
[13]	耿汝年, 须文波 . 基于自适应选择遗传算法的任务调度与分配[J]. 计算机工程, 2008,34(3):43-46.
	Geng Runian, Xu Wenbo . Task scheduling and allocation based on adaptive selection genetic algorithm[J]. Computer Engineering, 2008,34(3):43-46.
[14]	穆鹏程 , Jean Francois N, Mickael R, 等. 并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法[J]. 中国科学:信息科学, 2011,41(3):349-364.
	Mu Pengcheng, Jean Francois N, Mickael R , et al. Advanced list scheduling method for communication competing task scheduling problems in parallel embedded systems[J]. Science in China:Information Science, 2011,41(3):349-364.
[15]	陈茂强 . 一种基于DAG的并行系统任务调度方法[J]. 电子科技, 2014,27(9):29-32.
	Chen Maoqiang . A DAG-based parallel system task scheduling method[J]. Electronic Science and Technology, 2014,27(9):29-32
[16]	Sinnen O, Sousa L . List scheduling: extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures[J]. Parallel Computing, 2004,30(1):81-101.

变量	取值
NT	50、100、150、200
CCR	0.1、1、5、10
In/Out	2、3、4、5
NP	2、4、6、8