SIMD＜SIMT＜SMT: NVIDIA GPU的并行机制

原文出处：

SIMD < SIMT < SMT: parallelism in NVIDIA GPUs

1、概述

1.1、SIMD

2、SIMD vs SIMT

2.1 单指令、多套寄存器组

2.2 单指令、多个数据访问单元

2.3 单指令、多种运算逻辑路径

3、SIMD vs SIMT

3.1 GPU通过多thread来实现高throughput机制

3.2 latency很高的register很便宜

3.3 SIMT相比SMT的不足

4、总结

1、概述

NVIDIA GPU称为它们的并行编程模型为SIMT(Single Instruction,Multiple Threads)。与我们熟知的SIMD（Single Instruction,Multiple Data）以及SMT(Simultaneous Multithreading)相比，SIMT带来了一些新的特性，在并行机制上总结如下：

1、在SIMD中，在一个vector中的多个element是完全同步并行计算的；

2、在SMT中，多个线程（thread）中的指令是并行执行的；

3、在SIMT中，多个thread共享一条指令并行执行（SMT是各个线程run各自的指令），每个thread处理一个scalar数据，使之看起来像SIMD，但是并不限制同时执行的thread之间的同步性。

因此SIMT看起来更像是平衡了灵活性与计算效率的一种硬件结构。下面的文章中将会详细解释SIMT与SIMD/SMT的区别，以及通过这些区别SIMT获得了什么特性、失去了什么特性。

1.1、SIMD<SIMT<SMT

可以这样说：SIMT相比SIMD更加灵活，而SMT相比SIMT又更加灵活，SIMD在损失灵活性的前提下提升了运算效率。

所以对于灵活性而言，SIMD<SIMT<SMT；而对于计算效率而言，SIMD>SIMT>SMT，但是仅仅在那些SIMD灵活性足以处理的任务中进行比较。

2、SIMD vs SIMT

SIMT和SIMD都是通过广播同一条指令到多个执行单元的并行机制。因此多个执行单元可以共享同一套指令装载/指令译码逻辑。

那么，“单指令多线程（SIMT）” 和 “单指令多数据（SIMD）”之间的区别究竟在哪里呢？在NVIDIA GPU的模型里面，有3个特征是SIMD并不具备的：

1、单指令，多套寄存器组（SIMD是并行的元素都在同一个寄存器内）；

2、单指令，多个数据访问单元；

3、单指令，多种运算逻辑路径；

下面举例说明上述特性将如何解除掉一段可以并行化的程序的限制,并解释这些特性带来的额外成本。

2.1 单指令、多套寄存器组

假定我们需要把两个vector中的数据相加，C语言代码如下：

Matlab代码则可以用vector的写法：

SIMD使用了“short vector”的写法，是对程序员极不友好的。我们需要先将待加的数据vector拆分成多个更短的“short vector”，然后循环多次进行处理。以ARM NEON为例，上述实例功能的对应代码如下：

SIMT使用了一种“scalar”的写法：

看起来奇怪的关键字“__global__”表明add()函数是一个GPU thread的入口，加粗的blockIdx,blockDim,threadIdx则是在构建GPU thread时的thread ID。后面我们将看到为什么 thread ID不仅仅是一个简单的数字编码，但是在这个例子里面我们实际上把它看做一个数字，从而进行element的索引。

因此这一整套处理机制可以这样总结：CPU为每一个待处理element分配一个thread，随后GPU执行这些thread。GPU执行这些thread时发挥它的并行性，多个thread实际上是并行执行的。NVIDIA的GPU内包含多个完全独立的处理单元SM(Streaming Multiprocessor)，每一个SM又包含了多个“cores”,每一个core处理一个thread。比如Tesla系列GPU拥有14个SM，每个SM包含8个core，所以它可以并行处理112个thread。

同一个SM中的多个“core”(即上图中的SP，streaming processor)虽然执行不同的thread，但是实际上执行的指令是同一条指令，不过这条指令在不同的“core”中对应不同的register，处理不同的数据。这就是SIMT的由来。

2.1.1 单指令、多套寄存器组的收益

