异构云计算系统中能耗约束下并行任务集可靠性最大化算法

刘 科，张龙信，王 兰，王 苗，满君丰

(湖南工业大学 计算机学院，湖南 株洲 412007)

1 引 言

近年来，谷歌、亚马逊、微软、IBM等国际著名云提供商已经在云中大力地加入人工智能应用.人工智能和云计算的组合被称为智能云计算[1].在现代化的数据密集化环境，雾和云服务的部署日益增长，在不同层次需要越来越多的智能，以提供最佳的任务调度决策、虚拟机迁移等[2].为了适应大数据时代的计算服务需求，云计算系统数据中心处理器的数量急剧增加[3].运行规模庞大的数据中心，云计算系统需要消耗大量的电能.据统计，2020年美国所有数据中心的电能增长了14%，达到730亿千瓦时，我国数据中心消耗的电能已超过匈牙利和希腊两国用电总和[4].云计算系统数据中心的能耗问题已经引起了国内外研究人员的广泛关注.

在云计算系统中，降低能耗的方法包含改进硬件技术和设计能耗感知的调度算法，其中，硬件的改进技术包括设计低功耗的处理器和固态驱动等；能耗感知算法的设计包括操作系统级别的电源管理和应用级的电源管理等[5].动态电压和频率缩放(DVFS)技术通过降低处理器的电压和频率从而减少能量的消耗，这已成为一种重要的能耗调节技术[6，7].

由于云计算系统架构的复杂性，其运行过程中发生错误难以避免.同时，减少能量消耗和增强系统可靠性互斥，较低的能量消耗会导致系统可靠性低.近年来有诸多研究表明，动态调节处理器的电压可能导致处理器瞬态故障急剧增加，从而影响系统的可靠性[8-10].异构云计算系统中，除了降低数据中心的能耗，如何保证云系统的可靠性也是衡量服务质量的一个重要课题.

为了解决云计算系统中的高能量消耗问题，科研人员已经提出了大量的节能调度方法.Chen等[11]针对云计算环境中并行任务集的低成本和低能耗的需求，提出了可用的成本开销预分配算法，在满足任务集成本约束下，减少了能量消耗.Tang等[12]在满足基于云计算性能服务水平协议的基础上，提出了一种新的能源感知调度算法，在满足截止期限约束的前提下，有效地减少能源消耗.Li等[13]针对异构分布式计算系统中的并行应用提出了一种增强的调度算法(EECC)，该算法可以在满足给定能耗约束的同时获得更优的调度长度.Zhang等[14]提出异构云计算中成本约束下的工作流能量高效调度算法，算法包括任务优先级的计算、任务预算成本的分配以及最优执行虚拟机和能量高效频率的确定3个阶段，最大限度地节省能量.

以上方法虽然都采用DVFS技术减少云计算系统运行过程中的能量消耗，但并未考虑使用DVFS技术在减少能耗的同时会降低系统可靠性.Zhao等[15]为单处理器实时系统建立了能耗和可靠性之间的关系模型，后来的多处理器系统也使用的此模型解决能耗和可靠性相关的任务调度问题，为本文的研究提供了理论基础.Zhang等[16]针对DVFS技术减少能量消耗会带来可靠性降低的问题，提出了可靠性最大化能量节省策略，有效地提高了异构多处理器的可靠性.Zhang等[17]提出了一种能量和截止时间双重约束下并行应用任务集的可靠性感知算法，进一步提高了系统的可靠性.Xiao等人采用DVFS技术解决异构分布式系统上有能耗约束的并行应用可靠性最大化问题，并提出了MREC算法，该算法主要包含两个阶段，确定任务优先级和选择合适的处理器与频率组合[18].本文针对异构云计算系统中能耗约束下可靠性加强问题，提出了能耗约束下最大化可靠性算法(ERMEC).ERMEC算法主要包含以下3个阶段：1)确保任务的调度顺序不违反任务集的拓扑结构，建立任务的优先排序队列；2)计算任务集的最大能耗，最小能耗以及任务的能耗约束；3)根据任务的能耗约束，确定最优的处理器与频率组合，确保在满足能耗约束的前提下可靠性值最大.异构云计算系统中并行应用任务集调度是NP难问题，属于组合优化的范畴[19].

