| 陈晓旭,吴恒,吴悦文,陆志刚,张文博.基于最小费用最大流的大规模资源调度方法.软件学报,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 | |
|
| 摘要点击次数: 1769 |
| 全文下载次数: 1462 |
| 中文摘要: |
| 并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模，仅能满足局部最优解且只能适应调度目标固定不变的场景，灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法，将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先，选择公平性、优先级和放置约束这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阅读器 |
