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

发布时间：2018-05-06 16:43

本文选题：资源调度 + 最小费用最大流　；参考：《软件学报》2017年03期

【摘要】：并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模,仅能满足局部最优解且只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束这3种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构,使其具备适应性调整能力;其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法;最后,实验对比公平性、优先级和放置约束这3种资源调度典型系统,验证了该方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真,验证了万级规模下,基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%.
[Abstract]:Parallel jobs are the research focus of large-scale resource scheduling. The existing researches usually use queue to model the resource scheduling, which can only satisfy the local optimal solution and only adapt to the situation where the scheduling goal is fixed, so it is not flexible enough. In this paper, a modeling method of large-scale resource scheduling based on minimum cost and maximum flow is proposed. The problem of resource demand and physical resource supply of task is transformed into the construction and solution of minimum cost maximum flow graph. Firstly, three typical metrics, fairness, priority and placement constraints, are selected as the starting point to map to graph construction from the perspective of resources, and make the graph have adaptive adjustment ability by changing the structure of the graph. In order to solve the problem of high complexity of graph solving time, an incremental optimization algorithm is implemented. Finally, compared with three typical resource scheduling systems, fairness, priority and placement constraints, it is verified that the method can be configured on demand. Support for multiple scheduling objectives with flexibility. The simulation results show that the resource scheduling delay based on graph can be reduced by 90% compared with that based on unoptimized graph algorithm.
【作者单位】：中国科学院软件研究所软件工程技术研究开发中心;计算机科学国家重点实验室(中国科学院软件研究所);中国科学院大学;
【基金】：国家重点研发计划(2016YFB1000103) 国家自然科学基金(61572480) 国家科技支撑计划(2015BAH55F02)~~
【分类号】：O224

【相似文献】