因为SIMT没有将多个thread访问的数据绑定在一起（完全不相关的数据），使得可以以“scalar”的方式进行编码，即我们写代码时只需要按照标准的单thread运算模式来进行。毫无疑问这比丑陋的SIMD编码方式好的多，上面的例子中可以看到SIMD的编码方式已经很接近汇编语言了。

2.1.2 单指令、多套寄存器组的代价

从硬件资源的角度，SIMT带来了两方面的代价：

1、花费更多register来存放多余的数据

以上面的vector加法为例，a、b、c作为element的地址，在所有thread中值都是同样的，但是因为每个thread中i的值不一样，以至于每个thread必须单独存放地址（比如元素地址128/129/130）。显然每个thread中存放的element地址信息存在冗余。

在SIMD中，a/b/c可以只在“scalar”寄存器中存放一次。对于“short vector”中的数据a[i:i+4]的访问（即单条指令中参与运算的数据），可以通过在scalar中存放a、b、c、i，vector中存放a[i:i+4]的数据即可完成。因为确保了与a[i]相邻的数据一定是a[i+1]、a[i+2]、a[i+3]，实际上不需要去计算i+1、i+2、i+3。

SIMT的冗余运算不仅浪费更多的register，也产生了多余功耗。按道理通过compiler和硬件的优化可以消除这些冗余，但是NVIDIA没有对外公开这些细节。

2、narrow的数据类型按照widen的数据进行处理

假设SIMD的vector register宽度为128bit，那么通常可以可选的执行“4个32bit运算”、“8个16bit运算”，或者“16个8bit运算”。以ALU为例，同样的ALU硬件电路可以用于多种精度的加法，这些加法完全同步进行。但是在SIMT中，对于执行两项相加功能的thread，无论加数的位宽为多少都耗费一样的资源。

值得留意的是SIMT可以很容易的扩展支持narrow精度的运算（像SIMD一样），这样使得单个thread可以处理多个element。但是NVIDIA拒绝了这样的设计，因为32bit float任然是最受欢迎的数据类型，支持narrow精度的收益不大反而影响了编码效率。

2.2 单指令、多个数据访问单元

假定我们需要在GPU上部署一段类似于查找表的函数：

可以看到并行执行的多个thread中i的存储依然是冗余的，因为i是连续的。但是每个thread访问的地址lut+b[i]就不再是连续的了。

因为thread都独自存放了地址，无论是并行的load还是store都可以同时工作。当然由于写冲突，并行的store可能存在问题。试想一下如果同时有两个thread需要对直方图统计中的同一个bin做加1操作会怎么？不同的NVIDIA GPU有不同的处理策略，在这里不深入分析。

2.2.1单指令、多个数据访问单元的收益

比较容易理解，上述特点使得我们可以把一些SIMD无法并行的程序并行化。某些SIMD机器中设计了几种常见的并行随机访问机制，例如“permutation”、“suffling”、“table look-up”等等。但是这些操作总是在register之间进行，而不是在memory中进行，所以不能与SIMT相提并论。比如SIMD可以索引8/16/32个元素，但是无法索引16KB范围。

正如前面提到的，理论上SIMT也可以修改为SIMD的单个数据访问单元的方式。只需要先把上面的地址（lut+b[i]）计算后存入一个vector，然后使用一条ran_vec_load指令来读取数据。这样的指令将会有很大的latency。相比较而言SIMT模型在不牺牲throughput的情况下吸收了高latency，SIMD则差远了。

2.2.2单指令、多个数据访问单元的代价

GPU有多种类型的memory，例如外部的DRAM、L2 cache、texture memory、constant memory、share memory等等。我们讨论极端情况：即随机访问DRAM和share memory。其中DRAM是离GPU最远的存储单元，坐落在芯片之外；而share memory则是最靠近core的存储单元，它位于SM之内，同一个SM中的多个core使用它来share数据或者存放临时数据。

