利用访存模式构建GPU高效率数据访问

张 瑞，田 密

(1.延安大学教育科学学院，陕西延安716000；2.北京理工大学计算机学院，北京100081；3.延安职业技术学院网络信息中心，陕西延安716000)

计算机性能的提升越来越受制于频率墙、功耗墙和存储墙等因素，因此业界认为增加计算资源比单纯地提高时钟频率能够带来更大的性能提升[1]，GPU的高并行性正符合这一需求。GPU以及与其匹配的通用编程语言的发展使其成为数据并行和计算密集应用的理想平台之一并在通用计算领域发挥越来越重要的作用[2-4]。GPU采用同时执行大量线程的方式隐藏访问存储器带来的延迟，但是大量线程同时访存会引发访问延迟而导致线程数据饥饿，从而浪费GPU的计算资源。GPU访存系统效率主要受GPU硬件性能制约以及应用程序的访存模式影响[5]。因此为了使应用程序能够充分发挥GPU体系结构的计算潜能，非常有必要对应用程序的访存模式进行分析并结合GPU的存储器件特性探索提高访存系统效率的技术。

1 相关工作

目前国内外对GPU访存系统的研究已取得一些研究成果。研究表明GPU系统总体性能与访存系统效率密切相关，因此存储子系统是影响GPU性能的一个非常关键的因素[6]。

Govindaraju等[7]提出了一种基于GPU纹理硬件的存储模型，该模型采用分块访问的方法利用数据的局部性特性，不足在于分块带来计算开销的增加从而引起新的性能瓶颈。Fatahalian等[8]分析了GPU上的访存与计算的供求关系，得出GPU存储系统带宽对计算的性能至关重要的结论。Silberstein等[9]针对存储受限应用实现了片上scratchpad memory的数据重用，但是不适合对存储资源(如寄存器)需求较大的应用。Ryoo等[10]针对计算受限应用定义了GPU效率和利用率模型，通过对优化空间的裁剪来获得应用程序的最优配置。Baskaran等[11]针对CUDA平台利用多面体模型对循环嵌套结构进行优化进而提高全局存储器的访存效率。Ueng等[12]同样针对CUDA平台，提出CUDA-Lite实现程序的存储优化，该方法在源程序中加入注释以实现对全局存储器的联合访问。Jang等[13]提出多层嵌套循环结构内存访问模型，在该模型指导下分别针对AMD和NVIDIA GPU进行全局内存向量化和分类存储取得较高的性能提升，缺陷是耗费较多的片外存储且在对数组进行读写交替操作时，带来数据的一致性问题。Stuart等[14]提出RSVM动态创建和管理大小灵活的数据区域，解决了静态内存需求较大的应用程序的运行问题，缺陷是对于不同的应用程序数据区域大小的设定是需要多次实验才能取得最好性能。

Cope等[15]对GPU硬件进行了改进，即在GPU中加入可重构地址映射硬件逻辑，主要针对视频处理领域的数据访存优化，因而其局限性有两个方面，一是基于硬件的实现缺少灵活性，二是只适用领域局限在视频处理，无法适用在通用计算中。Kim等[16]提出GPUdmm(Dynamic GPU Memory Management)，主要思想是利用显存先天的数据局部性高的特点，通过修改GPU存储控制器，对DRAM进行两级控制，将显存看作主存到CU之间的最低级cache以提供给程序员一个面向主存大小的编程视图，减轻了程序员因为显存容量限制手动划分数据，修改kernel的负担，同时避免了因数据划分导致的多余CPU-GPU间的数据传输。

2 GPU访存子系统

为了满足GPU架构的高并行性要求，GPU访存子系统的设计以高带宽，低延迟为特征。大部分的GPU内存子系统由多种不同访存延迟的存储器组成，可以分成片上存储和片外存储两部分，见图1。

图1 GPU访存子系统

片上存储包含caches，软件可管理的本地数据共享存储(如scratchpad memory)以及寄存器等。一般而言组成GPU的每个流多处理器(如NVIDIA的SM，AMD的SIMD引擎)都有自己的L1cache和本地共享存储器，这些存储器对其他流多处理器透明。本地共享存储器主要用作存放线程块内的共享数据和重用数据以减少对片外存储器的访问次数，它一般被分为多个组，即bank结构，连续的数据存储在相邻的bank中，线程块内的所有线程可以通过它通信，带宽高，访存延迟略大于寄存器但远小于片外存储器。寄存器属于线程私有，访问速度非常快，延迟可忽略，当容量不足时借用片外存储器空间充当，这时访问延迟相当于片外存储器。GPU的缓存一般由两级构成，每个流多处理器拥有属于自己的L1 cache，所有的流多处理器共享L2 cache。

