主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第8期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
陈晓旭,吴恒,吴悦文,陆志刚,张文博.基于最小费用最大流的大规模资源调度方法.软件学报,2017,28(3):598-610
基于最小费用最大流的大规模资源调度方法
Large-Scale Resource Scheduling Based on Minimum Cost Maximum Flow
投稿时间:2016-07-31  修订日期:2016-09-14
DOI:10.13328/j.cnki.jos.005167
中文关键词:  资源调度  最小费用最大流  增量式算法
英文关键词:resource scheduling  minimum cost maximum flow  incremental algorithm
基金项目:国家重点研发计划(2016YFB1000103);国家自然科学基金(61572480);国家科技支撑计划(2015BAH55F02)
作者单位E-mail
陈晓旭 中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190
计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190
中国科学院大学, 北京 100049 
 
吴恒 中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190 wuheng@otcaix.iscas.ac.cn 
吴悦文 中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190
计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190
中国科学院大学, 北京 100049 
 
陆志刚 计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190
中国科学院大学, 北京 100049 
 
张文博 中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190  
摘要点击次数: 785
全文下载次数: 749
中文摘要:
      并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模,仅能满足局部最优解且只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束这3种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构,使其具备适应性调整能力;其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法;最后,实验对比公平性、优先级和放置约束这3种资源调度典型系统,验证了该方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真,验证了万级规模下,基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%.
英文摘要:
      Concurrent job execution is a hot topic in large-scale resource scheduling research. Existing efforts employ queueing model with local optimal solution to schedule co-located tasks, thus can only fit specific requirement. Hence, how to design a single scheduler to meet diverse requirements is challenging. This paper introduces Sirius, a new framework for resource scheduling based on minimum cost maximum flow network. This new approach makes it easy to express scheduling requirements, including fairness, priority and placement constraint, on a unified way as a typical graph construction and solution problem. Meanwhile, an incremental algorithm is implemented to speed up the flow network solver, significantly reducing its runtime by 90 percent.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利