论文研究-基于PEPA的云计算资源分配算法性能评价.pdf

所需积分/C币:10 2019-07-22 21:49:54 2MB .PDF
9
收藏 收藏
举报

资源分配是云计算的核心之一,对云计算资源分配算法的性能进行评价可为云计算平台设计提供指导。讨论了两种云计算资源分配算法,提出了一种基于PEPA的资源分配算法的性能评价模型,该模型通过建立云计算系统中各组件之间的交互关系进行形式化分析和推理,获得了云计算系统性能的评价指标。实验通过分析资源分配过程中不同参数变化对系统性能的影响,结果表明,PEPA模型方法可以直接评估资源分配算法性能的优劣,并能够确定算法性能提升的关键因素,从而减少云平台设计过程的周期。
第4期 王倩,等:基于PPA的云计算资源分配算法性能评价 1181 EⅤMSA基本流程图。 个连续时间马尔可夫进程。构造这个马尔可夫进程,求解出 匚用户请求 CTwC每个状态的稳定状态概率,在此基础上能够得出系统性 扦入合适队列 能分析结果。应用PEPA对系统模型进行性能评价分析一般 对首诘求比较与选招 分三个阶段22 虚我行]资源足够启动虚 请求等待池 )建立PEPA模型,把一个系统分为几个不同的子系统 根据PFPA提供的操作义对∫系统分别进行描述,如此层层 虚拟机部奢 成机实例,是< 启动虛拟机 分解就得到了系经的完全模型 图2 EYMSA基本流程 b)构造与该模型对应的CTMC; 基于CTMC求解稳定状态慨率,并在稳定状态慨率的 3基于PEPA的资源配置过程的评价模型与分析 基础上分析系统性能的定量指标。 3.2云计算平台模型的形式化描述 PFPA语法中最基本的元素是组件( cnmpunenls)和活动 对云计算资源调度算法采用PEPA方法进行形式化性能 (aci),对应于基本随机模型中的状态(sas)和转换评价需要建立云计算平台的PPA模型,采用如下规则可将云 ( transitions)。组件通过执行单个或多个活动进行交互的过程 计算平台樸型转换为PEPA模型 可以用PEPA模型来描述。组件通常用大写字母表示,活动则 a)云计算平台中的模块可以用PEPA中的组件表示 由动作由类型a和速率λ进行描述,表示为(a,λ)。PEPA基 b)状态转换时执行的操作可以用PEPA中的活动表小 本语法定义如下: c)状态转换间的顺序关系相当于PFPA的前缀运算; P:=(α,A).PIP+Q|P‖QPLA d)状态转换间的选择关系相当于PA的选择运算; PFPA采用较小的组合操作集合,这些操作包括2 e)组件间并发执行关系相当于PPA组件的协作运算。 )前缀操作。(m,A).P表示在速率A下执行动作类型 根据第2章所揹述的 Eucalyptus默认调度算法和EⅤMSA 后转换为组件P 流程以及上述转换规则,本文构建了两者的PEPA描述模型 b)选择操作。P+Q表示组件P和Q有且仅有一个被执 其屮USER表示用户组件,SQ表示队列管理组件,SV表示虚 行,动作的选择一般是由最快执行的那个组件决定,因此每个 拟机资源调度组件。对这三个组件的活动进行抽象,然后利用 P和Q动作的执行概率和它的速率成正比。 PEPA对其进行描述:当用户发送虚拟机请求时,用户组件首 c)协作操作。P‖Q(或PD<1Q),其中是动作类型集 先以速率r1执行动作 vin_request,状态由USER转变为US 合,当动作类型属于L时组作P和Q同步合作;如果动作类型F。由丁虚拟机请求的到达,队列管理组件由等待态Q转 不属于L时则异步执行组件P或Q,用P‖Q表示并发执行 变为SQ,之后以r3的速率执行动作 request_enqueue将虚拟机 d)隐减操作。P/L表小活动L在组件P中可以被视为内部 请求入队,此时状态从SQ1转变为SQ。虚拟机资源调度组件 动作。 以速率r4执行动作 request dequeue从队列中取出虚拟机请 e)常数。A代表常量,用十对组件的定义。 求,状态山SV转变为SV1;又以速率r5执行动作 estimate I 与其他性能评价形式化方法相比,PEPA方法具有如表1 所示的优点2 quest_size计算任务完成所需资源的数量,状态由SV1到S2 如果资源数量符合所需的要求,则以速率r执行动作 select 表1PFPA与其他性能评价方法的对比 VM选择合适的虚拟机,状态转为SV4,最终虚拟机以r。的速率 性能参数 PEPA 表达能力 有限 有限 较好 执行动作 vIn finished完成请求任务,状态转变为Sv。如果没 模型去示表达内容 模犁物理 模犁动态模型物理结构 有足够的资源,则以速率r执行动作 request- pending-pl请 行为 和动态行为 较大,但可以 求等待池中的资源,状态由Sv2转为Sv3;如果池中资源大小 信息量 较大 有效化简 模烈操作是否结构化无结构化机制结构化稍好系统化结构化好 满足需求,则以速率r,执行动作 select_VM选择虚拟机,状态 推能力 差 推理能力不足推理能力好 转为SVs,最终虚拟机同样以r的速率完成请求仁务,状态转 状态空间 无 白,难以解决有,但是能够有效 变为SV;否则虚拟机资源调度组件将以rs的速率执行动作wm 模型求解 爆炸 reject拒绝该虚拟机请求,状态直接由Sv3转变为SV。当虚拟 仅作性能性能分析 性能分析 具他分析功能质量研究功能质量研究 机运行结束后,用户组件得到计算结果,状态由USER1转变为 如下所示为一个多处理器共享内存计算架构的简单 PE- USER。当虚拟机请求被拒绝后,用户组件继续以速率r2执行动 PA模型 作 vm_request发送该虚拟机请求,状态由LSER,转变为USER。 P,-(think, A,).(get, g).(use, Ali ).(release, /).PI 如下所小为 Eucalyptus默认调度模型的PEPA描述 //user component P2=(think, A2).(get, g).(use, u,).( release, r). P2i Mem =(get, T).( release, T). Mem: [SER=(vIm_request, 1).USE Bus=( get, T).(release, T).Bus USER=(vm_finished, 7). USER+(vm_reject, 7). USER2 USER2=(vm_request, r8). USER; System =(P1 P2D< Bus D<Mer //schedule queue component( sigle queue where /=get, release 3.1PEPA性能分析的一般步骤 QI =(request_enqueue, r,). sQ PEPA是基于基本随机过程的,在指数分布的假定下是 //schedule VM component( sigle queue l182· 计算机应用研究 第32卷 p(s)=0c从而 vm_request的吞吐量定义为 (4) SV =(eslimale_requestsize, Ts ).SL 7( vm_request)=∑丌(s)ⅹs[ vm_request.xr1 SI,=( request_pending _pool, r). SV,+(select_VM, ,). SV4; 此时可以看出吞吐量由稳定状态概率与活动速率r1共同 SV, =(select_ VM, ry). SIs +(vm_reject, r8).Sk 决定,增加r1或减少停顿均可提高春吐量的大小。 5y vm_finished, g).SV 组件的资源利用率即组件处在一个局部活动状态的概率。 如组件USER的利用率即为USER的数目占整个用户组件数 目usmn比例,对应的回报为(s)=UEB,此时 System=SQ DXUSER >XSV m request USER的利用率为 N=ivm_finished, vm_reject utilization( USER) L USER 丁(s)x EVMSA的PEPA模型是山三个类似于 Eucalyptus默认调度 模型构成,即三队列调度模型。除了与 Eucalyptus默认调度模 表2 Eucalyptus默认调度模型的引导图转换表 型相类似的处理流程外, , EVMS的PEPA模型在队列组件中加状号8RNN 状念 输入次念号输出状念号 入了决定虛拟机请求类型的活动;虚拟机资源调度组件将采用 16,19,21 2,3 sQ1‖UsER‖Sk 多级队列的思想以三个不同的速率从三种不同的队列中选择虚 3 sQ‖MSFR‖ssV1 5.6 拟机请求,并且处理每一种不同虚拟机请求的速率也不同。在 SQ‖ LUSER1|xSV 构建PPA模型之后可以获得稳定状念概率分布(3.3节)并 P1 mUSER, I SQ‖ yUsER‖sSV2 3,26 8,9,10 以此计算组件活动的吞吐量和利用率来评价系统的性能。 S(‖ uSeR1‖xs 3.3使用PEPA进行性能分析 8 QI MUSER! N SI 5,6 l1,12,I3 ‖ yUsER‖ssl 6.30 LPA的引导图DG( derivation graph)对应的CIMC最终 SQ‖ MUSER‖Sv4 可以转换为速率矩阵。通过求解马尔可夫链每个状态的稳定 sYO‖ y sER:‖NsV2 15,16 sQ1‖ yUsEn1|xsV3 89 15.17.18 状态概率,可以进一步得到系统性能评价指标的定量指标,如 SQI MUSER,I N SI 10 16,19 吞吐量、利用率和平均响应时间等。基于转换关系的引导图能 SQ" yUsEi‖sss 够描述PEPA模型任意组件的所冇可能演变,冇效推理模型的 SQ‖ cSER1‖xsv 11.12 SQ MUSEE1‖Nsv 行为。分析由系统语义模型得到引导图,能够得出系统的定性 SQ1‖ uSEr2‖NsV 20,22 特征。由于 Eucalyptus默认调庋模型的引导图过于复杂,此处 ‖ MUSER1|xS 12.14 用表结构展示,表2所示为 Eucalyptus默认调度模型的引导图 Q1‖ yUSER 13,18.20 的表结构。 SO‖ usER1‖NsVs 为了能够获得云计算资源调度算法的定量性能指标.首先 1‖MUsi2|xSv 24.25 要获得其模型的稳定状态分布。云计算资源调度算法PEA SO1| MUSER‖xsv 19,24 3,26 24 SER 模型的稳定状态分布可由式(2)进行求解 SQ1‖ yUseR2|NSV2 27.28.29 ∑丌(S;)=1,mQ=0 SO1| yUSER‖Nsv2 sQ‖ yUSER2‖xsV2 其中:丌(S)代表PEPA模型第i个状态的稳定状态分布,是 SQ1‖ yUsEn2|xSv 个行向量;Q为马尔可夫进程转移速率矩阵。其定义为:记S、 s1‖ yUSER2‖ S.两状态之间的变江速率为s;短阵的非对角元素是状态S SQ1| yUSER‖xs SO1 MUSER‖xsv 到状态S的转换速率,若状态S不是状态S的直接派生则 M q、s为0;矩阵对角元素是每一行的非对角儿素的总和的负数, SQ‖MSER2‖xSV sQ1‖ yUsEn2|NSl5 即 35 1| yUSER‖xsl Reward函数23的概念是由 Howard提出的,PEA强调的361s2s323435 是活动的行为,所以给系统中特定的活动联系回报,性能指标4实验与分析 由基于稳定状态概率分布的总回报得到。若ρ,是与状态S,相 关联的回报,且π(S;)是稳定状态分布,那么总的 reward函数 为了能够对不同资源凋度算法的性能进行量化分析,本文 如式(3)所示。 共设计了一个实验,分別说明了算法模型中各组件变化对算法 R=∑p1T(S) (3)性能的影响,同时在每个实验甲也比较了 Eucalyptus默认调度 根据回报函数可以进一步定义春吐量和利用率等性能指算法和 EVMSA的性能差别 标。本文实验部分主要关注虚拟机分配活动的吞吐量。 第一个实验计算了当用户发送虚拟机请求速率从1~101 个活动的吞吐量定义为系统在单位时间内所完成的该变化时不同并发用户请求数对虚拟机分配活动吞吐量的影响。 活动的量。 Eucalyptus默认调度模型中,对于虚拟机请求活动图3所示为两种不同PEPA模型在不同并发用户请求数下虚 vm_ request,在单位时间内完成的活动量由USER的数目和活拟机分配活动的吞吐量曲线。由图3可知,随着并发用户请求 动变迁速率r决定,定义ρ(s)=s[ USER]ⅹr;,其中 sL USER]数的增加,虚拟机分配活动昋吐量趋近饱和,即系统性能提升 表示USER在状态s时的数目,特别地,若 sL USER」=0,则可能在某处遇到瓶颈限制;图3同时也说明了三队列算法吞吐 第4期 王倩,等:基于PPA的云计算资源分配算法性能评价 1183 量饱和值远高于单队列算法岙吐量饱和值。此实验直接地告置过程交互组件建模的能力,并能有攽减少系统的状态空间, 诉了云计算平台设计者和云计算动态资源分配算法设计者,在降低了求解的复杂性和开销,高效地对云计算资源分配算法进 与此实验类似的情况下需要考虑采取优化措施以突破并发用行评价从而为云计算平台设计提供指导。实验结果表明负载 户请求数增加时限制系统性能提升的瓶颈。 较大情況下的三队列资源调度算法比单队列资源调度算法更 加高效,相比丁 Eucalyptus默认算法能够为服务请求者提供更 高质量的服务。 目前笔者还在研究采用PEPA模型获得一些其他性能评 价指标,比如算法的利用率和响应时间等。在之后的研究屮将 在系统中加入更多的组件,将配置资源的组件和类型考虑进 三20 去,并通过实际测量和比较来验证当前的方法是否能够满足应 用需求 l00 参考文献: 户请求发送速率 图3用户请求数和用户发送请求速率对虚拟机分配活动吞 [1 FOSTER I, ZHAO Yong, RAICU I, et al. Cloud computing and grid 吐量的影响(S:单队列模型,T:三队列模型) computing 360-degree compared[ C]//Proc of Grid Computing Envi 第二个实验屮的变量是并发用户请求数以及调度模块数。 onments Workshop. Austin: GCE, 2008 如图4所示,并发用户请求数增加时,调度模块越少则系统资2林闯,李推娟,王忠民性能评价形式亿方法的现状和发展[J,软 源分配性能的提升越快地趋于饱和,且饱和值较小,反之亦然。 件学报,2002,30(12):19191921 图4同吋也说明了三队列模型在相同变量设置下的系统性能 [3 HILLSTON J, KLOUL L Formal techniques for performance analysis 要远高于单队刎模型。由该实验可知,诓过增加调度模块数量 blending SAN and PEPA[ J]. Formal Aspects of Computing 的方式可以很好地提高系统性能。 [4 GILMORE S, HILLSTON J. The PEPA workbench: a tool to support a process algebra-based approach to performance modelling]//proc 100 of the 7 th Conference on Modelling Techniques and Tools for Compu 调度嗅块数 ter Performanee Evaluation [. L.I: Springer- Verlag [5]李春燕,何一舟,戴彬.Hadp平台的多队列作业调度优化方法 [J].计算机应用研究,2014,31(3):705-738 [6 WANG Guo-hui, NG T S E. The impaet of virtualization on network performance of Amazon EC2 data center[ C]//Proc of the 2 th Con- ference on Information Communications [S.1.]: IEF.F. Press, 2010 户请求数量 图4用户请求数以及调度模块数变化对虚拟机分配活动 [7 ASSUNCAO M DD, COSTANZO A D, BUYYA R. Evaluating the 乔吐量的影响(S:单队列模型,T:三队列模型) c'osl-benefit of using cloud computing lo extend the capacity of clusters 第三个实验研究了并发用户请求数和队列模块数增加时 I Cl// Proc of the 18th ACM International Symposium on High Per 虚拟机分配活动吞吐量的变化。由图5可知,当并发用户请求 formance Distributed Computing. New York: ACM Press, 2009 数大于2和调度模块数增加时虚拟机分配活动吞吐量几乎不「8110sLPA, OSTERMANN,) YIGITBASI N.a. Performance analys: 会增加,且各由线儿乎車合。该实验说明,云计算屮台设计者 of cloud computing services for many-lasks scientifie computing J] 不需要考虑增加更多队列模块数这种方式來提高系统性能。 IEEE Trans on Parallel and Distributed Systems, 2011, 22(6) 931-945 图5同样也说明了三队列模型在相同坼境下的性能要远髙于 [9 LI Ang, YANG Xiao-wei, KANDULA S, ct al. Cloud Cmp: comparing 单队列模型的性能。 public cloud providers[c]//Proc of the 10th ACM SIGCOMM Conl- ference on Internet Measurement. New York: ACM Press,2010 [1O LI Zhi- chun, ZIIANG Ming, ZIlU Zhao-sheng, et al. WebProphet: au tomatina performance predietion for Web services[ C]//Proc of the 队列模块数量 7ih USENIX Conference on Networked Systerms Design and Impleme tation Ber: USENIX Association, 2010 罕 [11 STANTCHEV V Performance evaluation of clud compuling offerings C//Proc of the 3rd International Conference on Advanced Engi neering Computing and Applications in Sciences. 2009 12.5 川户请求数量 [12 KHAZAEI H, MISIC J, MISIC V B. Performance analysis of cloud 吞叶量的影响(S:单队列模型,T:=队列模型产" 图5用户请求数以及队列模块数变化对虚拟机分配 computing centers using M/G/m/ n t r quell ystems [ J」.EEE Trans on Parallel and Distributed Systems, 2012, 23(5): 936 5结束语 13 WARNEKE D, KAO 0. Exploiting dynamic resource allocation for 本文基于PEPA的相关理论,提出了·种利用PEPA对云 efficient parallel data processing in the cloud L J. IEEE Trans on 计算资源分配算法建模的方法,进而评价了云计算平台资源分 Parallel and Distributed Systems, 2011, 22(6): 985-997 配过程的性能。与传统的进程代数相比,PFPA提供了资源配 (下转第1187页) 第4期 佥伟健,等:基于蝙蝠算法的云计算资源分配研究 1187 从图中可以看出两个算法在经过若干次迭代以后都在某一值于时间和成本为双约束的云计算资源分配方法,并将蝙蝠算法 进行了收敛,这说明两个算法都能在可行解空间中找到相对最引入其中进行资源分配调度,仿真实验测试结果表明,该方法 优的解,但两者最终的收敛值不一样,表明在搜索过程中可能可以为用户快速找到合适的虚拟机资源来分配任务,减少了云 陷人了局部最优解。在迭代早期,曲线下降较快,说明算法均环境下任务调度总时间,在成本消耗方面,蝙蝈算法明显优于 能较快地找到当前的某个局部最优解,传统的φSO算法在迭传统的粒∫群算法。但是,蝙蝸算法在迭代次数方面仍梢显不 代到第35次左右的时候,就开始牧敛于算法认为的全局最优足,具有较大的改进空间,下一步工作可以就加快收敛速度方 解,即认为任务完成总时间最小的可能值为106s。而本文的面着于 BA词度算法的达代次效达到66次附近后才收敛,且收敛值参考文献 75s,显然要比PO算法在收敛精度上更有优势,在任务完成 总时问上减少了33s [Ⅰ』李乔,郑啸.云计算研究现汏综述[J].计算机科学,2011,38(4) 图3反映的是权重因子=0.38时总任务完成成木消耗。 从图中可以看出两个算法最终都收敛,且随着选代次数的增2 ARFEEN M A, PAWLIKOWSKI K, WILLIG A. A for re- source allocation strategies in cloud computing environment [C]// 加,两个算法分别所得到的总务完成成本消耗差距逐渐变 大,最终趋于稳妵。传统的PSO算汏在整个迭代过程中相对 Proc of Compuler Software and Application Conference 2011: 261 266 比较平缓,在迭代至48次时就找到了算法所完成任务的全局 [3]刘万,张盂华,郭文越.基于MPSO算法的云计算资源调度策略 最优解,有可能陷人了某个局部最优解。而本文的BA任务调 [J].计算机工程,2011,37(11):43-48 度算法寻优过程在迭代值60次左右的时候找到了算法认为的 [4左利云,左利锋.云资源中多日标集成蚁群优化调度算法[冂.计 最优解。相对于PSO调度算法,BA调度算法虽然多迭代了1 算机应用,2012,32(7):1916-1919 次收敛,但任务完成总成本降低了25%左右,成本消耗有较大 [5 ZHU Kai, SONG Hua-guang, LIU Li-jing. Hybrid genetic algorithm for 幅度的减少。 cloud computing applicalions C//Pree of IEEE Asia-Pac ific Services Computing Conference 2011: 182-187 回140 「6〗盛晓华,叶春明.蝙蝠算法在PFSP调度问题中的应用硏究「J 500 工业工程,2013(1):119-124 [冂]李枝勇,马良,张惠珍,蝙娙算法在多目标多选择背包问題中的应 用「J1.汁算机仿真,2013,30(10):350-353 150 迭代次数 迄代次数 [8 YANG Xin-she. A new metaheuristic bat-inspired algorithm[ C//Na- 图2-0.38时的任务完成总时间图3t0.38时的任务完成成本 ture Inspired Cooperative Stralegies for Optimization. Berlin: Springer 综合图2、3可知,随着迭代次数的增加,PSO算法与BA 2010:65-74 算法调度产生的总任务完成时间与总任务完成成本消耗都在 9 BUYYA R, RANJAN R, CALHEIROS R N. Modeling and simulation 逐渐减少,并且最终都收敛于某一特定值,但是在总仁务完成 of sealable cloud computing environments and the CloudSin toolkit 时间以及总任务完成成本上,BA调度算法产生的结果都要优 challenges and opportunities [C J//Proe of HPCS Conference. New York. IEEE Press .2009:1-11 于传统PSO算法的调度结果。 [10]葛新,陈华平,杜冰。基于云计算集群护展中的调度策略硏究 5结束语 LJ」.计算机应月研究,2011,28(3):995-997 [11]尹红军,栾京,宋浒.云计算中运营商效益最优的资源分配机刽 木文通过对云环境下资源分配的深入研究,提出了一种基 [J].华肀科技大学学报:自然科学版,2010,39(1):51-55 (上接第1183页) cations in cloud simulations[ C]//Proc of the 4th IEEE International L 14 BUYYA R, GARG S K, CALLIIEIROS R N, et al. SLA-oriented re Conference on Utility and Cloud Computing. 2011: 105-113 source provisioning for cloud computing: challenges, architecture, [19] NURMI D, WOLSKI R, GRZEGORCZYK C, et al. The eucalyptus and solutions[C]//Proc of International Conferenee on Cloud and open-source cloud-computing system[ Cl// Proc of Grid Computing Service Computing. 2011 Environments Workshop. 2009 [151 CARC S K, VERSTEEC S, BUYYA R. SMICloud: a framework for [20] KYI H M NAING T T Stochastic Markov model approach for efficient comparing and ranking cloud services[C//Proe of the 4th IEEE virtual machines scheduling on private cloud[ J.. International Jour nal on Cloud Computing: Services and Architecture, 2011.1 International Conference on Utility and Cloud Computing. 2011: 210 (3):1-13 21 DONATELLI S, RIBAUDO M, HILLSTON J. A comparison of per- 16 LOSUP A, YIGITBASI N, EPEMA D On the performance variability formance evaluation process algebra and generalized slox hastie Petri f production cloud services[ C// Proc of the 1 l th International Con- nels[ C//Proc of the 6th International Workshop on Petri Nets and ference on Cluster, Cloud and Grid Computing. 2011: 104-113 Performance Models. 1995 17 SCHAD J, TTRICH J, QLIANERUIZ J A. Runtime measurements in[22]郭辉,进程代数及其在性能中的应用综述[J].微计算机应用, the cloud: observing, analyzing, and reducing variance[J]. Proc 2007,28(9):901905 VLDB Endow,2010,3(12):460-471 L23」马梁,李明,宋洁,等.进程代数在性能评价中的应用研究LJ」.河 18 GARG S K, BUYYA R Network CloudSim: modelling parallel appli- 匕工业大学学报,206,35(4):35-39

...展开详情
试读 6P 论文研究-基于PEPA的云计算资源分配算法性能评价.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840924 欢迎大家使用并留下宝贵意见
2019-07-22
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-基于PEPA的云计算资源分配算法性能评价.pdf 10积分/C币 立即下载
    1/6
    论文研究-基于PEPA的云计算资源分配算法性能评价.pdf第1页
    论文研究-基于PEPA的云计算资源分配算法性能评价.pdf第2页

    试读结束, 可继续阅读

    10积分/C币 立即下载 >