gpu上两阶段负载调度问题的建模与近似算法

随着硬件功能的不断丰富和软件开发环境的逐渐成熟，gpu(graphicsprocessingunit)越来越多地被应用到通用计算领域，并对诸多计算系统(尤其是嵌入式系统)性能的显著提升起到了至关重要的作用.在基于gpu的计算系统中，大规模并行负载同时进行数据传输和加载的情况时常发生，数据传输延时在系统性能全局最优化中变得不容忽视.综合考虑负载的传输时间和执行时间，以总负载makespan最小化作为系统性能的全局优化目标，研究了gpu上负载“传输-执行”联合调度问题.首先，将负载的时间信息和并行任务数与矩形域的二维空间联系起来，建立了负载的2d双层矩形域模型；然后，将gpu上负载调度问题归结为一类strip-packing问题；最后，基于贪婪策略给出了近似度为3的多项式时间近似算法，算法复杂度为o(nlogn).该近似算法的核心是对数据传输阶段进行负载排序调度.这从理论层面上证明了gpu系统采取“传输-执行”两阶段调度的有效性，即，在数据传输阶段采取负载排序调度，在负载执行阶段采取先来先服务(first-come-first-serve，简称fcfs)调度，能够使gpu性能达到全局最优或近似最优.