2 系统模型

本文使用集合U={u1，u2，…，uk}表示一组异构的处理器集合，其中k为云计算系统数据中心处理器的数量，每个处理器都支持DVFS技术.处理器的电压和频率满足随机的均匀分布.任意两个处理器之间可以直接通信，处理器之间的数据通信速率一致.相对于任务的处理时间而言，处理器上频率切换的开销通常很小，在设计调度算法的过程中忽略不计.

2.1 任务模型

异构云计算系统中存在优先约束的任务集通常采用有向无环图(DAG)描述[20]，并使用四元组G={N，E，C，W}表示，其中，N为所有任务的集合，节点ni∈N表示并行应用任务集中第i个任务；E为任务间所有通信链路的集合，边ei，j∈E表示任务ni-nj之间存在的依赖关系，ni是nj的直接前驱节点；C为任务间通信时间的集合，对于ci，j∈C，ci，j表示当任务ni和nj被分配至不同处理器时的通信时间，若两个任务被分配至同一个处理器，则ci，j=0；W是一个|N|×|U|的矩阵，矩阵中的元素wi，j表示任务ni在处理器uj上以最大频率运行时的计算开销.另外，本文使用pred(ni)表示任务ni的直接前驱任务的集合，succ(ni)表示任务ni的直接后继任务的集合，没有直接前驱的任务称为入口任务，没有直接后继的任务称为出口任务.

图1展示了一个包含10个任务的并行应用任务集.根据前文的定义：图1中的节点n1-n10代表并行应用的任务，其中n1为入口任务，n10为出口任务；边e1，2(e1，2∈E)为两个任务间的通信链路，边上的数值表示相连两个任务被分配至不同处理器执行时的平均通信开销.当n2唯一的直接前驱任务n1执行完成并将数据传输至执行n2的处理器时，n2进入准备就绪状态，等待处理器空闲时执行.本文约定，并行应用任务集仅包含一个入口任务和一个出口任务，如果给定的并行应用任务集不符合此约定，可以通过增加零计算的虚拟节点作为入口任务或出口任务，同时增加零通信开销的虚拟通信链路以满足此约定.

图1 一个简单的工作流图

由于处理器的异构性，任务在不同的处理器上的计算时间不同.表1展示了图1中各任务在3个处理器{u1，u2，u3}上对应的计算时间.任务的平均计算时间表达式如式(1)所示：

表1 图1中任务在各处理器上的计算开销

(1)

其中，wi，k为任务ni在处理器uk上以最大频率执行时所需要的时间，|U|为异构云计算系统中处理器的数量.

2.2 能耗模型

异构云计算系统中处理器的功耗分为动态功耗和静态功耗两部分[21].动态功耗指处理器处于激活状态所产生的功耗，它是系统功耗的主要来源，静态功耗指无论系统处于活动状态还是睡眠状态都会持续产生的功耗.基于DVFS技术降低异构分布式系统能耗的设计已经得到了广泛的研究，DVFS技术通过降低电压和频率以减少能量消耗[21].

本文采用乔治梅森大学的Aydin教授等人提出的系统级功率模型[8]为异构云计算系统的功率模型，该模型被广泛用于网格计算、云计算、异构分布式计算[5，6，9，10，15-18].当处理器运行的频率为f时，系统功率定义为：

P(f)=Ps+h(Pind+Pd)=Ps+h(Pind+Ceffm)

(2)

其中，Ps表示静态功率，只有关闭整个系统的电源Ps才能消除，它所引起的能耗很小，在能耗的统计过程中忽略不计；h表示系统的状态，当系统处于活动状态时，h=1；当系统处于关闭状态时，h=0；Pind表示与频率无关的功率，是一个常量；Pd表示与频率相关的动态功率；Cef表示有效开关电容；m表示动态功率指数，通常不小于2.

