这次回顾ECE408 Lecture 9，这次介绍了分块卷积分析（Tiled Convolution Analysis）。

课程主页：

搬运视频：

GPU内存架构

模板模式

  • 数字处理算法根据某种固定模式更新数组元素，称为模板；
  • 卷积只是其中一个例子；

示例：

除此之外，卷积还可以应用于卷积神经网络。

1D卷积

  • 上图是块1的输出和输入块；
    • 第一行为输入，第二行为输出；
  • 对于$\text{MASK_WIDTH}$为5，每个块加载8 + (5 – 1) = 12​个元素（​12个内存加载）；

  • $P[8]$使用$N[6],N[7],N[8],N[9],N[10]$；
  • $P[9]$使用$N[7],N[8],N[9],N[10],N[11]$；
  • ……
  • $P[15]$使用$N[13],N[14],N[15],N[16],N[17]$；
  • 一共8 * 5 = 40值用于输出；

计算tiling收益的简单方法

  • 加载8 + (5 - 1) = 12个输入数组元素；
  • 8 * 5 = 40个全局内存访问可能被共享内存访问取代；
    • 指加载12个共享内存；
  • 这样带宽减少了40/12=3.3倍；
  • 这与$N$的大小无关；

一般情形：

  • 将$\text{(TILE_WIDTH + MASK_WIDTH – 1)}$个元素从全局内存加载到共享内存；
  • 将$\mathrm{(TILE_WIDTH \times MASK_WIDTH)}$全局内存访问替换为共享内存访问；
  • 这导致带宽减少$\mathrm{(TILE_SIZE \times MASK_WIDTH) / (TILE_SIZE + MASK_WIDTH - 1)}$倍；

示例

从下表理解带宽减少的示例：

TILE_WIDTH 16 32 64 128 256
Reduction MASK_WIDTH = 5 4.0 4.4 4.7 4.9 4.9
Reduction MASK_WIDTH = 9 6.0 7.2 8.0 8.5 8.7

另一个视角查看复用

这里从输入角度理解复用：

  • $tile[6]$被$P[8]$使用(1×)；
  • $tile[7]$被$P[8],P[9]$使用(2×)；
  • $tile[8] $被$P[8],P[9],P[10]$使用(3×)；
  • $tile[9] $被$P[8],P[9],P[10],P[11]$使用(4×)；
  • $tile[10] $被$P[8],P[9],P[10],P[11],P[12]$使用(5×)；
  • ……(5×)；
  • $tile[14] $被$P[12],P[13],P[14],P[15]$使用(4×)；
  • $tile[15] $被$P[13],P[14],P[15]$使用(3×)；
  • $tile[16] $被$P[14],P[15]$使用(2×)；
  • $tile[17] $被$P[15]$使用(1×)；

分析：

  • 每个对tile的访问替换对输入$N$的访问；

  • 替换的总数为：

  • 因为输入$N$有12个元素，所以带宽减少了40/12=3.3倍；

那么边界Tile又如何呢？

  • ${P}[0]$使用${N}[0], {N}[1],{N}[2]$；
  • $P[1]$使用$N[0],N[1],N[2],N[3]$；
  • $P[2]$使用$N[0],N[1],N[2],N[3],N[4]$；

一共加载了：

次共享内存。

Ghost元素影响比例

  • 对于边界tile，我们加载$\mathrm{TILE_WIDTH + (MASK_WIDTH-1)/2}$个元素；
    • 在我们的$\mathrm{TILE_WIDTH}$为8和$\mathrm{MASK_WIDTH}$为5的示例中为10；
  • 计算访问全局内存的数量；
    • 总访问次数为$6\times 5 + 4 + 3 = 37$次访问（计算$P$元素时）；
  • 减少的比例为为$37/10 = 3.7$；

2D卷积

计算tiling收益的简单方法

分析8×8输出块，$\mathrm{MASK_WIDTH}$为5:

  • 加载输入块需要$(8+(5-1))^2 = 144$次读取；
  • 每个输出的计算需要$5^2 = 25$个输入元素；
  • $8×8×25 = 1,600$次全局内存访问被转换为共享内存访问；
  • 带宽减少$1,600/144 = 11.1$倍；

一般情形：

  • 将$(\text{TILE_WIDTH} + \text{MASK_WIDTH} – 1)^2$个元素从全局内存加载到共享内存；
  • 输出$P$的每个元素需要访问$N$的$\text {MASK_WIDTH}^2$个元素；
  • 将$(\text{TILE_WIDTH} \times \text{MASK_WIDTH})^2$全局内存访问替换为共享内存访问；
  • 这导致带宽减少$(\text{TILE_WIDTH} + \text{MASK_WIDTH} – 1)^2/(\text{TILE_WIDTH} \times \text{MASK_WIDTH})^2$倍；

示例

TILE_WIDTH 8 16 32 64
Reduction MASK_WIDTH = 5 11.1 16 19.7 22.1
Reduction MASK_WIDTH = 9 20.3 36 51.8 64

非分块情形

  • untiled卷积中每个浮点运算(FLOP)使用多少全局内存？
  • 在untiled convolution中，
    • $N$的每个值（来自全局内存的4B）；
    • 乘以来自$M$的每值
      （来自常量缓存的4B，1个FLOP）；
    • 然后添加到sum（1 FLOP）；
  • 这给出了2B / FLOP；
    • 全局内存4B / 2FLOP；

充分利用计算需要13.3倍的重用

  • 回忆一下我们在矩阵乘法中的重用讨论：

    • 1,000 GFLOP/s, 以及150 GB/s内存带宽（2010年的GPU）；

  • 将内存带宽除以2B/FLOP：

  • 这说明至少需要$100/7.50 = 13.3$倍的重用才能充分利用计算资源；

那么在2021年呢？

  • GRID K520提供5,000 GFLOP/s, 以及192 GB/s内存带宽；

  • 将内存带宽除以2B/FLOP：

  • 这说明至少需要$100/1.92 = 52.1$倍的重用才能充分利用计算资源；

需要非常大的Mask来平衡资源

根据之前的讨论，要充分利用GPU，我们需要更大的Mask。

1D：

MASK_WIDTH 2010 2020
5 37% 9.6%
9 67% 17%
15 100% 28%
55 100% 100%

2D：

MASK_WIDTH 2010 2020
3 60% 15%
5 100% 37%
7 100% 67%
9 100% almost 100%