不规则任务在图形处理器集群上的调度策略

doi:10.11772/j.issn.1001-9081.2020121984

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (11): 3295-3301.DOI: 10.11772/j.issn.1001-9081.2020121984

不规则任务在图形处理器集群上的调度策略

平凡¹^,², 汤小春¹^,²(), 潘彦宇¹^,², 李战怀¹^,²

^1.西北工业大学计算机学院，西安 710129
^2.工信部大数据存储与管理重点实验室（西北工业大学），西安 710129

收稿日期:2020-12-16 修回日期:2021-06-02 接受日期:2021-08-03 发布日期:2021-07-24 出版日期:2021-11-10
通讯作者: 汤小春
作者简介:平凡（1997—），女，陕西咸阳人，硕士研究生，主要研究方向：分布式计算、集群资源管理
汤小春（1969—），男，陕西汉中人，副教授，博士，主要研究方向：图数据管理、分布式计算、集群资源管理
潘彦宇（1997—），女，甘肃兰州人，硕士研究生，主要研究方向：大数据、集群资源管理
李战怀（1961—），男，陕西咸阳人，教授，博士，CCF会员，主要研究方向：海量数据管理、大数据计算。
基金资助:
国家重点研发计划项目(2018YFB1003400)

Scheduling strategy of irregular tasks on graphics processing unit cluster

Fan PING¹^,², Xiaochun TANG¹^,²(), Yanyu PAN¹^,², Zhanhuai LI¹^,²

^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)

摘要/Abstract

摘要：

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

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

Abstract:

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

中图分类号:

TP301.6