首先声明一点，对DRAM的随机访问从来做不到高效。在GPU中，所有正在run的thread在同一个cycle内发起的memory访问都被尝试合并起来，最终发出尽量少的DRAM访问，这实际上并不是真的DRAM随机访问。最终发出的高效连续DRAM访问实际上是由许多单一的index计算出来的，如果这些index是真正的随机访问（无法进行合并），实际上的性能将取决于这些index的“离散度”。出现这样的结果是由DRAM的自身结构决定的，GPU并不能做更多，其他类型的处理器也不能。

对share memory的随机访问受限于bank冲突。一般来说，硬件上的同一个memory一次只能相应一个访问请求。因此share memory是由多个单独的bank memory组建而成的，NVIDIA GPU中设计的bank数量为16。例如x是一个存放在share memory中的vector变量(32bit)，它的第n个元素实际存放bank编号为：n/4。换句话讲，如果遍历访问一个数组，每间隔4Byte则切换一次bank。如果所有的访问地址都位于不同bank则可以获得峰值访问吞吐率（throughtput），因为硬件上的冲突检测逻辑只会增加latency，但如果真的发生了bank冲突将直接影响throughput。如果某一个bank同时被2个地址指向访问，那它的throughput降低为1/2；同时被3个地址指向访问则降低为1/3，最差的情况将降低为1/16。

理论上memory bank和地址之间存在多种不同的映射方式，每种都有相应的短处。例如在NVIDIA的映射方式上，对float类型数组的连续访问将获得最大throughput，但是对int8类型的数组连续访问却只能获得1/4的throughput(因为每隔4Byte切换一次bank)。

很多编程时的trick可以避免bank冲突。例如对于上述的int8类型数组访问，我们可以尽量高频的处理间隔为4的元素，例如分组访问a[i*4],a[i*4+1],a[i*4+2],a[i*4+3]，就比连续访问a[i]更高效。虽然代码更多，但是冲突更少。

2.3 单指令、多种运算逻辑路径

假设实现这样的功能：找出一个vector中所有的非零元素。我们可以写出代码如下，其中每个thread都将处理多个元素。

每个thread都处理len/nthread个元素，负责那些index从thread自身ID开始且每次跳跃nthread距离的元素。相比更自然的每个thread负责连续的元素，这样跳跃的方式使得同时run的thread访问连续的元素，更利于访问的合并。

比较有趣的是代码中的if(vec[i])，由于vec[i]的不同，一些thread将执行保存index的动作，另一些可能不会。这使得不同的thread的控制流是不同的。

2.3.1 单指令、多种运算逻辑路径的收益

为了支持在并行程序中执行一些运算路径不同的操作，尤其是并行的随机访问，SIMD提供了“条件执行（select）”的指令。例如select(flag,a,b)表示 if(flag) then a;else b。但是select不能用来抑制值的更新，因为在那些thread中vec[i]==0的位置不能给myind(last)写入任何值。

SIMD为了支持抑制值的更新提供了mask指令，元素更新时只更新mask值生效的部分。但是除非SIMD机器支持同时并行的随机访问，否则作用还是很有限（比如上面的find()的例子，mask指令需要多条指令循环才能起到一样的功能）。

2.3.2 单指令、多种运算逻辑路径的代价

1、就算只有一个thread在运行，其他没有运行的thread也必须等待。

最根本上SIMT的多个同时run的thread执行同一条指令，从而实现多个thread的资源共享。如果所有指令均run if分支，则所有thread均有同样的运算逻辑路径。但是如果这些同时run的thread部分执行if分支，另一部分执行else分支则需要先等待全部if分支执行结束，再等待全部的else分支执行结束，这样虽然逻辑分支可以正确执行，但是速度很慢。因此深度嵌套的控制结构将使得数据处理串行化，在GPU编程中是很不被推荐的。

2、不同的运算逻辑路径可能在随机访问memory时出现冲突

在上面的例子中，所有的thread都读取vec[i]，并且读取序列经过错位来避免bank冲突。然而在myind[last]被更新的时候，由于不同的thread更新last的次数不同（last值不同），这可能造成myind[last]的更新带来bank冲突，从而再次将导致处理串行化。原本由并行处理带来的的优势可能在不同运算方式以及不同输入数据的条件下不在存在。

