CUDA性能简易优化（一）背景知识

CUDA性能优化简单教程，本篇介绍性能优化背景。
想知道实际中如何优化特定的层，或者某一层怎么设计才可能充分利用GPU，我们需要了解一些GPU的基础知识。
以下教程主要来源自NVIDIA官方：GPU Performance Background User’s Guide[1]，主要是讲解深度学习中，网络中一些operation在GPU中是如何执行的，已经一些和性能相关的细节注意点。
具体内容如下：
GPU的基本结构 (GPU Architecture Fundamentals[2])
OP（operation）是如何被拆分设计为并行计算的 (GPU Execution Model[3])
如何通过算术强度（arithmetic intensity）估算性能限制 (Understanding Performance[4])
深度学习操作的大概分类及其各自的性能限制(DNN Operation Categories[5])
0x10. GPU的基础结构
GPU是一种高度并行的处理器架构，由processing elements and a memory hierarchy组成，和我们经常提到的SM和显存有直接关系。
在高层次上，NVIDIA® GPU由多个流多处理器（SM）组成，具有片上的L2缓存和高带宽DRAM。SM执行算术和其他指令；通过L2缓存从DRAM访问数据和代码。例如，NVIDIA A100 GPU包含108个SM，40 MB L2缓存以及来自80 GB HBM2内存的高达2039 GB/s的带宽。

GPU架构
每个SM都有自己的instruction schedulers和各种instruction execution pipelines。在现代神经网络中，Multiply-add是最常见的操作，作为全连接和卷积层的核心块操作，两者都可以视为向量点积（vector dot-products.）的集合。
下表显示了NVIDIA Ampere GPU架构上单个SM的每个时钟的乘加操作的各种数据类型。每个乘加操作包括两个操作，因此可以将表中的吞吐量乘以2，以获得FLOP counts per clock。
要获取GPU的FLOPS具体值，我们可以将这些乘以SM的数量和SM时钟速率。例如，带有108个SM和1.41 GHz时钟速率的A100 GPU具有156 TF32 TFLOPS和312 FP16 TFLOPS的峰值密集吞吐量（实际能达到的吞吐量取决于后续讨论的多个因素，这只是理论值）。

Multiply-add operations per clock per SM
另外，FP16操作可以在Tensor Cores或NVIDIA CUDA®核心中执行。NVIDIA Turing™架构可以在Tensor Cores或CUDA核心中执行INT8操作。Tensor Cores在NVIDIA Volta™ GPU架构中引入，用于加速机器学习和科学应用的矩阵乘法和累加操作。这些指令在小的矩阵块（例如4×4块）上操作。
Tensor Cores还可以在比输入更高的精度下进行乘积计算和累加。例如，在使用FP16（半精度浮点数）输入进行训练时，张量核心可以在不损失精度的情况下进行乘积计算，并以FP32（单精度浮点数）进行累加。
满足特定操作的可以在Tensor Core中执行，不满足的就在普通Cuda Core中执行（比如一个简单的FP16精度的element-wise的加法操作）。
0x20. GPU Execution Model[6]
为了利用其并行资源，GPU通常会同时执行许多线程。
了解线程数与GPU性能之间的关系，有两个关键概念：
GPU使用2级线程层次结构来执行函数。给定函数的线程被分组成相同大小的线程块，并启动一组线程块来执行函数。
GPU通过切换到其他线程的执行来隐藏依赖指令的延迟。因此，为了有效利用GPU，所需的线程数量远远高于核心数或指令流水线数。
两级线程层次结构是因为GPU拥有许多流式多处理器（SM），每个SM又具有执行许多线程的流水线，并使其线程通过共享内存和同步进行通信。在运行时，一个线程块会被放置在一个SM上执行，使线程块中的所有线程能够高效地进行通信和同步。
使用单个线程块启动一个函数只会使一个SM工作，因此为了充分利用拥有多个SM的GPU，需要启动许多线程块。由于一个SM可以同时执行多个线程块，通常希望线程块的数量是SM数量的几倍。这样做的原因是为了尽量减少“尾部”效应，即在函数执行结束时只剩下少数活跃的线程块，从而在那段时间内GPU利用率不足，如下图所示。

