基于时间-能耗权重比的任务调度算法

摘要

异构并行系统是高性能低功耗计算机系统的主要发展趋势之一，异构并行系统下的低功耗研究是近年来学者研究的热点问题。由于动态电压频率调整（DVFS，Dynamic Voltage and Frequency Scaling）技术以及任务调度在能耗优化方面的潜能，近年来不少基于DVFS技术的任务调度算法被提出并取得了不错的效果。然而，这些算法没有综合考虑任务的执行时间和能耗，无法做到时间和能耗的权衡优化，且这些算法在其任务模型中使用平均值表示任务的执行时间和通信时间，这种表示方法不够精确，会对任务调度的性能产生影响。
　　异构并行系统下基于时间-能耗权重比的任务调度算法（Weight-ratio-based Task Scheduling，WTS）与DVFS技术相结合，它同时考虑时间和能耗这两个性能指标，能够根据时间-能耗的权重比为每个任务选择合适的处理器及电压级别，做到时间和能耗的权衡优化，获取相较于现有算法更优的系统加权性能。在任务初次分配阶段，WTS算法为每个任务选择使其加权性能提升值最大的处理器及电压级别；在任务再次优化分配阶段，该算法随机选择一个任务，并将该任务重新分配给相对于原有分配有系统加权性能提升的处理器及电压级别，使系统的加权性能进一步提升。同时，WTS算法考虑到任务执行时间以及任务间通信时间的不确定性，在任务模型中使用近似权重代替平均值，以获取更优的调度性能。
　　为证明WTS算法的有效性，仿真实验将其与两个现有算法在时间、能耗、系统加权性能以及相对性能提升等方面进行了对比，实验结果显示，WTS算法能做到时间和能耗的权衡优化，使系统的加权性能更优，同时在时间和能耗单个性能指标方面也具有优势。