论文研究-网格环境下分布式仿真应用的资源调度.pdf

所需积分/C币:6 2019-07-22 23:48:44 1.41MB .PDF
收藏 收藏
举报

针对网格环境中典型的交互密集型应用——分布式仿真问题,综合考虑具体应用的计算量及通信需求情况,结合网络资源的限制约束,提出了实现资源节点优化选择的过程框架,给出了节点优化选择的问题模型和求解算法。仿真实验表明所提出的优化策略能够显著提高分布式仿真应用执行的效率。
892 计算机应用研究 已知:图R(n)=(V,E,U)是一个边带权的无向简单网络 表1随机选择与采用优化算法的100步到达同步点的 没有环与重复边)。其中:V=}(i=1,2,…,)为顶点集 通信时间消耗 F为边集;U={n(n;,v)}(i,=(1,2,…,n);≠为权函数 实验1(图5(a))实验Ⅱ(图5(b)) 算法 (权值为不小丁零整数)。X={x1,x2,…,x4}为一个元素为正 随机选择算法1随机选算法2 平均通信时间消耗/s52.04 6.64 81.41 整数的向量,且∑x;≥n。 提高效率北率/% l6.1 问题:将R(n)中顶点划分为k个顶点子集R1,R2,…,R, 仿真结果表明:在仿真应用资澳节点选择过程中,优化算 记每个子集的顶点数为N(R);优化目标函数 法相对随机选择明显缩短应用运行中的通信时间,提高了应用 的执行效率。算法1同时考虑了对网络资源带宽的合理使用 ∑u(x1,n2)} 和星型通信模式应用需求,显著提高星型模式的通信效率;算 满足约束条件:1≤i≤h,N(R)≤x 法2中,主要考虑了应用需求因素,对资源带宽的使用没有达 这个问题属于组合图论中 Minimum k-cut间题的变形,是 到最优化。 NP闲难的。虽然其对丁确定NR)(i=1,2,…,k)的划分 上面的仿直仅采用了图4和5的算例,难以保证对各种不 存在一个多项式时间解法,但由丁过丁复杂(复杂性为O 同应用都获得一致的效果。但实验表明考虑应用需求情况的 资源选择优化算法在合理分配网络资源、提高应用执行效率方 (n2)2,实际难以使用。具体在资源节点选择间题中,采用面能起到一定的作用。 算法2。 模型屮可以敚宽节点计算能力没有差别(认为每个网格节 输入:仿真应用通信需求图R(n);网络资源状况图G(k) (n)将()的面点按权值X=Px;}(i=1,2,…,k)从大到小排点承载一个子任务的能力相同)的假设,而通过诸如CPL计算 序,排序后为x1≥x2≥…≥x 能力、内冇容量和负载比率等因索的量化值来衡量具体节点计 (b)定义顶点集R=K(n);i=1; 算能力大小,并评估具体应用计算需求来获得最优化的限制条 (c)从R中找出内部连接权值较大的子集R;,R;的顶点数目为 件。模型没有区分通信的方向性,即认为双向的通信资源与需 。其具体实现如下 (1)从R'找出连接边权值和最大的顶点n,定义顶点子集R2= 求是等同的。考虑通信的双向性是未来需要展开的工作之 t};R=R′-R:;j=1; (2)从R中找出R与连接权值最大的顶点;R=B+1,R=3结束语 R-1r;}=j+1; 当j<x1,返回(2):香则转到(d 网格环境资源选择中如何考虑具体应用的定量需求是 (d)R'=R′-R1;i=i+1;当N(R)>x’返回(c);否则m 还未被深入研究的课题,本文针对交互密集型应用—分布 Rn=R';结束 式仿真问题,介绍了在考虑应用需求情况下资源的优化选择策 输出:R(n)顶点的m(m≤k)个于集的划分R1,R,…,Rn,子集的 顶点数目分别相应于G(k)中较大的m个顶点权值,即满足略与其实现过程。在一系列简化假设的基础上,给出了问题的 N(R:)=x’当(i=1,2 优化模型与算法实现。 N(Ra)≤x'm 接下来的工作包括针对更多的网络资源和应用需求状况 算法2的思路是:根据网络计算资源较多的LAN中的资的仿真。另外,一个简单的网格资源分配与应用性能测试环境 源约束,依次从仿真子任务集中选出内部交互较大的任务子集也正在设计之中。日前网络资源状况和应用需求状况的获取 进行加载,获得一个近似较优的结果。其中步骤(c)的复杂程以及优化算法的实现过程很大程度还需要通过于上方式表述, 度约为O(n2k),完整算法2的复杂程度约为O(n2k2)。 硏究如何基于计算机完全自动实现是进一步的工作 例如,对应图4的资源状况图5(b)中的子任务的分配计参考文献 算结果为:④⑥③加载到LAN3,①2⑤加载到LA\,⑦加载 [1 NABRZYSKI J, SCHIOPE J M, WEGLARZ J. GIid resource manage- 钊LAN2。 ment: state of the art and future trends[M.[S1.l: Kluwer Aca- demic publishers 2003 2仿真实验与结果的讨论 [2] CZAJKOWSKI K, FOSTER I, KARONIS N, el aL. A resource mana gement architecture for metacomputing systems[C//Proc of Work 通过实例仿真对算法进行了对比测试。资源状况G(k)如 shop on Job Scheduling Strategies for Parallel Processing. London 图4所示。 Springer-Verlag, 1998: 62-82 仿真屮为了简化问题,同一局域网或集群内节点间的通信时3] SHAO G, BERMAN F, WOLSKI R. Master/ Slave computing on the 间忽略不计;不同时段局域网间的数据传输速率(单位:Mbps)根 rid[C]// Proc of Heterogeneous Computing Workshop( HCW 00) 据带宽大小( bandwidth)在一定区间(区间(0, bandwidth)内服从 Washington DC: IEFF Computer Society Press, 2000: 628-617 正态分布(均值取 bandwidth/2,标准差取 bandwidth/6)。 [4 SUBHLOK J, LIEU P, LOWEKAMP B. Automatic node selection for high performance applications on networks[ C//Proc of the 7th ACM 为了模拟分布式仿真应用的同步需求,每阶段的数据交互 SICPLAN Symposium on Principles and Practice of Parallel program 需全部完成到达同步点后才能进入下一交互时段。实验中,同 ming.1999:164-172 步点要求所有∫仟务间完成传输需求的每秒平均数据量。这5]CUES, SUBHLOK J. Communication pattern based node selec 里不考虑应用执行过程中的计算时间消耗。 tion for shared networks[C//Proc of Active Middleware Services 实验Ⅰ针对图5(a),仿真计算两种分配策略的道信时间 2003:69-76 [6 WOLSKI R, SPRING N, HAYES J. The net work weather service:a 消耗:不考虑具体应用需求按随机分配与按算法1分配。实验 distributed resource performance forecasting service for metacomputing Ⅱ对图5(b)进行类似仿真。到达100次同步点的数据如表1 [J]. Future Generation Computer Systems, 1999, 15(5-6) 所示。 757-768 (下转第896页) 896· 计算机应用研究 第26卷 初始的变更口志 伴随变更修正 日志清洗算法相比,时间较少,效率较高,算法性能比较稳定, B: =A: 1:=2. T lset(参加考博撰写毕业论文,|~=参加考博NneB→出=参加考博! 其中,c4清洗后之所以比原变更事务数多是因为cl中带有 毕业答辩),pi <pp2= Insert(S,选洙情况,完成选课仨务 伴随变更的变更事务太多且相互的伴随变更互异,不能相互抵 T:=;nent(,选课情况,完成选课任务,参加考博 4-(ap3=Mve(完成于题发表学术论文 消,从而使得清洗后的操作数反而变多,但实际的操作数却已 撰写毕业论文), prinary A,=(op,= iNsert(s,完成开题完成选课任务, 大大减小。实验结果表明该算法是正确和有效的。 发表学术论文) 42(o3 Delete(S完成开题),pr N=完成开题,MnB→AB={参加考博,完成开题 (yDl(s研究方向 concomitant>) I=m:=s研究方间 4结束语 4=(o2= Delete(,中期第选), prmary V=中期年选,NB→步{参加考博完成开题,中筛选} op=Date发论文情况) concomitant)9neZm 72=06研究方向Dobs发表论文情况) 4=(qp1=nrtS,中期崎选发表学木论文,M=中期选NB=参加考博,完成开题,中期筛选 消除过程变更日志中的噪声和不相关信息是过程变更挖 撰写毕业论文,pr 文期知的她发表学一爱来途受热据研究中亟待解决的热点问题。笔者针对带有复杂变更事务 的过程变更日志,以基丁图的工作流过程模型为例,通过对复 ms:=T-/Ta={ iNsert(s先课情况完成选课 任务参加考博} 杂变更事务中的主变更操作及其伴随变更操作的分析,得出了 rn:-rn/T-- isDelete (S,究方向 日志中复杂变史事务处理规则,解决∫过程模型中活动、控制 图6变更日志伴随变更修正 弧、数据元素和数据弧的变更操作的处理问题。实验结果证明 修正伴随变更摸怍后的变更日 N三参加考博}D远误特况 该日志清洗算法是正确的 lnet(s,选课情况完成选课选课情况A→A=远课悄况 下一步研究将细化到由变更引起的偏差产生的原因,从语 謀情况,参加考博 义层面对变更日忐清洗算法作进一步改进;同时将利用得到的 oP。=Move(S,完成开题,发表学术 选课情况,参加老博,完成开题 (s,完成开题,完成选课 开趣M“UD)∧ new Position→ 过程变更信息结合执行日志的上下文信息对过程模型进行 任务,发表学术论文 op= Delete(s研究方向) 研究方向A=A=4∪研究方向 致性分析。 op= Delete(S:完成开题) 完成开题∈A op =dElete 期筛选∈A→A=A 参考文献 爷远eM:UD 中 qp= slnsert'(s中期师选发表学术一十中期进∈4 论文撰写毕业论文 [1 GUNTHER C W, RINDERLE S, REICHERT M, et aL. Change adaptive process management systems[ C]//Prcc Df OTM Ce 消洗后的变更日志 ferences.2006:309-326 oD:= iNserts,选课情况,完成选课任务,参加考博) 2]RINDERLE S. Schema evolution in process management systems [D PINsent(,参加考博撰写业论文毕业答辩) 28 reMove(S,完成开题发表学术论文撰写毕业论文 Germany: University of UIm. 2004 D= Delete(S,研究方向) [3 RINDERLE S, REICHERT M, JURISCH M, et al. On representing purging, and utilizing change logs in process management system 图7变更日志清洗 [C]//Proc cf International Conference on Business Process Manage 3.2算法效率和性能分析 ment(BPM06). Berlin: Springer, 2006: 241-256 为了判断算法的效率和性能,构建包含复杂变更事务的变[4] AALST W van der, GUENTHER C, RECKER J,eta. Using process 更日志实验原型。利用 ProM Import Framework模拟生成变更 mining to analyze and improve process flexibility C]//Proc of the 日志文件。确定MXML模型保证模拟生成变更日志中每个变 18th International Conference on Advanced Information Systems Engi merril 006:168-177 更事务只包含一个主变更操作,即第一个对活动节点的操作。 AALST W van der. Business alignment: using process mining as a 利用实验原型处理生成的变更日志,实验结果如表1所示。 tool for delta analysis and conformance testing J]. Requirements 表1实验测试结果 Engineering Joumal, 2005, 10(3): 198-21I 变更日志工作流变更事务数/具有伴随清洗后变所需时间 [6 RINDERLE S. REICHERT M, DADAM P. Flexible support of team 名称轨迹数 变更的变可事务数 更操作数 processes by adaptive workflow systems[ J]. Distributed and Parallel 5975/1280 2655 Databases,2004,16{1):91-116 1000 8750/244 4793 1000 1350/209 936 [7] LEYMANN F, ALTENHUBER W. Managing business processes as 1000 8240/5232 8578 916 an infoImation resource[ J]. IBM Systems Journal, 1994, 33(2) 1000 10550317 6361 1307 326-348 [8 DONGEN B van, AALST W van der. A meta model for process mi 测试结果表明,算法能够对基于变更事务的变更日志进行 ning data[ C//Proc of CAiSE'05 Workshops. 2005: 309-320 日忐清洗,清洗后的变更日志m只包含对原过程模型S产[9] EICHERT M, DADAM P. ADEPT Ilex- upporting dynamic changes 生实际影响的变更操作。同时该算法解决了原变更日志中变 of workflows without loosing control[ J_. Journal of Intelligent Infor 更事务的主变更操作相互抵消产生的隐藏影响。与文献[3] mation Systems,1998,10(2):93-129 (上接第892页) IM.IS1.I: Kluwer Academic Publishers, 2004:77-91 [7 DINDA P, GROSS T, KARRER R, et al. The architecture of the re- [10] GOTETI S, SUBHLOK J. Communication pattern based node selec mos system[ C_//Prme of the 10th IFEF. International Symposium on tion for shared networks[C //Proc of the 5th Annual Workshop on High Performance Distributed Computing. San Francisco: IEEE Com Active Middleware Services. Seattle: IEEE Computer Society Press puter Society Press, 2001: 252-265 2003:69-76 [ 8] KUHNEMANN M, RAUBER T, RUNGER C Z. A source code anal- [11] GAREY M R, JOHNSON D S. Computers and intractability a guide yzer for performance prediction C //Proc of the 4th Workshop on to the theory of NP-completeness[M. New York: W H Freeman Massively Parallel Processing04[S 1.]: IFEF Computer Society Co.1990 2004:262-270 [12 CLODSCHMIDT O, HOCHBAUM D S. Poly nomial algorithm for the [9 KUHNEMANN M, RAUBER T, RUNGER G. Performance modeling k-cut problem C//Proc of the 29th Annual Symp on the Founda- for task-parallel programs performance analysis and grid computing tions of Computer Science. Tokyo: Springer-Verlag, 1988: 444-451

...展开详情
试读 4P 论文研究-网格环境下分布式仿真应用的资源调度.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-网格环境下分布式仿真应用的资源调度.pdf 6积分/C币 立即下载
    1/4
    论文研究-网格环境下分布式仿真应用的资源调度.pdf第1页
    论文研究-网格环境下分布式仿真应用的资源调度.pdf第2页

    试读已结束,剩余2页未读...

    6积分/C币 立即下载 >