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

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

Scheduling strategy of irregular tasks on graphics processing unit cluster

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.