由于存在与频率无关的动态功率，随着处理器频率的降低，系统的功率随之减低.式(2)为一个关于频率的凸函数，而能耗等于功率乘以时间，因此能耗亦为关于频率的凸函数.每个处理器必然存在一个最优节能频率fme，当处理器的运行频率低于fme后，降低频率将会消耗更多的能量，fme可由式(3)计算得出[16]：

(3)

假设处理器的频率的变化范围为最低频率fmin到最高频率fmax，为了保证能量效率，处理器的最小可用频率flow定义为：

flow=max(fmin，fme)

(4)

因此，可以得到处理器的实际有效频率f的取值范围[flow，fmax].

在包含k个处理器的异构云计算系统中，每个处理器都对应各自的功率，以下为处理器功率参数集合：

·Pind集合：{P1，ind，P2，ind，…，Pk，ind}

·Pd集合：{P1，d，P2，d，…，Pk，d}

·Cef集合：{C1，ef，C2，ef，…，Ck，ef}

·m集合：{m1，ef，m2，ef，…，mk，ef}

·flow集合：{f1，low，f2，low，…，fk，low}

·fmax集合：{f1，max，f2，max，…，fk，max}

任务ni在处理器uk上运行，当处理器的运行频率为fk，h时，完成此任务消耗能量的计算表达式如式(5)所示：

(5)

并行应用任务集的能耗为完成所有任务消耗能量的总和，计算表达式如式(6)所示：

(6)

其中，uord(i)为分配给任务ni的处理器，ford(i)，fz(i)为处理器uord(i)的运行频率.

2.3 可靠性模型

当云计算系统运行时，几乎不可能避免由于软件错误、硬件错误等导致的故障[18].并行应用任务集的可靠性被定义为该任务集在云计算系统上成功完成的概率.瞬态故障满足平均到达率为λ的泊松分布，并且任务运行时发生故障的概率是独立的[16].若λk表示处理器uk单位时间的故障率，则任务ni在处理器uk上以最大频率fk，max运行时的可靠性如式(7)所示[16]：

R(ni，uk)=e-λk×wi，k

(7)

对于支持DVFS技术的处理器而言，以不同的频率运行时系统的故障到达率不同.定义λk，max为处理器uk在最大频率运行状态下的故障到达率，则处理器uk以频率为fk，h运行时的故障到达率λk，h可由式(8)计算[16].

(8)

其中，d为处理器灵敏度因子，用以衡量归一化后处理器的频率改变时系统故障率改变的速率，其取值为常数1.

根据式(7)与式(8)，可以计算出任务ni在处理器uk上以频率为fk，h运行时的可靠性，其计算表达式如式(9)所示[18]：

(9)

由式(9)可得，在同一处理器上，可靠性和频率是单调递增的关系.为了节约能量，动态降低处理器的频率，可能导致可靠性低.DVFS系统中并行应用任务集可靠性的计算表达式如式(10)所示：

(10)

3 能耗约束下最大化可靠性

对于一个给定的并行应用任务集G，在满足指定能耗约束Egoal(G)的前提下，为G中的每个任务选择合适的处理器与执行频率，确保并行应用任务集消耗的能量不会超过能耗约束，同时最大程度地增加并行应用任务集执行可靠性.上述问题的形式化描述如式(11)和式(12)所示：

(11)

Subjectto：Eresult(G)≤Egoal(G)

(12)

其中，Rresult(G)为并行应用任务集执行可靠性，Egoal(G)和Eresult(G)分别为并行应用任务集的能耗约束和实际能量消耗.

3.1 任务优先级排序

定义1.(向上优先等级(ranku))：并行应用任务集中任务的ranku值是基于任务的平均计算成本和平均通信成本计算得出.ranku的计算表达式如式(13)所示：

