论文部分内容阅读
随着CMP的出现,如何提升其运行效率和最大化并行性倍受国内外专家和学者的关注。系统性能的提升不仅与硬件平台有关,同时也离不开硬件平台上的优化软件设计,只有两者充分结合,才能充分发挥硬件平台自身及软件设计的优良性能。因此,CMP任务调度问题已经成为高性能CMP研究领域的热点之一。鉴于CMP平台的优良性能和未来发展趋势,本文将异构CMP上的静态任务调度算法作为研究对象,设计一种适合其硬件平台且性能较好的静态任务调度算法,该算法能够缩短全部任务执行完成时间,充分发挥出异构CMP的性能优势,提升CMP的执行效率。本文通过对CMP架构、任务调度技术及其现有四种经典异构CMP上的静态任务调度算法进行分析,并针对现有静态任务调度算法的不足,提出一种全局较优任务调度算法。新算法首先对任务图中某些特殊任务进行归并优化;然后通过任务分层、标记关键任务和任务优先级权值计算三个过程顺序执行来构造任务调度列表;最后在任务分配的同时加入冗余任务处理过程,两个过程交替进行,直到所有任务调度完成。新算法保证逐层调度任务,考虑赋予关键任务较高优先级,缩短整个任务图的总完成时间。在任务分配时,采用区间插入和任务复制技术,通过在空闲时间段进行必要的插入和复制,复制当前任务的关键父任务来提前当前任务的最早完成时间,同时对冗余任务进行了检测、删除操作,充分利用处理器资源,提前后续任务的最早完成时间;且能及时删除调度结果中的冗余任务,避免处理器资源的浪费,缩短全部任务执行完成时间,最终提升了整个CMP的性能。为了验证全局较优任务调度算法的可行性和高效性,本文采用TGFF随机生成大量具有不同特点的任务图,在不同的硬件条件下对算法进行测试,并在Matlab平台编程实现该算法,验证新算法的调度性能。实验结果表明:新的算法继承了现有算法优先调度关键任务的优点,同时改善了现有算法的任务优先级选取过于单一所产生的局部较优调度结果的问题,且能有效的处理任务复制所带来的冗余;在任务执行过程中,任务间的并行性明显提高,任务总调度长度也明显减小,达到了算法改进的预期效果,实现了全局较优的调度性能,为异构CMP中任务调度问题的研究提供了一定的借鉴意义。