论文部分内容阅读
随着半导体技术的飞速发展,片上多核处理器芯片(Chip Multi-Processor,CMP)已经成为高性能微处理器的发展潮流。多核处理器规模的不断增加使得制造过程误差、硬件磨损等不可预见的可变因素带来的动态异构性问题日益突出。不可预见的故障会使得芯片上的各个处理器内核在使用过程中物理特性和功能发生变化,它们会在计算性能和功耗等关键参数上变得与预先设计的值不同。如果调度器忽略这种差异,将会造成处理器芯片性能与能耗上的损失。本文针对由不可预见因素导致的动态异构CMP上的任务调度问题开展研究工作,本文主要研究工作如下:首先,构建了具有可扩展性的调度算法仿真平台。该平台将多个单核模拟器互连,并能够对每个单核模拟器上的性能与能耗数据进行统计。该平台能够通过改变单核模拟器的静态配置来模拟同构多核处理器由于硬错误而导致降级的场景。本文构建的多核处理器模拟平台具有以下优点:(1)调度算法模拟运行速度快。(2)能够模拟不可预见动态异构。(3)可扩展性强,能够模拟大规模片上多核处理器。其次,已有的针对多核处理器不可预见故障的任务调度算法虽然可以提高应用线程的计算性能和能量的有效性,但在调度决策过程中需要在不同内核上通过交换执行线程并采样获得其运行时性能数据,开销较大。为了减少线程迁移和采样的次数,本文提出了面向动态异构多处理器的禁忌搜索调度算法(TSU,TabuSearch-based UnpredictedScheduling Algorithm)。该算法考虑到程序的计算性能和能量消耗在较为细粒度的执行阶段内不会有突然的变化,通过禁忌表来记录线程采样历史数据,找到线程“交换对”在各种调度策略中的“偏好”。以此为基础,TSU算法使用禁忌表降低线程重复采样次数,有效地减少了线程迁移次数。实验结果表明,TSU调度算法以不超过0.5%的ED~2代价,平均减少了33.6%的线程迁移次数和27.8%的采样次数。更进一步考虑到现有调度算法通过随机选择在两个处理器内核上执行的线程对交换和性能采样的方式较为简单、算法收敛速度慢的缺点,基于某些“线程对”交换后对ED~2的影响很小的事实,本文提出了基于影响力的半在线调度算法(IBS,Impact-based Semi-online Scheduling Algorithm)。该算法选择更有性能优势的线程对进行采样从而加速局部搜索算法的搜索效率。本文提出了“线程对”影响力的评价指标和计算方法,影响力越大的“线程对”交换后ED~2变化越大。IBS调度算法通过优先交换影响力大的“线程对”,提高了算法的收敛速度。实验结果表明,在25个功耗管理时间片上,IBS调度算法的ED~2比局部搜索调度算法平均降低了2.49%;在8核CMP中,当功耗管理时间片在70个以下时,IBS调度算法的ED~2始终低于局部搜索调度算法。