没有合适的资源?快使用搜索试试~ 我知道了~
GPU上两阶段负载调度问题的建模与近似算法1
需积分: 0 0 下载量 15 浏览量
2022-08-04
15:01:59
上传
评论
收藏 584KB PDF 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/86330991/0001-f2a43ac1dd9a59c6ef0716b297af381d_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
16页
摘要:随着硬件功能的不断丰富和软件开发环境的逐渐成熟,GPU(graphics processing unit)越来越多地被应用到通用计算领域,并对诸多计算系统
资源详情
资源评论
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/86330991/bg1.jpg)
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2014,25(2):298313 [doi: 10.13328/j.cnki.jos.004527] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563
GPU 上两阶段负载调度问题的建模与近似算法
孙景昊
,
邓庆绪
,
孟亚坤
(东北大学 信息科学与工程学院,辽宁 沈阳 110004)
通讯作者: 邓庆绪, E-mail: dengqx@mail.neu.edu.cn
摘 要: 随着硬件功能的不断丰富和软件开发环境的逐渐成熟,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;近似算法
中图法分类号: TP316 文献标识码: A
中文引用格式: 孙景昊,邓庆绪,孟亚坤.GPU 上两阶段负载调度问题的建模与近似算法.软件学报,2014,25(2):298313. http://
www.jos.org.cn/1000-9825/4527.htm
英文引用格式: Sun JH, Deng QX, Meng YK. Two-Stage workload scheduling problem on GPU architectures: Formulation and
approximation algorithm. Ruan Jian Xue Bao/Journal of Software, 2014,25(2):298313 (in Chinese). http://www.jos.org.cn/1000-
9825/4527.htm
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)
Corresponding author: DENG Qing-Xu, E-mail: dengqx@mail.neu.edu.cn
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
基金项目: 国家自然科学基金(61300194); 国家教育部博士点基金(20110042110021); 国家科技支撑计划(2012BAK24B01);
河北省自然科学基金(F2013501048)
收稿时间: 2013-05-06; 定稿时间: 2003-09-29
![](https://csdnimg.cn/release/download_crawler_static/86330991/bg2.jpg)
孙景昊 等:GPU 上两阶段负载调度问题的建模与近似算法
299
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.
Key words: GPU (graphics processing unit); data transfer; workload sequencing; strip-packing; approximation algorithm
随着半导体工艺的日臻成熟,处理器芯片上集成的晶体管越来越多,目前已突破 10 亿量级,图形处理器
(graphics processing unit,简称 GPU)的性能也因此得到飞速提升,并远远超过通用 CPU
[1]
.2012 年,GPU 集群已成
为世界 TOP 500 超级计算机中主要的计算资源.GPU 优良的计算性能,一方面得益于核心运算单元独享内存容
量和内核数量的增长,另一方面,更依赖于并行计算平台中负载调度策略的程序实现.
CUDA 和 OpenCL 是 GPU 系统中应用最广泛的并行计算平台.在这两类经典程序设计范式中,负载被定义
为 GPU 上运行的一个或多个并行程序段(内核),并关联有程序运行时所需的数据资源.在 GPU 集群中,负载一旦
被分配到某个 GPU 上,该负载就只能访问这个 GPU 独享的内存,而且,负载必须在其关联数据加载到独享内存
后才能开始处理和执行.在过去的几十年间,主存和 GPU 独享内存之间数据传输带宽的提升速度一直落后于
GPU 内核数量的增长速度,数据传输延时问题变得不容忽视.特别是在实时系统中
[2,3]
,大规模并行负载同时加
载到 GPU 上时,主存和独享内存间的数据传输时间成为影响系统全局性能的重要参数.目前,考虑数据传输的
GPU 内核负载调度还处于较低的自动化水平,这成为制约 GPU 系统全局性能提升的重要问题之一.
针对以上问题,本文综合考虑数据传输时间和负载均衡,对 GPU 上的大规模并行负载调度问题展开研究,
将总负载 makespan 最小化作为 GPU 全局性能的优化目标,给出一系列能够同时提升负载执行并行度和缩短数
据传输时延的调度策略.迄今为止,GPU 负载调度的研究工作主要集中在处理器如何提升负载并行度上,其中代
表性的工作有:Gregg 等人
[4]
提出了一种 GPU 上细粒度的动态控制策略,实现对大规模负载的并行调度;Li 等
人
[5]
提出了一类虚拟化方法,使多处理器上的不同负载共享 GPU 资源,提升负载执行的并行度;Kato 等人
[68]
针
对优先级、抢占和隔离等实时需求,提出了一系列实时计算系统上的 GPU 资源管理策略.以上研究尚未考虑
GPU 独享内存与主存之间的数据传输延时问题.对于 GPU 系统全局性能而言,尤其是在实时系统中,当大规模
并行负载同时加载到存储器上时,数据传输和负载均衡同样重要.下面通过 Nvidia Geforce GT 630M 平台中的
例子,说明数据传输在调度中的重要性.
图 1 给出了由 Nvidia SDK 开发的两段程序在 GPU 上调度的情况
[9]
.其中,
1
为异步 API 程序关联的负载,
大小为 32 768 区块(每个区块的规模为 1024KB1KB);
2
为向量加载程序关联的负载,大小为 35 157 区块(每个
区块的规模为 256KB1KB);负载
1
和
2
均在 GPU 上由两个内核并行执行.通过 API 函数 cudaEventRecord 获
取 GPU 流处理器时钟周期的方法对负载时间信息进行估算得到:
1
(以及
2
)的数据传输时间和负载执行时间分
别为 23.392ms 和 29.215ms(以及 28.626ms 和 6.398ms).两负载数据传输顺序改变,将导致不同的调度结果:
首先,假设两并行负载任务
1
和
2
同时到达,若不考虑负载的传输时间,随机对负载进行调度,不妨设
2
先于
1
进行传输;然后,负载的第2 阶段按照先来先服务(first-come-first-serve,简称FCFS)策略进行调度
执行,如图 1(a)所示.这种调度方案对应的 makespan 值为 81.233.
若综合考虑负载的传输时间和执行时间,先传输负载
1
,如图 1(b)所示.在这种方案下,调度系统的
makespan 值降低至 58.416.
由此对比可知,
1
在
2
之前传输能够有效提升 GPU 利用率.一种优良的调度算法应该能够很好地统筹负载
的数据传输时间和执行时间,综合考虑 GPU 中的通信和计算资源,使二者相互协调,以达到更好的优化效果.
本文的主要贡献如下:针对 GPU 上负载“传输-执行”联合调度问题,从理论上给出一系列多项式时间的近
似结果.首先,将负载的时间信息和并行任务数与矩形域的二维空间联系起来,建立负载的 2D 双层矩形域模型;
然后,将 GPU 上负载调度问题归结为一类新的 Strip-Packing 问题;最后,基于贪婪策略给出近似度为 3 的多项式
时间近似算法,算法复杂度为 O(nlogn).从文中近似算法能够很容易地得出 GPU 最优或近似最优的调度策略:
在数据传输阶段采取负载排序调度,在负载执行阶段采取 FCFS 调度.这也从理论层面上证明了 GPU 系统采取
“传输-执行”两阶段调度的正确性和有效性.
![](https://csdnimg.cn/release/download_crawler_static/86330991/bg3.jpg)
300
Journal of Software 软件学报 Vol.25, No.2, February 2014
Fig.1 Different results for scheduling two workloads
1
and
2
by considering the transfer times or not
[9]
图 1 考虑传输时间与否对负载
1
和
2
调度结果的影响
[9]
本文第 1 节介绍 GPU 计算系统模型和问题定义.第 2 节提出调度问题的 2D 双层矩形 Strip-Packing 模型.
第 3 节给出问题的近似算法以及相关的理论分析和证明.第 4 节是实验结果.第 5 节介绍多处理器调度领域在
近似算法方面的相关研究进展.最后是结束语.
1 系统模型和问题定义
1.1 GPU计算系统模型
本文研究具有 m 个流式多处理器的单 GPU 计算系统,m 为常数(m≥2).在 GPU 系统中,负载调度架构基于
Linux 3.0.0.48 内核设计,并遵循 CUDA 5.0 规范,如图 2 所示.GPU 上的负载调度分为两个阶段:(1) 负载关联的
数据传输称为调度的第 1 阶段;(2) 负载在 GPU 上并行执行称为调度的第 2 阶段.
操作系统
程序切片
程序切片
负载任务
负载任务
API
lock
驱动器
等待队列
GPU硬件资源
Fig.2 Architecture for scheduling workload on GPU system
[9]
图 2 GPU 系统中的负载调度架构
[9]
0
10 20 30 40 50 60 70 80
PCI-E总线
(传输阶段)
两个流式处理器
(执行阶段)
0
10 20 30 40 50 60 70 80
PCI-E总线
(传输阶段)
两个流式处理器
(执行阶段)
Time (ms)
Time (ms)
(a) 负载 首先进行数据传输
(b) 负载 首先进行数据传输
2
1
1
1
1
1
2
2
2
2
![](https://csdnimg.cn/release/download_crawler_static/86330991/bg4.jpg)
孙景昊 等:GPU 上两阶段负载调度问题的建模与近似算法
301
1.1.1 数据传输阶段
在本文的计算系统中,GPU 独享内存和主存之间的数据传输采取异步模式,这具体由 Linux 内核中的
wrapper 模块应用二元信号量实现.也就是说,任何负载若要占用 GPU 的硬件资源(PCI-E 总线),在主存和独享内
存之间进行数据传输,必须先获取二元信号量,并实现对信号量的加锁操作.相应地,一旦某负载完成了数据传
输操作,它必须释放二元信号量,实现对信号量的解锁操作.本文将数据传输占用 PCI-E 总线看作一种独立的计
算资源,比如,在第 1.3 节的问题定义中,PCI-E 总线被抽象为调度问题中第 1 阶段的单机资源.
注意到,在大规模并行负载同时进行数据传输时,如何控制二元信号量的锁操作、确定数据传输顺序,对计
算系统全局性能有重要影响(详见图 1 中实例).数据传输阶段的负载排序是本文关注的主要问题.
1.1.2 负载执行阶段
在负载执行阶段,Linux 内核采用默认的 FCFS 等待队列实现并行负载的分配操作.即,先完成数据传输的负
载先被加载到 GPU 上的多处理器上并行执行.多处理器对应第 1.3 节调度问题定义中的 m 台并行机器
.
FCFS 策略实现简单,不会占用额外的计算资源,但是调度效果会受到阶段1 中数据传输顺序的影响.数据传
输阶段不同的负载排序将导致不同的调度结果.FCFS 调度策略是否能保证 GPU 系统的全局最优性,还尚未可
知.本文研究 GPU 上“传输-执行”联合调度问题,第 3 节给出的近似算法结果从理论上证明:FCFS 策略与数据传
输阶段负载排序策略相结合的方法能够保证 GPU 系统全局最优或近似最优.
1.2 并行负载模型
本文考虑 GPU 计算系统中的一组并行负载(又称任务)集合
={
1
,…,
n
},负载
i
用三元组(tran
i
,size
i
,exec
i
)
表示,其中,tran
i
是负载
i
关联的数据从主存传输到 GPU 独享内存上所耗费的时间;size
i
是负载
i
运行所需的处
理器个数,一般情况下,size
i
需少于 GPU 中的处理器总数 m;exec
i
是负载
i
在 GPU 上的执行时间.本文假设负载
符合伙伴调度(gang scheduling)方式,即负载
i
的所有并行程序块同时分配到一组处理器上执行,并且每个程序
块的执行时间相同,且同时开始执行.
当系统加载
i
时,以上三元组变量将被存储在 Linux 内核的 task_struct 结构中.下面介绍负载特征量在 GPU
计算系统中的抽象过程.
1.2.1 数据传输时间
为了获取负载
i
的数据传输时间 tran
i
,首先需要估算出由主存传输到 GPU 内存的数据量
i
,以及 PCI-E 总
线的有效带宽
;然后,数据传输时间 tran
i
即可由公式
i
/
计算得出.
i
在经过数据传输后,即可加载到 GPU 上
开始执行.
1.2.2 并行程序块
对于大多数程序而言,负载通常由大量的程序块构成,每个程序块又被划分为若干线程.GPU 将每个程序块
分配到一个流式处理器中执行,每个程序块中并行线程的数量由程序员根据处理器参数决定.
本文模型不具体考虑 GPU 上处理器内核运行时的动态参数,而是采取一种粗粒度的静态方法
[8]
估算出每
个程序块中的并行线程数量.该方法基于如下考虑:GPU 中一个处理器的计算资源是有限的,因此,一个负载加
载到该处理器上的最大并行线程数量也是有限的.不妨设负载
i
中的线程总数为
i
,
i
在一个处理器上能够并行
运行的最大线程数为
i
.在满足处理器资源约束的条件下,负载
i
并行执行所需的机器数 size
i
等于
i
/
i
.在第 1.3
节中,负载的并行程序块对应于任务在第 2 阶段的并行操作.
1.2.3 负载执行时间
同一负载的所有并行程序块在 GPU 上的执行时间均相等,这是本文的重要假设之一.该假设在基于 Nvidia
SDK 开发的绝大多数程序中普遍成立.
由上一节中负载并行程序块模型易知,在负载
i
的 size
i
个并行程序块中,至少有 size
i
1 个程序块包含相同
的线程数
i
(剩余的一个程序块所包含的线程数一定小于
i
,其线程数计算公式为
i
mod
i
).对于具有相同线程
数的程序块,假设所有线程的执行时间均相同,则可应用文献[10]中的方法估算负载执行时间 exec
i
.另外,对于线
程数小于
i
的程序块,令其执行时间等于 exec
i
.这种近似使得调度算法的实际效果一定不会低于理论值.
剩余15页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![avatar](https://profile-avatar.csdnimg.cn/02f9d88c8fb746b58bed39845a9a5234_weixin_35805055.jpg!1)
小小二-yan
- 粉丝: 28
- 资源: 299
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)
评论0