论文部分内容阅读
随着多核技术的快速发展,并行处理得到了广泛研究和应用。能耗管理不仅是电池供电设备的一个重要的研究方向,而且在大规模的多核系统中也越来越重要和复杂。因此,多核系统上的并行实时任务的节能调度成为多核系统的一个重要的研究方向。现有的关于多核上节能调度方面的研究,主要是针对串行任务(sequential tasks)模型。该模型中每个任务每次只能在一个处理器上运行,通过优化任务调度最小化系统的最早完成时间(makespan)实现系统最小能耗。目前还没有人对多核上的并行任务(parallel tasks)模型,即每个任务可以同时在多个处理器上运行的节能调度问题进行研究。本文基于并行任务模型,并且考虑到实时任务的实时性要求,研究了2种不同类型的并行任务并给出最小能耗算法。一类是每个任务都事先确定好运行时所使用的处理器核心个数的严格并行度(Rigid)实时任务。另外一类是每个任务运行时所使用的处理器核心个数不是事先确定的,其将要使用的处理的个数在被调度时才分配的可塑并行度(Moldable)实时任务。对严格并行度实时任务,本文首先给出3种基于层调度(level-packing)的启发式任务调度算法研究该类任务的调度,然后设计了一个多项式时间复杂度的任务执行频率确定算法,使实时任务运行完成时系统的能耗最小,并通过数学公式证明出由该算法求解出的基于层调度的任务调度结果的最优性。针对可塑并行度实时任务,本文给出了任务执行速度提升与所使用处理器核心个数成非单调关系的次线性加速比模型(Sublinear)下多项式复杂的节能调度算法,完成该类任务所使用处理个数的分配、任务调度和执行频率分配,实现运行该类任务的系统能耗最小。由于本文是首次对并行实时任务系统的节能调度问题进行研究的,所以在模拟试验环节,不仅对本文提出的算法进行了模拟,而且还为其设计的相应的对比试验。实验结果显示,本文改进的层调度算法相对于经典层调度算法能够节能13.5%到17.8%,而次线性加速比模型下的可塑并行任务节能调度算法相对于用最小最早完成时间方法得到的最小能耗,可以节能14.7%到28.6%。