【计算机系统结构：量化研究方法】第四章：向量、SIMD和GPU结构中的数据级并行

前言

SIMD有三个变体：向量体系结构，多媒体SIMD指令集，图形处理器。本章着重介绍了这三者。在最后，还谈了循环相关性的问题。

向量体系结构

向量体系结构的主要操作是：有一组专门的寄存器叫做向量寄存器，一个向量寄存器里面能保存很多元素。一条指令可以对一个向量寄存器的元素施加同一个操作。这就是SIMD的体现。由于向量寄存器的元素很多，因此向量的载入和存储实现了流水化。需要注意的是，载入和存储的时延一般很长。

对于向量体系结构来说：因为单个向量内产生的相关性而出现的转发操作被称为链接(chaining)。执行单个元素的功能单元被称为车道，向量长度为一个向量的元素大小（而并非字节数量）。护航指令组(convoy)是指一组能够一直执行的向量指令（按照书上的理解，感觉是指可以一起发射的向量指令），需要注意的是，其内部不能出现结构冒险（出现的地方：功能单元个数，寄存器读写端口数量，访存数量），数据冒险通过链接的方式解决。执行一个护航指令组所花费的时间被称为一个钟鸣(chime)，一个钟鸣的大小为一个向量指令执行所需的周期数。钟鸣模型的开销：单周期发射指令数限制，启动时间（流水线越深，这一时间可能越久）提升单条向量指令的运算速度的手段是增加车道数，但相应的，需要考虑功耗的问题。

接下来，向量体系结构有两个很重要的寄存器：向量长度寄存器(VLR)和向量遮罩寄存器。前者记录需要进行运算的元素个数（因为单个元素都要占据一个车道），但是其中的值不能大于向量本身的元素个数，即最大向量长度(MVL)。而向量遮罩寄存器用来处理代码中的IF语句。如果IF为真，控制位为1，进行某些运算，否则控制位为0，不参与运算。

由于向量体系结构具有大量元素，因此需要向量载入存储单元提供带宽，于是向量处理器使用存储器组，将大量对象分散到多个存储器中，以提供更大的带宽。需要注意的是，由于需要载入非连续值，因此需要进行独立的组寻址。由于存储器组对地址空间进行了划分，我们需要特别关注某些具有固定步长的访问方式，比如矩阵乘法。如果步幅大小不合适，导致每次访存都是少数几个存储器的话，由于结构冒险，会导致一定程度的性能下降。除此之外还支持按照某个数组存的下标进行访存：A[B[i]]，这种访存操作被称为集中-分散操作，典型的应用就是稀疏矩阵索引。

SIMD指令集多媒体扩展

这里首先强调一下SIMD指令集多媒体扩展和向量体系结构的不同：

• 固定了数据操作数的个数，还有向量长度寄存器，有隐含的最大向量长度，但不提供向量遮罩寄存器
• 没有复杂的寻址模式，即集中-分散和步幅寻址
• SIMD指令集多媒体扩展数据传输要求在存储器中对齐，以避免页错误的产生，并且其不需要大量存储器带宽支持

x86提供的扩展：

• MMX：8*8位运算或4*16位运算
• SSE：16*8位运算或8*16位运算或4*32位运算，开始支持单精度浮点运算，在SSE2、SSE3、SSE4提供了双精度浮点运算
• AVX：寄存器宽度变为256位

Roofline可视性能模型：
就是一个浮点运算次数关于运算密度的函数，其中：

而运算密度等于浮点运算数与所访问存储器字节的比值。峰值浮点性能表征的是计算能力，受限于硬件，使用硬件规范（？翻译问题？Hardware Spec.）求得；峰值存储器带宽使用Stream基准测试求得。

图形处理器

以CUDA为例：CUDA编程模型定义为单指令多线程(SIMT)，于是出现了线程块的概念，一个线程块有16条线程，一条指令处理多个元素（32个元素？）。执行线程块的硬件称为多线程SIMD处理器，而负责指派线程块给处理器的是线程块调度程序（由此可见一个处理器处理一个线程块，因此处理器内部还有线程调度程序）。大量功能单元都是深度流水化的。