平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 计算机应用, 2021, 41(11): 3295-3301.

Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster[J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.

图/表 7

图1 GSF系统架构

Fig. 1 GSF system architecture

图2 多线程执行示意图

Fig. 2 Schematic diagram of multi-threaded execution

表1 基准程序详情

Tab. 1 Benchmark program details

程序	来源	说明
图片检测	YOLOv3	对图片进行目标检测，单个程序大概占用2 GB显存
矩阵乘法	NVIDIA编程示例	资源需求与矩阵维度相关，采用维度为256、512和1 024的矩阵相乘任务
判断素数	Rodinia	输入不同的数值范围，即可产生不同资源需求的任务

图3 不同精度值的结果对比

Fig. 3 Comparison of results with different precision values

图4 不同并行任务数目的结果对比

Fig. 4 Comparison of results with different numbers of parallel tasks

图5 不同调度算法的执行时长对比

Fig. 5 Comparison of execution time of different scheduling algorithms

图6 不同调度算法的资源利用率对比

Fig. 6 Comparison of resource utilization of different scheduling algorithms

参考文献 21

1	吕相文，袁家斌，张玉洁.云计算环境下多GPU资源调度机制研究［J］.小型微型计算机系统，2016，37（4）：687-693. 10.3969/j.issn.1000-1220.2016.04.009
	LYU X W， YUAN J B， ZHANG Y J. Study on resource scheduling mechanism of multi-GPU in cloud computing environment ［J］. Journal of Chinese Computer Systems， 2016， 37（4）： 687-693. 10.3969/j.issn.1000-1220.2016.04.009
2	PAI S， THAZHUTHAVEETIL M J， GOVINDARAJAN R. Improving GPGPU concurrency with elastic kernels ［C］// Proceedings of the 2013 18th International Conference on Architectural Support for Programming Languages and Operating Systems. New York： ACM， 2013： 407-418. 10.1145/2451116.2451160
3	NVIDIA Corporation. Tuning CUDA applications for Kepler ［EB/OL］. ［2021-08-02］. .
4	SUZUKI Y， KATO S， YAMADA H， et al. GPUvm： why not virtualizing GPUs at the hypervisor？［C］// Proceedings of the 2014 USENIX Technical Conference. Berkeley： USENIX Association， 2014： 109-120.
5	KRIEDER S J， WOZNIAK J M， ARMSTRONG T， et al. Design and evaluation of the GeMTC framework for GPU-enabled many-task computing ［C］// Proceedings of the 2014 23rd International Symposium on High-performance Parallel and Distributed Computing. New York： ACM， 2014： 153-164. 10.1145/2600212.2600228
6	YEH T T， SABNE A， SAKDHNAGOOL P， et al. Pagoda： fine-grained GPU resource virtualization for narrow tasks ［C］// Proceedings of the 2017 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York： ACM， 2017： 221-234. 10.1145/3018743.3018754
7	SHAO J L， MA J M， LI Y， et al. GPU scheduling for short tasks in private cloud ［C］// Proceedings of the 2019 IEEE International Conference on Service-Oriented System Engineering. Piscataway： IEEE， 2019： 215-220. 10.1109/sose.2019.00037
8	FUNG W W L， SHAM I， YUAN G， et al. Dynamic warp formation and scheduling for efficient GPU control flow ［C］// Proceedings of the 2007 40th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway： IEEE， 2007： 407-420. 10.1109/micro.2007.30
9	李涛，董前琨，张帅，等.基于线程池的GPU任务并行计算模式研究［J］.计算机学报，2018，41（10）：2175-2192. 10.11897/SP.J.1016.2018.02175
	LI T， DONG Q K， ZHANG S， et al. GPU task parallel computing paradigm based on thread pool model ［J］. Chinese Journal of Computers， 2018， 41（10）： 2175-2192. 10.11897/SP.J.1016.2018.02175
10	ZHU Z， LI J J， LI G H. Load-balanced breadth-first search on GPUs ［C］// Proceedings of the 2014 International Conference on Web-Age Information Management， LNCS8485. Cham： Springer， 2014： 435-447.
11	LI J， LIU L， WU Y， et al. Two-level task scheduling for irregular applications on GPU platform ［J］. International Journal of Parallel Programming， 2017， 45（1）： 79-93. 10.1007/s10766-015-0387-0
12	FANG J， ZHANG J X， LU S B， et al. Exploration on task scheduling strategy for CPU-GPU heterogeneous computing system ［C］// Proceedings of the 2020 IEEE Computer Society Annual Symposium on VLSI. Piscataway： IEEE， 2020： 306-311. 10.1109/isvlsi49217.2020.00063
13	SINGH H， SINGH G. Task scheduling in cluster computing environment ［C］// Proceedings of the 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management. Piscataway： IEEE， 2015： 316-321. 10.1109/ablaze.2015.7155004
14	AlEBRAHIM S， AHMAD I. Task scheduling for heterogeneous computing systems ［J］. The Journal of Supercomputing， 2017， 73（6）： 2313-2338. 10.1007/s11227-016-1917-2
15	HEMAMALIMI M. Review on grid task scheduling in distributed heterogeneous environment ［J］. International Journal of Computer Applications， 2012， 40（2）： 24-30. 10.5120/4929-7159
16	吕向宇.面向异构多核的调度算法研究［D］.武汉：武汉科技大学，2019：2-18. 10.22606/jaer.2020.51003
	LYU X Y. Research on scheduling for heterogeneous multi-core processors ［D］. Wuhan： Wuhan University of Science and Technology， 2019： 2-18. 10.22606/jaer.2020.51003
17	BLEUSE R， KEDAD-SIDHOUM S， MONNA F， et al. Scheduling independent tasks on multi-cores with GPU accelerators ［J］. Concurrency and Computation： Practice and Experience， 2015， 27（6）： 1625-1638. 10.1002/cpe.3359
18	KERRISK M. Cgroups（7）-Linux manual page ［EB/OL］. ［2021-03-22］. .
19	FUKUTOMI D， IIDA Y， AZUMIT， et al. GPUhd： augmenting YARN with GPU resource management ［C］// Proceedings of the 2018 International Conference on High Performance Computing in Asia-pacific Region. New York： ACM， 2018： 127-136. 10.1145/3149457.3155313
20	HINDMAN B， KONWINSKI A， ZAHARIA M， et al. Mesos： platform for fine-grained resource sharing in the data center ［C］// Proceedings of the 2011 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2011： 295-308.
21	NVIDIA Corporation. CUDA samples ［EB/OL］. ［2021-08-02］. .

[1]	李启锐, 彭志平, 崔得龙, 何杰光. 容器云环境虚拟资源配置策略的优化[J]. 计算机应用, 2019, 39(3): 784-789.
[2]	赵春, 闫连山, 崔允贺, 邢焕来, 冯斌. 基于动态调整阈值的虚拟机迁移算法[J]. 计算机应用, 2017, 37(9): 2547-2550.
[3]	张小红, 涂平生. 存储分割编码技术在移动云安全中的应用[J]. 计算机应用, 2016, 36(4): 931-936.
[4]	刘万军王晓宇曲海成孟煜姜庆玲. 基于蚁群算法的遥感影像传输资源调度方法[J]. 计算机应用, 2014, 34(11): 3210-3213.
[5]	陈波张曦煌. 基于分层与容错机制的云计算负载均衡策略[J]. 计算机应用, 2013, 33(11): 3155-3159.
[6]	金永贤黄经州. 开放式实时系统双层调度框架的一种改进方案[J]. 计算机应用, 2009, 29(06): 1509-1513.
[7]	王秀丽宁正元 . 基于动态适应度的独立任务调度算法[J]. 计算机应用, 2006, 26(12): 3001-3003.

不规则任务在图形处理器集群上的调度策略

Scheduling strategy of irregular tasks on graphics processing unit cluster

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 21

相关文章 7

编辑推荐

Metrics