片外存储一般有全局存储，常量存储和纹理存储组成，通常共享显存容量。片外存储器访问延迟比较大，一般在几百个时钟周期。受显存控制器影响，需要按照一定方式访存才能够取得较高的带宽，在计算能力比较强的产品上具有cache机制提高访存效率。

3 基于访存模式的高效率数据访问

GPU采用SIMD或SIMT的方式并行处理大量数据集，创建和切换线程完全由硬件自动完成，当线程数据饥饿，硬件会自动调度其他线程运行，因此理论上当硬件自动调度多线程时可以隐藏访存延迟，但是当大量线程数据饥饿时，计算资源多处于空转状态得不到充分利用。因此当应用程序移植到GPU平台上时，非常必要对其数据访问的模式和特性进行分析并利用数据访问优化技术避免重复访问或减少访问延迟尽可能地确保活动线程的数据供给。

3.1 数组访存模式

程序的访存模式是程序在访问存储器件时所体现出来的规律[17]。通过对应用程序进行分析可以得出其访存模式的形式化表达。数组是科学计算中使用最频繁的数据结构，其访问方式分规则和不规则两类，以二维数组A[N][N]数据访问为例，存在如图2(a)所示的多种常见的访问方式。将图2(a)中的数组访问方式进行组合变换可得出数组访问的各种情况，并可借鉴多面体模型的概念做抽象化的表示。

多面体模型是一种通过迭代域、访问函数和仿射调度三种操作表示程序的代数框架，可用于处理具有仿射数组访问和循环边界的循环结构。假设程序循环边界和数组访问与循环索引和全局参数存在映射关系，那么一个n重嵌套循环就定义了一个n维空间里的迭代空间多面体，可以表示为

其中DS表示循环边界限制，一般为常数矩阵；xs表示外层到内层的循环迭代向量；n表示全局参数，如问题规模。一个以数组操作为循环体的D层嵌套循环S即定义了一个在D维空间里的多面体，多面体里的每个点代表一个数组元素，多面体的子空间代表数组的非空子集，那么循环体对一个数组的访问函数可以用齐次方程表示。循环体S对数组A的访问可以表示为：

FA表示对数组A的访问矩阵，FA的行数由数组A的维数决定，FA的列数由对数组访问的迭代空间维数决定，因此有图2(b)即为图2(a)中迭代循环对数组A的访问矩阵。如对一个二维数组A[10][10]进行元素的按行优先遍历访问，那么数组A的访问矩阵FA可以表示为：

其中FA的第一行第一列的1表示对A按行优先访问，且从下标为0的行开始访问，第一行第四列的0表示从行下标为0的元素开始由小到大的顺序访问，第二行第二列的1表示从下标为0的列开始访问，第二行第四列的0表示从列下标为0的元素开始由小到大顺序访问，如遇到负数则表示下标由大到小的顺序访问。

(a)行主遍历 (b)列主遍历

(c)偏移 (d)行主列逆向

(e)三角访问 (f)跳跃访问

(b)

3.2 应用程序数据的访存模式分析

访存优化技术作为缓解存储墙问题的有效手段，可以分为三类：避免存储访问延迟、减少冗余访问和隐藏存储访问延迟。三者都可以提高访存系统性能，但是有本质的区别。避免存储访问延迟是通过对数据的重新组织改善数据局部性以减少访存开销。减少冗余访问是通过对迭代循环程序访问模式的分析重新构造循环空间以去掉对数据的冗余访问。隐藏存储访问延迟时通过将访存和计算重叠进行以隐藏访存延迟，既不减少访存次数也没有减少访存延迟。本文提出的优化方法是通过减少冗余访问提高访问的效率。

图3 迭代循环示例

利用多面体模型对迭代循环程序数据访问模式进行形式化表达，可得到数据的访存矩阵，通过将访存矩阵的秩与循环迭代空间的维数进行对比可以得出该数组是否存在迭代循环里的重复访问，如果存在数组的重复访问则结合GPU存储系统特性重新构造程序的迭代空间减少对全局存储的访存次数从而达到不影响程序性能却提高访存效率的目的。以图3中的迭代循环为例，其构成的迭代空间可以用S矩阵表示，

