| 本文已被：浏览 3460次 下载 6373次 |
码上扫一扫！ |
|
|
| 基于最小费用最大流的大规模资源调度方法 |
|
陈晓旭1,2,3, 吴恒1, 吴悦文1,2,3, 陆志刚2,3, 张文博1
|
|
1.中国科学院 软件研究所 软件工程技术研究开发中心, 北京 100190;2.计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;3.中国科学院大学, 北京 100049
|
|
| 摘要: |
| 并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模，仅能满足局部最优解且只能适应调度目标固定不变的场景，灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法，将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先，选择公平性、优先级和放置约束这3种典型度量作为切入点，从资源视角映射为图的构造问题，通过改变图的结构，使其具备适应性调整能力；其次，针对图的求解时间复杂度高的问题，实现了一种增量式优化算法；最后，实验对比公平性、优先级和放置约束这3种资源调度典型系统，验证了该方法可通过按需配置，支持多种调度目标，具备灵活性.并通过实验仿真，验证了万级规模下，基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%. |
| 关键词: 资源调度 最小费用最大流 增量式算法 |
| DOI：10.13328/j.cnki.jos.005167 |
| 分类号:TP316 |
| 基金项目:国家重点研发计划（2016YFB1000103）；国家自然科学基金（61572480）；国家科技支撑计划（2015BAH55F02） |
|
| Large-Scale Resource Scheduling Based on Minimum Cost Maximum Flow |
|
CHEN Xiao-Xu1,2,3, WU Heng1, WU Yue-Wen1,2,3, LU Zhi-Gang2,3, ZHANG Wen-Bo1
|
|
1.Technology Center of Software Engineering, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;2.State Key Laboratory of Computer Science(Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;3.University of Chinese Academy of Sciences, Beijing 100049, China
|
| Abstract: |
| 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. |
| Key words: resource scheduling minimum cost maximum flow incremental algorithm |
