基于GPU的高性能并行算法研究

发布时间：2020-03-25 06:43

【摘要】： 计算机图形处理器(Graphics Processing Unit,GPU)的高速发展,不但促进了图像处理、虚拟现实、计算机仿真等应用领域的快速发展,同时也为人们利用GPU进行图形处理以外的通用计算提供了良好的运行平台。基于GPU的图形处理及其通用计算成为图形学及高性能计算领域的热点研究课题。基于GPU的高性能并行算法研究是该课题的重要内容之一。本文以探索GPU大规模并行通用计算的运用模式为目标,从传统问题入手,选择典型算法进行研究,主要研究了数值类算法中的非计算密集型算法、数据密集类算法和元启发式优化算法这三类算法在GPU上的并行化。数值类算法中的非计算密集型算法存在内存墙问题,而在基于GPU的并行化过程中,该瓶颈尤为突出。本文以稀疏矩阵向量乘算法为代表,研究基于GPU并行化方法以及性能优化策略。数据密集类算法由于其特有的数据可分割性,因而比较适于GPU并行计算。本文以频繁模式挖掘算法和最近邻搜索算法为代表,研究了此类算法的GPU并行化方法以及性能优化策略;针对最近邻搜索问题,结合KD-Tree空间划分与ABT方法,提出了适于欧几里德距离的点剪枝策略。元启发式优化算法是求解大规模优化问题的高效方法之一,其解空间搜索过程具有天然的并行性。本文以蚁群算法为代表,研究了蚁群算法及其若干改进算法在GPU上的并行化方法;针对蚂蚁个体智能性不足的问题,提出了带有展望策略的蚁群优化算法;针对蚁群参数敏感问题,研究了多蚁群在GPU上同时进化方法,提出了适于GPU的粗/细粒度结合的多蚁群算法;针对异构多蚁群的信息交流问题,提出了一种新的基于共享信息素矩阵的交流策略。大量的标准测试表明,上述算法可以达到几倍甚至上百倍的加速比;与已有的同类基于GPU的并行算法相比,上述算法具有更高的实际浮点性能和存储器带宽。CPU+GPU的异构多核架构是目前GPU大规模并行通用计算的运用模式,探讨传统算法的GPU并行化方法,使之更适用于异构多核架构下并行计算,能够为基于GPU的高性能计算的普及提供理论和方法。
【图文】：

体系架构,多处理器

构和并行层次为主线讨论 GPU 通用计算与 CPU 指令级及多核并行、超级计的多处理器级并行和集群分布式并行的区别。2.1 GPU 体系架构GPU 体系架构在不断的发展，本节以最新的 NVIDIA Tesla GT200 体系架代表对 GPU 的并行层次进行分析。Tesla GT200 由两部分组成，分别是可伸处理器阵列(Scalable Streaming Processor Array，SPA)和存储器系统，它们由片上互联网络连接。如图 1.1 所示，可伸缩流处理器阵列由若干个线程处理(Thread Processing Cluster，TPC)构成，每个 TPC 包含 2～3 个流多处理treaming Multiprocessor，SM)，每个流多处理器中包含 8 个流处理器(Streamocessor，SP)。流处理器有独立的寄存器和指令指针，但缺少取指和调度单流多处理器才拥有完整前端，，包括取值、译码、发射和执行单元等。从结构，每个流多处理器相当于一个 8 路单指令流多数据流(Single Instruction Mulata，SIMD)处理器，不同的是，GPU 实现了自动向量机化，NVIDIA 将之命单指令流多线程(Single Instruction Multiple Thread，SIMT)[5]。

示意图,双核,架构,示意图

第 1 章绪论关 GPU 架构的细节见文献[4，5]。与多核 CPU 的区别统 CPU 的并行层次只有指令级并行，然而通用计算中可并行过超标量、深度流水、长指令字等手段增加指令级并行不能取U 性能提升主要依靠提高处理器的工作频率，先进的分支预测缓存增加命中率这三种方式。然而，制造工艺的提高是有限度工作频率的增长都因为量子效应等原因而趋缓，通过提高处理 CPU 的性能遇到了前所未有的困境。INTEL、AMD 等厂商转而在单块芯片内集成更多的处理器核心，使 CPU 向多核的方向了双核 CPU 产品，继而又有 3 核以及 4 核产品面市，图 1.2 给出PU 的架构示意图。
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2010
【分类号】：TP338.6

【参考文献】