GPU Execution Model
Utilization of an 8-SM GPU when 12 thread blocks with an occupancy of 1 block/SM at a time are launched for execution. Here, the blocks execute in 2 waves, the first wave utilizes 100% of the GPU, while the 2nd wave utilizes only 50%.
我们使用波（wave）这个术语来指代一组可以并行运行的线程块。以多个wave的线程块来启动函数执行是最高效的方式——在尾波（最后一个波次）中花费的时间占比较小，从而最小化尾效应，因此也减少了处理尾效应的需求（这种效应会导致总体执行效率降低，因为GPU的一部分核心在等待少数几个线程块完成时处于空闲状态）。对于高端GPU来说，通常只有当启动少于300个线程块的情况下，才需要考虑尾效应。
0x30. Understanding Performance[7]
在给定的处理器上执行函数的性能受以下三个因素之一的限制：
内存带宽
数学带宽
延迟
以下称呼的数学，意思就是某个op的算术强度，就是这个操作需要多少flops才能实现
考虑一个简化模型，其中一个函数从内存中读取其输入，执行数学运算，然后将其输出写入内存。假设：
是显存访问和读取的时间， 是在数学算子上计算的时间。如果我们假设这两个操作可以在不同线程中执行，可以重叠（overlap），那么总时间就是 。两个当中谁大谁就是限制当前op性能的原因。如果是数学那么就是math limited，如果是显存那就是memory limited。
在显存或数学运算中花费多少时间取决于算法及其实现方式，以及处理器的带宽。内存时间等于在内存中访问的字节数除以处理器的内存带宽。数学时间等于操作次数除以处理器的数学带宽。因此，在给定处理器上，如果一个给定算法是受到数学限制，则：

通过简单的代数，不等式可以重新排列为：

左侧是算法实现操作次数和访问字节数的比值，也就是俗称的arithmetic intensity。右侧是处理器计算能力和内存带宽之比，有时被称为ops:byte比率。因此，在给定处理器上，如果算法的算术强度高于处理器的ops:byte比率，则该算法受到数学限制。相反地，如果其算术强度低于处理器的ops:byte比率，则该算法受到内存限制。
让我们考虑一些深度神经网络的具体例子，列在下面的表格中。对于这些示例，我们将比较算法的算术强度与在NVIDIA Volta V100 GPU上的ops:byte比率。V100具有125 FP16 Tensor TFLOPS的峰值数学速率，约为900 GB/s 的芯片外存储器带宽和3.1 TB/s 的芯片内L2带宽，因此其ops:byte比率介于40到139之间，取决于操作数据（片内或片外存储器）的来源。
Operation Arithmetic Intensity Usually limited by…
Linear layer (4096 outputs, 1024 inputs, batch size 512) 315 FLOPS/B arithmetic
Linear layer (4096 outputs, 1024 inputs, batch size 1) 1 FLOPS/B memory
Max pooling with 3×3 window and unit stride 2.25 FLOPS/B memory
ReLU activation 0.25 FLOPS/B memory
Layer normalization < 10 FLOPS/B memory
如表所示，许多常见操作的算术强度很低——有时每从内存读取并写入两字节元素只执行一次操作。请注意，这种分析是一种简化，因为我们只计算了算法中使用的操作。实际上，函数还包含算法中未明确表达的操作指令，如内存访问指令、地址计算指令、控制流指令等。
算术强度和每字节操作数分析假设工作负载足够大，能够充分利用给定处理器的数学和内存管道。然而，如果工作负载不够大，或没有足够的并行性，处理器将被低效利用，性能将受到延迟的限制。例如，考虑启动一个单线程，它将访问16字节并执行16000次数学操作。尽管算术强度为1000 FLOPS/B，并且在V100 GPU上的执行应该是数学限制的，但只创建一个线程会严重低效利用GPU，使其几乎所有的数学管道和执行资源处于空闲状态。
此外，算术强度计算假设输入和输出仅从内存中访问一次。对于算法实现多次读取输入元素的情况并不少见，这会有效降低算术强度。因此，算术强度是一种初级近似；如果需要更准确的分析，需要看profiler。
0x40. DNN Operation Categories[8]
我们平常的深度学习网络中有很多基础的op层，大概分为三类：
0x41. Elementwise Operations[9]
Elementwise operations 可以是一元或二元操作；关键在于此类层对张量中的每个元素执行数学运算，独立于张量中所有其他元素。
例如，ReLU层对输入张量中的每个x返回max(0, x)。同样，两个张量的逐元素加法计算每个输出和值与其他和值无关。这类层包括大多数非线性函数（sigmoid、tanh等）、比例、偏置、加法等。
这些层往往受到内存限制，因为它们每访问一个字节只执行少量操作。有关激活函数的更多详细信息，请参见《优化内存限制层用户指南》中的激活[10]部分。
0x42. Reduction Operations[11]
reduce operations也就是常见的规约操作。
例如，池化层在输入张量的某些邻域内计算值。Batch normalization在每个输出元素的操作中使用之前，计算张量的均值和标准差。除了池化和归一化层外，SoftMax也属于归约类别。典型的归约操作算术强度较低，因此受到内存限制。有关池化层的更多详细信息，可以在池化[12]中找到。
0x43. Dot-Product Operations[13]
该类操作可以表示为两个tensor的点积，通常是一个权重（学习参数）张量和一个激活张量。也就是常说的矩阵乘法。
包括全连接层（fully-connected layers），可以很自然地表示为矩阵向量和矩阵矩阵乘积。
卷积也可以理解为就是做 matrix-vector and matrix-matrix multiplies，常见的卷积实现im2col就是典型的矩阵乘。不过矩阵乘处于算术瓶颈还是显存瓶颈也分情况，如果batch比较小或者输入比较小，那么还是memory bound，只有当batch大的时候才会是compute bound。
0x50. 总结[14]
如何大概预估我们某个op在某个GPU上的性能受限在哪，有以下几点方法：
弄清楚这个GPU上的 SM 数量，并确定 GPU 的 ops:bytes 比例
预估当前op算法的运算强度（arithmetic intensity）
通过估算线程块的数量和大小，判断是否有足够的并行度来充分利用 GPU。如果线程块的数量至少是 SM 数量的 4 倍，并且每个线程块由几百个线程组成，那么可能就有足够的并行度
最可能的性能瓶颈是：
如果没有足够的并行度，则是GPU常见的延迟问题，延迟无法掩盖
如果有足够的并行度且算法运算强度高于 GPU ops:bytes 比例，则是数学运算瓶颈
如果有足够的并行度且算法运算强度低于 GPU ops:bytes 比例，则是内存瓶颈
说白也就是看Memory-bound还是Compute-bound
参考资料
[1]GPU Performance Background User’s Guide: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html
[2]GPU Architecture Fundamentals: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#gpu-arch
[3]GPU Execution Model: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#gpu-execution
[4]Understanding Performance: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#understand-perf
[5]DNN Operation Categories: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#dnn-op-cat
[6]0x20. GPU Execution Model: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#gpu-execution
[7]0x30. Understanding Performance: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#understand-perf
[8]0x40. DNN Operation Categories: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#dnn-op-cat
[9]0x41. Elementwise Operations: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#element-op
[10]激活: https://docs.nvidia.com/deeplearning/performance/dl-performance-memory-bound/index.html#activations
[11]0x42. Reduction Operations: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#reduction-op
[12]池化: https://docs.nvidia.com/deeplearning/performance/dl-performance-memory-bound/index.html#pooling
[13]0x43. Dot-Product Operations: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#dot-prod-op
[14]0x50. 总结: https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html#gpu-perf-summary