计算机科学 ›› 2015, Vol. 42 ›› Issue (1): 86-89.doi: 10.11896/j.issn.1002-137X.2015.01.020
• 2013年全国理论计算机科学学术年会 • 上一篇 下一篇
杨辉华,张晓凤,谢谱模,韦向远
YANG Hui-hua, ZHANG Xiao-feng, XIE Pu-mo and WEI Xiang-yuan
摘要: 多处理器系统在高性能计算中扮演着重要角色。为提高系统的并行性能,基于布谷鸟搜索算法,提出一种新的多处理器任务调度算法。该算法以全部任务的最晚完成时间最小为目标,利用基于任务优先权的编码方式使连续的布谷鸟搜索算法适用于离散的多处理器任务调度问题。实验结果表明,所提算法不仅求解质量高,而且求解速度最快,与目前广泛采用的遗传算法和粒子群算法相比其执行时间缩短超过60%。
[1] Kwok Y K,Ahmad I.Static scheduling algorithms for allocating directed task graphs to multiprocessors[J].ACM Computing Surveys (CSUR),1999,31(4):406-471 [2] Daoud M I,Kharma N.A high performance algorithm for static task scheduling in heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing,2008,68(4):399-409 [3] 陈华平,黄刘生.启发式任务调度中的处理器选择策略[J].软件学报,1999,10(11):1194-1198 [4] 石威,郑纬民.相关任务图的均衡动态关键路径调度算法[J].计算机学报,2001,24(9):991-997 [5] Corrêa R C,Ferreira A,Rebreyend P.Scheduling multiprocessor tasks with genetic algorithms[J].IEEE Transactions on Parallel and Distributed Systems,1999,10(8):825-837 [6] Gupta S,Agarwal G,Kumar V.An Efficient and Robust Genetic Algorithm for Multiprocessor Task Scheduling[J].International Journal of Computer Theory and Engineering,2013,5(2);377-382 [7] 叶春晓,陆杰.基于改进遗传算法的网格任务调度研究[J].计算机科学,2010,7(7):233-235 [8] Omara F A,Arafa M M.Genetic algorithms for task scheduling problem[J].Journal of Parallel and Distributed Computing,2010,70(1):13-22 [9] Hwang R,Gen M,Katayama H.A comparison of multiprocessortask scheduling algorithms with communication costs[J].Computers & Operations Research,2008,35(3):976-993 [10] 王成昌,陈闳中,方钰,等.基于混合粒子群算法的网格任务调度[J].计算机科学,2012,9(2):18-21 [11] Al Badawi A,Shatnawi A.Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization[J].Computers & Operations Research,2013,40(10):2322-2328 [12] Yin P Y,Yu S S,Wang P P,et al.A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems[J].Computer Standards & Interfaces,2006,28(4):441-450 [13] Sivanandam S N,Visalakshi P,Bhuvaneswari A.Multiprocessor Scheduling Using Hybrid Particle Swarm Optimization with Dynamically Varying Inertia[J].IJCSA,2007,4(3):95-106 [14] 高尚,杨静宇.多处理机调度问题的粒子群优化算法[J].计算机工程与应用,2005,41(27):72-73 [15] Yang X S,Deb S.Engineering optimisation by cuckoo search[J].International Journal of Mathematical Modeling and Numerical Optimisation,2010,1(4):330-343 [16] Gandomi A H,Yang X S,Alavi A H.Cuckoo search algorithm:a metaheuristic approach to solve structural optimization problems[J].Engineering with computers,2013,29(1):17-35 [17] Ouaarab A,Ahiod B,Yang X S.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing and Applications,2014,24(7/8):1659-1669 [18] 邱卫东,陈燕,李洁萍,等.一种实时异构嵌入式系统的任务调度算法[J].软件学报,2004,15(4):504-511 [19] Yang X S,Deb S.Cuckoo search via Lévy flights[C]∥World Congress on Nature & Biologically Inspired Computing,2009(NaBIC 2009).IEEE,2009:210-214 [20] Standard Task Graph Set.http://www.kasahara.elec.waseda.ac.jp/schedule/index.html |
No related articles found! |
|