资源描述：
《云平台上基于关键路径截取的有向无环图应用调度算法（》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、云平台上基于关键路径截取的有向无环图应用调度算法*收稿日期：2015-XX-XX基金项目：国家自然科学基金资助项目（61572510）；国家公益行业专项计划资助项目(No.GYHY201306003)作者简介：刘少伟（1987－），男，陕西渭南人，博士研究生，E-mail：liushaowei@nudt.edu.cn；宋君强（通信作者），男，研究员，硕士，博士生导师，E-mail:junqiang@nudt.edu.cn.刘少伟1,任开军2,邓科峰2,宋君强2（1.国防科学技术大学计算机学院，湖南长沙410073；2.国防科学技术大学海洋科学与工程研
2、究院，湖南长沙410073）摘要：云计算虚拟机按需获取并按使用量付费的特性吸引着越来越多的大规模有向无环图应用科学应用部署到云平台上。由于云计算平台提供多种类型的虚拟机并按时间周期计费，使得这些科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题。针对此类问题，本文给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术，循环找出最晚完成的未分配任务，从该任务出发，在所有未分配任务构成的图中找出最大连通子图，并计算该子图的关键路径，然后将关键路径上的任务集调度到性能匹配的虚拟机上执行；同时通过任务回填技术充分利用虚拟机
3、的空闲时间槽，提高资源使用率。实验结果表明，在云计算平台上，该算法不仅能够在截止时间内完成有向无环图科学应用，而且可以提高资源使用率，有效减少完成该应用所需整体费用。关键词：云计算平台；关键路径；虚拟机；有向无环图；资源配置中图分类号：TP393文献标志码：A 文章编号：CriticalPathCutBasedDAGapplicationSchedulingStrategyOnCloudPlatformLIUShao-Wei1,2,RENKai-Jun1,2,DENGKe-Feng1,2,SONGJun-Qiang1,2(1.CollegeofC
4、omputer,NationalUniversityofDefenseTechnology,Changsha410073,China；2.AcademyofOceanScienceandEngineering，NationalUniversityofDefenseTechnology,Changsha410073,China)Abstract:Thecharacteristicsofcloudcomputingsuchason-demandprovisioningofvirtualmachinesinapay-as-you-gomannerhavea
5、ttractedmoreandmorescientificworkflowsdeployingoncloudplatforms.Sincetherearemanytypesofvirtualmachineswhicharechargedbytimeperiods,thedifficultiesofresourceprovisioningandtaskschedulinghindersefficientexecutionofscientificworkflowsoncloudplatforms.Toaddressthechallenge,anovelC
6、riticalPathCut(CPC)basedscientificworkflowschedulingalgorithmisproposedinthispaper.ThealgorithmschedulestasksonappropriatevirtualmachinebasedonCPCstrategybyanalyzingthedependenciesofthetasks;meanwhile,itusestheisolatedtaskstofillintheidleslotsofthevirtualmachines,suchthattheres
7、ourceutilizationcanbeimprovedwithoutaffectingtheoverallperformance.Experimentalresultsdemonstratethat,theproposedCPCalgorithmcaneffectivelyreducetheexecutioncostofthescientificworkflowswhilesatisfyingthedeadlineconstraintinmeantime.Keywords:Cloudplatform;Criticalpath;Virtualmac
8、hine;Directedacyclicgraph;Resourceallocation在许多科学研究领域，