数组A、B、C的访问矩阵分别为：

R(X)表示矩阵X的秩，由矩阵秩的概念可得

R(S)=3，R(FA)=2，R(FB)=2，R(FC)=2，

可得到：

R(A)

根据多面体模型的理论，如果一个数组的访问矩阵的秩小于访问该数组的迭代空间的维数，那么该数组在此迭代空间中存在重复访问。在迭代空间S上，即数组A，B，C在迭代循环中存在重复访问，因此可以通过构造新的迭代空间并创建能够被快速访问的临时变量，从而将对原数据的访问替换为对临时变量的访问。注意存储临时变量的存储器的访问代价一定要小于存放原数组数据存储器的访问代价。一般CPU-GPU结构中，数据通过PCIE总线从主机端到设备端后都存放在片外存储中，论文第2节提到GPU访存子系统上的寄存器和片上共享存储都有高于片外存储器的特性，那么符合上面存放临时变量的条件，所以通过合理的存储器使用可以减少数据的访存延迟。在上例中对数组A、B、C的访问都存在重复性，是否存在新的迭代循环可以一并消除三者的片外重复访问呢？通过对三个访问矩阵的比较得出结论，因为FA，FB，FC任意两个访问矩阵之间不存在相似关系，因此不存在可以同时消除三者重复访问的迭代循环，但是FA与FC，FB与FC存在相同的行向量，因此可以采用消除FA或FB片外重复访问的方法减少访存延迟。

3.3 基于访存模式的高效率数据布局算法

通过上面对应用程序数据访存模式的分析，结合GPU访存子系统的特点提出以下基于访存模式的高效率数据布局算法(Data Placement Based on Memory Access Patterns)。

算法：DPoMAP

输入：平台类型，程序迭代空间维数D，数组个数n，数组迭代矩阵F[n]，迭代矩阵的秩R[n]，ArraySize[n][2]，寄存器文件个数RF，片上共享存储容量SM，

输出：各个数组的内存位置Placement[n]

Placement[n]<—0；

SM_Occupancy=0；

RF_Occupancy=0；

