GPU的SIMD并行设计
Overview
大吞吐量与高并发的特点，让GPU不仅在图形计算方面无可替代，也使其在通用计算领域被广为使用。本文简要介绍了GPU上的SIMD设计，与结合了多线程的SIMT设计。
Flynn's Taxonomy
费林分类法是一种对计算机体系结构的分类，多用于针对于现代处理器的设计和功能的分类。
根据并行的指令流与数据流的数目，分为以下四类：
SISD( Single Instruction, Single Data ) SIMD( Single Instruction, Multiple Data ) MISD( Multiple Instruction, Single Data ) MIMD(Multiple Instruction, Multiple Data)
术语
为了保持简短和一致性，本文使用英伟达的术语。在阅读正文前，需要至少理解以下两个概念。
Thread：着色器的一次调用被称为一个“线程”，与CPU的线程不同，它仅由为该计算分配好的显存和寄存器组成。因此在SIMD中，尽管用语上是线程，但最终是面向数据的。 Warp：对于同一个着色器的调用被打包为一组。在微软的DirectX中对应Thread Group，在苹果公司的Metal中对应SIMD Group。
| Nvidia | OpenGL |
|---|---|
| Thread | Work-item |
| Warp | Wavefront |
| Block | Workgroup |
| Grid | NDRange |
SIMD：单指令多数据
Single Instruction, Multiple Data. 简称为SIMD。
SIMD指令广泛用于处理3D图像，并且现代GPU内建的SIMD基本让图形计算的主要负载从CPU侧转移。还有一些包含重新打包向量内部元素的置换函数的系统，让数据处理和压缩受用于SIMD。随着GPU的通用计算（GPGPU）的流行，SIMD被更加广泛地运用。
根据时间-空间二元性，SIMD可以进一步分为：
Array Processor：单个指令同时对多个数据元素进行操作，使用不同的空间。 Vector Processor：单个指令在连续的时间步长对多个数据元素进行操作，使用相同的空间。
一个SIMD设计的例子（Array Processor）
假定有100个线程，一个处理器具有8个核心，100/8 = 12....4，最终会有13个线程组，前12组含8个线程，第13组含4个线程。
第一个线程组的8个线程由8个核心同步计算，由于同线程组内的线程会同步执行相同的指令，若执行到需要从内存中读取数据的步骤（读取时间比执行指令的时间长很多），则线程会同时进入等待读取的状态。此时进行切换（开销极小），核心开始计算第二个线程组的线程。
由于每个线程都有自己独占的显存和寄存器，记录已经执行过的指令和计算结果十分容易。
四个线程组都执行到读取数据的步骤后，会切换回第一个线程组，利用读取完成的数据继续计算。如果第一个线程组仍在读取中，说明所有线程组都还在读取数据，则等待直到读取完毕。
下图则通过一个包含4个指令的例子展示了Array Processor与Vector Processor间的区别。
SIMD设计的瓶颈
占用率（Occupancy）
显存和寄存器容量有限，因此能被载入并执行的线程数量有限。不同的操作会对应不同的最佳占有率。
动态分支（Dynamic Branching）
由于同一wrap内的线程会被执行相同的操作，出现“if”语句时，会为所有线程执行所有分支，当某线程执行自身控制流以外的分支时，则会实际执行NOP( No Operation Performed )指令。Warp内线程的控制流出现分歧的情况被称为线程分歧（Thread Divergence）。
SIMT：单指令多线程
2006年十一月，英伟达在特斯拉架构的G80芯片引入了SIMT( Single Instruction, Multiple Thread. )。而ATI，也即现在的AMD，则在2007年五月发布同样支持SIMT的对标产品——基于TeraScale1的R600芯片。
SIMD在大量重复运算的场景中的优势，使其适用于图形计算。由于每个片元的运算独立于其他片元，也即着色器的执行具有彼此独立的特点，SIMD使用执行单元或向量单元，GPU的SIMT将之进行扩展以利用线程级的并行。因此认为SIMT是一种将SIMD与多线程结合的执行模型。
尽管SIMT与现代SIMD类似，但前者具有更宽的向量寄存器，并且流水线也更长，二者是相对独立的概念。SIMT在费林分类法中不属于一种严格的划分，而更像是SIMD的一个子集或变体。
此外，由于相同的指令在在SIMD机器的所有lane上执行，所以不论是SIMT还是SIMD，都依赖了数据级的并行。
同时，如果处理器发现一批指令是相互独立的，并且还有可并行执行的资源，那么这批指令就会被同时执行，因此指令级的并行同样存在。
为了能为任意的计算提供大量算力，现在几乎所有GPU都使用了支持SIMT或超线程的统一着色架构( unified shader architecture )。
SIMT的Flow Control
SIMT同样面对着和SIMD相同的困境：线程分歧。得益于同处理器上能低开销地实现线程间同步，针对线程的流程控制依赖于masking，当出现一个处理器的负责的多个线程需遵循不同的控制流的情况，会导致利用率降低。
例如处理IF-ELSE语块时，所有的线程必须执行所有的语块，而masking可以在正确的时机启用/禁用某些线程。在一个处理器负责的所有线程的控制流能被确定的情况下，应当避免masking。Masking的策略也是SIMT与SIMD的一个不同之处。
结语
像AMD GCN这样的处理器有64个寄存器集，但只有4个计算核心。因此它一次能执行4组SIMD指令，但实际情况往往不是所有的线程都就绪，而是只有就绪的线程真正地被执行。
对于开发者/硬件设计者而言，终极目标是“不论RAM/高速缓冲的延迟与负载如何，处理器每时每刻都在算着什么”。这也是现代GPU如此之快的原因，这样的设计几乎不会让循环周期因为等待资源而被浪费。
Reference
"BLOG: SIMD vs SIMT vs SMT: What’s the Difference Between Parallel Processing Models?" "WIKIPEDIA: Single instruction, multiple threads" "WIKIPEDIA: SIMT" "WIKIPEDIA: Flynn's Taxonomy" "BLOG: SIMD < SIMT < SMT: parallelism in NVIDIA GPUs" "LECTURE: SIMD (Vector Processors) - Carnegie Mellon - Comp. Arch. 2015 - Onur Mutlu" "TALK: DirectCompute: Optimizations and Best Practices - NVIDIA Coporation - San Jose, CA 2010 - Eric Young" "BOOK: Real Time Rendering 4th Edition"