每个SIMD处理器有特定的车道数，对于某些架构可能是16个，那么一个含有32个元素的指令需要两个周期。（也就是说，一个时刻只可能有一个线程在执行，而不是多个线程执行，宏观并行微观串行）。处理器使用计分板管理跟踪线程，多线程可以隐藏访存延迟。

一个SIMD处理器有32768个32位的寄存器，但每个SIMD线程最多拥有64个向量寄存器，每个向量寄存器有32个元素。

• Fermi有16个车道，每个车道有2048个32位的寄存器（如果是处理32位元素，那么就有64个元素的位置）。为了能处理SIMD的32个元素，CUDA线程可以使用2048个寄存器的一半。（？这个部分的数量关系实在没弄清楚）

NVIDIA GPU使用PTX(并行线程执行)作为其指令集。该指令集提供了谓词寄存器（有点类似于遮罩寄存器的作用），控制相关指令是否执行，控制流相关的指令有函数的call,return，线程的branch和exit，以及线程块内的屏障同步。CUDA为每个线程块指派特定编号blockIdx，为每个线程同样提供特定编号threadIdx。GPU的所有访存都是集中-分散的，因此有一个特殊的硬件结构：地址接合硬件，负责判断SIMD线程的多个车道何时一同发出顺序地址，将这些地址接合在一起，打包通知存储器进行传输。

在处理条件分支的时候，PTX使用指令分支，调用，返回和退出描述。具体来说，每个车道都有一位的谓词寄存器，如果谓词寄存器为0，则不执行指令；为1，则执行指令。16个车道组成了宽度为16位的遮罩寄存器，遮罩寄存器的值用栈进行管理。以if-else-end为例：在if操作的时候执行push操作，将旧值压栈，然后遮罩寄存器设置新值；else操作对遮罩寄存器求补；end后弹栈。需要注意的是，实际上每个元素将每个分支的指令在逻辑上都过了一遍，是否执行则取决于遮罩寄存器对应位上的值，这一点跟单核处理器的思路完全不同（毕竟每个车道都要执行相同的指令，SIMD嘛）。此外，还进行了一定优化：遮罩寄存器全为1或全为0，会跳过某些指令。

对于GPU来说，有三级存储器结构：单个CUDA线程使用的叫专用存储器，一个线程块使用的叫本地存储器(用__shared__关键字表示)，所有线程块共享的叫GPU存储器。

最后，4.4.7的表4-8和4.4.8的表4-9比较了GPU与前两种SIMD实现方式的不同。这里不具体展开（挖坑，后面也许会展开）。

循环相关性处理

由于循环实现向量化的基础是没有循环相关性，所以循环相关性常常受到关注。如果一个循环没有循环相关性，往往采用条带挖掘(strip mining)的技术进行循环向量化：在循环开始之前将不足MVL的部分计算出来，之后在每次循环都计算MVL的量。

如果一个循环语句构成循环间依赖，但是未出现循环依赖，那么这种循环有机会消除循环间依赖改写成可并行化的循环：

for (i = 0; i < 100; i++){
    a[i] = a[i] + b[i];         // S1
    b[i + 1] = c[i] + b[i];       // S2
}

注意到S1依赖于上一次循环的S2，但是循环内，S2不依赖S1，那么可以稍作修改：

a[0] = a[0] + b[0]
for (i = 0; i < 99; i++){
    b[i + 1] = c[i] + b[i];       // S2
    a[i + 1] = a[i + 1] + b[i + 1];         // S1
}
b[100] = c[99] + d[99]

这样修改后，每个循环体可以并行执行，只需要保持循环内顺序即可。

对于循环间的数组索引，我们称其为仿射的，如果其索引符合ax+b的形式，其中x是循环变量。而稀疏矩阵为典型的非仿射索引。如果循环内有两个仿射索引ax+b和cx+d，我们通过检查来判断是否构成循环间相关。如果等式成立，则构成循环间相关。

实际上循环间相关的检测是一个NPC问题，如果检测到循环间相关，编译器可以采用寄存器重命名和复制操作来消除这种相关。

参考资料

计算机系统结构：量化研究方法（第五版）