###
Journal of Software:2014.25(2):298-313

GPU上两阶段负载调度问题的建模与近似算法
孙景昊,邓庆绪,孟亚坤
(东北大学 信息科学与工程学院,辽宁 沈阳 110004)
Two-Stage Workload Scheduling Problem on GPU Architectures: Formulation and Approximation Algorithm
SUN Jing-Hao,DENG Qing-Xu,MENG Ya-Kun
(School of Information Science and Engineering, Northeastern University, Shenyang 110004, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4234   Download 3113
Received:May 06, 2013    Revised:September 29, 2003
> 中文摘要: 随着硬件功能的不断丰富和软件开发环境的逐渐成熟,GPU(graphics processing unit)越来越多地被应用到通用计算领域,并对诸多计算系统(尤其是嵌入式系统)性能的显著提升起到了至关重要的作用.在基于GPU的计算系统中,大规模并行负载同时进行数据传输和加载的情况时常发生,数据传输延时在系统性能全局最优化中变得不容忽视.综合考虑负载的传输时间和执行时间,以总负载makespan最小化作为系统性能的全局优化目标,研究了GPU上负载“传输-执行”联合调度问题.首先,将负载的时间信息和并行任务数与矩形域的二维空间联系起来,建立了负载的2D双层矩形域模型;然后,将GPU上负载调度问题归结为一类Strip-Packing问题;最后,基于贪婪策略给出了近似度为3的多项式时间近似算法,算法复杂度为O(nlogn).该近似算法的核心是对数据传输阶段进行负载排序调度.这从理论层面上证明了GPU系统采取“传输-执行”两阶段调度的有效性,即,在数据传输阶段采取负载排序调度,在负载执行阶段采取先来先服务(first-come-first-serve,简称FCFS)调度,能够使GPU 性能达到全局最优或近似最优.
Abstract:With the prevalence of general purpose computation, GPUs (graphics processing units) are becoming extremely important to significantly improve system performances for many computing systems, including embedded systems. Running massively parallel kernels on GPUs is challenging for system’s overall performance especially when large amount of workloads (kernels) are running together. This paper investigates how to schedule large amount of workloads that have to be executed on GPUs to minimize the makespan of all workloads to improve the system overall performance. By considering the transfer time and execution time together, the study makes an abstraction for each workload and formulate the scheduling problem on GPUs into a 2D rectangular strip-packing model. A polynomial 3-approxiamation algorithm is proposed to solve the strip-packing problem. The approximation results exhibit an effective approach for workload sequencing during the data offloading on GPUs. It also implies that the scheduling jointed by workload sequencing for GPUs data offloading and first-come-first-serve (FCFS) scheduling inside GPUs with workload conserving can improve the system performance optimally or near-optimally.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61300194);国家教育部博士点基金(20110042110021);国家科技支撑计划(2012BAK24B01);河北省自然科学基金(F2013501048) 国家自然科学基金(61300194);国家教育部博士点基金(20110042110021);国家科技支撑计划(2012BAK24B01);河北省自然科学基金(F2013501048)
Foundation items:
Reference text:

孙景昊,邓庆绪,孟亚坤.GPU上两阶段负载调度问题的建模与近似算法.软件学报,2014,25(2):298-313

SUN Jing-Hao,DENG Qing-Xu,MENG Ya-Kun.Two-Stage Workload Scheduling Problem on GPU Architectures: Formulation and Approximation Algorithm.Journal of Software,2014,25(2):298-313