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

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

else if inst.op==ST then //rd[offset]=rs
if regMap.find(inst.rs)!=null then
inst.rs=regMap[inst.rs] //将源寄存器 rs 替换为其他寄存器
end if
end if
ptxCode.append(inst)
end for
在对指令的遍历过程中,算法使用了 2 个哈希表记录相关状态.valueMap 用于将模板参数取值映射到真实
的稀疏卷积参数.regMap 用于处理由于冗余指令删除带来的寄存器依赖关系的变化,它记录了等价寄存器的映
射关系.对于中间表示中的每一条 PTX 指令,算法首先通过解析识别指令的具体类型和各个组成部分,这由字符
串匹配完成.对于乘累加指令 FFMA,我们首先检查是否需要修改指令的源寄存器,并通过查询 valueMap 对指令
中的立即数进行替换.例如,对图 5 中的第 1 条 FFMA 指令 FFMA R 3 , R i , 1.2, R 2 ,经过查询 valueMap,模板参数 1.2
被替换为真实参数 0,并且由于 regMap 为空,不需要进行源寄存器替换.同时,由于替换后立即数操作数为 0,这条
指令实际上进行了 R 3 =R 2 的操作,因此 R 3 和 R 2 实际上是等价的.如果能够将后续对 R 3 寄存器的引用替换为对
R 2 的引用,那么这条 FFMA 指令便可以删除(图 5 中使用横线标注).我们在 regMap 中记录 R 3 →R 2 的映射关系,
并删除这条指令.由于稀疏卷积参数涉及的指令为 FFMA 指令,被等价映射的寄存器为保存卷积计算临时结果
的寄存器,这些寄存器会被后面的 FFMA 指令作为源操作数使用.由于对寄存器的引用一定出现在寄存器的定
值之后,因此我们通过查询当前 regMap 中记录的寄存器映射关系,便可以实现相应的修改.当在后面的指令中
遇到对 R 3 的引用时,例如图 5 中的 FFMA R d ,R j ,1.4,R 3 ,由于 regMap 中已经记录了 R 3 到 R 2 的映射,因此可以正确
地将对 R 3 的引用修改为对 R 2 的引用.通过使用 regMap 记录寄存器的映射关系,我们可以删除使用 0 的 FFMA
计算指令.另外,寄存器映射关系也会影响存储指令.因为乘累加指令的目的寄存器保存了卷积计算的结果,因
此会作为存储指令的源操作数.对于存储指令 ST,我们也检查其源寄存器(保存待写出值的寄存器)是否被重命
名,并进行必要的修改.算法没有对可能存在的冗余访存指令进行显式的删除操作,这主要是基于对 GPU 的访
存指令特点的考虑.GPU 通常支持多种宽度不同的访存指令,例如 32 位、64 位等,并且不同宽度的指令能够实
现的访存吞吐量不同 [28] .当多个元素的访问被打包到同一条访存指令中时,删除其中某个元素的访问,并将其拆
分为多条宽度更小的访存指令,可能会影响访存吞吐量.因此,我们没有对访存指令进行直接删除,而是交给后
续的汇编器 ptxas 决定,是否对涉及未被引用操作数的访存指令进行修改.
我们设计的稀疏代码生成算法的复杂度是 O(n),其中,n 为中间表示模板的指令条数.对于每条指令,我们进
行解析和哈希表查找的操作.解析基于字符串匹配进行,而哈希表的查找也可以快速实现.综合来说,稀疏代码
生成算法的时间效率较好.
完成冗余指令删除后,我们就获得了针对稀疏卷积参数的 PTX 程序.接下来,该 PTX 程序经过汇编器 ptxas
优化(如图 4 所示),获得最终的二进制代码.由于 PTX 面向英伟达设计的虚拟 GPU 体系结构,基于 PTX 的中间
表示可以为不同体系结构的 GPU 生成最终的二进制代码(通过为 ptxas 汇编器提供不同的参数,指定具体的目
标 GPU 平台).另外,ptxas 会负责执行与具体 GPU 体系结构相关的优化,包括寄存器分配和指令调度等,所以我
们生成的稀疏算子程序也能够受益于这些优化.最后,由于 PTX 中间表示模板可以在不同的稀疏模型参数上复
用,相当于降低了获得中间表示模板的开销.我们通过实验发现,图 4 中的前两个编译阶段(从 cu 文件到 ptx 文件)
占用了编译过程的大部分时间(90%以上),所以选用 PTX 作为中间表示层次可以复用开销最大的编译过程,降
低后续生成具体稀疏算子代码的时间开销.在实验中,ptxas 编译生成的 ptx 代码所需的时间在几十到几百毫秒.
2.4 访存优化
尽管 GPU 能够提供强大的峰值计算性能,但达到峰值性能需要程序具有较高的计算访存比.访存密集型的
应用很容易受到访存带宽的限制,难以实现满意的性能.我们通过 roofline 模型 [29] 分析了不同计算密度下,GPU
程序的性能上限,如图 6 所示.横轴表示不同的计算密度,单位是操作数/字节,表示从全局内存访问的每字节数