基于访存分歧的gpu核心程序重组优化方法.docx

基于访存分歧的gpu核心程序重组优化方法专利名称：基于访存分歧的gpu核心程序重组优化方法技术领域：本发明涉及GPU核心程序(即GPU Kernel)重组优化方法，尤指基于访存分歧的GPU Kernel重组优化方法背景技术：近年来，GPU (Graphics Processing Unit,图形处理单元)强大的计算能力、海量线程并发的执行模式以及灵活的编程模型，使得GPU已经广泛应用于分子动力学模拟、生物起源分析、气象预测等众多高性能计算领域面对面对大规模的GPGPU (General Purposecomputing on Graphics Processing Units)应用映射，标准的单核心程序(Kernel)模式无法满足大规模应用程序的需求GPU核心程序(GPU Kernel)就是运行在GPU上的程序段，通常程序员会将程序中计算密集、运行耗时的核心子程序移植到GPU上加速，运行在GPU上这样的核心子程序通常称为 GPU Kernel面对大规模的GPGPU应用程序，其GPU Kernel数目多达数十上百个为了提高如此多GPU Kernel的调度效率，最大限度开发程序并行性，多GPU Kernel重组优化技术成为提高程序运行效率的有效途径。

目前GPU Kernel重组优化方法主要有以下几种:(I)基于Kernel并发的多Kernel合并NVIDIA第二代统一架构之前的GPU体系结构是不支持多Kernel并发执行的,为了让独立的GPU Kernel能够并发执行,多Kernel合并是多Kernel并发执行的有效方法NVIDIA第二代统一架构GPU虽然能够并发多Kernel同时执行，但是并发Kernel的数量也是极其有限的，因此，多Kernel合并方法可以提高多Kernel之间的并行性，缓解多Kernel顺序执行的压力，减少多Kernel启动开销，开发利用多Kernel之间的并行性，提高GPU程序的运行效率2)基于GPU共享存储器的多Kernel合并如果GPU Kernel之间存在数据依赖关系，即一个Kernel的输出刚好是另一个Kernel的输入,为了避免各Kernel顺序访问长延迟的全局存储器，可以将存在输入输出数据依赖关系的多个Kernel合并成一个独立的GPU Kernel，在GPU Kernel内显式管理GPU共享存储器作为数据传输中介，避免全局存储器的访问，提高访存效率，同时减少GPU Kernel数目，减少了 GPU Kernel启动开销并且有利于Kernel调度，提高GPU程序运行效率。

3)基于程序分支的多Kernel重组不同于传统的CPU体系结构，GPU将片上绝大部分资源用于计算，GPU中的控制单元和分支预测部件相对匮乏如何在GPU Kernel中避免线程分支，对于提高GPU Kernel的执行效率至关重要，因此，有学者提出将同一 GPUKernel中的不同程序分支分离出来组建不同的GPU Sub-Kernel,然后将具有相同执行路径的GPU Sub-Kernel合并组成一个新的GPU GPU Kernel,实验基于程序分支的GPU Kernel重组可以有效避免GPU线程分支而造成的线程等待与同步，显著提高了 GPU Kernel的执行效率上述三类GPU Kernel重组优化方法，在一定程度上，面向具体的大规模GPU应用优化加速都可以提高GPU Kernel的执行效率，提升GPU应用程序的性能但是，上述三类GPU Kernel重组优化方法忽略了 GPU线程存储访问模式对GPU Kernel的执行效率的影响实践中，GPU线程的访存行为特征将严重影响GPU Kernel的执行效率因此，如何从实践应用出发，解决因为GPU线程的访存行为特征导致的GPU系统效率低和GPU应用性能差的难题是本领域技术人员关注的重要技术问题。

GPU线程的访存行为特征可以分为以下两类:(I) Kernel中的线程访问一片连续的存储空间，这也是一种理想化的GPU线程的访存行为特征，在这种访存行为特征下GPU Kernel执行效率最高；(2) Kernel中的线程访存行为出现跳跃特征，即各线程访问不同的存储器空间或是非连续访问同一存储器空间的间断存储单元GPU线程的访存行为特征中Kernel线程出现跳跃特征的访存行为称之为GPU线程访存分歧SIMD (Single Instruction Multiple Data,单指令多数据)加速已经成为提升体系结构效能的有效方法，GPU体系结构就是一种典型的SIMD加速体系结构SIMD加速的工作模式是以GPU线程访问一段连续的存储空间为基础如果GPU线程的存储访问行为出现了跳跃特征，不仅不能提升 系统效能，加速GPU应用，还会严重影响GPU系统效能和GPU应用程序运行效率重组优化出现访存分歧的GPU线程是提升GPU系统性能和GPU应用程序运行效率的关键技术和方法因此，通过GPU Kernel重组方法来消除GPU线程访存分歧，能够最大限度提升GPU系统效能和GPU应用程序运行效率目前还没有公开文献涉及相关技术方案。

发明内容本发明要解决的技术问题在于:针对大规模多GPU Kernel应用执行效率低的问题，提出一种基于访存分歧的GPU Kernel重组优化方法，以提升大规模GPU Kernel的执行效率和应用程序性能为了解决上述技术问题，本发明的具体技术方案为:第一步、采用Create方法为GPU程序的每个Kernel函数构建访存行为特征表Create方法的具体步骤是:为GPU程序的每个Kernel函数建立一张访存行为特征表，访存行为特征表包含四个字段，分别为:线程编号Tid、线程访问的存储器类型MemT、线程访问的数据大小Size和访问的存储空间逻辑地址Addr线程编号Tid表示线程在该Kernel函数域中的唯一编号；线程访问的存储器类型MemT表示线程访问的存储器类型，存储器类型包括全局存储器Global、共享存储器Shared Memory、纹理存储器Texture Memory和常量存储器Constant Memory ;线程访问的数据大小Size表示该线程访问的数据占据存储空间字节的数目；线程访问的存储空间逻辑地址Addr表明线程操作计算需要的数据存放的地址空间第二步、采用Record方法记录各Kernel函数中各线程的访存轨迹。