For(i=0；i

{

If平台==NVIDIA

{

If F[i]行重用&&SM_Occupancy

{Placement[i]=1；行取到片上共享存储

SM_Occupancy=SM_Occupancy+

ArraySize[i][0]；

}

Else

{

If F[i]列重用&&SM_Occupancy

{Placement[i]=11；列取到片上共享存储

SM_Occupancy=SM_Occupancy+

ArraySize[i][1]；

}

Else Placement[i]=2；2表示寄存器

}

}

If平台==AMD

{If F[i]列重用&&SM_Occupancy

{Placement[i]=11；列取到片上共享存储

SM_Occupancy=SM_Occupancy+

ArraySize[i][1]；

}

Else

If SM_Occupancy

}

}

4 实验结果及分析

实验的硬件平台基于CPU+GPU结构，其中CPU采用Inteli7系列8核心、主频为2.8GHZ的处理器，内存为2G，GPU采用AMD和NVIDIA两个主流厂商的两款同性能等级的产品Caicos R5200 Series和GeForce GTS250，具体参数见表1，二者均支持基于OpenCL的开发，硬件之上运行着两个型号GPU对应的最新版本驱动程序。鉴于实验跨AMD和NVIDIA两个GPU两个平台，因此实验采用开放的并支持异构系统平台的开放计算语言OpenCL[18]。实验选取广泛存在于多个高性能测试集Rodinia、SPEC、NVIDIA OpenCL SDK和AMD OpenCL SDK的被广泛使用的矩阵乘法作为优化对象，为了验证EAoMAP算法的有效性以及方便对比，共计入Original、AL、BL、ALCL、ALBP、APBL和ALBL 7个不同的内核(内核代表的含义见表2)并分别在AMD和NVIDIA平台上进行了测试，结果见图4和图5，因为Original内核的加速比为1，所以在图中没有划出。

表1 实验平台参数

表2 内核含义

4.1 AMD GPU上的访存优化测试

在AMD GPU分别对设计的7个内核采用7个不同大小的数据集进行测试，分别是64*64，128*128，265*256，512*512，640*640，768*768，832*832，目的是为了观察同一个内核程序在不同数据量上的性能表现。

图4 优化策略在Caicos R5200上的效果

从图4中可以看出在AMD GPU上消除重复的片外访问取得明显的程序加速，最高达到8x，见上图4中matrixsize取768时，BL和ALBL加速比。AL中，将A数组的一行存储到local memory减少了重复的global memory访问，缩短了数组A的load时间以取得访存性能提升，然而与BL相比较，加速效果明显较差，因为乘操作中对应的两个操作数同时load成功，乘法操作指令才能执行，BL中将数组B的一列存放于local memory，减少数组B对global memory的重复访问，因为原程序对数组B的访问是列序进行，即图2(b)中的(b)类型，属于物理上的不连续访问，访存性能很低，因而采用BL优化后取得了比AL更高的性能提升。ALCL相比AL只有平均2%的性能提升，其原因在于在对数组C的访问密度相较于处理器的计算密度属于非密集，此时程序的性能主要由计算操作决定，因而即使提高了访存的性能，程序总体性能提升却并不明显。ALBP相较于AL平均有近25%的性能下降，这与AMD架构及其wave的组织策略相关，AMD架构规定每个CU上的最大wave数，但是在实际运行时，如果每个线程占用的寄存器空间较多，那么会导致分配在CU上的wave量减少从而降低处理核的利用效率。APBL相较于BL平均有近51%的性能下降，原因同ALBP。ALBL相较于AL有近77%的性能提升，相较于BL有8%的性能提升。总体而言，对于AMD架构，数据的非连续性访问明显降低系统效率，因而充分合理利用LDS(Local Data Share)器件对性能提升助益显著。

4.2 NVIDIA GPU上的访存优化测试

在NVIDIA GPU上同样对设计的7个内核采用与AMD GPU上相同大小的7个数据集进行测试以观察NVIDIA GPU上同一个内核程序在不同数据量上的性能表现。

图5 优化策略在GeForce GTS250上的效果

从图5中可以看出在NVIDIA GPU上消除重复的片外访问同样取得明显的程序加速，最高达到9x，见图5中matrixsize取640时ALBL的加速比。就AL和BL而言，将A数组的一行存储到shared memory或将数组B的一列存放于shared memory，两种策略都减少了重复的global memory访问，缩短了数组A或B的load时间而取得访存性能提升，平均取得2x的加速效果，与AMD架构不同的是，N卡的AL与BL加速效果区别微小，源于N卡数据访问非向量化的机制，数组B的列数据访问对系统性能的影响力远小于AMD架构。ALCL相比AL几乎没有性能提升，此处原因同AMD架构。ALBP和APBL相较于AL和BL平均有近138%的性能提升，同时ALBL平均有212%的性能提升，这个结果与AMD架构完全不同，在后三者中，矩阵相乘的两个操作数同时通过shared memory和寄存器批量存储，有效避免对同一数据反复地片外访问，较大地减少了操作数的load时间。需要注意的是以上两个图中当矩阵比较小时(如图4和5中Matrixsize<128，Matrixsize为二维方阵的单维大小)，ALBP和APBL两个内核效率不提升反而降低，尤其当Matrixsize=64，效率下降为AL的1/3不到，原因是当矩阵比较小时，程序总体开销比较小，数据访存优化带来的额外开销相比总体开销访存开销较大，因而导致系统性能不升反降。

4.3 NVIDIA GPU和AMD GPU加速率效果对比

针对NVIDIA GPU和AMD GPU，分别求出六种优化策略的平均加速比，如图6所示，从中可以看出NVIDIA GPU和AMD GPU的访存优化特征显然不同，因此在选择访存优化策略时，一定要考虑程序运行的平台因素，选择适合平台特性的访存优化策略，才能取得理想的加速效果。

图6 NVIDIA GPU和AMD GPU加速率效果对比

5 结论

GPU的高性能的确保需要处理核的高速运转和数据的及时充足供给，因此对于一些数据访问相对密集的应用，其数据访存成为性能瓶颈，提高其数据访问效率对提升系统性能至关重要。本文借助多面体模型理论，在对应用程序访存模式分析的基础上提出的多个提高数据访问效率的策略在NVIDIA和AMD GPU上最高取得9倍于原程序的加速效果，一方面说明了优化策略的有效性，另一方面进一步证明访存效率的确是影响GPU高性能发挥的重要因素。由于不同架构GPU访存特性的不同，同一优化策略会有差异悬殊的效果，那么在实际中应该根据平台选择适合的优化策略。