一种面向同构集群系统的并行任务节能调度优化方法

《一种面向同构集群系统的并行任务节能调度优化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３５卷第３期计算机学报Ｖｏｌ．３５Ｎｏ．３２０１２年３月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＭａｒ．２０１２一种面向同构集群系统的并行任务节能调度优化方法李新１）贾智平１）鞠雷１）赵衍恒１）宗子良２）１）（山东大学计算机科学与技术学院济南２５０１０１）２）（德克萨斯州立大学计算机科学系圣马科斯７８６６６美国）摘要节能调度算法设计是高性能计算领域中的一个研究热点．复制调度算法能够减少后继任务等待延时，缩短任务总体调度时间，但是耗费了更多的能量．为此，作者提出一种启发式处理器合并优化方法ＰＲＯ．该方法按照任务最早开始时间和最早

2、结束时间查找处理器时间空隙，将轻负载处理器上的任务重新分配到其它处理器上，从而减少使用的处理器数目，降低系统总体能耗．实验结果表明，和已有的复制任务调度算法ＴＤＳ、ＥＡＤ和ＰＥＢＤ相比，优化后的调度算法在不增加调度时间的条件下，能够明显减少使用的处理器数和系统总体能耗，从而更好地实现性能和能耗之间的平衡．关键词绿色网络；集群；并行；同构；前驱约束；节能调度；绿色计算中图法分类号ＴＰ３９３犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１２．００５９１犈狀犲狉犵狔犈犳犳犻犮犻犲狀狋犛犮犺犲犱狌犾犻狀犵犪狀犱犗狆狋犻犿犻狕犪狋犻狅狀犳狅狉犘

3、犪狉犪犾犾犲犾犜犪狊犽狊狅狀犎狅犿狅犵犲狀犲狅狌狊犆犾狌狊狋犲狉狊ＬＩＸｉｎ１）ＪＩＡＺｈｉＰｉｎｇ１）ＪＵＬｅｉ１）ＺＨＡＯＹａｎＨｅｎｇ１）ＺＯＮＧＺｉＬｉａｎｇ２）１）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犛犺犪狀犱狅狀犵犝狀犻狏犲狉狊犻狋狔，犑犻狀犪狀２５０１０１）２）（犇犲狆犪狉狋犿犲狀狋狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲，犜犲狓犪狊犛狋犪狋犲犝狀犻狏犲狉狊犻狋狔，犛犪狀犕犪狉犮狅狊犜犡７８６６６，犝犛犃）犃犫狊狋狉犪犮狋Ｔｈｅｄｅｓｉｇｎｏｆｅｎｅｒｇｙｅｆｆｉｃｉｅｎｔｓｃｈｅｄ

4、ｕｌｉｎｇａｌｇｏｒｉｔｈｍｓｈａｓｂｅｃｏｍｅａｈｏｔｒｅｓｅａｒｃｈｔｏｐｉｃｉｎｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｃｏｍｐｕｔｉｎｇ．Ｔｏｓｈｏｒｔｅｎｓｃｈｅｄｕｌｅｌｅｎｇｔｈｏｆｐａｒａｌｌｅｌｔａｓｋｓｗｉｔｈｐｒｅｃｅｄｅｎｃｅｃｏｎｓｔｒａｉｎｔｓ，ｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓｃｏｕｌｄｄｕｐｌｉｃａｔｅｔａｓｋｓｏｎｃｒｉｔｉｃａｌｐａｔｈｓｔｏａｖｏｉｄｃｏｍｍｕｎｉｃａｔｉｏｎｄｅｌａｙｃａｕｓｅｄｂｙｉｎｔｅｒｔａｓｋｄｅｐｅｎｄｅｎｃｅ．Ｈｏｗｅｖｅｒ，ｔａｓｋｄｕｐｌｉｃａｔｉｏｎｓｉｎｃｕｒｍ

5、ｏｒｅｅｎｅｒｇｙｃｏｎｓｕｍｐｔｉｏｎ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｐｒｏｐｏｓｅａｈｅｕｒｉｓｔｉｃＰｒｏｃｅｓｓｏｒＲｅｄｕｃｔｉｏｎＯｐｔｉｍｉｚｉｎｇ（ＰＲＯ）ａｐｐｒｏａｃｈｔｏｒｅｄｕｃｅｔｈｅｎｕｍｂｅｒｏｆｐｒｏｃｅｓｓｏｒｓｕｓｅｄｔｏｒｕｎｐａｒａｌｌｅｌｔａｓｋｓ，ｔｈｅｒｅｂｙｄｅｃｒｅａｓｉｎｇｓｙｓｔｅｍｅｎｅｒｇｙｃｏｎｓｕｍｐｔｉｏｎ．ＴｈｅＰＲＯａｐｐｒｏａｃｈｃａｎｆｉｎｄａｐｐｒｏｐｒｉａｔｅｔｉｍｅｓｌｏｔｓｔｏａｃｃｏｍｍｏｄａｔｅｔａｓｋｓｆｒｏｍｌｏｗｕｔｉｌｉｚｅｄｐｒｏｃｅｓｓｏｒｓ

6、ａｃｃｏｒｄｉｎｇｔｏｔｈｅｉｒｅａｒｌｉｅｓｔｓｔａｒｔｔｉｍｅａｎｄｅａｒｌｉｅｓｔｃｏｍｐｌｅｔｅｔｉｍｅ．ＥｘｔｅｎｓｉｖｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄＰＲＯａｐｐｒｏａｃｈ，ｃｏｍｐａｒｅｄｔｏｅｘｉｓｔｉｎｇｄｕｐｌｉｃａｔｉｏｎｂａｓｅｄｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓ，ｓｕｃｈａｓＴａｓｋＤｕｐｌｉｃａｔｉｏｎＳｃｈｅｄｕｌｉｎｇ（ＴＤＳ），ＥｎｅｒｇｙＡｗａｒｅＤｕｐｌｉｃａｔｉｏｎ（ＥＡＤ）ａｎｄＰｅｒｆｏｒｍａｎｃｅＥｎｅｒｇｙＢａｌａｎｃｅｄＤｕｐｌ

7、ｉｃａｔｉｏｎ（ＰＥＢＤ）ａｌｇｏｒｉｔｈｍｓ，ｃａｎｅｆｆｅｃｔｉｖｅｌｙｄｅｃｒｅａｓｅｔｈｅｎｕｍｂｅｒｏｆｕｓｅｄｐｒｏｃｅｓｓｏｒｓａｎｄｓａｖｅｅｎｅｒｇｙｗｉｔｈｏｕｔｐｅｒｆｏｒｍａｎｃｅｄｅｇｒａｄａｔｉｏｎ．犓犲狔狑狅狉犱狊ｇｒｅｅｎｎｅｔｗｏｒｋ；ｃｌｕｓｔｅｒ；ｐａｒａｌｌｅｌ；ｈｏｍｏｇｅｎｏｕｓ；ｐｒｅｃｅｄｅｎｃｅｃｏｎｓｔｒａｉｎｔ；ｅｎｅｒｇｙｅｆｆｉｃｉｅｎｔｓｃｈｅｄｕｌｉｎｇ；ｇｒｅｅｎｃｏｍｐｕｔｉｎｇ收稿日期：２０１１０８２５；最终修改稿收到日期：２０１２０１１０．本课题得到国家自然科

8、学基金（６０９０３０３１，６１０７００２２）、Ｕ．Ｓ．ＮａｔｉｏｎａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎ（ＣＮＳ０９１５７６２，ＣＮＳ１１１８０４３）、山东省自然科学基金（ＺＲ２０１０ＦＭ