(13)

3.2 满足能耗约束

为了方便表述，本文定义任务ni的最小能耗Emin(ni)和最大能耗Emax(ni)，由式(5)可知，任务运行的能量消耗与运行频率成正比，即任务运行时消耗的能量随着频率的升高而增加.因此Emin(ni)和Emax(ni)的计算表达式分别如式(14)和式(15)所示：

(14)

(15)

并行应用任务集的总能量消耗为所有任务的能耗之和，因此并行应用任务集的最小能耗Emin(G)和最大能耗Emax(G)表达式定义如下：

(16)

(17)

在并行应用任务集G开始调度之前，它的能耗约束Egoal(G)由用户给定.为保证能耗约束有意义，能耗约束应满足Emin(G)≤Egoal(G)≤Emax(G).本文提出的任务能耗预分配方案由式(18)表示：

(18)

假设等待调度的并行应用任务集按ranku值排序后的任务调度列表为{ns(1)，ns(2)，…，ns(|N|)}.若当前准备就绪的候选任务为ns(i)，则{ns(1)，ns(2)，…，ns(i-1)}表示已经完成调度的任务集合；{ns(i+1)，ns(i+2)，…，ns(|N|)}表示尚未调度的任务集合，此时并行应用的能耗应为：

(19)

根据式(19)将并行应用任务集的能耗约束转移至每个任务，得到任务的能耗约束.任务的能耗约束计算表达式如式(20)所示.在任务的调度过程中，只需为每个任务找到满足能耗约束的处理器与频率的组合即可.

(20)

证明：本文使用数学归纳法来证明通过上述策略对等待调度的任务进行能耗预分配[5]，并行应用中每个任务ns(i)都能被分配一个处理器和频率组合，使并行应用的总能耗满足式(12).

首先，考虑调度列表中第一个任务ns(1).ns(1)是当前被调度的任务，剩下|N|-1个任务还未被调度.根据式(19)和式(20)，可以得到此时应用的总能耗为：

(21)

由式(18)可知：Epre(ns(1))≥Emin(ns(1)).因此，当E(ns(1)，uk，fk，h)=Emin(ns(1))时，式(21)可表示为：

Es(1)(G)=Emin(ns(1))+Egoal(G)-Epre(ns(1))≤Egoal(G)

(22)

对任务ns(1)而言，使用该能耗预分配策略产生的能量满足能耗约束.

不失一般性，调度第i个任务的总能耗为：

(23)

然后，当调度第i+1个任务时，应用的总能耗为：

(24)

结合式(23)和式(24)可得：

(25)

又因Emin(ns(i+1))≤E(ns(i+1)，uk，fk，h)≤Epre(ns(i+1))，由式(25)可得：

Es(i+1)(G)≤Egoal(G)

(26)

通过上述证明可知，本文提出的能耗预分配策略理论上可以满足式(12).

3.3 能耗约束下最大化可靠性算法

算法1.The ERMEC algorithm

输入：G={N，E，C，W}，Egoal(G).

输出：任务集的能耗Eresult(G)和可靠性Rresult(G).

1.计算G中所有节点的ranku值，降序排列，得到任务优先队列task_list

2.计算任务节点的Emin(ni)和Emax(ni)

3.计算任务节点的预分配能耗Epre(ni)

4.while队列task_list非空

5.ni=task_list.out

6.计算任务的能耗约束Egoal(ni)

7.foreachuk∈Udo

8.foreachfk，h∈[fk，max，fk，low]do

9. 计算E(ni，uk，fk，h)

10.ifE(ni，uk，fk，h)>Egoal(ni)then

11. continue;

12.endif

13. 计算R(ni，uk，fk，h)

14.ifR(ni，uk，fk，h)>R(ni，uord(i)，ford(i)，hz(i))

15.upr(i)←ukandfpr(i)，hz(i)←fk，h

16.E(ni，uk，fk，h)←E(ni，uord(i)，ford(i)，hz(i))

