摘要
提出了一种混合静态调度算法—Hybrid Successor Concerned Heuristic-Genetic Scheduling(HSCGS).该算法分为启发式算法和遗传算法两个阶段.第一阶段采用考虑后继节点的列表启发式调度算法(SCLS)产生一个近似最优的调度结果.SCLS算法在优先级计算和计算单元选择阶段都充分考虑了当前节点的调度对后继节点产生的影响.第二阶段采用改进的遗传算法—IGA,对上一阶段的调度结果进行迭代优化.IGA算法在优选之前加入了一个预处理阶段,去除部分重复的个体,以避免遗传算法由于"再生"现象而陷入局部优化.IGA算法的优选阶段采用三重优选方案,既达到了优化的效果,又保持了种群的多样性.实验部分分别使用随机应用程序和几种标准应用程序,将HSCGS与几种具有代表性的调度算法进行了对比测试.结果显示HSCGS的调度结果优于其他算法,而且优势随着计算单元间通信带宽异构系数增大而增加.
Propose a novel hybrid static scheduling algorithm named Hybrid Successor Concerned Heuristic-Genetic Scheduling （HSCGS） algorithm. The algorithm is a combination of heuristic and genetic scheduling algorithm. In the first phase we propose a heuristic algorithm named Successor Concerned List Heuristic Scheduling （SCLS） to generate a high quality scheduling result. SCLS algorithm takes the impact of current task ＇s scheduling to its successor into account. The second phase implements an Improved Genetic Algorithm （IGA） for scheduling, to optimize the scheduling results of SCLS iteratively. The comparison experiments are based on both random generated applications and some real world applications. The performance of HSCGS is compared with some famous task scheduling algorithms, such as HEFT and DLS. The results show that HSCGS is the best of them, and the advantages go up with the increase of the heterogeneous factor of inter-core link bandwidth.
出处
《微电子学与计算机》
CSCD
北大核心
2013年第6期61-65,共5页
Microelectronics & Computer
基金
西北工业大学研究生创业种子基金(Z2012126)
关键词
异构多核
任务调度
启发式
遗传算法
有向无环图
heterogeneous multi-core
task scheduling
heuristic algorithm
genetic algorithm
directed acyclicgraph
