计算机科学 ›› 2014, Vol. 41 ›› Issue (5): 20-23.doi: 10.11896/j.issn.1002-137X.2014.05.004
李静梅,王雪,吴艳霞
LI Jing-mei,WANG Xue and WU Yan-xia
摘要: 异构多核处理器任务调度是高性能计算领域的重要问题。针对优先级列表调度算法中存在的优先级排序方法失当、调度结果不理想的问题,提出一种改进的优先级列表任务调度算法。该算法对传统优先级列表任务调度中以任务执行时间平均值作为参数的优先级计算方式进行优化,提出一种基于异构核性能差异性、依赖任务特征加权优先级的排序方式。在此基础上,以当前格局下每个任务的向后关键路径执行时间为权值作为任务分配到处理器内核的依据,克服贪心思想在内核选择中带来的局部最优解问题。此外,在任务分配阶段利用任务复制和区间插入技术,缩短任务最早开始时间,提高处理器利用率。实例分析和模拟实验结果表明,该算法可有效降低任务的执行时间,能发挥异构多核处理器优势。
[1] 张建军,宋业新,旷文.基于异构环境的Out_Tree任务图的调度算法[J].计算机科学,2013,0(4):107-111 [2] Topcuoglu H,Hariri S,Wu Min-you.Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[J].IEEE Transactions on parallel and distributed systems,2002,13(3):260-274 [3] Prashanth C,Sai Ran-ga.Algorithms for task scheduling in heterogeneous computing environments[D].Alabama:Auburn University,2006 [4] Ullman J D.Np-complete scheduling problem[J].Journal ofComputer and System Sciences,1975,10(3):384-393 [5] Hagras T,Janecek J.A high performance low complexity algorithm for compile-time task scheduling in heterogeneous systems[J].Parallel computing,2005,31(7):653-670 [6] Daolud 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 [7] 何琨,赵勇,黄文奇.基于任务复制的分簇与调度算法[J].计算机学报,2008,31(5):733-740 [8] Darbha S,Agrawal D P.Optimal scheduling algorithm for distributed memory machines[J].IEEE transactions on parallel and distributed systems,1998,9(1):87-95 [9] 王小非,方明.一种基于调度簇树的周期性分布实时任务调度算法[J].计算机科学,2007,4(3):256-261 [10] 曹仰杰,钱德沛,伍卫国,等.众核处理器系统核资源动态分组的自适应调度算法[J].软件学报,2012,3(2):240-252 |
No related articles found! |
|