17.R(ni，uk，fk，h)←R(ni，uord(i)，ford(i)，hz(i))

18.break;

19.endif

20.endfor

21.endfor

22.endwhile

23.计算任务集的能耗Eresult(G)

24.计算任务集的可靠性Rresult(G)

异构云计算系统中具有能耗约束的并行应用任务集的可靠性最大化算法(ERMEC)的伪代码如算法1所示.步骤1计算并行应用任务集中所有任务的ranku值，并按ranku值非递增方式排序得到任务的调度列表task_list.步骤2计算任务ni的最小能耗Emin(ni)和最大能耗Emax(ni).步骤3计算任务ni的预分配能耗Epre(ni).步骤4-步骤22从任务调度列表中依次取出等待调度的任务，计算其对应的能耗约束，并为其选择该能耗约束下最优的执行处理器及使可靠性值最大的执行频率.其中，步骤5取出task_list中的任务；步骤6根据式(20)计算该任务的能耗约束；步骤7-步骤21为等待调度的任务选择合适的处理器与频率；步骤8从最大频率开始以递减顺序遍历选择的频率，由于较小的频率会导致可靠性值偏低，一旦找到满足任务能耗约束的处理器与频率组合时，则停止遍历该处理器剩下的频率.步骤23统计并行应用任务集的总能量消耗，步骤24计算任务集的可靠性.

不难得出，ERMEC算法的时间复杂度为O(|N|×|U|×|F|)，其中|F|表示所有处理器中从fk，low到fk，max的最大离散频率级别数量.调度过程将遍历调度列表中所有的任务，需要的时间为O(|N|)，为每个任务选择合适的处理器与频率组合消耗的时间为O(|U|×|F|).

3.4 ERMEC算法实例

使用ERMEC算法调度图1所示并行应用任务集，处理器的功率参数如表2所示，每个处理器归一化后的最大频率fk，max为1.0，频率的精度设置为0.01.根据式(16)和式(17)可以计算出并行应用的最小能耗和最大能耗.给定并行应用任务集的能耗约束为Egoal(G)=3×Emin(G)=72.8073.

表2 处理器参数

表3展示了使用ERMEC算法调度并行应用任务集实例的结果，第1列根据ranku值排序得到的任务调度列表.表3中每行的元素分别为任务的编号、任务的能耗约束、任务分配的处理器及其工作频率组合、产生的能耗值和可靠性值.从表3可以看出，每个任务的实际能耗值都小于任务的能耗约束值.并行应用的实际总能耗为72.7985，小于给定的并行应用的能耗约束Egoal(G).使用MREC算法在相同环境下调度同一并行应用任务集得到的可靠性为0.8197.与MREC算法相比，在满足并行应用任务集能耗约束的同时，ERMEC算法使得系统的可靠性提升了19.14%.

表3 使用ERMEC算法调度图1并行应用的分配过程

使用ERMEC算法调度图1所示并行应用任务集的结果如图2所示，调度长度为SL(G)=85.55.

图2 ERMEC算法调度应用结果

4 实 验

4.1 实验设置

本文使用64个不同计算能力、存储空间和带宽的虚拟节点，来模拟异构云计算环境中的64个处理器.实验中任务的计算开销为10h≤wi，k≤100h，处理器的通信开销为10h≤ci，j≤100h，与功率相关的处理器其他重要参数的取值范围：0.03≤Pind≤0.07、0.8≤Cef≤1.2、2.5≤m≤3.0、fmax=1.0G Hz.处理器的工作频率为区间[flow，fmax]内的离散值，其精度为0.01G Hz，处理器在最大频率下运行的故障到达率0.0000001≤λmax≤0.0000128[18].实验中使用Intel Core(TM)i7-9750H CPU @2.60GHz六核处理器，16GB内存，JDK版本为1.8，系统运行环境为Windows 10.