在上文中讲述了SIMT和比它的更笨拙的“SIMD”之间的区别，接下来将比较SIMT和比它更为灵活的“SMT”。

3、SIMD vs SIMT

SIMT和SMT都是用thread作为提高throughput的手段，尽管存在高latency。它们解决了单thread在处理高latency指令时的处理停顿问题，在停顿期处理器很多执行单元都是空闲的（例如等待DRAM数据返回）。

解决上述问题的一种手段就是在处理器停顿期间将处理器切换到另一个thread，随后再切换回来。要使这个方法真的奏效的话，必须保证thread之间的切换是迅速的。目前最好的切换手段就是各个thread都有各自的register file但是却共享执行单元，从而保证无缝切换。

那是不是SIMT也是每个thread都有自己的register file呢？实际上确实如此，前面提到SIMT的重要特性之一是“单指令，多个寄存器组。下面我将GPU的register file看做一个二维register：

1、第一个维度称为“warp”，含义是同一个SM内同时run的thread组成一个warp，因为他们同时run，每个thread必然需要独占的register。

2、第二个维度称为“block”，含义是划分到同一个SM内的多组warp，在实际运行时SM 在这些warp中切换执行，所以每个warp也需要独占的register。

在这样的二维register file下，实际上需要多少寄存器呢？数量非常庞大，以一个可以同时运行512个thread、每个thread处理位宽为32bit的block为例，它对应的register file大小为64KB。

我们再对比一下SMT，一般的SMT机器有多少套寄存器组呢？通常是2套或4套。

为何如此之少？主要原因就是register set增多，收益逐减。每增加一组register都付出了对应的代价，希望增加的register能减少处理器的空闲，增加工作效率。但是随着thread的增加，处理器空闲的时间越来越少，导致收益抵不过代价。

如果CPU在SMT机制下停步在了2或4 thread，为什么GPU却在SIMT机制下将thread提高到了512呢？

3.1 GPU通过多thread来实现高throughput机制

对CPU而言，SMT机制对性能的提升是比较“鸡肋”的。因为CPU的设计原则就是希望处理器有更少的空闲时间，SMT又是希望去利用这些空闲时间来提升效率，形成了一种“相悖”的设计现象。在CPU的设计原则里，如何快速的run单thread才是第一要务，把一个程序拆解成多个独立的thread比较少见，就算进行拆解也拆得很粗糙。

以服务器的相关任务处理为例，在服务器中run的程序通常拥有很高并行性，但是依然十分看重单thread的latency。虽然低latency的core比高latency的core稍稍贵一些，但实际性能表现却优异许多。正如google的Urs Holzle发表的观点：

“brawny core beat wimpycore”强大的core击败了弱小的core，串行的代码也必须run得很快才行。

为了run一个单thread尽可能的快，意味着指令issue单元必须尽可能快的把当前thread中的指令发射出去执行。CPU围绕着这个目的提出了许多解决方案，比如有以下方式：

1、超标量执行

2、乱序执行

3、寄存器重命名

4、分支预测

5、预测执行

6、分层级cache

7、预测的预取

……

所有的上述技术都有着相同的原则，那就是尽可能提高当前run的thread中的指令被正确发射执行的概率，而不用切换thread。

SMT则是CPU的最后一道防线了，在上述技术都失效的情况下，尝试让处理器做一些事情。尽管如此，当切换了thread之后影响了之前的thread处理性能时仍然是不可接受的，参见Agner的 CPU日志。通常情况是这样的，如果两个thread中的任何一个都不需要与其他的thread分享硬件资源的话，它们的执行时间会更短一些。这就是CPU保持较少thread的原因，尽管提升thread后任然可以提高throughout。

在GPU中情况就完全不同了。GPU中处理的任务本身拥有足够高的数据并行度，从而可以把大量的thread利用起来。在这样的情况下，我们完全可以采用不同的方法进行设计，将优先考虑多thread来处理上述的处理器空闲问题。如果thread足够多，我们只需要在遇到处理器停顿时切换另一批thread即可，这样执行单元永远有任务可做。

