Page 47 - 《软件学报》2020年第9期

2668 Journal of Software 软件学报 Vol.31, No.9, September 2020

(control flow graph,简称 CFG)来建模 kernel 程序的行为,对 GPU 的硬件调度器分配线程块的行为进行建模,利
用 kernel 的执行路径(execution traces)来帮助分析多个 wrap 之间的干涉,并估算干涉对执行时间产生的影响.
干涉的开销会累积并沿着执行路径传导,最终获得 SM 上最后一个 wrap 的执行时间.遗憾的是,实验表明:这种干
涉分析方法非常不精确,分析得到的 WCET 过于悲观.Punniyamurthy 等学者提出了基于混合模型模拟的 GPU
kernel 运行时间分析技术 [90] ,并基于开源 GPU 模拟器 GPGPU-Sim [91,92] 开发了抽象时间仿真工具 GATSim.
GATSim 使用功能模型(function model)与时间模型(time model)来快速模拟 GPU 程序在 SM 上的动态运行情况,
并报告较准确的预测运行时间.其中,功能模型描述了 wrap 对应的指令序列块和每条指令的执行周期.时间模
型描述 GPU 对负载的映射与调度、SM 上 wrap 的并行与干涉,从而实现对指令序列块动态运行状况的模拟.
实验表明:GATSim的平均预测准确率达 96%,平均运算速度高于 80MIPS(million instructions per second).这个速
度远高于被学术界广泛使用的 GPGPU-Sim(2MIPS).
Zhang 等学者对 GPU WCET 分析的研究主要于 GPU 的片上存储器(L1/L2 cache 等),研究目标是提高 GPU
程序对片上存储器访问的时间和可预测性.文献[93]研究了把缓存锁定(cache locking)与缓存分区(cache
partitioning)技术应用于 CPU/GPU 共享缓存管理.他们研究了 64KB~1024KB 不同大小末级缓存上锁定和分区
技术下的程序性能,结果表明,这两种技术对于提高 GPU 程序性能的作用甚微.在文献[94]中,Zhang 等学者研究
了对 GPU 片上 L2 缓存使用锁定技术的效果.实验结果表明:对于部分程序,L2 缓存锁定能够显著提高程序性能.
实际上,这一研究结果隐含的另一层结论是:如果多个 wrap 的线程在 L2 缓存上大量冲突,可能严重降低执行性
能.此外,Zhang 等学者研究了通过调整 wrap 线程对内存的读写操作顺序来提高程序的时间可预测性与总体性
能 [95,96] .
当前,GPU WCET 分析框架所遇到的瓶颈与多核 CPU 时间分析遇到的问题 [97] 相似.当 GPU 上运行多个
kernel 程序时,一个程序的执行时间势必受到并发执行的其他程序的严重干扰.为了保证 WCET 分析的安全性,
通常假设最坏的干扰情况发生,其结果是 WCET 分析过于悲观,造成系统运行资源的过量预留和严重浪费.而在
GPU 上,由于程序执行的并行度要远远高于多核 CPU 系统,上述问题会更加突出.如果能够获取并行 kernel 程序
执行交叠信息,则可以大大提高干涉分析的准确性.但是问题的关键在于:并行 kernel 程序的执行交叠取决于任
务调度,而 WCET 的结果又是任务调度的输入(即程序级和系统级时间分析存在耦合关系).因此,学术界亟待在
WCET 分析上突破原有的两级分析框架,把程序级 WCET 与可调度分析结合在一个分析框架中,从而提高时间
分析的精确性.

4.2 GPU实时调度策略
GPU 实时调度需要解决的问题是调度不同优先级且相互竞争的作业完成数据移动任务和 GPU 计算任务,
保证每个作业能在截止期之前完成.该方向的研究主要聚焦在为 GPU 设计实时调度算法和框架,并建立用于可
调度性分析的数学模型.由于 GPU 的硬件调度器不提供抢占机制,所以早期研究的 GPU 调度算法都是固定优先
级的.有限的优化措施是把大的 kernel 任务切分成小的任务,增加调度的灵活性.近几年,有学者提出了基于软件
机制实现 kernel 任务抢占,从而有可能实现动态优先级调度.
GPU 实时调度领域较早期的工作是 Kato 等学者于 2011 年提出的 TimeGraph 调度器 [98] .TimeGraph 可被内
嵌到开源的 GPU 驱动中,其所提供的 PRT(predictable response time)调度算法支持固定优先级调度,通过预分配
给每个任务固定的执行预算以及监视每个任务已使用的执行预算来调整资源分配.TimeGraph 下,任务有可能
运行超时,所以它本质上支持的是软实时调度.此后,Kato 等学者又提出了 RGEM [99] ,一个 GPGPU 实时调度器,
支持固定优先级调度,主要贡献是在固定优先级调度分析中考虑了 DMA 操作的时间延迟.此外,RGEM 把 GPU
程序的执行分为了逻辑执行和数据拷贝两个阶段,这符合 GPU 程序的执行特点.Basaran 和 Kang 等学者研究了
如何把一个运行时间较长且不可抢占的 GPU 程序进行切分,从而提高系统的可调度性 [100] .但是该工作中,GPU
kernel 的切分需要用户参与而非自动化进行.此后,Zhong 和 He 等学者提出了 Kernelet 框架 [101] ,该框架能够自动
化分析 kernel 程序代码,但是代码优化是在运行阶段进行的,因此无法支持静态分析,也难以用于硬实时系统.
Verner 等学者研究了如何把 sporadic 任务模型下的多个作业(运行在 GPU 上)综合成一个大的作业,并让这