论文部分内容阅读
由于传统单核处理器的性能已经遇到发展瓶颈,多核处理器应运而生并获得广泛应用。作为多核技术的一个重要方面,任务调度是备受关注的一类NPC(Non-deterministic Polynomial Complete)问题。对于多核处理器的静态任务调度问题,经典列表调度(Simple List Scheduling, SLS)算法难以获得满意的调度解。本文从经典列表调度算法缺陷——只考虑任务优先级列表而忽略其它对应于更好调度结果的任务图拓扑序列出发,以拓展任务图拓扑序列搜索空间为指导,提出了迭代型列表调度方法,并给出两种迭代型列表调度算法实现：ILS-Mb (Iterative List Scheduling with Macroblock)和ILS-RS (Iterative List Scheduling with Random Swapping).其中迭代型列表调度算法ILS-Mb通过遍历宏块拓扑序列扩大任务图拓扑序列搜索空间,迭代型列表调度算法ILS-RS则通过对换两个随机任务的优先级以生成新的任务图拓扑序列。ILS-Mb算法和ILS-RS算法的共同之处在于多次进行列表调度并根据调度长度最小化原则筛选最优调度解。本文进一步地结合粒子群算法采用多个初始最优解的基本思路提出组合型列表调度方法。组合型列表调度方法以多个最优任务图拓扑序列作为初始解避免单个任务图拓扑序列陷入局部最优解。迭代型列表调度方法和组合型列表调度方法的结合形成迭代-组合型列表调度方法,以更高的算法时间复杂度以期获取更小的调度长度。文中通过理论分析证明,对于任意的一个任务图,两种迭代型列表调度方法所得的调度长度必不大于经典列表调度算法。为证实本文提出的迭代型列表调度方法的良好性能,文中采用四种常见类型任务图生成大量的任务图样本进行两个部分的对比实验。统计结果首先表明：在全互联通讯环境迭代型的列表调度算法ILS-Mb和ILS-RS能够有效改善经典列表调度算法的调度解,尤其在通信代价比超过1的情况下,调度性能提升超过14.6%,最大的调度性能提升达到102.8%以上：在片上网络通讯环境ILS-Mb算法和ILS-RS算法的相对性能优势更加明显。统计结果指出迭代型列表调度算法的调度效果优于ALS (Advanced List Scheduling)和CPOP (Critical Path on Processor)算法。实验数据还表明ILS-Mb和ILS-RS算法对调度解初始值不具有敏感性。