论文部分内容阅读
伴随着半导体制造工艺的发展,单位面积内所能集成的晶体管的数目已经达到极限,单核处理器碰到了无法逾越的障碍,多核处理器逐渐变成人们研究的热门和重点。多核处理器分为同构多核处理器和异构多核处理器,专家学者和界内人士普遍认为异构多核处理器将会是未来的主流处理器。任务调度的顺序将会直接影响处理器的性能,因此,异构多核处理器的任务调度研究已经成为研究热点。异构多核处理器的任务调度已经被证明是NP完全问题,目前还没有算法可以在多项式时间内求得最优解,现有算法大都是使用启发式的算法求得近似解,而其中的基于列表调度算法应用较为广泛。经典的基于列表调度算法有HEFT(Heterogeneous Earlier Finish Time)算法和HCNF(Heterogeneous Critical Node First)算法。HEFT算法按照ranku非递增次序调度任务,使用区间插入技术分配任务。HCNF算法优先调度关键任务,使用任务复制技术分配任务。以上算法存在调度结果不理想、处理器空闲时间段较多等问题,众多专家学者对此都提出了改进方案。综合考虑任务的约束依赖关系对调度结果的影响,使用区间插入技术和任务复制技术充分利用处理器的空闲时间段。本文吸取典型算法的优点,并综合专家学者的改进策略,在现有算法的基础上加以改进。为了评价改进算法的性能,本文通过具体的测试用例说明改进算法的具体实现过程,并对比调度结果,接着设计测试方案,调度随机生成的DAG任务图集,对实验结果进行分析比较。通过实验证明,改进算法可以在一定程度上缩短任务调度的长度,提高处理器的性能。