本文选择的对比算法为MREC和EECC*.MREC算法解决基于DVFS的异构分布式系统上能量受限并行应用的可靠性最大问题.EECC*为文献[13]中能耗约束下最小化调度长度EECC算法的扩展，旨在提高并行应用的可靠性.本文采用的算法性能标准指标为并行应用任务集的实际能量消耗和可靠性.

实验中采用两个广泛使用的并行应用任务集，分别为高斯消元(GE)并行应用和快速傅里叶变换(FFT)并行应用.

4.2 GE并行应用任务集

图3 GE并行应用

由图4(a)可得，固定GE并行应用的规模大小，随着能耗约束的增大，并行应用的可靠性不断提高.当能耗约束较小时，即α=7，本文提出的ERMEC算法比MREC、EECC*算法得到的可靠性分别提高了16.25%、11.37%；当能耗约束较大时，即α=4，ERMEC算法比MREC和EECC*算法得到的可靠性平均可提高35.04%、16.65%.

图4 GE并行应用的结果

由图4(b)可得，随着GE并行任务集的规模不断增大，任务集的可靠性都有所下降，这是由于任务的可靠性值小于1，根据式(10)可知，任务集的可靠性为所有任务可靠性的乘积.当GE并行应用的规模较小时，即σ=8，ERMEC算法比MREC、EECC*算法得到的可靠性分别提高了6.38%、5.74%.并且，当GE并行应用的规模较大时，即σ=50，ERMEC算法比MREC、EECC*算法得到的可靠性分别提高了85.24%、45.53%.这表明ERMEC算法对于提高大规模GE并行应用的可靠性更加有效.

4.3 FFT并行应用任务集

FFT由输入向量和进行迭代的蝶形运算组成.若用σ表示FFT并行应用任务集的规模参数，则节点总数满足|N|=(2×σ-1)+σ×log2σ，σ=2y，y为正整数.规模为σ的FFT并行应用包含σ个底层节点.图5为一个σ=4的FFT并行应用任务集.为了保证并行应用出口节点唯一，实验过程中将为FFT任务集添加零计算开销的出口节点nexit，并为所有底层节点和nexit之间添加零通信开销的边.

图5 FFT并行应用

由图6(a)可得，当FFT并行应用的节点数相同时，随着能耗约束的增大，并行应用的可靠性不断提高.当能耗约束较小时，即α=7，ERMEC算法比MREC、EECC*算法得到的可靠性分别提高了14.64%、8.79%.当能耗约束较大时，即α=3，ERMEC算法比MREC、EECC*算法得到的可靠性分别提高了30.55%、13.47%.

图6 FFT并行应用的结果

由图6(b)不难得出，随着FFT并行应用的规模不断增大，应用的可靠性都有所下降，其趋势与GE并行应用的结果相似.当FFT应用的规模较小时，即σ=8，采用ERMEC算法得到的可靠性最大；当FFT并行应用的规模较大时，即σ=128，ERMEC算法比MREC、EECC*算法得到的可靠性分别提高了82.17%、33.46%.这表明ERMEC算法对于提高大规模的FFT并行应用的可靠性更有效.

5 总 结

本文研究异构云计算系统中能耗约束并行应用任务集可靠性加强问题，基于动态电压和频率缩放技术，提出了低时间复杂度的能耗约束下可靠性最大化(ERMEC)算法.ERMEC算法首先使用ranku值对并行应用中所有的任务排序得到优先级列表、计算每个任务的预分配能耗值；再将并行应用任务集的能耗约束转移到每个任务上，得到任务的能耗约束；最后遍历处理器选择该能耗约束下最优的执行处理器及使可靠性值最大的执行频率.实验采用现实世界的大规模GE和FFT并行应用任务集对算法进行性能测试，与现有的MREC算法和改进的EECC*算法相比，本文提出的ERMEC算法比MREC和EECC*算法能获得更高的可靠性值.并且，当并行应用任务集的规模较大时，ERMEC算法对于提高其可靠性更加有效.