Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (11): 3295-3301.DOI: 10.11772/j.issn.1001-9081.2020121984

• Advanced computing • Previous Articles     Next Articles

Scheduling strategy of irregular tasks on graphics processing unit cluster

Fan PING1,2, Xiaochun TANG1,2(), Yanyu PAN1,2, Zhanhuai LI1,2   

  1. 1.School of Computer Science,Northwestern Polytechnical University,Xi’an Shaanxi 710129,China
    2.Key Laboratory of Big Data Storage and Management,Ministry of Industry and Information Technology (Northwestern Polytechnical University),Xi’an Shaanxi 710129,China
  • Received:2020-12-16 Revised:2021-06-02 Accepted:2021-08-03 Online:2021-07-24 Published:2021-11-10
  • Contact: Xiaochun TANG
  • About author:PING Fan,born in 1997,M. S. candidate. Her research interests include distributed computing,cluster resource management
    TANG Xiaochun,born in 1969,Ph. D.,associate professor. His research interests include graph data management, distributed computing,cluster resource management
    PAN Yanyu,born in 1997,M. S. candidate. Her research interests include big data,cluster resource management
    LI Zhanhuai,born in 1961,Ph. D.,professor. His research interests include massive data management,big data computing.
  • Supported by:
    the National Key Research and Development Program of China(2018YFB1003400)


平凡1,2, 汤小春1,2(), 潘彦宇1,2, 李战怀1,2   

  1. 1.西北工业大学 计算机学院,西安 710129
    2.工信部大数据存储与管理重点实验室(西北工业大学),西安 710129
  • 通讯作者: 汤小春
  • 作者简介:平凡(1997—),女,陕西咸阳人,硕士研究生,主要研究方向:分布式计算、集群资源管理
    汤小春(1969—),男,陕西汉中人,副 教授,博士,主要研究方向:图数据管理、分布式计算、集群资源管理
    潘彦宇(1997—),女,甘肃兰州人,硕士研究生,主要研究方向:大数据、集 群资源管理
  • 基金资助:


Since a large number of irregular task sets have low resource requirements and high parallelism, the use of Graphics Processing Unit (GPU) to accelerate processing is the current mainstream. However, the existing irregular task scheduling strategies either use an exclusive GPU approach or use the traditional optimization methods to map tasks to GPU devices. The former leads to the idleness of GPU resources, and the latter cannot make maximum use of GPU computing resources. Based on the analysis of existing problems, an idea of multi-knapsack optimization was adopted to enable more irregular tasks to share GPU equipment in the best way. Firstly, according to the characteristics of GPU clusters, a distributed GPU job scheduling framework consisting of schedulers and executions was given. Then, with GPU memory as the cost, an Extended-grained Greedy Scheduling (EGS) algorithm based on GPU computing resources was designed. In the algorithm, as many irregular tasks as possible were scheduled on multiple available GPUs to maximize the use of GPU computing resources, and the problem of idle GPU resources was solved. Finally, the actual benchmark programs were used to randomly generate a target task set to verify the effectiveness of the proposed scheduling strategy. Experimental results show that, compared with the traditional greedy algorithm, the Minimum Completion Time (MCT) algorithm and the Min-min algorithm, when the number of tasks is equal to 1 000,the execution time of EGS algorithm is reduced to 58%, 64% and 80% of the original ones on average respectively, and the proposed algorithm can effectively improve the GPU resource utilization.

Key words: Graphics Processing Unit (GPU) general computing, independent task, task scheduling strategy, scheduling framework, resource utilization


针对大量的资源需求少且并行度高的不规则任务集合,利用图形处理器(GPU)来加速处理是目前的主流。然而现有的不规则任务调度策略要么采用独占GPU的方式,要么使用传统的优化方法将任务映射到GPU设备上。前者导致GPU资源的闲置,后者不能最大限度利用GPU计算资源。在分析了现存问题的基础上,采用多背包优化思想,使更多的不规则任务以最佳的方式共享GPU设备。首先,针对GPU集群的特点,给出了由调度器、执行器组成的分布式GPU作业调度框架;然后,以GPU显存为代价,设计了一种基于GPU计算资源的扩展贪心调度(EGS)算法,该算法将尽可能多的不规则任务调度到多个可用的GPU上,以最大限度地利用GPU计算资源,并解决了GPU资源的闲置问题;最后,使用实际基准程序随机生成目标任务集来验证所提调度策略的有效性。实验结果表明,与传统的贪心算法、最早完成时间(MCT)算法和Min-min算法相比,当任务数量等于1 000时,EGS算法的执行时长分别平均降低至原来的58%、64%和80%,并且能有效提升GPU资源利用率。

关键词: 图形处理器通用计算, 独立任务, 任务调度策略, 调度框架, 资源利用率

CLC Number: