通过在不同的状态下进行速度调节能够达到降低能耗的目的，研究了基于随机服务决策网模型的云计算速度动态优化的技术。这种模型将随机Petri网络和Markov决策过程模型结合在一起，从而能够动态调整速度调节策略和进行性能评估。同时这种模型是以服务为导向的，因此能够运用典型模式将复杂模型简化为具有较小状态空间的简单模型。这种模型能够描述复杂的系统行为和决策过程，仿真也表明了这种模型的有效性。
第9期 罗侃:基于随机服务决策网的云计算速度调节动态优化技术研究 2793 图1所示的并行路山的细节图如图3所示。过渡时间 图1所示的顺序路由的细节图如图6所示。过渡状态 T ,T简化为了图4所示的选择路由的单一的T1,Tm-、T3、T 7简化为单一的状态T,其中开启率 其中开启率和奖励函数分别满足式(1)和(2)。 和奖励函数满足式(7)和(8) 选择路由就是可能会有多个过渡状态开启,但是一次只能 Incout iterative routing 开启一个过渡状态。选择路由的细节图如图4所示。每一个 点分解为多条支路.起始位置的信令可以一定的慨率开启任意 条支路。在选择路由中,等效过度状态t,期望开启率λ,奖 励值r满足 1 (3) buffe A ∑A,r 图5迭代路由的细节图 A sequence ro 图1所示的选择路由的细节图如图4所示。过渡状态 mn,71简化为单一的状态T,如图5所示,其中开启率和 奖励函数满足式(3)和(4)。 timeout 图6顺序路由细节图 4模型分析与策略优化 模型分析 简化的性能和奖励等效的SDN模型是离散事件触发的 T uting 且决策时间在需求到达或者完成时。 1)行为空间与每一个状态对应的两个独立的行为空间 分别为#Pu=1,#Po3对于状态#Pucm=1,行为空间为 图3并行路由细节图 1D2n,Dm21},Dmn表示维持当前的高服务速率状态,Dm表示 转换到低服务速率状态。对于状态#P1ow=1,行为空间为 T. Memcache pyu- selective ut 1D12,D,2n},Da表示维持当前的低服务速率状态,D12表示转 换到高服务速率状态。 2)代价函数对行为a的每一个系统行为会产生一个代 价,C(a)。这个代价由提供cst(a)速率的服务所需要的功 耗决定的或者是由脉冲转换所需要的功耗cost1(a)造成的。 除此之外,每一个需求的完成将会产生一个激励R,对式(10) 所示的奖励函数。 图4选择路由细节图 3)策略优化的目的是找到个最优策珞丌,使得累积的 迭代路由意味着一个特定的行为重复进行。迭代路由的 奖励数最大化。 细节图如图5所小。在迭代路由中等效过渡状态t,期望开启 率λ、奖励值r满足 maxE∑R(t) (9) A1+2+A 十A2 R(s(t),a,s(+1) A1a R-cost,(a)-cost,(a) if s(1+1)=s(1)+1AaE UDI r=(r2+n1)+(1+r3 (6) if s(t+1)=s(t)+lAaE DIH U DI 图1所示的诜择路山的细节图如图5所示。过渡状态 t, (a) ifs(t+1)=s(1)-1∧a∈D2UD Tn、T,Tm简化为单一的状态T,如图6所示,其中开启 0 率和奖励函数满足式(5)和(6) 顺序路由按照一定的顺序,一个一个地处理请求。顺序路42MDP模型 由的细节图如图6所小。在顺序路由中等效过渡状态t期望 采用文献[10]提出的方法来得到图7所示的MDP模型的 开启率λ、奖励值r满足 同构MDP。在图7中,圆圈表示系统状态,方框表示与状相 关的行为 MDP模型是一个嵌入离散链(DIMC)的连续时间 Markov (8) 链(CTMC)。P?(s(4+1)|s(t),a)表示对于行为a,系统在时 2794· 计算机应用研究 第31卷 间t山状态s(t)在时间t+1转换到状态s(t+1)的概率。状态 表1仿真中用到的主要参数 转换慨率如式(11)所示 name H A arrival +Ahigh 3.04.0:5.0 access.i ifs(t+1)=s(:)+1 H HIGH P(s(t+1)ls(t),) T 5.0/10.0 10.0 ifs(t+1)=s(:)-1,=L 图8所示为最初的SDN模型和优化后的SSDN模型关于 等待队列长度的关系图。本文给出的模型精简方法有效地简 ifs(t+1)=s(扌)+1,w=L arrival FLOW 化了复杂的服务模型。对于等待队列长度为30和60的情况 (11)优化后的SSDN模型的状态空间明显少于原始模型。除此之 1D-小 外,随着等待队列长度的增加,两个模型的状态空间都会增加 +1,H) 但是优化模犁增加的绝对值明显少于原始模型。 从图9中可以看出,求解SSDN模型的最优策略是基于门 限的策略,门限随着情况的不同而发生变化。在图9中,x轴 的值表示由低服务速率状态到高服务速率状态的转换门限;y 轴的值表示需求的奖励和能耗之间的柑对值。对于系统的任 务到达速率,随着任务奖励值变大,由低速率状态到高速率状 态的转换门限会降低。这种趋势表明服务器在高速率状态会 图7MD模型 花费更多的时间来得到相同的奖励。对于门限值为0~40,服 采用动态规划来解决MDP问题。优化标准是使式(9)最务器不会转换到高速率状态因为奖励太低。在这种情况下就 大化。因此, Bellman等式1可以表示为 将门限设置为0。对于系统的任务奖励,随着到达率的增加 ()= maxa(iiR(s,a(1)+8E(a)x()}(12) 门限会降低,因为到达率增加会使得服务速率需求提高,从而 其中:R(s,())表示行为a在当前状态的奖励;na(a)为状态需要更早转换到高速率状态。 转换概率;X为状态空间;8为没有考虑的因素。采用值迭代算 法来求解非受限MDP问题。在每一次迭代中最优解的界限,502 700 最优解V满足 Bne≤≤V (13) 78 ne lengthe 其中:e为单位向量,a、β满足 ratio of reward to energy cos 图8两种模型的状态空间的对比图9门限的变化情况 max[Vn],-[V2-1] 从佟10中可以看出,较高的奖励能够提高服务性能,比如 Bn=max{Vn,-[V。1] 14)降低响应时间。当门限为0~40时,响应时间仍然较高,当其 4.3标准制定 值大于40时,响应时间就降低。这是由于图9中的变化门限 通过求解MD得到最优策略,然后应用到SSDN中,以得值造成的。服务器在门限为0-40时不会转换到高速率状态。 到其性能和能量标准。采用的标准为响应吋间和节约的能量。 因此,对于相同的到达速率,系统的响应吋间是系统的。随着 通过求解PN来得到这两个标准。响应时间可以由Lie公在务奖励值的增大,服务器会以较大的率转换到高速率状 式得到: 态,从而使得性能提升。 F hufeng 任务奖励的增加会使得节约的能量减少,如图11所示。 PriE (15) 节约的能量与服务器处于低速率的概卒成正比,而服务器处于 其中:E{ buffer;}表示等待队列的平均长度;Pr{ Decision end}表低速夲的概率会随着奖励的增加而降低。 示队列中的信令数量大于0的概率;丌r、表示转换Tuma的 1.1 -arrivalthteni 70 川启概率;Aa为平均到达率 节约的能量定义为运行在低服务速率的概率与高低服务90 返率之间的能耗差的乘积: PrIEI 3>0) x(EuGu-ELow (16) 0204060801000 ratio of reward to energy cost ratio of reward to energy cost 5仿真结果 图10不同到达率下的响应时间图11不同到达率下的能耗 6结束语 本章将通过仿真来验证本文方法的有效性。图1中状态 转换的廾启率如表1所示。高服务速率假定为10.低服务速 木文研究了基于SSN模型的云计算速度调节技术。这 率假定为5,到达率为3~5,需求的奖励和能耗比的变化范围种模型结合了SDN和MDP来动态优化云计算的速度调节策 为0~100。 略和服务新评估。同时,这种模型是以服务为(下转第2802页) 2802 计算机应用研究 第31卷 调度的资源分配优化问题。 ling concurrent workflows in HPC cloud through exploiting schedule 由于云计算环境下不同用户对DAG的Qos需求可能不一 gaps[ C ] //Algorithms and Architceturcs for Parallel Proccssing 样。除了DAG的调度长度以外,还有其他一些Qos需求。囚 2011:282-293 此,未来可以利用本文所提的进化方法对具有多种Q需求1】 TTENCOURTL H, MADEIRAE R M.He: a cost optimization 的多DAG共享云计算资源调度的资源分配及其优化等问题展 algorithm for workflow scheduling in hybrid clouds[ J]. Journal of In 开进一步的研究。 tenet Services and Applications, 2011, 2(3): 207-227 12 JAVADI B, TOMKO M, SINNOTT R O. Decentralized orchestration 参考文献 of data-centric workflows in cloud environments ). Future Genera [1]刘少伟,孔令梅,任开军,等.云环境下优化科学工作流执行泩能 tion Computer Systems, 2013, 29(7): 1826-1837. 钓两阶段数据放置与任务调度策略[J.计算机学报,201,34[13] TAKPE N, SLTER F. Concurrent scheduling of parallel task graphs (11):2111-2130 on multi-clusters using constrained resource allocations [C]//Proc of [2 FAHRINGER T, PRODAN R. ASKALON: a grid application deve- IEEE International Symposium on Parallel and Distributed Processing. opment and computing environment[ C]//Proc of the 6th IEEE/ACM 2009:1-8 International Workshop on Grid Computing. Piscataway: EEE Press,141g目忠,肖创柏,徐竹胜,等.异构分布式环境下多DAC工作流的 混合调度策略[J].软件学报,2012,23(10):2720-2734 [3DagmAn.coNdor7.4.2[eb/olj.2010.http://www.cs.wisc 15 CASANOVA F, SUTER F. On cluster resource allocation for multiple edu/condor/ dagman/ [4]林海略,韩燕波.多租户应用的性能管理关键问题硏究[J.宀算 parallel task graphs[ J] Journal of Parallel and Distributed Com- puting,2010,70(12):1193-120 机学报,2010,33(10):1881-1895 [5]韩燕波,王桂玲,刘晨,等.互联网计算的原理与实践一探索网修,I16 TAKPE N,TERF, CASANOVAF. A comparison of scheduling ap 云和WcbX.0背后的本质问题和关键技术[M].北京:科学出版 proaches for mixed-parallel applications on heterogeneous platforms LC//Proc of the GIh Inlernalioral Sympt sium on Parallel and Dis- 社,2010 buted ct ng.2007:35 [6 HONIG U, SCHIFFMANN W. A meta-algorithm for scheduling mul- tiple DAGs in homogeneous system environments[ C]//Proc of the [17 BARBOSA J G, MOREIRA B. Dynamic scheduling of a batch of I8 th International Conference on Parallcl and Distributed Computin para-llel task jobs on heterogeneous clusters J. Parallel Compu and Systems. S.I.: IEEE Press, 2006 ting,2011,37(8):428-438 [7 ZHAO Hc-nan, SAKELLARIOU R. Scheduling multiple DAGs onto 18 CIRNE W, BERMAN F. A model for moldable supercomputer jobs heterogeneous systems[ C]//Proc of the 20th International Symposium [C]//Proc of the 15th International Symposium Parallel and Distribu- on Parallel and Distributed Processing. [S 1.]: IEEE Press, 2006 ed Processing. Washington DC: IEEE Computer Society, 2001 [8] YU Zhi-feng, SHI Wei-song. A planner-guided scheduling strategy for [19 HUNOLDS, L.EPPING J. Evolutionary scheduling of parallel tasks multiple workflow applications[ C]//Proc of International Conference graphs onto homogeneous clusters[ C 1 //Proc of IEEE International on Parallel processing. 2008:1-8 Conference on Cluster Computing 2011: 344-352 [9] BITTENCOURT L F, MADEIRA E R M. Towards the scheduling of [20] KWOK Y K, AMAD I. Dynamic critical-path scheduling: an effec multiple workflows on computational grids[ J]. Joumal of Grid Com tive technique for allocating task graphs to multiprocessors[ J1.IEEE puting,2009,8(3):419-441. Trans on Parallel and Distributed Systems, 1996, 7(5): 506 [ 10] JIANG He-jhan, HUANG Kuo-chan, CHANG H Y, et al.Schedu- 521 (上接第27舛4页)导向的,因此能够运用典型模式将复杂模型简 the 2l st International Conference on Computer Communications and 化为具有较小状悆空间的简单模型。这种模型能够措述复杂 Nel works. 2012. 1-5. 的系统行为和决策过程,仿真也表明了这种模型的有效性。 [7 LAM T W, LEE L K, TO I, ct al. Speed scaling functions for flow 参考文献: li me scheduling hased on aclive job eDun[C]//Pro of the 161h An nual European Symposium on Algorithms. Berlin: Springer-Verla I 1 HAMILTON J. Cost of power in large-scale data centers[ EB/OL T 2008:647-659 hp: //perspectives. Tnlvrlirona [om/2008/1 1/28 [8 ANDREW L L, LIN Ming-hong, WIERMAN A Optimality, fairness [2 GARG S K, YEO C S, ANANDASIRAM A, et al. Environmcnt-con- and robustness in speed scaling designs[J. ACM SIGMETRICS scious scheduling of HPC applications on distributed cloud-oriented Perfor-mance Evaluation Review, 2010, 38(1): 37-48 data centers[. ] Journal of Parallel and Distributed Computing, [9] LIN Chuang, QU Yang, REN Feng-yuan, et al. Performance equiva- 2011,71(6):732-749 lent analysis of workflow systems based on stochastic Petri net models L 3 YUN D, LEE Research in green network for future Internet[ J] [Cl//Proc of the I st International Confcrencc on Enginccring and Journal of KlISE, 2010, 28(1): 41-51 Deployment of Cooperative Information Systems. Berlin: Springer [4 BARROSO L A, IIOLZLE U. The case for energy proportional compu- 2002:64-79 ting「J]. Computer,2007,40(12):33-37. [10 BFCCUTI M, FRANCESCHINIS G, HADDAD S. Markov decision Pe- [5 LIN Chuang, TIAN Yuan, YAO Min Green network and green evalu tri net and Markov decision well-formed net formalisms[ C//Proc of ation: Mechanism, modeling and cvaluation J]. Chinese Journal of the 28th lu llerralional comfereneeoII of petri Computers,2011,34(4):593-612 Nets and Other Models of Concurrency. Berlin: Springer, 2007: 43-62 [6]chenZhcn,ShiXi,RuaNLing-yun,etal.Highspccdtrafficar-[11]Bellmanequation[Eb/Ol].(2013).http://en.wikipediaorg/wi chiving system for flow granularity storage and querying[ c]//Proc of ki/ Bellmanequation/