同构DVS集群中基于自适应阈值的并行任务节能调度算法  

Adaptive Threshold-Based Energy-Efficient Scheduling Algorithm for Parallel Tasks on Homogeneous DVS-Enabled Clusters

作　　者：刘伟[1,2,3,4] 尹行[1] 段玉光[1] 杜薇[1,2,3] 王伟[3,4] 曾国荪[3,4] 

机构地区：[1]武汉理工大学计算机科学与技术学院,武汉430063 [2]武汉大学软件工程国家重点实验室,武汉430072 [3]同济大学嵌入式系统与服务计算教育部重点实验室,上海200092 [4]同济大学计算机科学与技术系,上海200092

出　　处：《计算机学报》2013年第2期393-407,共15页Chinese Journal of Computers

基　　金：国家自然科学基金(61202173;61272107;61103068);高等学校博士学科点专项科研基金(20090072110035;20110072120017);武汉大学软件工程国家重点实验室开放基金(SKLSE20080720;SKLSE2012-09-29);同济大学嵌入式系统与服务计算教育部重点实验室开放基金资助

摘　　要：目前,高能效的并行任务调度算法设计已经成为集群系统的研究热点.现有基于复制的节能调度算法主要利用阈值平衡系统的性能和能耗,但随机设置的阈值无法根据性能需求和环境参数等特征自动调节,导致调度算法存在一定的局限性.文中提出一种面向同构集群系统的两阶段节能调度算法ATES(Adaptive Threshold-basedEnergy-efficient Scheduling).首先,设计一种基于自适应阈值的任务复制策略,该策略能够自动计算最佳阈值,利用该阈值获取近似最优的任务分组.然后,将各分组任务调度到支持DVS的处理器上,并充分利用任务之间的空闲时间降低处理器电压.该算法将任务复制策略与电压调节技术有机结合,在调度过程中能够自动调整阈值,有效提高调度算法的能效.为了验证ATES算法的合理性,通过典型应用进行仿真实验,并与常见任务调度算法进行比较,结果表明ATES算法能够更好地实现性能和能耗之间的平衡.Increasing attention has been directly towards the energy efficient scheduling algo- rithms for parallel applications in high performance clusters. The existing duplication-based ener- gy scheduling algorithms mainly leverage a threshold to balance system performance and energy consumption. However, the threshold is given randomly which cannot flexibly adapt to the clus- ter system and application performance requirements, thus making the ideal energy efficient scheduling results. In this paper, we propose a novel two-phase Adaptive Threshold-based Energy- efficient Scheduling algorithm fATES）. At first, we propose an adaptive threshold-based task duplication strategy, which can obtain an optimal tnresnom. It then leverages the optimal threshold to balance schedule lengths and energy savings by selectively replicating predecessor of a task. Therefore, the proposed task duplication strategy can get the suboptimal task groups. Then, it schedules the groups on the DVS-enabled processors to reduce processor energy whenever tasks have slack time due to task dependencies. The algorithm combines DVS（Dynamic Voltage Scal- ing） technique with adaptive threshold-based task duplication strategy. It justifies the threshold automatically to improve the energy efficiency of the scheduling algorithm. To illustrate the effec- tiveness of ATES, we simulate the real-world applications and compare ATES with the other four common task scheduling algorithms. Extensive experiment results show that our algorithm can much effectively balance schedule lengths and energy savings.

关 键 词：高性能集群 动态电压调节 任务复制 自适应阈值 调度算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]