积分商城

最新搜索： CH340 排插 入门教程 canopen TMC5160 altium Designer 20 电路设计与仿真从入门到精通
您现在的位置是：首页 > 技术资料 > 基于最小费用最大流的大规模资源调度方法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

基于最小费用最大流的大规模资源调度方法

更新时间：2019-12-25 17:38:49 大小：1M 上传用户：zhiyao6查看TA发布的资源 标签：大规模资源调度 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模,仅能满足局部最优解且只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束这3种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构,使其具备适应性调整能力;其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法;最后,实验对比公平性、优先级和放置约束这3种资源调度典型系统,验证了该方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真,验证了万级规模下,基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%.


部分文件列表

文件名 大小
基于最小费用最大流的大规模资源调度方法.pdf 1M

【关注视频号领20积分】   【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
软件学报 ISSN 1000-9825, CODEN RUXUEW  
Journal of Software,2017,28(3):598-610 [doi: 10.13328/j.cnki.jos.005167]  
©中国科学院软件研究所版权所有.  
E-mail:  
Tel: +86-10-62562563  
基于最小费用最大流的大规模资源调度方法∗  
1,2,3  
1
1,2,3  
2,3  
1
陈晓旭  
,
吴
恒
,
吴悦文  
,
陆志刚  
,
张文博  
1(中国科学院 软件研究所 软件工程技术研究开发中心,北京 100190)  
2(计算机科学国家重点实验室(中国科学院 软件研究所),北京 100190)  
3(中国科学院大学,北京 100049)  
通讯作者: 吴恒, E-mail:  
摘
要: 并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模,仅能满足局  
部最优解且只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建  
模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优  
先级和放置约束这 3 种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构,使其具备适应性  
调整能力;其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法;最后,实验对比公平性、优先级和放  
置约束这 3 种资源调度典型系统,验证了该方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真,  
验证了万级规模下,基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低 90%.  
关键词: 资源调度;最小费用最大流;增量式算法  
中图法分类号: TP316  
中文引用格式: 陈晓旭,吴恒,吴悦文,陆志刚,张文博.基于最小费用最大流的大规模资源调度方法.软件学报,2017,28(3):  
598-
英文引用格式: Chen XX, Wu H, Wu YW, Lu ZG, Zhang WB. Large-Scale resource scheduling based on minimum cost  
maximum flow. Ruan Jian Xue Bao/Journal of Software, 2017,28(3):598-
5167.htm  
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  
∗ 基金项目: 国家重点研发计划(2016YFB1000103); 国家自然科学基金(61572480); 国家科技支撑计划(2015BAH55F02)  
Foundation item: National Key Research and Development Plan (2016YFB1000103); National Natural Science Foundation of China  
(61572480); National Key Technology Research and Development Program of the Ministry of Science and Technology China (2015BAH  
55F02)  
收稿时间: 2016-07-31; 修改时间: 2016-09-14; 采用时间: 2016-11-01; jos 在线出版时间: 2016-11-29  
CNKI 网络优先出版: 2016-11-29 13:35:09, http://www.cnki.net/kcms/detail/11.2560.TP.20161129.1335.009.html  
陈晓旭 等:基于最小费用最大流的大规模资源调度方法  
599  
随着互联网(Internet)、物联网(IoT)等技术的快速发展,数据(data)开始从简单处理对象向基础性服务转变,  
多个作业(job)同时提交,分解成并行执行任务(task),在至少万级规模的物理服务器上运行处理,已成主流的应  
用模式,学术界称为并行作业(concurrent job)[1]问题.例如,Github 每年需处理 2 000 多万个作业[2],Facebook 每天  
要响应近万个作业请求[3]  
大规模资源调度是指决策任务与物理资源映射关系的过程,它是解决并行作业问题的关键.已有的研究工  
作或权衡任务干扰约束(cross-task interference)和资源利用率(high resource utilization),如 Whare-Map[4]  
Tetrisched[5];或权衡公平性(fairness)和数据局部性(data locality),如 Quincy[6],YARN[7];或权衡公平性(fairness)和  
隔离性(isolation),如 Mesos[8],Omega[9];或满足优先级(priority)等单一约束条件,如 Borg[3],Alsched[10],Quasar[11]  
.
,
.
上述研究均假设决策目标固定不变,但相关研究表明:相同的作业集合采用固定的调度决策算法,或导致极低的  
资源利用率,如 Twitter 平均资源利用率小于 20%[11];或引起作业性能下降 80%[8],如任务未绑定特殊硬件进行加  
速,违反优先级约束.因此,如何提高大规模资源调度的灵活性,使其具备按需配置能力,正逐渐引起工业界和学  
术界的广泛关注,面临巨大挑战.所谓灵活性,是指调度系统支持多种调度目标,且可针对不同场景需求,灵活选  
取最优调度目标以适应需求.例如典型的电商场景,商品的推荐任务关注时效性,应优先处理;涉及商品的各种  
统计任务则强调公平性,需平分资源[6]  
.
本文首先对相关工作进行总结,归纳出 3 种典型的度量指标,接着分析基于队列(queueing)的大规模资源调  
度模型,举例说明队列模型灵活性不足,难以支持多种调度场景,无法按需配置生效,其本质原因是该模型表达  
能力不足,且仅能满足局部最优解.然后,基于最小费用最大流图对大规模资源调度建模,将满足 3 种典型度量的  
资源调度方法映射为图的构造问题.最后,采用增量方法降低图的求解复杂度.通过实测和仿真两个方面,验证  
了本方法的有效性.  
本文的主要贡献是:提出了基于最小费用最大流的大规模资源调度方法,将资源调度问题转换成最小费用  
最大流图的构造和求解问题;总结相关工作,从公平性、优先级和放置约束这 3 种典型度量入手,将调度目标映  
射为图的构造问题,并通过改变图的结构使其具备适应性调整能力,支持按需配置;图的求解过程本质是资源调  
度决策过程,快速决策是方法实用性前提.本文针对图的求解时间复杂度高的问题,实现了一种增量式优化算  
法;实现原型系统,通过实测验证本方法的灵活性,可应对真实场景下按需配置调度目标的需求,且调度延迟几  
乎与队列模型相当,可适应万级规模的资源调度场景.  
本文第 1 节是相关工作介绍和总结.第 2 节是问题描述和研究思路,分析队列模型灵活性不足的原因,提出  
基于最小费用最大流的资源调度建模方法.第 3 节介绍采用最小费用最大流的求解过程,核心是图的构造和求  
解方法.第 4 节从实测和仿真两个方面验证本方法的有效性.最后总结本文工作,并展望未来的研究方向.  
1
相关工作  
大规模资源调度是近年来学术界研究热点,根据度量指标的不同,大致可以分为 3 类.  
·
面向公平性的资源调度方法  
Delay-Schedule[12]采用队列模型,主要权衡任务调度公平性和数据局部性,针对已有贪心算法难以计算全  
局最优解的不足,设计了“匹配-调度”和“不匹配-超时等待-重调度”机制;Sparrow[13]采用队列模型,提出了一种  
基于采样的资源调度方法,根据历史运行数据不断修正调度策略,其目的是兼顾公平性和数据局部性;Mesos[8]  
实现一种面向异构任务的资源调度框架,主要考虑任务公平性需求,采用两级队列模型,任务只允许在分配的资  
源上运行;Quincy[6]将任务资源需求和物理资源供给转变为最小费用流图问题,通过费用的调整达到权衡任务  
公平性和数据局部性目标.Choosy[14]将 Max-Min 算法应用到队列模型,提出了一种资源公平调度方法.  
·
面向优先级的资源调度方法  
Borg[3] 采用队列模型,主要考虑任务的优先级特性,设计了任务排序算法和低优先级任务置换机制;  
Omega[9]是 Borg 工作的扩展,主要解决任务调度优先级和任务运行干扰之间的矛盾;Quasar[11]面向异构物理资  
源场景,提出了一种基于分类的资源调度方法,建立了一套任务和资源匹配的评估模型,优先将应用调度到合适  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号