第 24 卷第 8 期
2014 年 8 月
计算机技术与发展
COMPUTER TECHNOLOGY AND DEVELOPMENT
Vol. 24
Aug. 2014
异构云中综合时间能耗成本的任务调度算法
李君，殷小龙，万明祥
(南京邮电大学计算机学院，江苏南京 210003 )
摘 要:针对异构云环境下不合理的任务-资源映射而导致依赖任务在运行过程中产生高能耗的问题，提出→种综合时间
能耗成本的任务调度算法(Time and Energy Consumption Cost Scheduling , TECCS )。根据任务图逐层进行任务调度，面对
同一层任务调度顺序只单独基于时间因素考虑而过于单一的问题，引入通信因子和计算因子，综合时间与能耗成本决定
同一层任务的调度顺序;分析任务之间的依赖关系，自上而下，为任务分配计算节点，使得整个任务在期望完成时间条件
下节省更多能耗。从性能和能耗方面将 TECCS 与 TUGS (Time Unify Greed Scheduling) 、 CATS ( Communication - A ware
Task Scheduling) 、EETDS (Energy Efficient Task Duplication Scheduling)进行比较，结果表明 TECCS 在满足任务期望完成
时间条件下能耗最少。
关键词:异构系统;云数据中心;依赖任务;层次;节能
中图分类号 :T凹93 文献标识码 :A
doi: 10. 3969/j. issn. 1673-629X. 2014. 08. 028
文章编号: 1673-629X( 2014 )08-0121-05
Task Scheduling Algorithm ßased on Time and Energy Consumption
Cost in Heterogeneous Cloud
LI Jun ,YIN Xiao-long ,WAN Ming-xiang
(College of Computer ,Nanjing University of Posts and Te1ecomrnunications , Nanjing 210003 ,China)
Abstract:Facing the problem of high energy consumption produced by unreasonable task-resource mapping inheterogeneous c1oud ,pro-
pose a task scheduling aIgorithm based on time and energy consumption (TECCS) . Dividing the hierarchicaI of the tasks to determine the
order of tasks , and facing the problem of 由e scheduling sequence of the same layer tasks based solely on time factors into consideration
and too one-dimensionaI, introduce communication factor and ∞mputation factor , integrating time and energy consumption cost to deter-
mine the order of the same level t臼ks. AnaIysis of dependencies between tasks , based on hierarchicaI top-町down to task scheduling , make
the whole task completion time under the expected conditions to save more energy. Comparison on performance and energy consumption
is ∞nducted for TECCS wi由 TUGS ( Time Unify Greed Scheduling) , CA TS ( Communication - Aware Task Scheduling) , EETDS (Ener-
gy Efficient Task Duplication Scheduling) . Experimental results show 由at TECCS saves much energy under the condition of task desired
.
Key words: heterogeneous system; c10ud data center; dependent tasks; hierarchical ; energy saving
o 51 士一同
随着云计算正在引领信息产业的新浪潮，云数据
中心的能量消耗逐渐成为制约云计算发展因素之一。
据统计，Google 的云计算数据中心每年消耗的电能为
1 亿千瓦，这相当于一个小型城市的总能耗。由 IDC
提供的报告显示，在最近的 30 年之中，由大规模数据
中心所带来的能源消耗已经增长了 400% ，并且这
数字正快速地持续增长。目前，在全球 70% 的计算中
心中，能耗开销已成为第二大运营开销 [1 -5 J 。为避免
云数据中心的高能耗问题成为制约云计算发展的瓶
颈，高能耗问题亟须解决[←7 J 。
云数据中心的硬件资源通常由大规模的异构计算
节点组成，各计算节点之间通过具有不同传输率的链
路连接而成，构成一个大规模异构云计算环境。任务
调度是云计算的关键技术，是提高系统性能的重要手
段[ 8-13 J 。云计算系统中的一些任务之间往往具有某
种依颇关系，在异构云数据中心，同一个任务在不同计
算节点的执行时间以及任务间的通信在不同传输路径
收稿日期 :2013-10-18 修回日期 :2014-01-20 网络出版时间 :2014-05-21
基金项目:江苏省研究生科研创新计划项目 (CXLXI2_0481 )
仰者简介:李 君(1988-) ，女，硕士研究生，研究方向为绿色计算、任务调度。
网络出版地址:
. 122. 计算机技术与发展 第 24 卷
中的传输时间均有所差异，在任务调度的过程中，不但
要保证任务之间的依赖性不被破坏，还要保证整个任
务在期望完成时间的条件下，能耗开销最小，故异构云
数据中心中依赖任务的节能调度首要问题便是如何确
定任务的调度顺序，其次是如何给任务分配计算节点。
基于不同环境的假设，云计算中节能的依赖任务
调度算法可分为基于同构和基于异构环境两种。文献
[8-9J基于列表调度技术对依赖任务进行节能调度，
其方法均是确定 DAG 任务图的关键路径任务，调节
非关键路径上的任务进行节能调度，然而，其都是基于
同构环境的假设，对于组成云数据中心的异构系统而
言，任务的执行时间和任务间的通信时间都是不确定
的，随着调度而改变。文献[lO J 面向高性能计算和绿
色计算，给出并行任务在异构处理机上时间与能耗的
启发式优化执行算法。但文献中假设任务执行时间与
能耗之间存在线性关系，且算法性能受能耗时间归一
因子的影响较大。文献[ 11 J 设计了异构分布式系统
中能耗感知的任务调度算法，分析相互约束的并行应
用程序，基于 DVFS 技术，利用进程间通信造成的 CPU
空闲时间槽进行电压调节从而减少能耗。文献 [12J
对通信感知的节能任务调度问题进行研究，任务的最
早开始时间和任务最晚完成时间之和决定任务的优先
级，最小优先级最先调度，并通过通信感知算法进行认
证，目的是尽量减少计算节点间的通信量，从而减少节
点间的通信能耗，当计算节点有松弛时间，通过电压调
节减少任务的执行能耗开销。文献[ 13 J 面向异构系
统中依赖任务的节能调度，将任务分组，在为任务分配
计算节点时，通过任务复制减少任务间通信能耗，从而
节省整个任务执行能耗。
文献[lO-13J 均是基于时间因素单独确定任务调
度顺序，确定任务优先级的方法过于单一。首先，一个
任务的调度顺序是由该任务的计算量及其前驱任务之
间的通信量决定，对于依赖任务和异构云数据中心而
言，任务的计算量和任务问通信量存在权重比较，不可
直接相加而确定任务调度顺序;其次，对于节能调度，
时间并不是唯→反映该任务优先级的属性，任务的调
度顺序应由计算节点执行任务需要的执行成本(时
间、能耗)和任务间通信需要的通信成本(时间、能耗)
共同决定。
文中面对异构云数据中心中依赖任务的节能调度
问题，提出了一种基于时间能耗成本的任务调度算法，
在性能和能耗之间达到平衡。主要贡献:
(1)提出一种云计算节能任务调度模型;
(2)提出一种综合时间与能耗成本的方法确定同
层中任务的调度顺序;
(3)通过分析任务之间的依颇关系，自上而下，为
任务分配计算节点，并结合 DVFS 技术进行电压调节;
(4)在任务期望完成时间条件下，节省更多能耗，
实现了性能和能耗之间的平衡。
1 问题建模
由 m个资源和 n 个任务组成的 M*N云计算节
能任务调度模型中，云计算任务调度模型可以描述为
五元组，即 M = (P ， T ， EN ， 0 ， ð) 。其中 ， P 表示由 m
个资源所组成的资源集合 ;T 为 n 个具有依赖关系的
任务组成的任务集合 ;EN 表示任务调度过程中的能
耗开销 o 表示节能调度优化算法;ð 表示云节能调
度系统的调度优化目标函数。其具体特征描述如下:
云资源集合 P = Ipl ，P2' … ，pJ 由 m 个异构计算
节点组成 ， Pj = I 叭， en飞 ， vbj ， ent鸟|包含4 个不同维度
的特征属性，其中，叫表示Pj 的计算能力，文中假设每
个资源均支持 DVFS 技术，有不同的运行速度，因此资
源 Pj 的计算能力 s飞进一步可以刻画为 SVj = I Sjk ,k E
1 ,2 , ... ,q\ ，其中 k 表示节点执行速度的级别 ， Sjmin = 与
< Sj2 < … < Sjq = Sjmax ，在为任务选择合适的计算节点
的过程中，初始一律选择计算节点的最大速度，即
Sjmax en飞表示 Pj 的执行速度的能量消耗率，同样，在
不同执行速度级别下的能量消耗率进一步刻画为:
envj = I eVjk ,k E 1 ， 2 ，…，肘，其中 k 表示节点执行速度
能量消耗率的级别， eVjmin = evβ< eVj1 <…< eVjq =
叫max; vbj 表示资源 Pj 与其他资源的数据传输率， vbJ=
I bj1 ， … ， bjk ， …，ι\ ，其中 bjk 表示资源 Pj 与 Pk 之间的
数据传输率 ent马表示资源 Pj 与其他资源的数据传输
能量消耗率 entrj 勺，… ， tjk ， … ， tjm} ，其中 tjk 表示资
惊 Pj 与 Pk 之间的数据传输能量消耗率。
云任务集合由 n 个具有依赖关系的任务用有向无
环图 (Directed Acyc1ic Graph , DAG) T = (V , E) 表示。
顶点集合 V表示任务 ， V = I V i I 1 "'" i "'" n \ 边集合 E
表示任务之间的依藏关系 ， E = I eij I 1 "三 i "'" n , 1 "", j :运
nl ，其中 eij 表示任务纠传递给任务吨的数据量。
V i Iwι ， pred(vJ ,succ(vJ ,EST(vJ ， ECT( 叭) \
包含 5 个不同维度的特征属性。其中 ， Wi 表示任务 Pι
的计算量 ; pred( v) 表示任务气的直接前驱任务集合，
pred( 马) = I v i I eij E E \ ，没有前驱任务的任务记为入
口任务 succ( vi ) 表示任务纠直接后继任务集合，
succ(vi ) = I 气 I eij ε E\ ，没有后继任务的任务记为出
口任务; EST(飞)为任务 P 的最早开始时间，入口任务
的最早开始时间为 0; ECT(川为任务 vi 的最早完成
时间。
云计算节能任务调度系统的能耗开销主要考虑计
算能耗和通信能耗[ll] ， ecexec ( T ， P) 表示执行所有任务
的计算能耗开销， ec',an( T ， P) 表示执行所有任务的传
第 8 期 李 君等:异构云中综合时间能耗成本的任务调度算法 . 123 .
输能耗开销。云计算节能任务调度系统分配矩阵 x=
lx iQ I 1 运 i 运 n ， 1 :S;;; q :S;;; ml ，飞= 1 表示任务 Vi 分配
到资源节点儿上执行;飞 =0 表示任务 Uι 不在 Pq 上执
行。
ecex气 T ， P) 的计算公式如式(1) :
俨
其中 ， s与l片k 表示计算节点 p岛J 执行任务的处理速度;
ev飞jk 为其能量消耗率。
ec".n( T ， P) 的计算公式如式(2) :
ectra刊P)= ￡￡ z zzzr·η-f-tn(2)
根据式(1)和式(2) 可知，总能耗的计算公式如式
(3) :
EN = ecex飞 T ， P) + ec".气 T ， P) (3)
记任务执行的用户期望时间为盯，整个依赖任务
调度的时间用 Lspan 表示，计算公式如式(4) :
Lspan = max 1 ECT( 叫) I - minl EST( 叭) I (4)
为了保证整个任务调度过程中能耗开销最小，需
要满足目标式(5) ，为了保证任务在期望时间内完成，
需要满足约束条件式(6) :
minimize EN = ecexec ( T ,P) + ec".n( T ,P) (5)
subject to Lspan - Ff ~三 o (6)
2 一种综合时间能耗成本的任务调度算法
一种综合时间能耗成本的调度过程主要包括确定
任务的调度顺序以及为任务分配计算节点。
任务调度顺序的确定
调度的顺序必须保证任务依赖性不被破坏，文中
对任务进行层次划分以确定任务调度次序，针对同一
层中任务调度次序只单独考虑时间因素而过于单一的
问题，引入计算因子和通信因子，综合时间与能耗成本
的方法确定调度次序。
定义 1 :任务的层次为其直接前驱任务中最大层
次加 1 ，用 level( V.) 表示。表达式如下:
level (v i ) = (0 ,if Fed(U)= ￠ (7)
max(level( pred( v.) ) ) + 1 , if . pred( V.) 笋②
定义 2:计算因子 δ 为调度过程中任务计算量权
重。
定义 3:通信因子 a 为调度过程中任务间通信量
的权重。
同一层中的不同任务，按照优先级从大到小的次
序依次分配计算节点，同层中任务 vi 优先级 PL (v.)
按下式确定:
PL(叭 )=ð.maxl 勺 I +δ .Wι (8)
其中 ， maxlejιi 为任务 Vi 与其各直接前驱任务之
间的通信量的最大值 ; Wi 为任务叭的计算量。
计算因子 8 和通信因子 a 反映整个任务调度过程
中任务计算量和任务间通信量的重要程度，即 δ +ð=
1 。欧几里得空间常用于确定权重系数，文中采用欧几
里得距离确定 a 和 δ，具体方法如下:
记 Tran 为整个 DAG任务节点的平均通信时间 ， T，兀ex
为平均计算时间 ， Eιm曰阳‘<c 为整个任务执行的平均计算能
耗， Et阳'.r酬a创.n 为平均通信能耗;记 α叫1 和 α叫2 分别为整个有向
无环图任务节点的王平F均通信时间和平均计算时间占整
个任务执行时间的比例 ;ì记己 β1 和 β2 分别为整个有向无
环图任务节点的平均通信能耗和平均计算能耗占整体
能耗开销的比例;则有:
---c -c-c-x -x-K-e -Te-TeLE
!-ii-]-n
-n-n--m-m-M -Ta-mI-v === 121 ααQY (9)
(10)
、‘，/'EA --A ，，，‘、
E (12) β2 = E.___ + E
记点 A( α1 ,ßl) ， B( 屿，βJ ，综合时间与能耗成本
确定计算因子和通信因子，分别计算 A 与 B 大小，如
式(13 )、 (14) :
dA= 而万万
dB=R可7
(13 )
(14)
则有8=JL a =」」dA + dB' ~ dA + dB 。
任务计算节点的选取
针对 DAG 任务图中某一个任务叭，根据其直接前
驱任务的个数分别讨论，为其选择计算节点:
1 )当前任务 Uι 只有一个直接前驱任务乌，从所有
可用计算节点中选择使当前任务叭的最早开始时间
ESTC川最小的计算节点作为当前任务 vi 的计算节
点;将当前任务盯z 分配给任意一个计算节点 Pk 时的最
早开始时间 EST(ρ 按照式(15) 确定:
EST( 飞) = max 1 ECT( v) + tt( 吨 ，Pm;叭 ，Pk) ,
Mw.;t(Pk) I (15)
式中 ， ECT(v) 为当前任务 vi 的直接前驱任务吨
的最早完成时间 ; Pm 为任务句所分配的计算节点;
M wa;.(Pk) 表示计算节点 Pk 中等待任务队列中所有任务
的最早完成时间的最大值; tt( 吨 ，Pm;Vi'Pk) 为任务约
和 vi 之间的通信量巧在计算节点Pm 和 Pk 之间传输所
需的时间，则h川i ,Pk) = 去。
任务 vi 在计算节点Pk 中的最早完成时间 ECT(v)
. 124. 计算机技术与发展 第 24 卷
按照下式确定:
w
ECT( V ,) = EST( 叫)+i:1711(16)
2) 当前任务 Vi 有至少两个直接前驱任务，则采取
前驱任务节点预分配原则为任务纠分配计算节点。任
务叭的直接前驱任务分配好计算节点后，这些前驱任
务分别为其后继任务 Vi 分配一个预计算节点，则在这
些预计算节点中选择一个计算节点作为飞的计算节
点。
若矶的直接前驱任务有 2 个，记为飞和凡。当对
V， 分配计算节点后，给其直接后继任务 Vi 分配一个计
算节点，从所有可用计算节点中选择使其直接后继任
务矶的最早开始时间 EST1 (v) 最小的计算节点作为
任务叭的预分配计算节点;将任务纠分配给任意一个
计算节点 Pk 时的最早开始时间 EST1 (v) 按照下式确
定:
EST1(vi)=max1ECT(Vj) +u(孔 ，Pm;叭 ，Pk) ,
Mwait(Pk) } (17)
同理 ， Vu 分配结束后从所有可用计算节点中选择
使其直接后继任务叭的最早开始时间。 EST2 (v) 最小
的计算节点作为任务飞的预分配计算节点，将任务 Vi
分配给任意一个计算节点 Pk 时的最早开始时间
EST2 (v) 按照下式确定:
EST2 ( V,) = max 1 ECT( v) + u( 仇 ，Pm;叭 ，Pk) ,
Mwait(Pk) I (18)
任务叭的执行节点是其直接前驱任务给其分配的
使其具有最大最早开始时间节点，如式(19) :
EST( 飞) = max 1 EST1 (vJ ， EST2 ( 叫) I (19)
节点中待执行任务的电压调节
当确定任务飞的计算节点为 Pk 后，计算该计算节
点的空闲时间 slacktime(Pk) ，令
slacktime(Pk) = EST( vJ -
max(wait(k ,ECT(vJ)) (20)
当 slacktime (Pk) >0，表明在计算节点 Pk 中等待
任务队列中所有任务完成之后，任务 Vi 还没有到达计
算节点 Pk ，此时存在空闲时间，基于 DVFS 技术，调节
计算节点 Pk 中等待执行任务的电压。
3 实验及结果分析
将文中提出的算法与文献[ 10 ]中的时间归一贪
婪算法(TUGS) 、文献 [12]中的通信感知的节能调度
算法( CATS) 以及文献[ 13 ]中基于任务复制的节能调
度算法( EETDS) 进行比较。由于文中目的是通过任
务调度实现节能，任务完成时间是评价一个任务调度
算法的性能标准，整个任务调度过程中系统产生的总
能耗能直观表现调度算法节能程度，故评价指标如下:
(1)任务完成时间:为具有最晚完成时间的任务
与最早开始时间任务之差;
(2) 系统总能耗:任务调度中系统产生的能耗。
实验环境及参数设置
仿真实验使用 SimGrid 模拟异构云数据中心，设
置 3 种类型的计算节点分别为 Node1 、 Node2 、 Node3 ，计
算节点速度和计算节点能量消耗率服从均匀分布。各
节点计算速度分别为 200 - 500 kbps 、4∞ -800 kbps 、
700-1 000 kbps;能量消耗率为 1-2 kJ/s 、2-4 kJ/s 、4-
6 kJ/s;通信链路传输为 NET1 ，传输率泡围为 -10
Mbit/s ，链路传输能量消耗率范围为 5-10 kJ/s; 能量
消耗率与通信链路传输率服从均匀分布。异构云数据
中心的计算节点个数 m选为 12 ，每组实验中随机选取
计算节点和通信链路体现云数据中心的异构性。
不同任务个数对算法性能的影晌
本组实验测试任务大小对算法性能的影响。在
CCR= ，任务数目 n = 150 ， 100 ， 300 ， 500 厅00 ， 10∞ i
的条件下进行实验，通过获得的任务完成时间、系统总
能耗开销验证 TECCS 在不同任务数下的适应性。实
验获得的任务完成时间如图 1 所示。
120
foo俨ATS ~ TECCS • EETDS • TUG斗
40
20
。
50 100 300 500 700 1 000
任务个数/个
图 1 不同任务个数时各算法的任务完成时间
由图 1 可知， TECCS 任务完成时间比 CATS 大
% ，比 TUGS 小 % ，比 EETDS 小 % ;算法
CATS 的任务完成时间优于算法 TECCS，因为在为任
务分配调度顺序的时候，CATS 仅仅从时间角度考虑优
先分配当前最需要调度的任务。
由图 2 可知， TECCS 系统总能耗开销比 CATS 小
% ，比 TUGS /J、 % ，比 EETDS /J、 % ;
TECCS 能耗开销优于算法 CATS 、TUGS 和 EETDS。
任务类型(CCR) 对算法性能的影晌
本组实验验证不同任务类型对算法性能的影响。
CCR[14]表示整个任务的平均通信时间与平均计算时
间的比率，反应任务类型。取 n = 200 , m = 12 , CCR =
， ， ， 1 ， 2 ， 。通过实验获得任务完成
时间和系统总能耗开销验证算法的性能。获得的任务
完成时间如图 3 所示。
第 8 期 李 君等:异构云中综合时间能耗成本的任务调度算法 • 125 •
4
:;J
o 芝 3
J!l!;
时:::
墨 2
毒1. 5
1喝 I
任务个数/个
国 2 不同任务个数时各算法的总能耗开销
50 700 1000 100
-Pδ--T
且一
-AA--plu--·--ed--FU--pu--h
也一
-TA--囚一•
ed-
-nu--町一-pu--翻一-cd{ -FU
•
-Nu--TA →
oM
一
}ltιfll4 巳UAHVRυAYA"Aqd
05050 η3
刊，"nr"
咱i1A
的\应苦货
Mhhm
剧中
5
0 O. 75 2
CCR
圈 3 不同 CCR 时各算法的任务完成时间
由图 3 可知，TECCS 的平均任务完成时间比 CATS
小 % ，比 EETDS 大毛，比 TUGS 大% ;随着
CCR 值的增加，任务间的通信增加，各算法的任务完
成时间均增加。在 CCR 值很小，为 时，由于任务
间的通信较少，算法 TECCS 的任务完成时间略大于算
法 CATS。
由图 4 可知，算法 TECCS 的平均系统总能耗开销
比 TUGS IJ、 % ，比 EETDS IJ、 1 1. 2% ，比 CATS 小
% ;随着 CCR 的增加，算法 TECCS 的系统总能耗开
销明显优于 CATS。
号 3.: I !h豁川川T町配肌ω 帽 αm臼 • EETDS呻叫.配川T凹U
骂恋11' 3
告
4吕 2
鸡1. 551
。
O. 25 O. 5 O. 75 2 2. 5
CCR
图 4 不同 CCR 时各算法的总能耗开销
4 结束语
文中研究了异构云环境下依赖任务的节能调度问
题，仿真结果表明， TECCS 调度策略在任务完成时间
和能量消耗上能有效地达到平衡。
参考文献:
[1 J Jifang. 云计算与能源管理[EB/OLJ. 201 1. http://www. jiι
ang360. com/news/20l1112. html.
[2J 刘 鹏.云计算[MJ. 北京:电子工业出版社，201 1.
[3J 周洪波.云计算技术、应用、标准和商业模式[MJ. 北京:电
子工业出版社，201 1.
[4J 云计算[EB/OLJ. 2013. http://baike. baidu. com/viewl
1316082. htm.
[ 5 J Chinadaily. 打造绿色节能的云计算数据中心 [EB/OLJ.
201 1.
201 1. html.
[6J 张法，Anta A F，王林，等.网络能耗系统模型及能效
算法[JJ. 计算机学报，2012 ，35 (3) :603-615.
[7J 林闯，回源，姚敏.绿色网络和绿色评价:节能机制、
模型和评价[JJ. 计算机学报，2011 ,34( 4) :593-612.
[8 J Zhang Y M, Hu X B. Task scheduling and voltage selection for
energy- minimization [ C JIIProceedings of DAC. New Orle-
ans ,LA:[. J ,2010.
[9 J Kang J , Ranka S. DVS based energy minimization algorithm for
parallel machines [ C J IIProc of IEEE international symposium
on parallel and distributed processing. Miami , FL: IEEE ,
2008 ,1 -12
[lO J Huang Qingjia , Su Sen , Li Jian , et a!. Enhanced energy-effi-
cient scheduling for parallel applications in cloud [ C J IIPro-
ceedings of the 2012 12th IEEEI ACM international symposi-
um on cluster , cloud and grid computing. OUawa , ON: IEEE ,
2012 ,781-786.
[ 11 J Liu Y ongpeng ,Zhu Hong , Lu Kai , et a!. A power provision and
capping architecture 岛r large scale systems [ C J IIProc of
2012 IEEE 26th international parallel and distributed proce崎
ing symposium workshops & PhD forum. Shanghai: IEEE ,
2012 ,954-963.
[12J Varatkar G,Marculescu R. Communication-aware task sched-
uling and voltage selection for total systems energy minimiza-
tion [ C J IIProceedings of the 2∞3 international conference on
computer aided design. [s.!. J :IEEE ,2003 :510-517.
[13 J 张建军，李庆华，瞿 勇.基于任务复制的调度算法[1].计
算机工程与设计，2棚，如何) :1896-1899.
[14J 施步青.基于能量优化的网格资源调度算法研究 [D J. 武
汉:武汉理工大学，2∞9.
