首页 | 官方网站   微博 | 高级检索  
     

GPU上两阶段负载调度问题的建模与近似算法
引用本文:孙景昊,邓庆绪,孟亚坤.GPU上两阶段负载调度问题的建模与近似算法[J].软件学报,2014,25(2):298-313.
作者姓名:孙景昊  邓庆绪  孟亚坤
作者单位:东北大学 信息科学与工程学院,辽宁 沈阳 110004;东北大学 信息科学与工程学院,辽宁 沈阳 110004;东北大学 信息科学与工程学院,辽宁 沈阳 110004
基金项目:国家自然科学基金(61300194);国家教育部博士点基金(20110042110021);国家科技支撑计划(2012BAK24B01);河北省自然科学基金(F2013501048)
摘    要:随着硬件功能的不断丰富和软件开发环境的逐渐成熟,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  近似算法
收稿时间:5/6/2013 12:00:00 AM
修稿时间:2003/9/29 0:00:00

Two-Stage Workload Scheduling Problem on GPU Architectures: Formulation and Approximation Algorithm
SUN Jing-Hao,DENG Qing-Xu and MENG Ya-Kun.Two-Stage Workload Scheduling Problem on GPU Architectures: Formulation and Approximation Algorithm[J].Journal of Software,2014,25(2):298-313.
Authors:SUN Jing-Hao  DENG Qing-Xu and MENG Ya-Kun
Affiliation:School of Information Science and Engineering, Northeastern University, Shenyang 110004, China;School of Information Science and Engineering, Northeastern University, Shenyang 110004, China;School of Information Science and Engineering, Northeastern University, Shenyang 110004, China
Abstract:
Keywords:GPU (graphics processing unit)  data transfer  workload sequencing  strip-packing  approximation algorithm
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号