论文研究-异构云环境下基于分簇的云资源感知任务调度方案.pdf

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

针对提高异构云平台中资源调度的效率,提出了一种基于任务和资源分簇的异构云计算平台任务调度方案。利用K-means算法,根据任务的CPU和I/O处理时间对任务分簇,根据资源的计算能力对资源分簇;然后,将任务簇对应到合适的资源簇,并利用最早截止时间优先(EDF)算法对任务簇中的独立任务进行调度,利用提出的改进型最小关键路径(MCP)算法对依赖性任务进行调度。实验结果表明,在资源异构的云计算环境中,该方案执行任务时间短、能耗低。
·3424· 计算机应用研究 笃33卷 distance(E,, E,=.(PEa-pes)'(Pfa-Pfb)? (6) 5for每一个节点n;do 6创建一个列表L1=② 2)依赖性任务的分簇对于依赖性任务(非独立任务), L,=LU: (n;, ALAP(n: )); 木文根据两个不同的DAG图的CCR(通信与计算比)的比较 对 succs(n1)按照ALAP进行降序排列; 来计算“距离” 9for所有的n=sucs(n:)do; L:=L:U(n;, ALAP(n: ) CCR可以定义为平均边权重除以平均节点权重,定义为 V×∑can(x,) LELUL CCR. (G):=CCR,(G(V, E, w, ew.)) IE|×∑(x)(7) CCR有助于判定任务DGA图中通信的重要性,其决定了 14将这些列表(L)按词典升序排列; 15重复 调度行为。定义两个DAG图G和G,之间的距离为 16提取节点列表L中的第一个节点L1 distance(Ge, Gs)=ICCR(C)-CCR(CB)I (8) 17从允许最早执行的R中调度一个资源给L1 另外,给出一个DAG图G的粒度g的定义 18L=L-L1;//移除未自于节点列表的节点; 19直到L= g(G)=g(G(V, E, w, ewn))=mir aev max [ eu (r i (9) 20结束程序 ,)∈ 根据粒度,G可被分为粗粒度(计算为卞导)和细粒度(通 信为主导)。其中,DO密集型任务为细粒度(CCR>1) 2实验及分析 CPU密集型为粗粒度(CCR<1),CP和LO混合密集型为混 2.1实验环境 合粒度(CCR≈1)。分簇结束后,在任务调度阶段,会根据任务 簇的类型,将其关联到相应的资湶簇,如将CPU密集型任务簇 本文选择·种多媒体应用场景来进行实验,多媒体应用通 关联到具有高计算能量的资源簇上。本文分簇阶段如图2常包含信息采集分析处理、描述和存储过程,例如大范围边 示,在分簇阶段完成之后,将对输人任务进行实质资源调度。 境视频监控系统、自然灾害监控系统、现代视频会议系统等等。 多媒体应用场景由独立任务和依赖性任务工作流组成.另外. 1.4任务调度 多媒体应用中具有大量CPU密集型任务(需要处理大量数据) 谎度算法运行在词度器模块中,主要分为以下两步 和L/O密集型任务(需要访问远程数据)。 1)根据仟务和资源组中的平均参数、关联任务组和资源 本文利用云仿真器 Cloudsim3.010上进行实验仿真,将本 组。即,若任务簇中存在需要高于平均处理时间的任务(“大”文方法与 RC-Min3)、5FT和 Aneka方案进行比较。本 任务),则为其分配高计算能力的资源。对于依赖性任务的文方法是针对异构分布式计算提出,所以在实验中考虑了资源 DAG,为粗粒度图分配高计算能力的资源,为细粒度图可分配异构性,设定资源计算能力分为以下等级:50100200 任何种类的资源 40005000、8000和1000MIPS(百万条指令每秒);内存 2)在每个资源组内运行特定的调度算法,来分配任务或DAG (RAM)分为:512、1024、20484096、8192和16384M(兆) 在任务调度中,本文针对两种不同的仁务(独立任务和依 生成的任务长度值分布在[10000,30000],任务对资源的计 賴性任务)运用了两种不同的调度算法,描述如下。 算能力需求为[200500。 1)独立任务调度算法对于独立任务,本文采用最早截 2.2综合任务的实验 止时间优先(EDF)调度算法,EDF算法恨据任务的截止时间, 将任务降序排列,一且有可用资源,则将其分配给截止时间列 首先随机生成最大数目为1000个任务和50个计算资源 表中截止时间最近的任务上。EDF算法如算法1所示。 的云计算环境。其屮,既包含独立和依赖性任务,也包含各种 算法1最早截止吋间优先(FDF):EDF(T,R) 密集型任务。在不同任务数量下,对各种调度方法进行性能比 1根据截止日期(P)对T中任务进行递减排序; 较,其中,实验数据为10次实验的平均值。 2 while t≠gdo 图3描述了不同调度方案下,执行100~1000个任务所 if任何资源可用(R)==真then 3456 对应的完成时间。可以看出,总执行时间随着任务量的增加而 R←获取随机可用资源(R); 7←读取任务(T); 增加。其中,在仼务量较少时,各种算法的性能比较接近,随着 执行T,R 任务量增大,本文方案的性能伉势越来越明显,当任务量为 000时,本文方案比 RC-Min、 SHEFT和 Aneka方案的执行时 8 n whi 间分别缩短了32.1%、19.2%和14.9% 9结束程序 2)依赖性任务(DAG)调度算法对于依颧性任务,运用 本文提出的一种改进型最小关键路径(M)算法进行任务调(。 度。木文改进型MCP算法基于列表有两个阶段:优先级和资 独立任务 DGA 源选择。其中,优先级是根据木文提岀的节点ALAP属性获得, 可推迟吋间越长,优先级越低。本文MCP算法如算法?所示。 圆度算法1 HySARC'调存算法2圣叫 算法2最小关键路径(ⅥCP)算法:MCP(T,R 每一个 2计算ALAP(n1) 资源簇 Q90)= 源簇 1002030040050060C7008009001000 4创建节点表L= 图2本文方案中的分簇阶段图3不同任务数量下的完成时间 第11期 江务学,等:异构云环境下基于分簇的云资源感知任务调度方案 3425· 图4描述了不同任务数量下的系统总能耗,其中,系统能性,研究动态任务调度的资源负载均衡,进一步提高调度方 耗由计算能耗和通信能耗组成,设定CPU每计算200Kbit数案的性能。 据消耗1k能量,每传输500Ki数据消耗1J能量。可以参考文献 看出,本文方案的总能耗最小,这是因为本文将资源进行了分 簇,同一种类型的工作流可以被分配到同一个资源簇中,减少 1〗刘少伟,孔令梅,任开军,等.云环境下优化科学二作流汍行性 了工作流中务之间的通信开销。 能的两阶段数据放置与任务调度策略「J1.汁算机学报,20lI 34(11):2121-2130 23不同密集型任务的实验 L2」张鹏,三桂玲,徐学辉.云计算环境下适于工作流的数据布局方 为了更好地验证本文方法的性能,在由依赖性任务组成的 法[J.计算机硏究与发展,2013,50(3):636-647, 不同密集型工作流下进行实验,本文构建9个工作流,包含3「31Liw,wuJ, Zhang g,eta. Trust-driven and Qos demand cluste 个CP密集型、3个混合密集型和3个O密集型,每个工作 ring analvsis based cloud workflow scheduling strategies J. Cluster 流包含600-700个子任务,各作流参数如表I所示。 Computing,2014,17(3):1-18 表1工作流参数 [4〗田国忠,肖创柏,谢军奇.有期限约束的多DAG共享资源的洞度 工作流编号任务数边数目平均CCR粒度 类型 及公平赀月优化方法「J.计算机学报,204.37(7):I 616186350.1393.957 粗粒度(CPU密集型) [5』左利云,左利锋,云计算中基于预先分癸的调度优化算法[J] 628194910.404.000粒度(CPU集型) 计算机工程与设计,2012,33(4):1357-131 681225050.1423.958粒度(CPU密集犁) 16 Canon L C, Jeannot E. Evaluation and optimization of the robustness 686228170.9980.991混合粒度(混合密集型) of DAG schedules in heterogeneous environments J|. IEEE Trans 688229540.9980.998混合粒度(混合密集型) on Parallel Distributed Systems. 2010, 21(4): 532-546 700241181.0070.988混合粒度(混合密集型) [7 Mao Yingehi, Zhu Lili, Chen Xi, et al. Associate lask scheduling al 667216376,620.029细粒度(L密集型) gorithm based on delay-bound constraint in cloud computing. C]// 631195396.6150.03 细粒度(LO密集型) Proc of the 13th International Symposium on Distributed Computing 627192026.7800.029 细粒度(O密集型) and Applications to Business, Engineering and Science. Washington 图5描述∫不同调度方法下,完成每个工作流所需的时 DC: IEEE Computer Society, 2012: 92-96 。可以看出,CPU密集型和混合密集型工作流的完成时间 L8 Calheiros R N, Vecchiola C arunamoort et al. The aneka 要远远高于IO密集型作流,这是因为L/O密集型作流所 platform and Qos-driven resource provisioning for elastic applications 需的CPU计算量小,主要为数据传输,且数据传输所消耗的时 on hybrid Clouds J]. Future Generation Computer Systems 2012,28(6):861-870 闰相比于数据计算较少。其中,本文方法所需的执行时间最 王健宗,谌炎悛,谢长生。面向云存储的ⅣO资源效用优化调度 小,因为本文对于不同类型的工作流,匹配相应的资源簇,提高 了资源的利用率。同时,在调度过程中考虑了任务的截止时问 算法研究[J].计算机研究与发展,2013,50{8):1657-1666 10 1 Cai Z, Li X, Gupta J N D. Critical path -based iterative heuristic for 和可推迟执行时间,使紧急任务优先处理,从而缩短了整体执 utility and cloud 行时间 ing[ J]. Lecture Notes in Computer Science, 2013, 35(7): 207-221 [1l Rahman M, Hassan R, Ranjan R, et al. Adaptive workflow schedu- ling for dynamic grid and cloud computing environment J. Concur rency Computation Practice Expenence, 2013,25(13) 181-1842 [12]张希翔,李陶深.云计算下适应用户任务动态变更的凋度算法 [J].华肀和技大学学报:自然科学版,2012,40(1):165-169. 3+ 56 789[13 Sun X Y, Fu X L, Hu H, et al. The cloud computing tasks schedu 江务数量 图4不同任务数量下的总能耗图5完成每个工作流所需的时间 ling algorithm based on improved K-rneans[ J]. Applied Mechanics & Materials,2014,28(2):1830-1834 3结束语 [14 Blakstad J, Kare Marius, Andreassen M. Security in cloud compu 本文提出一种异构云计算¥台中的基于任务和资源分簇 receipt storage[ J]. Institutt for Datateknikk Og Informasjons 的江务调度方案。首先,利用K- means算法,以预估任务的 vitenskap,2014,13(2):95-96 CPU和I/0处理时间作为分簇“距离”对任务分簇,以资源的[15] Abrishami s, Naghibzadeh M, pema DH J. Deadline-constrained 计算能力作为分簇“距离”对资源分簇;然后,利用EDF算法 workflow scheduling algorithms for infrastructure as a service clouds 对任务簇屮的独立任务进行调度,将提出的节点ALAP属性 [J]. Future Generation Computer Systems, 2013, 29(1): 158- 融人到最小关键路径(MCP)算法中,并以此对依赖性任务进 行调度。实验结果表明,与现有RC-Min、SHFT和 Aneka方l6] Wu zhangjun, Liu xiao, Ni Zhiwei,etal. A market-oriented hierar- 案相比,在资源异构的云计算环境中,本文方案具有较低的 chical scheduling strategy in cloud workflow systems[ J]. Joumal of 仁务执行时间和能耗。在今后的工作中,将考虑任务的动态 Supercomputing, 2013, 63(1): 256-293

...展开详情
试读 4P 论文研究-异构云环境下基于分簇的云资源感知任务调度方案.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840924 如果觉得有用,不妨留言支持一下
2019-07-22
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-异构云环境下基于分簇的云资源感知任务调度方案.pdf 10积分/C币 立即下载
    1/4
    论文研究-异构云环境下基于分簇的云资源感知任务调度方案.pdf第1页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >