论文部分内容阅读
大规模数据并行应用对可扩展性、计算能力和存储带宽的迫切需求促使高性能微处理器正在向众核体系结构演变。作为一种新型的众核体系结构,图形处理器(GPU)采用大量晶体管用于计算单元,采用相对简单的控制逻辑,具有非常高效的存储带宽层次。现代GPU体系结构所具有的片上计算单元密集、存储带宽高效、性价比高等鲜明的特点,形成了一个崭新的研究领域一基于GPU的通用计算(GPGPU),即利用GPU来实现更为广泛的数据并行计算。受体系结构和可编程性的制约,早期的GPU未能在并行计算领域普及。随着高级编程模型(如AMD/ATI STREAM TM、NVIDIA CUDATM和OpenCL)的相继推出,GPU程序设计的复杂性在一定程度上得到降低。为了节约设计成本并实现未来体系结构的可扩展性,GPU体系结构通常采用分散式硬件设计。与CPU存储系统相比,GPU存储系统的设计目标是维持高吞吐量而非低延迟。虽然GPU体系结构可以同时维持大量的线程,以零开销的硬件线程切换来隐藏存储访问延迟,但是如果应用程序中存在大量的不规则数据访问,势必会造成很多线程因同时访存而出现暂停,浪费了宝贵的计算资源。GPU特殊的体系结构使得高级编程模型下的应用程序难以充分利用其强大的计算能力和高效的存储带宽,编写高性能的GPGPU程序需要考虑如何将应用程序有效映射至GPU硬件上加以执行。此外,GPU的并行编程模型与传统的串行编程模型存在差异,基于GPU体系结构的应用开发与优化方法也与传统方法有着很大不同。由于GPU体系结构底层硬件的复杂性,编译器并没有对应用程序进行充分的优化。为了指导应用程序高效映射到GPU体系结构上执行,本文研究了面向众核GPU体系结构的性能评估与优化方法,具体工作如下：(1)当应用程序映射到GPU体系结构上执行时,很多因素都会降低程序的性能,一种量化的性能模型可以用于评估特定应用移植至GPU体系结构上的实际执行性能。由于现代GPU体系结构的复杂性,传统的并行计算模型无法用于评估GPGPU程序的性能。为了预测应用程序并行化后的执行性能,评估并行化过程中可能存在的性能瓶颈,本文针对GPU体系结构提出了一种量化的性能评估模型。该模型建立在抽象GPU体系结构和执行模型的基础上,充分考虑了影响GPGPU程序性能的各种因素(如全局存储器的接合访问、局部存储器的冲突访问、计算与存储访问重叠、条件分支转移、同步),在无需编写实际GPGPU程序的前提下,通过对应用程序的静态分析并结合GPU的性能参数设定具体的执行配置,即可估算出应用程序并行化后的执行时间。实验结果表明,该性能模型能够较为准确地评估应用程序在GPU体系结构上的执行时间。(2)在GPU体系结构的存储系统中,全局存储器容量较大但访问延迟较高,快速存储器(如局部存储器)访问速度较快但容量有限。因此,改善数据在全局存储器中的布局,减少不规则存储访问,合理利用片上快速存储器,减少总体的存储访问开销对于提升GPGPU程序的性能至关重要。为了充分发挥GPU体系结构在存储带宽方面的优势,本文提出了基于多面体模型的存储优化方法。该方法建立源程序的多面体表示,分别对GPU的全局存储器和快速存储器进行优化与分配：通过检测存储访问模式,发掘可向量化的存储访问实例,利用数据空间变换对不规则存储访问模式进行转换,提高了GPU片外存储器的带宽利用率；通过检测程序中的数据重用,根据数据的访问属性和GPU存储器硬件的特性,实现了快速存储器的有效分配；采用坐标转换和增加偏移量的技术分别对IMAGE存储对象和局部存储器进行优化,提高了片上存储器的使用效率。实验结果表明,该存储优化方法可以使得程序的性能相对优化前提升1.2-8.4倍。(3)循环和数组结构通常具有计算密集和数据并行的特征,因此这种结构通常是GPU计算核心的天然候选。然而在一些应用程序中,数据依赖和控制相关阻碍了它们在GPU体系结构上高效地运行。由于GPU体系结构同时强调计算密集与数据并行,因此将计算重构和数据重构加以组合更能够充分开发其性能潜力。为了使应用程序能够充分开发GPU体系结构的性能潜力,本文提出了面向GPU体系结构的程序重构方法：首先通过循环合并与拆分的计算重构增大了应用程序的可并行性,尽可能消除操作间的依赖关系,提高所生成GPU计算核心的计算密集性,有利于存储访问延迟的隐藏；其次,通过对线程内和线程问的数据访问进行重构,减少了GPU计算核心的存储访问次数；最后,通过条件执行、分支化简和间接索引等重构技术,减少了分支转移对于程序性能的负面影响。实验结果表明,该程序重构方法可以使得程序性能相对重构前提升1.18-2.56倍。(4)数据并行应用中的非计算密集型算法存在存储墙问题,在基于GPU的并行化过程中显得更为突出。为了有效缓解存储受限型应用的存储墙问题,本文针对生物序列比对领域设计了一种基于GPU的Smith-Waterman并行算法：通过改变原有Smith-Waterman算法的计算流程和数据依赖关系,进一步增加了序列比对的并行性；通过实施面向GPU体系结构的优化方法,进一步提升了序列比对的性能和效率。实验结果表明,经过优化的Smith-Waterman算法与CPU上的串行算法相比提升了近115倍。本文在众核GPU体系结构上的研究成果对今后在GPU上开发通用计算及面向其他众核体系结构的优化编译器方面具有借鉴意义。