这样节省了大量硬件资源和设计工作，因为不再需要像CPU设计那样考虑许多高级技术了。甚至都不需要考虑使用cache和硬件prefetch来解决GPU的访存拥塞问题，GPU直接访问外部DRAM。试想一下，如果在等待读数据返回的空隙中GPU可以切换另一组warp来执行，GPU并没有因等待数据而空闲，又有什么必要去用cache和硬件prefetch呢？只需要保证GPU一直在工作即可。

更细节一点，GPU对于哪怕最基本的算术操作也是按照“高latency、高throughput”来设计的。根据这篇文章“通过微基准来揭秘GPU的微架构”可以看出，GPU没有任何操作latency低于24个cycle，但是大部分操作都支持throughput为1个cycle（throughput和数据输入间隔cycle数成反比，cycle为1表示可以支持pipeline输入）。

因此总结一下，GPU利用处理的任务存在的天然多thread性质可以把GPU的throughput做到非常高，并且这些任务又不要求低latency。在此基础上可以有许多手段来降低硬件设计复杂度与成本。

3.2 latency很高的register很便宜

多thread有利于设计高throughput的硬件。那实际设计情况如何呢？以上述512 并行的thread为例，需要设计64KB的register，这是一个巨量的数字，为什么实际可行？

其实这取决于我们对register的定义。register最初的定义是一种拥有最小访问延迟的存储单元，在CPU中，对register的访问速度快于L1 cache，当然更加快于L2 cache。最小的访问延迟意味着最高的实现代价，这是CPU中register很少的原因。

但是在GPU中访问register可以很慢。上面已经提到过，GPU总是在warp之间进行切换，同一个warp中的前后两条指令之间间隔着很多cycle（因为必须要轮一遍SM中的全部warp才会执行同一个warp中的第二条指令），而CPU访问register必须很快的原因是“访问register的指令”的下一条指令就要用到register中的数据。当然GPU也是下一条指令需要用上一条“访问register的指令”返回的register中的数据，但是因为中间间隔着很多个cycle，足够隐藏掉register的访问时间。

因此，就指令编码而言GPU的register和CPU的register是类似的。在底层硬件看来，register就是一个临时变量存放空间，并且只需要只需要少数几 bit 编码就能引用其中的数据（例如32个register只需要5bit就能指定），这点和memory不同，因为引用一个memory中的数据往往需要更长的地址（一般32bit）。从这个角度讲，register和memory就是完全不同的东西。

但是，在硬件实现时GPU的register与CPU的register区别就很大了，GPU的register看起来更像memory（NVIDIA没有披露细节，此处只是猜测），64KB的片上RAM看起来是一个更为合理的规模（64KB 触发器太吓人了）。因此在CPU中register非常昂贵，但是高latency、高throughput的register就便宜很多了。

无论怎么说，如果512个thread都把相同的值存储在它们的register中总是一种浪费，例如之前的例子中的数组指针。但是这些thread的register中存放大部分数据还是不同的，在很多case中并没有造成多少浪费，并且退一万步讲，有哪个处理器保证存放的数据是完全独一无二的呢？可以在功能上把这些大量的GPU register看做一种data cache。

3.3 SIMT相比SMT的不足

上面我们已经看到：

1、巨量的thread使得高throughput、高latency的设计变为可能；

2、高throughput、高latency的设计可以通过廉价的register来实现；

这让我们得出了一个惊人的结论：SIMT中巨量的多thread设计成本可能比在传统的CPU中添加多thread容易很多。当然毫不意外，成本的节省来源于灵活性的降低，主要体现在三个方面：

1、SIMT在低占用率时性能将降低；

2、SIMT在thread之间运行方式不同时性能将降低；

3、SIMT的同步机制十分有限；

3.3.1 SIMT在低占用率时性能将降低

“占用率(occupancy)”是NVIDIA用来描述多thread利用率的名词。同一个SM中待run的thread越多，占用率就越高。占用率较低显然会降低处理性能，因为没有足够多的的warp来切换，GPU就无法隐藏单条指令处理的高latency。而足够多的thread直接来源于足够多的的并行处理任务。SMT则不受这方面的影响。

