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

摘要：

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

关键词：GPU(graphics processing unit)、数据传输、负载排序、strip-packing、近似算法

所属期刊栏目：25

分类号：TP316(计算技术、计算机技术)

资助基金：国家自然科学基金61300194;国家教育部博士点基金20110042110021;国家科技支撑计划2012BAK24B01;河北省自然科学基金F2013501048

在线出版日期：2014-04-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：298-313