An Approximate Optimal Solution to GPU Workload Scheduling

作者：Wang, Yanhua^*; Qiao, Jianzhong; Lin, Shukuan; Zhao, Tinglei

来源：Computing in Science & Engineering, 2018, 20(5): 63-76.

DOI：10.1109/MCSE.2018.110145709

• PARALLELISM
• FRAMEWORK

One of the hot topics in graphic processing unit (GPU) research is workload scheduling. For parallel workloads with a large scale, the scheduling strategy can affect seriously system performance. To address this, the authors carry out scheduling of data transfer before workload execution scheduling, and propose an optimal scheduling algorithm for GPU workload. By hiding data transfer in workload execution to the maximum extent, the algorithm can reduce wait time, thus achieving a small timespan. They attribute the problem of hiding data transfer in workload execution to the 0-1 knapsack problem, and propose the pseudo-polynomial time algorithm based on the Dyer-Zemel algorithm. The authors then deduce the fully polynomial-time algorithm scheme for PPTA. By testing on cloud platform equipped with Nvidia Geforce GTX 750, they show that their scheduling algorithm estimates the optimal schedule sequence effectively.

• 出版日期2018-10
• 单位东北大学