3.3.2 SIMT在thread之间运行方式不同时性能将降低

前面已经描述过不同thread运算逻辑不一致时GPU可以正确的处理，但是并不高效。SMT没有这个问题，它处理完全不相同的thread时仍然工作得很好。

这里有两个原因导致SIMT处理不好完全不同的thread：

1、SIMD式的指令广播机制，同一个warp中所有thread共享一条指令，如果执行路径不同不可能做到高效。

2、SIMT的thread数量远超于SMT，完全不相关的warp将对共享的资源造成竞争，例如指令cache空间。SMT同样有这个问题，只是thread较小还可以忍受。

因此SIMT的两个关键点：SIMD式的指令广播以及SMT式的巨量thread，都对thread之间的差异性十分排斥。而更为相关的thread之间更有利于共享指令以及部分数据，尽管thread之间存在一些差异性，在多thread处理时表现更好。但是如果无法利用广播的指令就会导致执行单元空闲。

然而在很多时候，相关的thread往往都有完全一样的数据流。再这样的情况下，如果某个机器拥有巨量thread但是没有指令的广播机制将错失许多提升处理性能的机会。

3.3.3 SIMT的同步机制十分有限；

就编程模型而言，SMT实际上是“单指令、时分CPU”的扩展。后者相当丰富的thread之间、设备之间的同步和通信机制同样在SMT上可用。这包括中断、信息队列、事件、阻塞和非阻塞系统调用等等。我们后续分析将基于下面的假设开展：

1、处理任务中存在很多thread；

2、通常，每个thread处理的任务都和其他thread不同；

3、在任何使用，大部分thread都需要能够响应突发事件；

SMT是在基本的时分CPU上扩展增加了多thread。因此SMT类似于传统的CPU，为了响应一个事件发生可以将运行的thread 暂停住。这可以通过上下文切换来实现--那就是把当前的register保存到memory中，如果一个可以执行的thread已经准备好，则又从memory中将register的数据load回来执行执行这个thread。

SIMT则不太可能把运行的thread暂停住，有以下原因：

1、通常，正在run的thread非常多，并且它们之间是相互关联的。必须要将它们同时停住才有意义，因为只有这样才能切换同样规模的thread来run。然而切换64KB规模的上下文是不太可能的。从这个角度来讲，“register”是非常昂贵的，哪怕这些register实际上是memory。

2、SIMT的性能很大程度上取决于有多少个正在run的thread，并没有理由去支持哪些有很多thread都处于等待状态的场景，因为SIMT无论如何都不会在这样的场景下工作得很好。从使用场景的角度来看，一般是“系统/控制”类型的软件会存在较多等待的thread，这些thread等待文件、socket等等。SIMT作为一种纯运算硬件并不支持这些OS相关的应用，对SIMT而言这些应用不仅奇怪、也不应该出现在SIMT的载荷里面。

3、一般地，SIMT支持数据级并行--相同的code，不同的data。数据级并行通常不需要复杂的同步，虽然所有的thread需要共同等待某一个操作步骤的完成，但是对于完成的先后就没有限制了。怎样的情况下会有复杂的同步机制呢？例如某些thread在run的时候另一些thread对这些正在run的thread有数据依赖，那有依赖的thread必须停住，这也就是任务级并行--code不同，data不同。然而，任务级并行就意味着thread之间运算逻辑的不同，SIMT本身也不擅长这个场景，所以不用为了复杂的同步机制苦恼。

因此，SIMT粗暴的提供了一种同步机制--syncthread()。这个函数为同一个block中的所有thread创建了一个同步指针。如果知道某一个thread已经run过了这个指针，其他的thread也一定run过了这个指针。这样thread之间就可以安全的share数据。比如矩阵乘的例子：

1、每个thread都根据它的ID-x,y来从DRAM中读取两个元素A(x,y)，B(x,y)到片内的share memory（当然不是把整个A、B矩阵搬到share memory上，这里是拆分成block处理）。

2、thread同步，使得所有的thread可以安全的访问A和B；

3、每个thread，根据它的ID，用A的y行乘上B的x列；