Record方法的具体步骤是:2.1扫描GPU核心程序，定义GPU核心程序中Kernel函数的函数编号Kid依次为O,I,…i，…M-1，其中，O ( i〈M，M为GPU核心程序中Kernel函数的数目；并定义编号为i的Kernel函数启动的线程数目为Ti,则访存行为特征表的总数为M ;编号为i的Kernel函数对应的访存行为特征表的表项数目为该Kernel函数启动的线程数目1\将GPU程序中的Kernel线程的访问访存轨迹信息写入访存行为特征表对应的表项和字段；2.2初始化」=0;2.3获取函数编号为j的Kernel函数启动的线程数目Ir并初始化k=0 ；2.4将函数编号为j的Kernel函数的第k线程的访存轨迹信息分别写入访存行为特征表的字段TicU MemT>Size和Addr,更新k=k+l ；2.5 如果 k ( T厂I，转 2.4 ;否则转 2.6 ；2.6 更新 j=j+l ；2.7 如果 j ( M-1，转 2.3，否则转 2.8 ；2.8各Kernel函数中各线程的访存轨迹信息记录完毕，执行第三步第三步、访存分歧判断根据每个Kernel函数中的GPU线程的访存地址，判断同一 Kernel函数中的GPU线程中的线程访存是否出现访存分歧。

判断方法如下:3.1 初始化 j=0 ；3.2获取函数编号为j的Kernel函数启动的线程数目Tj,定义该Kernel函数访问的存储器类型集合Sj为空，即& =0，并定以分歧地址集合Aj为空，即為=0，初始化m=0 ；3.3查询访存行为特征表获取线程Tm访问的存储器类型表示第m个线程Tm的访问存储器类 型如果与线程Tm+1访问的存储器类型riff不同，则判定线程Tm与线程m+1出现访存分歧，将出现分歧的存储器类型添加到集合Sj中，即具体实施例方式图1为访存行为特征表结构，具体的特征表建立方式如下:为GPU程序的每个Kernel函数建立一张访存行为特征表，访存行为特征表包含四个字段，分别为:线程编号Tid、线程访问的存储器类型MemT、线程访问的数据大小Size和访问的存储空间逻辑地址Addr线程编号Tid表示线程在该Kernel函数域中的唯一编号；线程访问的存储器类型MemT表示线程访问的存储器类型，存储器类型包括全局存储器Global、共享存储器Shared Memory、纹理存储器Texture Memory和常量存储器ConstantMemory ;线程访问的数据大小Size表示该线程访问的数据占据存储空间字节的数目；线程访问的存储空间逻辑地址Addr表明线程操作计算需要的数据存放的地址空间。

图2为本发明的总体流程图，其具体实施步骤如下:第一步、构建访存行为特征表第二步、记录各Kernel函数中各线程的访存轨迹第三步、访存分歧判断第四步、基于访存分歧的GPU Kernel重组优化4.1基于访存分歧的GPU Kernel分裂4.2基于连续访存的GPU Kernel融合第五步、结束权利要求1.一种基于访存分歧的GPU核心程序重组优化方法，其特征在于包括以下步骤: 第一步、采用Create方法构建访存行为特征表，具体步骤是:为GPU程序的每个Kernel函数建立一张访存行为特征表，访存行为特征表包含四个字段，分别为:线程编号Tid、线程访问的存储器类型MemT、线程访问的数据大小Size和访问的存储空间逻辑地址Addr ;线程编号Tid表示线程在该Kernel函数域中的唯一编号；线程访问的存储器类型MemT表示线程访问的存储器类型；线程访问的数据大小Size表示该线程访问的数据占据存储空间字节的数目；线程访问的存储空间逻辑地址Addr表明线程操作计算需要的数据存放的地址空间； 第二步、采用Record方法记录各Kernel函数中各线程的访存轨迹,具体步骤是: .2.1扫描GPU核心程序，定义GPU核心程序中Kernel函数的函数编号Kid依次为.0,1,…i，…M-1，其中，0 ≤i〈M，M为GPU核心程序中Kernel函数的数目；并定义编号为i的Kernel函数启动的线程数目为Ti,则访存行为特征表的总数为M ;编号为i的Kernel函数对应的访存行为特征表的表项数目为Ti JfGPU程序中的Kernel线程的访问访存轨迹信息写入访存行为特征表对应的表项和字段； .2.2初始化J=0 ； .2.3获取函数编号为j的Kernel函数启动的线程数目Ir并初始化k=0 ； .2.4将函数编号为j的Kernel函数的第k线程的访存轨迹信息分别写入访存行为特征表的字段 Tid、MemT、Size 和 Addr,更新 k=k+l ； .2.5如果k ≤ T1-1,转2.4 ;否则转2.6 ；.2.6 更新 j=j+l ； .2.7如果j≤M-1，转2.3，否则转2.8 ； .2.8各Kernel函数中各线程的访存轨迹信息记录完毕，执行第三步； 第三步、根据每个Kernel函数中的GPU线程的访存地址，判断同一 Kernel函数中的GPU线程中的线程访存是否出现访存分歧，方法如下: .3.1初始化j=0 ； .3.2获取函数编号为j的Kernel函数启动的线程数目Tj,定义该Kernel函数访问的存储器类型集合Sj为空，即Sj=Φ，并定以分歧地址集合Aj为空，即Aj=0，初始化m=0 ； .3.3查询访存行为特征表获取线程Tm访问的存储器类型TMomTm,TMomTm表示第m个线程Tm的访问存储器类型，如果TMomTm与线程Tm+1访问的存储器类型TMomTm+1。