CAJ | 학술논문

随着硬件功能的不断丰富和软件开发环境的逐渐成熟,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)월래월다지피응용도통용계산영역,병대제다계산계통(우기시감입식계통)성능적현저제승기도료지관중요적작용.재기우GPU적계산계통중,대규모병행부재동시진행수거전수화가재적정황시상발생,수거전수연시재계통성능전국최우화중변득불용홀시.종합고필부재적전수시간화집행시간,이총부재makespan최소화작위계통성능적전국우화목표,연구료GPU상부재“전수-집행”연합조도문제.수선,장부재적시간신식화병행임무수여구형역적이유공간련계기래,건립료부재적2D쌍층구형역모형;연후,장GPU상부재조도문제귀결위일류Strip-Packing문제;최후,기우탐람책략급출료근사도위3적다항식시간근사산법,산법복잡도위O(nlogn).해근사산법적핵심시대수거전수계단진행부재배서조도.저종이론층면상증명료GPU계통채취“전수-집행”량계단조도적유효성,즉,재수거전수계단채취부재배서조도,재부재집행계단채취선래선복무(first-come-first-serve,간칭FCFS)조도,능구사GPU성능체도전국최우혹근사최우.