【IT168 技术】1. GPU通用计算简介
注：本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见：http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案，将会逐步与大家分享，不可错过哦!
CUDA ZONE专区：http://cuda.it168.com/
CUDA技术论坛：http://cuda.itpub.net
CPU和GPU都是具有运算能力的芯片，CPU更像“通才”——指令运算(执行)为重+ 数值运算，GPU更像“专才”——图形类数值计算为核心。在不同类型的运算方面的速度也就决定了它们的能力——“擅长和不擅长”。芯片的速度主要取决于三个方面：微架构，主频和IPC(每个时钟周期执行的指令数)。
1.微架构
CPU的微架构是按照兼顾“指令并行执行”和“数据并行运算”的思路而设计，就是要兼顾程序执行和数据运算的并行性、通用性以及它们的平衡性。CPU的微架构偏重于程序执行的效率，不会一味追求某种运算极致速度而牺牲程序执行的效率。
CPU微架构的设计是面向指令执行高效率而设计的，因而CPU是计算机中设计最复杂的芯片。和GPU相比，CPU核心的重复设计部分不多，这种复杂性不能仅以晶体管的多寡来衡量，这种复杂性来自于实现：如程序分支预测，推测执行，多重嵌套分支执行，并行执行时候的指令相关性和数据相关性，多核协同处理时候的数据一致性等等复杂逻辑。
GPU其实是由硬件实现的一组图形函数的集合，这些函数主要用于绘制各种图形所需要的运算。这些和像素，光影处理，3D 坐标变换等相关的运算由GPU硬件加速来实现。图形运算的特点是大量同类型数据的密集运算——如图形数据的矩阵运算，GPU的微架构就是面向适合于矩阵类型的数值计算而设计的，大量重复设计的计算单元，这类计算可以分成众多独立的数值计算——大量数值运算的线程，而且数据之间没有像程序执行的那种逻辑关联性。
GPU微架构复杂度不高，尽管晶体管的数量不少。从应用的角度看，如何运用好GPU的并行计算能力主要的工作是开发好它的驱动程序。GPU驱动程序的优劣很大程度左右了GPU实际性能的发挥。
因此从微架构上看，CPU擅长的是像操作系统、系统软件和通用应用程序这类拥有复杂指令调度、循环、分支、逻辑判断以及执行等的程序任务。它的并行优势是程序执行层面的，程序逻辑的复杂度也限定了程序执行的指令并行性，上百个并行程序执行的线程基本看不到。GPU擅长的是图形类的或者是非图形类的高度并行数值计算，GPU可以容纳上千个没有逻辑关系的数值计算线程，它的优势是无逻辑关系数据的并行计算。
2.主频
GPU执行每个数值计算的速度并没有比CPU快，从目前主流CPU和GPU的主频就可以看出了，CPU的主频都超过了1GHz，2GHz，甚至3GHz，而Fermi的主频为1.15GHz。GPU数值计算的优势主要是浮点运算，它执行浮点运算快是靠大量并行，但是这种数值运算的并行性在面对程序的逻辑执行不如CPU。
3.IPC(每个时钟周期执行的指令数)
GPU大多数指令都是面向数值计算的，少量的控制指令也无法被操作系统和软件直接使用。如果比较数据指令的IPC，GPU显然要高过CPU，因为并行的原因。但是，如果比较控制指令的IPC，自然是CPU的要高的多。原因很简单，CPU着重的是指令执行的并行性。
另外，目前有些GPU也能够支持比较复杂的控制指令，比如条件转移、分支、循环和子程序调用等，但是GPU程序控制这方面的增加，和支持操作系统所需要的能力CPU相比还是天壤之别，而且指令执行的效率也无法和CPU相提并论。
CPU擅长的：操作系统，系统软件，应用程序，通用计算，系统控制等等;游戏中人工智能，物理模拟等等;3D建模-光线追踪渲染;虚拟化技术——抽象硬件，同时运行多个操作系统或者一个操作系统的多个副本等等。GPU擅长的：图形类矩阵运算，非图形类并行数值计算，高端3D游戏。
综上所述，在一台均衡计算的计算机系统中，CPU和GPU还是各司其职，除了图形运算，GPU将来可能主要集中在高效率低成本的高性能并行数值计算，帮助CPU分担这种类型的计算，提高系统这方面的性能。而当前的典型应用还是高端3D游戏，一个高效的GPU配合一个高效的CPU，3D游戏的整体效率才能得到保证。“高端3D游戏只需要高端显卡”或者“高端3D游戏只需要CPU”都是无稽之谈。
2. nVidia GPU简介
第一款被称作可编程的GPU是NVIDIA的NV20，就是传说中的Geforce3，不过它远远不能对CPU的地位构成威胁。它能够处理的程序指令还非常有限，大约在10条左右，另外它所能处理的数据类型也非常之有限，只能处理9或12bit固定长度的数据。当NVIDIA的NV30发布的时候，摩尔定律再次得到了印证，不仅仅是晶体管数量的增加，计算单元的数量也成倍增长。同时这也使得显卡芯片更具灵活性。因此NVIDIA的NV30具备许多革命性的突破。从NV30起，GPU开始支持单精度浮点运算，即使它并不完全支持IEEE754标准，
2.1 G80架构
主要包括2006年11月发布GeForce 8800，500 GFLOPS，2008年4月发布的GeForce 8800 GTX，使用GDDR3 DRAM，每个core有一个单精度浮点乘加，可以进行整数运算，每个SM包括8个core，还包括2个special functional units(SFUs)，执行特殊的函数，每个SM包括8096字节寄存器空间，16KB 软件管理的共享内存空间。
2.2 GT200架构
主要包括2008年发布GeForce GTX 280，900 GFLOPS，支持双精计算，每个SM一个双精计算单元，共享内存增加为32KB共享内存空间，加入合并全局内存访问，共享存储空间原子操作，每个core的整数逻辑单元(ALU)仅限于24bit的乘法操作
2.3 Fermi架构
2010年刚刚发布的Fermi架构，基于CUDA 2.0，主要包括以下特点：支持C++，支持IEEE 754-2008 32位和64位计算，支持ECC，支持cache hierarchy。64位虚拟地址空间，不同memory统一编址。40位线性地址空间。原子操作快20倍。双精度计算速度比GT200快8倍，单精要慢，1.5 TFLOPS单精，750 GFLOPS双精。S2050 3G memory，S2070 6G memory。不同程序切换时间为20到25 微秒。线程切换速度提高10倍，最多支持6GB GDDR5内存，将DRAM分为6块64位，总共384位内存接口，Fermi和PTX 2.0 ISA将分离的线程local memory，线程块shared memory和global memory地址空间统一编址，40位寻址能力。在PTX 1.0中，load/store指令在编译时就指向三种地址空间中一种。
Tesla C2050，2010年5月发布，包含14个SM，448个core，1.15GHz，双精和单精峰值分别为525GFlops和1.03TFlops。C2050为3G GDDR5内存，C2070为6G GDDR5内存，所有存储层次都支持ECC校验，如果使用ECC，则可用内存减少12.5%。内存频率和位宽分别为1.5GHz和384bit，带宽为144GB/s。使用PCIe x16 Gen2(理论峰值为8GB/s)互联GPU与CPU，支持C/C++/Fortran，OpenCL，DirectCompute。
32core/SM，共512个core，每个core有一个FPU和一个整数运算单元，每个SM包括以下部分：一个指令cache;16个core为一个计算单元;16个load/store单元(一个clock计算16个线程的地址)和4个SFU。双精度计算需要32个core，因此SM可以同时发送16个双精度计算或者32个单精度计算。每个SM有两个warp scheduler和dispatch unit，每个时钟周期可以调度和发射2个32线程warp。在同一时刻，第一个warp调度器可以发射奇数ID号warp中的指令，第二个调度器可以发射偶数ID号中的指令，唯一的例外是只有一个调度器可以发射双精度指令，此时另一个不能发射指令。因此对一个warp，调度器要用2个cycles来发射一个整数，浮点运算指令或双精度浮点运算指令，用8个cycles发射单精度transcendental指令。而1.x调度器需要4个cycles发射整数和单精浮点运算指令，32个cycles发射双精度运算指令，16个cycles发射单精度transcendental指令。每个时钟周期可以执行16个存储指令。每个SM最多支持16个kernel并行执行。发布的Fermi支持4个kernel并行执行，因为concurrent kernels最大并行数量是由GPC确定的。
GigaThread将线程块分配到一个SM调度器。每个SM有32K 32-bit寄存器，128KB大小。每个SM可以运行48个warp，1536个线程，32个SM可运行24576个线程。每个SM有64KB空间，可以配置成16KB共享内存加48KB L1 cache，或者配置成48KB共享内存加16KB L1 cache。 768KB统一L2 cache。为某些数据并行度较低而不能产生大量线程以隐藏延迟，或者某些数据重用模式不固定的应用。Fermi寄存器大小为16*128KB=2048KB，L1 cache大小为16*48KB=768KB，L2 cache大小为768KB。而不是传统存储层次距离较远具有较大存储空间。L1和L2中cache line大小为128bytes，映射到global内存128byte对齐段。
Fermi以前的架构由于没有cache存储层次，并且线程块没有同步机制，所以分配到不同SM的线程块不会引起冲突，由于Fermi引入了2层存储层次，因此性能模型设计和算法优化必须考虑调度到GPU运行的所有线程块间协作，在一段时间内其总体数据量不要超过L2 cache，否则会导致冲突缺失。而由于维护L1 cache coherence开销，所有SM访问写数据应该保持独立，避免不同SM同时写入同一数据。
由于每个SM有64KB空间，可以配置成16KB共享内存加48KB L1 cache，或者配置成48KB共享内存加16KB L1 cache。对于可以充分利用共享内存的算法，配置为48KB共享内存可以增大GPU整体缓存大小=16*48KB+768KB=1536KB，如果配置为16KB共享内存，则GPU可利用缓存大小最小，为=16*16KB+768KB=1024KB。
Fermi挑战：面向双精，比单精增加一倍带宽需求。频率增加，计算能力更前，双精515GFLOPS，使得内存墙问题更为严重。为了弥补前面二点，加入了多层存储层次，增加了调优难度。加入更多寄存器，提供更多threads，以更好隐藏延迟。
3. CUDA简介
nVidia GPU使用了CUDA编程模型，对硬件进行抽象，包括三个基本概念：线程组的层次，共享内存，同步。提供了细粒度数据并行和线程并行，循环的粗粒度数据并行和任务并行。CUDA有可扩展的多线程流处理器(SMs)阵列构成。当执行CUDA的kernel时，grid的块就被分布到多处理器上。一个多处理器由8个标量处理器(SP)。
CUDA线程模型：GPU上的thread有三个层次。最高层是grid，grid内的thread执行相同的kernel，每个grid可以有2^16-1个blocks， blocks组织成一维或者二维形式。中间层是block，每个block内部的thread可以组织成三维，最多可以有512个threads。同一block内部的thread可以通过一个低延迟的片上共享内存共享数据，对数据进行原子操作，并通过__syncthreads原语进行同步。最后，硬件将thread分为warp执行以提高访存性能。
CUDA kernel函数是C函数，在被调用时按照指定的grid维数和线程块维数并行的执行。CUDA可以通过内置的threadIdx变量获得线程ID。kernel的限制：不能包含循环，静态变量，参数的个数必须固定。threadIdx是一个三元矢量，所以可以将线程按照一维，二维或者三维来划分。在kernel内可以通过内置的blockIdx变量和blockDim变量访问某个线程块。同一网格中不同线程块中的线程不能互相通信和同步。Block内的线程通过shared memory，atomic operations和barrier synchronization协同工作，不同block内的线程不能通信。Kernel启动时内置变量和函数参数存放在shared memory中。
每个线程有私有本地内存，每个线程块有共享内存，所有线程可以访问全局内存。所有线程还可以访问二个只读内存空间，常量和纹理内存空间。Kernel内的数组存储在local memory中。Shared memory，G80上为16个bank，4bytes为单位进行寻址，bank ID=4-byte address%16，相邻的4-byte地址映射为相邻的bank，每一个bank的带宽为4bytes per clock cycle。对同一个bank的同时访问导致bank conflict，只能顺序处理。解决方法，padding，transpose。Coalesced global memory accesses，在half-warp层对访问global memory进行协调，
CUDA将32个标量线程称为warp，以warp为单位来进行创建，管理，调度，执行。一个warp共享和执行相同的指令，由于每个SM有8个core，执行一个warp指令需要4个cycles，类似于一组矢量指令的流，所以标量线程可以看成矢量处理单元。一个cycle一条指令从L1指令cache加载到指令buffer中，当warp的数据都可用时被选择执行。Block内的thread按顺序分配到不同的warp中，但是warp的顺序可能随着GPU的更新而变化。GPU调度线程零开销。执行结构为单指令多线程SIMT，SM将线程块中的每一个线程映射到一个标量处理器，每一个标量线程独立的在自己的指令空间和寄存器状态运行。SIMT与SIMD的不同指出在于后者指定了数据宽度，然而SIMT中的每一个线程可以执行不同的代码路径。SIMT可以使得程序员编写指令级并行代码，
| Compute Capability |
1.0 |
1.1 |
1.2 |
1.3 |
2.0 |
| Threads / Warp |
32 |
32 |
32 |
32 |
32 |
| Warps / Multiprocessor |
24 |
24 |
32 |
32 |
48 |
| Threads / Multiprocessor |
768 |
768 |
1024 |
1024 |
1536 |
| Thread Blocks / Multiprocessor |
8 |
8 |
8 |
8 |
8 |
| Shared Memory / Multiprocessor (bytes) |
16384 |
16384 |
16384 |
16384 |
49152 |
主要的编译制导语句：
l __device__均为inline函数，__noinline__指示编译器不要inline。
l #pragma unroll n告知编译器展开循环5次，#pragma unroll 1禁止循环展开，如果不加数字，#pragma unroll，如果循环计数为常数，则全部展开，否则不展开。
l __restrict__告诉编译器指针没有重名，即写入一个指针不会影响其他指针指向的数据，所有的指针参数都要指定__restrict__，因此编译器可以使用指令重排和公共子表达式消除优化方法。这样可能增加了register需求数量，因此需要平衡。
l 编译时可以配置global内存为L1和L2都 (-Xptxas -dlcm=ca)，或者只有L2进行缓存(-Xptxas -dlcm=cg)。
l __align__(n)，在n字节位置对齐。例如struct __align__(16){float x,y,z;}，主机和设备端内存分配函数返回的首地址均在256字节对齐。
主要的编译选项：
l 加入--ptxas-options=-v编译选项可以看各存储空间分配大小。
l 加入-cubin生成.cubin
l 加入-ptx生成. Ptx文件。
l 加入--keep，保留中间结果，中间文件。
4. CUDA优化方法
4.1 从硬件角度观察
共享内存作用：
l 同一线程块内线程共享数据，减少内存带宽需求，增加计算访存比。例如，不利用共享内存的矩阵乘代码，假设每个线程计算一个矩阵C元素，内存带宽需求为2n2+2n3，分块矩阵乘代码[PPOPP08，CUBLAS1.1]在共享内存中缓存矩阵A和B大小为16*16子块，内存带宽需求降为2n2+2n3/B。
l 可以缓存内存全局数据，优化warp内线程内存访问，使得coalesced加载内存数据。例如考虑矩阵转置，计算访存比为1，不存在数据重用，似乎利用不到共享内存，如果要求源矩阵A和目标矩阵B均为行主或列主存储，每个线程处理一个元素，则无论怎样组织一个warp内的线程，对其中一个矩阵中元素一定是非coalesced访问，如果利用共享内存，一个线程块处理矩阵一个子块，则可以进行优化使得所有内存访问均为coalesced，且共享内存没有bank冲突。
共享内存优化方法，防止bank冲突：
l 数组填充。
l 矩阵转置。
l 共享数据大小要考虑同步作用，由于在共享内存的数据通常被线程块内所有部分线程访问，所以要在加载数据之后进行同步，共享数据太小会导致同步次数增多，降低性能。
l 利用共享内存数据通常要在kernel内循环利用不用数据，共享数据太大会导致循环次数增多，可以利用循环展开降低循环等待时间。
全局内存优化方法：合并访问，利用共享内存降低带宽需求。解决非coalesced内存访问方法：
l 使用structure of array(SOA)而不是AOS，
l 使用__align(x)对齐数据，
l 或者使用shared memory来协作访问。
l Coalescing float3 access说明如何使用shared memory进行Coalesced access。
寄存器作用：
l GPU的设计理念是大量并行多线程隐藏延迟，因此在一个SM上配置了大量寄存器。
l 开发ILP可以在寄存器重用数据，而TLP只能在共享内存重用数据。[SC08]GEMM对矩阵A和C元素在寄存器重用以开发ILP，对矩阵B子块在共享内存重用以开发TLP。ILP-TLP trade-off，寄存器比共享内存空间大，
4.2 从软件角度观察
由于GPU的设计理念是大量并行多线程隐藏延迟，因此在一个SM上配置了大量寄存器，由于SM还限制了thread block，warp和threads数目，所以通常利用循环展开增加寄存器利用率。Tesla C1060上每个SM最多容纳768个threads，而每个SM有64KB大小寄存器，所以每个线程可以使用85B，[SC08]中的GEMM算法每个线程使用30个寄存器，而CUBLAS 1.1使用15个寄存器。
GPU的目标是高带宽而不是低延迟。GPU的线程切换低开销，较高访存延迟和较小共享内存和寄存器空间都限制了GPU上应用以细粒度并行为主。GPU带宽比CPU高，可以通过线程间调度隐藏延迟，因此GPU优化主要在访存对齐以及利用共享内存，优化：最大化独立并行性，最大化算术计算密度，重复计算优于访问存储器
对于CUDA线程模型三个层次，[PPOPP10]进行了分析并提出了相应指标计算方法评估算法在每一层中特性：在线程级提出ILP，表示在寄存器一级共享数据以及隐藏延迟;在warp级开发DLP，保证全局内存coalesced访问，减少共享内存bank冲突;在线程块一级开发线程间数据共享。由于一个warp内线程同步运行，我们将GPU上运行的一个warp视为CPU中一个线程，则本文所指GPU线程ILP(Instruction-Level parallelism，指令级并行)为一个GPU上单线程内部指令级并行性，而GPU线程TLP(Thread-Level Parallelism，线程级并行性)指一个SM上活动warp间并行性。优化计算：循环展开减少动态指令数。[SC08]过多的线程并不能提高性能，增加线程内计算任务，提高ILP。
ILP vs.TLP：访存延迟为400cycles，一个warp在G200上需要4个cycles，如果每个n个指令有一个访存操作，则容忍延迟需要400/4n个warp。如果增加一个register能够增加独立指令个数，但是降低了block数量或者block内线程数量，即降低TLP，需要比较两者孰优孰劣。
4.3 Fermi基本优化方法
Global内存可以配置成L1和L2缓存，或者只有L2缓存，而local内存必须进行L1和L2缓存。如果kernel使用较多local内存，则设置为48KB L1 cache。计算能力1.x可以利用texture内存加速数据访问，然而由于2.0加入了带宽更高的L1 cache，使用texture cache并不一定能改进性能。
计算能力1.x的global内存访问以half-warp为单位，而2.0则以一个warp为单位。
计算能力1.x的shared内存访问以half-warp为单位，有16个bank，而2.0则以一个warp为单位，有32个bank，依然以32bit为单位存储，即连续32bit存储在连续bank，每个bank的带宽为32bit/(2 cycles)。只有在两个或更多线程同时访存一个bank内不同32bit字时产生bank conflict，多个线程访问同一数据不会产生bank conflict，而且2.0增加多播使得多个字可以在一个transaction内完成，多个线程可以访问同一个32bit字内的不同字节。对于64bit double寻址，只要一个half-warp内线程不访问同一bank内的不同32bit数据，就不存在bank conflict，因此double data = shared[BaseIndex + tid]没有bank conflict。
l 计算能力1.x中整数乘以mul24为基本实现，而2.0则32bit实现整数乘。
l 浮点运算配置成-ftz=true (denormalized numbers are flushed to zero)，-prec-div=false (less precise division), and -prec-sqrt=false (less precise square root)会生成性能更高的代码。
l nvcc设置–m64或者–m32将生成64位和32位代码，如果GPU不用更多内存，可以分别编译设备代码和主机代码。
l 标准函数可以在主机或者设备端调用，intrinsic函数只运行在设备端调用，并且具有更高性能，准确率降低。intrinsic函数以__为前缀。
l 2.0提供了一些高级intrinsic函数。
为了隐藏延迟为L的指令，1.x需要L/4个warp，而2.0需要L/2个warp，因此2.0上需要更多warp隐藏延迟。
由于2.0支持并发kernel，可以将并行度较低或者串行部分代码交由GPU执行，以减少主机和设备端数据交换，对于未来主机和设备融合共享内存，这种优化则不必要。
