| 引用本文: | 刘少伟,任开军,邓科峰,等.云平台上基于关键路径截取的有向无环图应用调度算法.[J].国防科技大学学报,2017,39(3):97-104.[点击复制] |
| LIU Shaowei,REN Kaijun,DENG Kefeng,et al.Directed acyclic graph application scheduling strategy based on critical path cut on cloud platform[J].Journal of National University of Defense Technology,2017,39(3):97-104[点击复制] |
|
| |
|
|
| 本文已被：浏览 8003次 下载 6928次 |
| 云平台上基于关键路径截取的有向无环图应用调度算法 |
| 刘少伟1, 任开军2, 邓科峰2, 宋君强2 |
|
(1. 国防科技大学 计算机学院， 湖南 长沙 410073;2. 国防科技大学 海洋科学与工程研究院， 湖南 长沙 410073)
|
| 摘要: |
| 针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题，给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术，循环找出最晚完成的未分配任务，从该任务出发，在所有未分配任务构成的图中找出最大连通子图，并计算该子图的关键路径，然后将关键路径上的任务集调度到性能匹配的虚拟机上执行；同时通过任务回填技术充分利用虚拟机的空闲时间槽，提高资源使用率。实验结果表明，在云计算平台上，该算法不仅能够在截止时间内完成有向无环图科学应用，而且可以提高资源使用率，有效减少完成该应用所需整体费用。 |
| 关键词: 云计算平台 关键路径 虚拟机 有向无环图 资源配置 |
| DOI：10.11887/j.cn.201703016 |
| 投稿日期：2016-02-14 |
| 基金项目:国家自然科学基金资助项目（61572510）；国家公益行业专项计划资助项目(GYHY201306003) |
|
| Directed acyclic graph application scheduling strategy based on critical path cut on cloud platform |
| LIU Shaowei1, REN Kaijun2, DENG Kefeng2, SONG Junqiang2 |
|
(1. College of Computer, National University of Defense Technology, Changsha 410073, China;2. Academy of Ocean Science and Engineering, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| To address the problems that the resource is surplus, the resource utilization rate is low and the cost is unreasonably high for virtual machines in the scientific application of DAG(directed acyclic graph), a novel DAG scientific workflow scheduling algorithm based on CPC(critical path cut) was proposed. In the algorithm, the CPC technology was adopted to circularly find the unallocated task which is finished at last; the biggest connected subgraph was found from the graph constructed by the whole unallocated tasks; the critical path of this subgraph was calculated and the task set on the critical path was scheduled to the performance-matched virtual machine to execute. Meanwhile, the isolated tasks were used to fill in the idle slots of the virtual machines, such that the resource utilization could be improved. Experimental results demonstrate that, the proposed CPC algorithm can effectively reduce the execution cost of the scientific workflows while satisfying the deadline constraint in mean time. |
| Keywords: cloud computing platform critical path virtual machine directed acyclic graph resource allocation |
|
|
|
|
|
