实时渲染管线:（二）CPU/GPU 体系结构简介[转]

作者：木头骨头石头
原文地址：https://zhuanlan.zhihu.com/p/440586327

书接上文：实时渲染管线:（一）基本概念与发展简史。介绍了实时渲染管线的发展简史，下面进入正题，简单介绍 CPU/GPU 的体系结构。实时渲染管线通常运行在 CPU/GPU 异构计算（Heterogeneous Compute）系统上。异构计算是由不同指令集架构（Instruction Set Architecture，ISA）的处理器组成的计算系统。笔者是一个游戏开发人员，没有硬件相关的开发经验，以下内容请谨慎阅读，参考资料如下：

有关于 GPU 架构、指令集、开发者文档，在各家硬件厂商的官方网站中都能查到：

几款典型的 GPU 架构白皮书：

1 CPU 与 GPU 的区别

中央处理器（Central Processing Unit，CPU） ：通常包含以下单元：

控制单元（Control Unit，CU）：是 CPU 中最复杂的一部分，负责整台计算机工作
执行单元（Execution Unit，EU）：是 CPU 执行指令的单元，执行单元可进一步细分为算数逻辑单元（Arithmetic Logic Unit，ALU）负责算数逻辑指令、浮点运算单元（Floating-point Unit，FPU）负责浮点数运算指令、加载存储单元（Load/Store Unit，LSU）负责内存存取指令、地址生成单元（Address Generation Unit，AGU）负责计算内存地址
寄存器（Register）：CPU 寄存器会根据用途分为不同类型寄存器。比如通用寄存器（General Purpose Register，GPR）和专用寄存器（Special Purpose Register，SPR）。通用寄存器可以用来存放指令执行过程中计算的结果；专用寄存器用于程序计数。更多寄存器分类详见：Processor register
内存管理单元（Memory Management Unit，MMU）：负责逻辑地址到内存物理地址的映射

CPU 和 GPU 都有多级存储器。不同时代，不同用途的电脑，多级存储结构是不一样的。

CPU 多级存储结构：

寄存器（Register）：在 CPU 核心内部，容量仅有数千字节，速度最快，时延仅 1 个时钟周期
L1 Cache：容量有 64 KB，时延 2-4 个时钟周期，使用造价高容量小的 SRAM
L2 Cache：容量有 256 KB，时延有10-20 个时钟周期，同样使用 SRAM
L3 Cache：容量有数 8-32MB，时延20-40 个时钟周期，同样使用 SRAM
内存（Memory）：容量有数 4-64 GB，时延 200-300 个时钟周期，在多核 CPU 中所有核心共享内存，内存通常使用 DRAM
外存（Storage）：容量 256 GB- 4 TB，属于外部设备，时延 100000-10000000 个时钟周期

上述结论来自：Approximate cost to access various caches and main memory? 通常，CPU 一个核心一个时钟周期可以执行一条指令

多核处理器（Multi-Core Processor）：在一个处理器上集成多个独立的处理单元（Processing Unit）也即核心（Core），每个核心有自己寄存器、控制器、执行单元。多核 CPU 每个核心对有自己私有的 L1/L2 Cache，所有核心共享 L3 Cache 和 Memory。

图形处理单元（Graphics Processing Unit，GPU）：可以看成是将单核 CPU“复制粘贴”数千份，同时简化控制单元，并搭载一些固定功能的电路单元，比如光栅器、纹理采样器、光线追踪单元……不同时代、不同厂商的 GPU 架构不一样，但自 2006 年统一着色架构提出以后，GPU 的基本结构也就定型了。

2006 年，D3D10 规范合并了顶点着色器与片元着色器，称为流处理器（Stream Processer，SP），NVIDIA 特称流处理器为 CUDA Core。一个流处理器相当于 CPU 的算数逻辑单元（ALU），流处理器可进一步分为整数运算单元（int unit）、浮点数运算单元（FP unit）。单个流处理器不能工作，需要将多个流处理器为一组执行指令。在运行时，一个流处理器就是一个线程。

多个流处理器、寄存器、指令调度器、L1 Cache、加载存储单元、纹理单元、特殊函数单元…… 为一组构成一个更大的处理器单元，NVIDIA 称为流多处理器（Stream Multiprocessor，SM），AMD 称为计算单元（Compute Unit，CU）

在 NVIDIA 的显卡中，若干个流多处理器、L2 Cache、光栅器、显存控制器……一起构成一个完整的 GPU。在 AMD 的显卡中，若干个计算单元、L2 Cache、显存控制器……一起构成一个完整的 GPU。下图是 NVIDIA TU102 核心的架构图，其中有 72 个 SM，每个 SM 又有 64 个 CUDA Cores，一共有 4608 个 CUDA Cores。

GPU 多级存储结构：

寄存器（Register）：GPU 有数千个流处理器会同时工作，因此需要数量庞大的寄存器。在 GPU 中，每个 SM 中有数千个寄存器，每个寄存器 32-bit，称为寄存器文件（Register File）。在 NVIDIA Fermi 架构 GPU 中，一个 SM 拥有 32768 个寄存器，寄存器文件大小 128 KB；在较新的 NVIDIA Turing 架构 GPU 中，一个 SM 拥有 16384*4 个寄存器，寄存器文件大小 256 KB。虽然 GPU 的寄存器数量远多于 CPU，但依然是非常珍贵的资源，GPU 寄存器读写时延同样只有 1 个时钟周期
L1 Cache：在一个 SM（或 CU）之中，供其中所有的流处理器共享，时延有 1-32 个时钟周期，容量 64-69 KB
L2 Cache：在 SM（或 CU）外，由多个 SM（或 CU）共享，时延有 32-64 个时钟周期，容量 2000-6000 KB
显存（Video memory）：对于 Dedicated GPU，其拥有专门为适应大数据吞吐设计的存储器 GDRAM 。对所有的 SM（或 CU）共享，时延有 400-600 个时钟周期，容量 2 GB – 20 GB

2 指令集

在指令集中会定义一台设备可以执行的所有指令，不同处理器的指令集不同，CPU 和 GPU 都有各自的指令集。一条指令对应处理器一种操作，人为的重排一系列指令，就是程序。

CPU 的指令集：按照指令集的复杂程度，可以把 CPU 指令集分成两类：

CISC 和 RISC 的区别这里就不介绍。其中，Intel 和 AMD CPU 使用的 x86 指令集架构是一类典型的 CISC ；在移动设备 CPU 上常用的 ARM 指令集架构属于 RISC。不管是 x86 还是 ARM，指令都是按流水线的方式执行，以提高 CPU 的使用率，在下面的章节中详细介绍。

指令流水线（Instruction Pipeline）：一条指令通常被分成若干个阶段交由处理器中不同单元执行，有分三步的，也有分六步的。按照 RISC-V 标准，指令流水线被划分成五个阶段：

指令获取（Instruction Fetch，IF）：控制单元从程序计数器（Program Counter）寄存器中取出即将执行的指令的地址。当指令获取后，PC 寄存器的值会指向下一条指令的地址。指令获取所需的时钟周期取决于指令所在的存储器，因此我们要保证尽可能保证局部性原理
指令解码（Instruction Decode，ID）：指令解码器将获取到的指令解码成成控制CPU其他部分的信号。
执行（Execute，EX）：指令进入执行单元，如 ALU、FPU、LSU、AGU 中执行
内存访问（Memory Access，MEM）：访问内存，读写数据
寄存器回写（Register Write Back，WB）：将执行结果或内存读取结果写入到通用寄存器（GPR）中

GPU 的指令集：与 CPU 的指令集不同，GPU 的架构每代变化很大，不同厂商的 GPU 架构也不同，ISA 很难做到统一。GPU 指令同样会划分出取指令、指令解码、执行……等流水线阶段，GPU 指令的执行也在后面的章节详细介绍

软件人员需要调用图形 API 才能控制 GPU 工作。图形程序可以使用高级着色语言（High Level Shading Language）比如：HLSL、GLSL，对渲染管线的可编程阶段编程，比如：顶点着色阶段、片元着色阶段。得益于同一着色架构，所有的可编程着色阶段都使用相同 ISA。这些着色语言会被先编译成中间语言（Intermediate Language），HLSL 编译成 DXIL（DirectX Intermediate Language），GLSL 编程成 SPIR（Standard Portable Intermediate Representation），然后驱动再将中间语言翻译成目标 GPU 的二进制指令。

对于 GPU 通用计算程序，非图形程序员也开始接触 GPU 编程，为了追求至极的性能优化，硬件厂商开始发布官方文档介绍旗下 GPU 的指令集。AMD 公开了近十年各代 GPU 的 ISA：Developer Guides, Manuals & ISA Documents ； NVIDIA 从未公布任何文档介绍旗下 GPU 的 ISA，取而代之提供了 CUDA 程序编译之后会得到的 PTX（Parallel Thread Execution）指令集代码。PTX 指令集抽象了各代 GPU 指令集的差异，是一种面向软件开发者的 GPU 抽象指令集，其地位类似于 CUDA 程序的汇编。PTX 指令需要驱动进一步编译，才能得到目标 GPU 的二进制指令。实际上，NVIDIA 官网还介绍了比 PTX 更底层的 CUDA 程序编译后的二进制码，只与目标 GPU 兼容。官方对其的介绍不多，参考：CUDA Binary Utilities 。

3 内存管理

存储器是计算系统最重要的资源，但存储器的空间并不是无限的，而且存储的读写速度也是有限的。现实是，存储器读写速度越快，单位容量的造价越高。为了平衡速度、容量、造价三者之间的关系，现代计算机都采用了多级存储结构（Memory Hierarchy）。高速存储器容量小，速度快，读写时延小，距离核心更近；低速存储器容量大，速度慢，读写时延大，距离核心更源。多级存储结构对计算机技术影响极大，高效的内存管理也关乎整个计算机的效率。

3.1 局部性原理

因为每级存储器读写的时延依次增大，为了提高计算机的效率，我们应将频繁使用或即将使用的指令或数据放在高速存储器中，如果能在缓存中取出即将使用的指令或数据称为缓存命中（Cache Hit），最好的情况是 CPU 每一次存储器访问都能 Cache Hit，但高速存储器的空间有限，不常使用的指令和数据应该放在低速存储器中。如果我们将即将要使用或频繁使用的数据缓存高速存储器，比如我们无法从缓存中拿到想要的数据，就称为缓存缺失（Cache Miss），需要访问内存，那么会极大影响计算效率。

随着软件规模的扩大以及允许多道程序同时运行，内存空间的限制越来越明显，操作系统都提供了虚拟内存技术，用外存拓展内存空间。如果即将使用的指令或数据不在内存中，会导致缺页中断，需要访问外存，这可能进一步影响计算效率

为了更好的利用计算机的多级存储结构，软件设计应该尽可能满足局部性（Locality）。

局部性（Locality） 是指处理器在短时间内重复访问存储器同一区间的趋势。因为处理器多级存储结构的存在，如果我们编写的程序能保证局部性，那么我们就可以放心的把数据或指令放在高速存储器中，提高读写效率。局部性进一步可分为两种：

时间局部性（Temporal Locality）：某一存储空间被访问后，在短时间内，处理器会再次访问它。因为在短时间内会重复访问同一地址，那么就可以把该数据放到高速存储器中，不用担心缓存不命中或缺页中断
空间局部性（Spatial Locality）：某一存储空间被访问后，在短时间内，处理器会访问它相邻的存储空间。因为各级存储器之间置换的数据地址都是连续的，在短时间内会重复访问某一连续区间的地址，那么就可以把该区间数据放到高速存储器中，不用担心缓存不命中或缺页中断

在《Computer Architecture：A Quantitative Approach》一书中介绍了十种提高缓存命中率的策略，有硬件层面的，有软件层面的。下面简单介绍两个最常见的策略：

循环交换（Loop Interchange）：在一些循环语句中可能会以非连续的方式访问存储器，比如下面的代码：

for(int j=0; j<100; j++)
{
    for(int i=0; i<5000; i++)
    {
        x[i][j] = 2 * x[i][j];
    }
}

因为 x[i][j] 与 x[i][j+1] 是连续存放的，x[i][j] 与 x[i+1][j] 是不连续存放的，所以上面的内存访问方式不满足空间局部性，容易造成 Cache Miss，因此编译器会交换循环嵌套方式，以提高缓存命中率：

for(int i=0; i<5000; i++)
{
    for(int j=0; j<100; j++)
    {
        x[i][j] = 2 * x[i][j];
    }
}

预取（Prefetching）：在处理器访问存储器之前，预测处理器需要的数据，提前将数据放到缓存中，提高缓存命中率，对指令和数据都可以预取。硬件预取机制的实现是依赖过去代码的执行特点，预测未来代码的行为。如果预取失败，可能需要将预取出来的指令和数据换出缓存，重新从内存中读取。因此，我们可以利用编译器或硬件的预取策略，优化代码，提高预取成功率。

数据预取：在循环代码中顺序访问数组元素是方便预取的，我们可以根据之前遍历的情况，提前将数组中的数据预取到缓存中：

for(int j=0; j<100; j++)
{
    a[j] = a[j + 1] + 5;
}

但如果是随机访问数组，那么预取机制将失效：

for(int j=0; j<100; j++)
{
    a[j] = b[rand()%100];
}

指令预取：指令通常是顺序执行的，因此很容易预取。但如果程序中出现跳转语句，那么指令预取将失效，这就是 goto 语句饱受诟病的原因。相比于 goto 语句， if … else … 同样会造成指令跳转，但比 goto 语句更好预测。比如下面的程序：

int a[10] = {1,2,3,4,5,6,7,8,9,10};
for(int i=0; i<10; i++)
{
    int p, q = 0;
    if(a[i] < 6) {
        p++;
    }
    else {
        q++;
    }
}

上面的循环中，if(a[i] < 6) 在前 5 次执行为 true，执行 p++ 指令；后 5 次执行为 false，执行 q++ 指令。根据这一特点，前五次执行时可预取 p++ 指令，放入缓存中；第六次预测失败，需要把 q++ 放入缓存。上面的代码保证了时间局部性，使分支预测成为可能。如果数组元素随机排列， if(a[i] < 6) 一会为 true，一会儿为 false，无法保证时间局部性，分支预测也会失败：

int a[10] = {2,1,6,7,5,3,9,10,4,8};
for(int i=0; i<10; i++)
{
    int p, q = 0;
    if(a[i] < 6) {
        p++;
    }
    else {
        q++;
    }
}

总的来说，不管是在 CPU 上运行的程序还是 GPU 上的程序，为了提高缓存命中率，软件编写都应该保证局部性

3.2 异构计算系统内存管理

CPU/GPU 异构计算的内存管理涉及：CPU 的缓存策略，内存地址管理，存储空间的申请与释放，内存-显存之间的数据拷贝……内存管理需要有一个置换策略，当高速存储空间不足时，把数据换入低速存储器，同时尽量避免即将要使用的数据或指令被换出高速存储器，引起缓存缺失或缺页中断。

置换算法（Replacement Algorithm）：常见的置换算法有以下三种：

最佳置换算法：选择被换出的数据是未来永不使用，或者是最长时间不再被访问的。但我们并不知道未来的情况是怎么样的，最佳置换算法无法实现，常用作检验其他置换算法的标志。
先进先出置换算法（First in first out，FIFO）：优先换出最早进入高速存储器的数据，该算法实现简单，但数据换入高速存储器的时间和访问的频率并不相关，可能会换出未来常使用的数据
最近最久未使用置换算法（Least recently used，LRU）：选择换出最近最长时间未访问的数据，因为该算法假设近期不常访问的数据在未来也不会经常访问。LRU 算法的性能最好，但实现复杂，需要额外的硬件支持

3.2.1 CPU 缓存管理

缓存行：数据从内存拷贝到缓存时，是以固定大小连续地址的内存块拷贝，通常是 64 Bytes，称为缓存行（Cache Line）或称缓存块（Cache Block）。缓存行中会包含数据本身和一些其他数据。当处理器需要读写内存时，会检测是否有 Cache Line 映射到这一数据。如果有，则缓存命中（Cache Hit），CPU 直接读写缓存；否则缓存缺失（Cache Miss），需要创建一个新的 Cache Line，并把数据拷贝到其中。

缓存行与内存地址的映射：内存空间远远大于缓存空间，因此内存地址与缓存行肯定不是一一映射的关系，为了建立缓存行中地址与内存地址的关联。有如下三种策略：

直接映射（Direct Mapping）
N 路组相连（N-Way Set Associativity）
全相连（Fully Associativity）

直接映射（Direct Mapping）：多对一映射，多个内存块对应同一个 Cache Line。

假设内存空间以 64 Bytes 连续地址划分出若干内存块，划分出 32 块。内存的最小单元是字节，一个内存块有 64 个连续内存地址，总共 64 * 32 = 2048 Bytes = 2 KB。缓存中可以存放 8 个 Cache Line，那么 4 个内存块会映射到同一个 Cache Line。这种映射关系可以用取模确定，也即：

其中， I是 Cache Line 索引， A是内存块索引， N是 Cache Line 数量。那么，0、8、16、32 这四个内存块会映射到 0 号 Cache Line 中，如上图左一。因此一个 Cache Line 不仅包含数据本身，还需要有一个 Tag 标记该 Cache Line 对应哪一个内存块。

直接映射实现简单，但当有新的内存块需要换入缓存时，相应 Cache Line 中的数据就要被换出，置换缺乏灵活性，因为缓存的 Cache Line 可能是未来会使用或者经常使用的，会降低缓存命中率。因此在直接映射的基础上，提出 N 路组相连模式。

N 路组相连（N-Way Set Associativity）：多个 Cache Line 组成一个组（Set），如果一个 Set 中有两个 Cache Line，就称为 2 路组相连；如果有四个 Cache Line，就称为 4 路组相连。多个内存块映射到同一个缓存组中任意一个 Cache Line 中。内存块与 Cache Line 是多对多映射，但内存块与 Cache Set 是多对一映射。内存块与 Cache Set 的映射关系可以用取模得到。

以 2 路组相连为例，0、8、16、32 这四个内存块会映射到 0 号 Cache Set 中，并任选一个 Cache Line 存放，如上图左 2。那么当一个内存块映射到一个 Cache Set 时，可以选择最近最久最少使用的 Cache Line 换出，可以有效的提高缓存命中率。缺点是，N 路组相连模式增加了电路设计的复杂性，而且当 CPU 读写缓存时，需要遍历一个 Cache Set 才能判断缓存是否命中。

直接映射也可以看成 1 路组相连

全相连（Fully Associativity）：全相连可以是 N 路组相连的极端情况，只有一个 Cache Set，一个 Cache Set 包含所有的 Cache Line，也即一个内存块可以映射到任意一个 Cache Line 中，如上图右 1。那么 CPU 读写缓存时，需要遍历整个缓存才能确定缓存是否命中，适合缓存比较小的计算机使用。

写入策略：因为一份数据在缓存和内存中都一个副本，所以需要有一个策略保证该数据在所有存储器中的一致性。内存写入通常有两种策略：

写直达（Write Through）：如果数据在缓存中，将数据同时写入内存和缓存；如果数据不在缓存中，将数据直接写入内存
写回（Write Back）：如果数据在缓存中，将数据写入缓存，并将该 Cache Line 标记为脏（dirty），当该 Cache Line 被替换时，才把数据写入内存。如果数据不在缓存中，还是将数据写入缓存，先检查目标 Cache Line 是否为脏，如果是，则该 Cache Line 存有别的内存地址需要写入的数据，把该数据写回到内存，然后替换 Cache Line；如果 Cache Line 不为脏，则直接替换并写入

写直达实现简单，但不管数据是否在缓存中，都需要写入内存，影响效率；写回实现复杂，在有必要时才将数据写入内存，效率更高，因此大多数 CPU 都采用回写策略。

缓存一致性（Cache Coherency）：在多核 CPU 下，内存供多个核心共享。同时，每个核心独占 L1/L2 缓存，因此同一数据在不同核心的 Cache 中都有一个副本。为了保证缓存一致性，某一 CPU 核心会在写入操作时，通知其他 CPU 核心更新缓存。另外引入锁，写入操作串行化。随着处理器中核数量的增多，保证缓存一致性的开销越来越大，这也是 CPU 核心不能无限扩展的重要原因。

3.2.2 CPU 内存管理

内存管理是操作系统最重要的任务之一，总结起来，分以下四个方面：

内存空间的分配与回收：内存分配与回收是操作系统的任务，现代操作系统通常采用非连续分配，它允许将一个进程分配到不连续的内存区域执行。
地址变换：在编写程序时，开发者只关心程序的逻辑地址，需要根据实际情况，将逻辑地址变换到内存的物理地址，不同的内存分配策略会有不同的地址变换方式
内存保护：操作系统允许多道程序同时运行，内存分配和地址变换策略既要避免用户进程相互影响，也要避免用户进程影响操作系统的地址空间
虚拟内存：因为内存资源是有限的，不能将所有进程全部放入内存执行，操作系统在保证局部性原理的前提下，利用磁盘资源扩展内存空间

为了减轻开发者负担，也避免程序在运行时影响到其他进程的地址空间或者操作系统的地址空间，开发者不需要与物理内存打交道，开发者分配和回收的都是逻辑内存空间，逻辑内存空间的地址就是逻辑地址（或称虚拟地址）。CPU 的 MMU 会把逻辑地址映射到物理地址。

传统的内存分配方式是连续分配，具体有两种策略：

固定分区分配：为了支持多道程序同时执行不会相互影响，将物理内存区域划分成一些不同大小的分区，一种大小的分区有若干个。一道程序，程序需要全部放入一个分区中才能进行。程序可能用不完一个分区全部的空间，因此会有空间浪费，这种浪费称为内部碎片。
动态分区分配：固定分区分配实现简单，但非常不灵活。动态分区分配不预先设置每个分区的大小，而是在程序装入是动态决定。随着内存的分配和回收，分区与分区之间会产生空隙，称为外部碎片，如下图：

连续分配策略要求进程放到连续的物理空间中，并且要求空间能完全容纳下程序所需的空间，当没有足够的连续空间时，程序只有等待。不管是固定分区还是动态分区，内存的利用率都非常低。因此提出非连续内存空间分配策略，只要有足够的物理空间就尽可能为进程分配，不需要物理地址一定连续。

非连续内存分配允许将一个进程分散装入到不相邻的内存分区中，根据分区大小是否固定也可分为两种：一、基本分页式；二、基本分段式。

基本分页式（分区大小固定）：把物理内存划分成等大的小分区，称为页框，或页帧（Page Frame）；把进程的逻辑空间也为一些小块称为页（Page）。在程序运行时，将一页装入一个页框中，并且用一个额外的内存空间记录页与页框的对应关系，称为页表（Page Table）。分页式内存管理除了最后一个页框会产生内部碎片外，其他的页框都是装满的。每个页框的大小应该是 2 的整数次幂，不易过大或过小。过大的页框会使外部碎片增加；过小的页框会使页表过大。

基本分页式地址变换：基本分页式的逻辑地址包含两个信息：一、页号（该地址属于哪一页）；二、页内偏移（该地址在页内的排第几）

页表包含两个信息，页表在内存中连续存放：一、页号（该页在逻辑空间中的编号）；二、块号（该页在物理空间中映射到哪一个页框）

另外还需要一个页表寄存器，其中包含两个信息：一、存放页表在内存的起始地址；二、页表的长度

那么变换的过程可以叙述为：通过逻辑地址的页号加上页表寄存器中的页表起始地址（如果页号大于页表长度，会发生缺页中断），算出页表中该页的物理地址，取出物理块号 B，假设每页大小为 L，页内偏移为 S，那么物理地址为：B * L + S。如下图所示：

基本分页式地址变换，需要两次内存访问，才能从内存中取出数据。因此为了提高转换速度，可以把最近使用的页表项放到 MMU 的转译后背缓存（Translation Lookaside Buffer，TLB）中，这是一个高速缓存，可以加快转换速度。

基本分段式（分区大小不固定）：把进程的逻辑空间拆分出不同段（Segment），比如汇编程序分为代码段、数据段、栈段三部分；C++ 称为代码段、数据段、BSS、栈、堆五部分…… 在装入时，为每个段分配连续的空间，但段与段之间不需要连续。用一个额外的内存空间记录段到物理地址的对象关系，称为段表（Segment Table）。分段式内存管理会产生外部碎片，但相比连续分配的动态分区分配，内存利用率还是要高很多。

基本分段式地址转换：基本分段式的逻辑地址包含两个信息：一、段号（该地址属于哪一段）；二、段内偏移（该地址在段内的排第几）

段表包含三个信息，段表在内存中连续存放：一、段号；二、段长；三、基址（段对应的内存物理起始地址）

另外还需要一个段表寄存器，其中包含两个信息：一、存放段表在内存的起始地址；二、段表的长度

那么变换的过程可以叙述为：通过逻辑地址的段号加上段表寄存器中的段表起始地址（如果段号大于段表长度，会发生越界中断），算出段表中该段的物理地址，取出该段对应的内存物理起始地址 B，段内偏移为 W，那么物理地址为：B + W。如下图所示：

基本段页式：基本分页式能极大提高内存的利用率，但进程的分页对开发者是一个黑盒；基本分段式由开发者决定进程的拆分，并且方便管理在多个作业之间共享的数据，但内存利用率相对较低。因此综合两种管理方式，现代操作系统通常采用段页式。段页式管理首先将进程的逻辑空间拆分成不同的段，然后再将每个段分成固定大小的页。在运行时，将段页放进固定大小的内存页框中。然后一个进程有一个段页表，每个段有一个页表，段页表和页表共同构建起逻辑地址到物理地址的对应关系。

基本段页式地址变换：基本段页式逻辑地址包含三个信息：段号：该地址属于哪个段；页号：该地址属于段中哪一页；页内偏移量：该地址在页内排第几

段页式的段页表包含三个信息：一、段号；二、页表长度（该段中有分有几个页）；三、页表起始地址（该段页的页表在内存中的起始地址）

段中的页的页表包含两个信息：一、页号；二、块号

段页式需要一个段页表寄存器：一、段页表起始地址；二、段页表长度

那么变换的过程如下图所示：

段页式地址变换需要三次存储访问才能取到数据，因此访问的效率要低于基本分页式和基本分段式。

虚拟内存（Virtual Memory）：内存的物理空间非常有限，现代操作系统都实现了虚拟内存技术，使用磁盘空间扩充内存的物理空间。虚拟内存建立在非连续内存分配策略的基础上，不同的内存分配策略有不同的虚拟内存实现方式。在基本分页式的基础上有请求分页式，在基本分段式的基础上有请求分段式，在基本段页式的基础上有请求段页式。

请求分页式：在分页式内存分配策略上，只需将进程的一部分页装入内存便可执行。当所要访问的页不在内存时，触发中断机制，将缺页装入内存；同时，还可以将暂时不用的页换出到外存上。请求分页式的页表需要增加一些信息：一、状态位（标识该页是否在内存中）；二、访问字段（用以记录该页多长时间未被访问）；三、修改位（该页在调入内存后是否被修改）；四、外存地址（页的外存地址；）

请求分页式地址转换：请求分页式和请求分段式的页表和段表都变得更加复杂，因此地址变换也更加复杂，下图以请求分页式为例，刻画了地址变换的流程：

触发缺页中断时进程将被阻塞，等待页面调入内存，这一过程非常缓慢，严重会导致应用卡顿。因此虚拟内存的管理也要有置换策略，通常使用 LRU 算法，将最近最久最少使用的页面换出内存。

请求分段式：在分段式内存分配策略上，只需将进程的一部分段装入内存便可执行。当所要访问的段不在内存时，触发中断机制，将缺段装入内存；同时，还可以将暂时不用的段换出到外存上。请求分段式的段表需要增加一些信息：一、状态位（标识该页是否在内存中）；二、访问字段（用以记录该段多长时间未被访问）；三、修改位（该段在调入内存后是否被修改）；四、外存地址（段的外存地址）

请求段页式：略

3.2.3 GPU 内存管理与 CUDA 内存模型

对于运行在 CPU 上的软件，现代计算机系统在硬件和操作系统层面做很多工作。比如保证共享数据的一致性、内存地址管理、内存的分配与回收、预取机制、置换机制……因此软件开发者只需关注程序逻辑的实现，不需要关注存储器的使用。

对于运行在 GPU 上的软件稍微麻烦一点。GPU 的核心数多，对于共享数据，同步成本高，因此运行在 GPU 上的程序线程之间应该尽可能独立，少同步。GPU 没有提供复杂的置换机制，需要开发者自己指定数据存放到哪一级存储器上，因此 GPU 内存管理更多是软件开发者的任务。CUDA 提供了一个内存模型简化开发者内存管理的难度，如下图：

线程组与线程：在 CUDA 程序一开始，需要给任务分配线程组和线程，一个线程组有若干线程，一个线程对应一个流处理器。

寄存器（Register）是在 SM 中，每个流处理器私有若干个寄存器。寄存器最主要的作用是用来暂存该流处理器线程执行指令过程中产生的局部变量。每个寄存器大小 32 bit，在早期的 GPU 中，一个流处理器最多可以独占 60 多个寄存器，存放 60 个单精度浮点数；如果是较新的 GPU，一个流处理器可以独占 200 多个寄存器，存放 200 个单精度浮点数。

这些寄存器除了用来暂存局部变量外，还用于线程切换，寄存器可以保持当前线程的上下文，然后切换到当另一作业执行。GPU 使用寄存器保存上线问，因此线程切换的代价很小，只用一个时钟周期即可完成上下文切换。GPU 这一特性常用到隐藏显存读写的时延，这在后面详细介绍。

流处理器私有的寄存器数据不会主动写入到 Cache 或显存中，除非该线程在执行过程中申请了超过 200 个局部变量。寄存器中的局部变量在该线程指令执行完之后释放，如果希望存储该线程执行的结果，需要把数据写入到全局内存区或共享内存区中。

局部内存（Local Memory）：每个流处理器有自己私有的局部内存，该局部内存是分配在显存上的，用来储存寄存器存不下的局部变量。从显存中读写数据自然会影响执行效率，因此我们需要控制每个线程需要的申请的局部变量的数量。局部内存中的数据在该线程指令执行完之后释放。

共享内存（Shared Memory）：线程组私有，分配在 SM 中的 L1 Cache 上，组中所有线程共享。共享内存同样是非常珍贵的资源，在 NVIDIA Fermi 架构 GPU 中，32 个 CUDA Cores 共享 64 KB Shared Memory/L1 Cache；在 NVIDIA Turing 架构 GPU 中，64 个 CUDA Cores 共享 96 KB Shared Memory/L1 Cache。共享内存中的数据在该线程组的所有的指令执行完之后释放。

在 NVIDIA GPU 中，共享内存会被分成多个 Bank，可供多个流处理器同时访问，Bank 数量通常和流处理器数量相同。如果每个流处理器与其访问的 Bank 一一对应，那么不需要同步。如果多个流处理器访问同一个 Bank 会导致 Bank Conflicts。下图中从左到右，1、3、4 没有 Bank Conflicts；2、5、6 有 Bank Conflicts。如果发生 Bank Conflict，需要给共享内存数据设置屏障，访问将会串行化。当所有线程的访问结束后，整个线程组的指令才会继续执行。发生 Bank Conflicts 之后，必然会影响性能，应该尽可能避免。

常量/纹理内存（Constant/Texture Memory）是分配在显存上的，流处理器只读的存储区，不需要同步，所有线程共享。CPU 通过 PCI-E 总线将数据写入常量\纹理内存，但因为 CPU 和 GPU 是异步执行的，所以 CPU 写入常量\纹理内存时需要跟 GPU 同步。另外，如果宿主程序是多线程的，那么这些 CPU 线程之间也需要同步。在保证局部性原理的情况下，可以将常量/纹理数据换入缓存中，加速读取速度。比如，纹理在图形渲染中通常是一张图片，这张图片由 Host 端发送到显存中。图形程序通常需要并行采样这张纹理，为了保证局部性原理，一个线程组（SM 或 CU）最好只采样纹理的连续区域，称为一个 tile，那么我们就可以把这个 tile 放到 L1 Cache 中，加速采样过程。如果使用 mipmap 技术，我们可以不需要原始分辨率的纹理，某一 mip 层级纹理的 tile 肯定小于原图的 tile，这样可以进步节约缓存空间。

常量内存和纹理内存的区别：常量内存中的数据是线性连续存放的，纹理内存中的数据是分块（tile）存放的。对于顺序访问的数据，建议放在常量内存中，比如顶点缓存、索引缓存，能提高缓存命中率；对于分块访问的数据，建议放在纹理内存中，比如纹理，能提高缓存命中率。

全局内存（Global Memory）：CPU/GPU 都可以读写的区域，分配在显存上，供所有线程共享。通常，可以把 Shared Memory 的数据或者寄存器中的数据写回到全局内存中，释放高速缓存区的存储空间，这一过程时延很长，通常是把计算结果写入到全局内存中。CPU 读写全局内存区也是通过 PCI-E 总线，比如把 GPU 计算的结果回读到内存中，这一过程非常缓慢。和共享内存一样，全局内存访问冲突时，需要给数据设置屏障，使访问串行化，当所有线程的访问结束后，整个线程组的指令才会继续执行。发生冲突之后，必然会影响性能，应该尽可能避免。

常量/纹理内存与全局内存中的数据在主机发送销毁指令后或程序执行完后释放。

3.2.4 CPU/GPU 的通信

GPU 在开始工作前，需要把指令和数据放到制定的存储区，GPU 才能开始工作。这涉及 CPU/GPU 的通信，CPU/GPU 有不同的存储架构，通信方式也有所不同，CPU/GPU 异构计算系统有如下两种常见的存储架构：

左图为独立显卡（Discrete GPU 或 Dedicated GPU），Dedicated GPU 属于外部设备，通过总线（如 PCIe ）与 CPU 相连。Dedicated GPU 有专用的显存（Video Memory），CPU 与 Dedicated GPU 的存储架构属于非统一内存访问（Non-uniform memory access，NUMA）架构，也即不同计算核心有独立的存储器。

右图为集成显卡（Integrated GPU），Integrated GPU 与 CPU 集成到同一张芯片，GPU 没有独立的显存，需要与 CPU 共享内存空间，属于统一内存访问（Uniform Memory Access，UMA）架构。

对于 Dedicated GPU，其不能直接读写内存，需要在工作之前，把数据从内存中经总线放到显存中。在 CUDA 程序中，GPU 显存地址访问经历了三个不同的时期：

分离式内存管理：需要区分 CPU 内存地址、GPU 显存地址、GPU 寄存器地址。如果我们需要传输大量数据到 GPU 中，通常考虑将数据拷贝到显存中，称为 Memory Copy，这由一个拷贝函数负责；如果只需要更新某一个变量，通常考虑将数据拷贝到寄存器中，称为 Zero Copy，这由另一个拷贝函数负责；CPU 可以从显存和寄存器中回读数据，这又由两个拷贝函数负责
统一虚拟地址（Unified Virtual Address，UVA）：CUDA 4.0 后为了简化数据拷贝，将内存地址、GPU 显存地址、GPU 寄存器地址统一成一套虚拟地址，在拷贝时 CUDA Runtime 会判断源和数据的地址，从而将拷贝函数也变成了一个，简化拷贝操作
统一内存（Unified Memory）：CUDA 6.0 之后开始支持，这里的 UM 不是 Integrated GPU 的 UMA 架构，GPU 显存依然是独立，而是将内存地址、GPU 显存地址、GPU 寄存器地址统一成一套虚拟地址。UM 与 UMA 的区别于实现了数据的按需迁移，在过去 CPU 不能一次开辟超过显存容量的空间，一个大数据只能分多次迁移或者将数据从显存中置换出来。而 UM 提供了类似操作系统虚拟内存的机制，当 GPU 发生“缺页”时，自动将数据经 PCIe 迁移到 GPU 显存中

工业界似乎很少讨论 Dedicated GPU 绕过 CPU 直接读写内存（Direct Memory Access，DMA）的技术，因为这种技术对 Dedicated GPU 意义不大，首先是 Dedicated GPU 有独立的显存，不需要内存扩充其地址空间，即使显存空间不够，那内存扩充其地址空间读写时延过大；第二是 GPU 的设计是希望其能尽可能脱离 CPU 独立运行，因此没有访问内存的必要。当然，如果数据发送到显存，需要从外存中读入内存，再从内存经总线发送到显存。两次 I/O 无疑是非常慢。NVIDIA 认识这一问题，为 CUDA 开发者提供了 NVIDIA GPUDirect 技术，它可以使 GPU 绕过 CPU 直接从外存中读取数据。GPUDirect 技术还支持其他外部设备（如网卡或另一个 GPU）绕过 CPU 直接从显存中读取数据。

UVA 和 UM 的出现是为了简化 CUDA 程序编写的难度，而在 PCIe 中，有一项标准称为内存映射 I/O（Memory Mapped I/O，MMIO）。它能将设备内存和主机物理内存映射到同一个逻辑地址空间。从 CPU 角度，当访问一个地址时，可能映射到主机物理内存地址，也可能映射到设备内存地址或设备寄存器地址。有了 MMIO 技术，CPU 就可以用访问主机内存的指令访问设备内存。在软件开发者眼中，内存地址和设备内存地址都是指针。

MMIO 或许是 UVA 或者 UM 实现的基础，但我在官方文档没有找到相关解释，对 PCIe 标准也不了解，需要进一步求证

对于 Integrated GPU，CPU 与 GPU 通信不需要经过外部总线，只需要将地址重新映射就可以了，这种技术称为 GART（Graphics address remapping table），GPU 可以直接绕过 CPU 直接访问内存。笔者对于 Integrated GPU 了解不多，日后有机会再作补充。

3.3 内存对齐

内存对齐不是内存管理的任务，是编译器和软件编写人员的任务，内存对齐在程序开发中非常重要，所以还是简单提一下。

CPU 和 GPU 在内存访问时都要求数据是内存对齐（Memory Alignment）的。以 CPU 为例，一次内存（或缓存）访问，可以并行读写 2 的整数次幂个字节的数据，称为存取粒度。比如 32 位的 CPU 一次可以读写 4 Bytes 数据、64 位 CPU 可一次读写 8 Bytes 数据、16 位 CPU 一次可读写 2 Bytes 数据。这 2 的整数次幂个字节的数据为一组，就将内存划分成一个一个的格子。在 32 位机上，一个 int 数据占 4 个字节，如果刚好放到一个内存“格子”中，那么 CPU 只需要一次内存访问就可以读出这个 int 数据，这就是内存对齐。如果内存不对齐，一个 int 跨越了两个“格子”，那么 CPU 就需要两次内存访问，还要遮掩掉无效的位，并把有效的位拼接起来才能得到一个 int 数据，如下图：

因此连续存放的数据结构，其成员需要考虑内存对齐，并且其首地址也要内存对齐，比如在 32 位机上的如下的 C++ 代码：

struct A{
    int b;
    char a;
    char c;
};

struct B{
    char a;
    int b;
    char c;
};

sizeof(A); // 占 8 字节
sizeof(B); // 占 12 字节

结构体可以看成是可以放置不同类型数据的数组，那么为了使内存对齐，成员变量之间就会出现“空隙”，而且不仅成员变量之间需要对齐，结构体对象的首地址也需要对齐。内存对齐是编译器自动完成的，但我们理解了对齐规则后，合理的安排结构体中成员的布局，可以减少成员与成员之间的内存空隙。32 位 CPU 是按照 4 字节对齐，那么上面 Struct A 和 Struct B 的内存布局如下：

对于 GPU 来说，也需要数据存放是对齐的，GPU 中每个线程的内存访问也有存取粒度，通常是 16 字节。显存中对齐的数据在访问时还能获得优化——访问合并。

GPU 访问合并：GPU 为了优化全局内存的访问，如果多个线程的内存访问是连续对齐的话，这些线程的访问请求会合并成一个请求，然后一次返回所有数据。

4 并行计算处理器

在渲染算法中，我们需要处理大量相似的任务，任务之间相互独立（每个像素的渲染没有关联性），适合并行计算。并行计算（Parallel computing）是计算科学的一大分支，并行的核心在于任务（Task）的同时执行。任务是一个比较宽泛的概念，它可以是处理器需要执行的指令、可以是处理器需要处理的数据、还可以是多道指令组成的函数（或者说线程 Thread）。

与并行非常接近的概念是并发（Concurrency），并发是指一段时间内同时处理多道任务，任务也可以分时间片执行。并行强调在一个时钟周期，同时执行多道任务。一个并发但不并行的例子是在单核 CPU 上，多道函数分时间片执行，这需要引入上下文切换机制

并行计算表面的原因是为了加速任务的完成，更深层次的原因是避免处理器闲置，增大处理器的吞吐量。为了设计高性能并行处理器，计算机科学家弗林提出了一种分类标准称为：弗林分类法（Flynn’s Taxonomy）。他根据指令流（Instruction Stream）和数据流（Data Stream）两个维度区分不同的处理器：

SISD（单指令流、单数据流处理器）：在任何一个时钟周期，只有一条指令流被处理单元执行，一条数据流被处理单元处理。在这种处理器中，通常只有一个执行单元（Processing Unit，PU），属于串行处理器。

SIMD（单指令流、多数据流）：在任何一个时钟周期，所有执行单元执行同一条指令，但每个执行单元输入的数据可以不同。在这种处理器适用于向量和矩阵运算，比如 GPU 就是一种 SIMD 处理器，属于并行处理器。

MISD（多指令流、单数据流）：在同一个时钟周期，不同处理器单元执行不同的指令，但输入处理器单元的数据是相同。这种并行处理器并不常见。

MIMD（多指令流、多数据流）：在一个时钟周期，每个处理单元执行不同的指令流，处理不同的数据流。指令之间可以同步或异步执行，在如今的超级计算、分布式系统、个人电脑多核 CPU 都是基于 MIMD

4.1 指令级并行

次标量处理器：一个单核 CPU 指令执行最简单的方式为，CPU 一个时钟周期只能执行一条指令的一个阶段，假设每个指令的每个阶段需要一个时钟周期，那么执行三条指令需要十五个时钟周期。

这种 CPU 平均一个时钟周期最多只有一条指令在执行（IPC < 1，Instructions Per Machine Circle），称为次标量处理器（Subscalar Processor）。其处理器资源利用率很低，假设某一指令的一个阶段消耗多于一个时钟周期，那么后面的阶段只有等待。

标量处理器：为了提高 CPU 资源利用率，一种最常见的方式是让 CPU 在一个时钟周期能执行多条指令的某一个阶段：

这种 CPU 平均一个时钟周期有一条指令在执行（IPC = 1），属于一种标量处理器（Scalar Processor）。这是一种最简单的指令级并行（Instruction-Level Parallelism，ILP）手段。指令流水线效率取决于程序指令的可并行性，当某一条指令依赖之前指令的执行结果时，将不能以流水线方式执行，还是会按照第一种方式执行，这种情况称为障碍（Hazard）。

超标量处理器：更进一步，在一个单核 CPU 中搭载多个执行单元（Execution Unit），比如多个 ALU、FPU、LSU 等。那么一个时钟周期可以将多条指令的一个阶段分发到不同功能单元上执行：

这处理器平均一个时钟周期有多条指令在执行（IPC > 1），属于一种超标量处理器（Superscaler Processor）。超标量处理器指令并行程度同样取决于程序指令的独立性。现代所有的通用 CPU 几乎都是超标量的。Superscaler Processor 同样要避免 Hazard。

并行障碍：因为指令之间的依赖性，后续指令需要等待前一指令结果的返回，这时需要改进硬件，处理障碍。下面介绍三种策略：1. 管线气泡；2. 操作数前移；3. 乱序执行

管线气泡（Pipeline Bubble）：管线气泡是最简单的解决方案。在一条指令在解码阶段被识别需要依赖前面指令执行的结果时，会创建一个管线气泡占据解码阶段，使当前管线的解码阶段处于空闲等待状态，管线气泡对导致后续指令被延迟。如下图，紫色指令依赖于绿色指令将执行结果写会寄存器，在其解码阶段会创建一个指令气泡，在第 5 个时钟周期，绿色指令的结果写回寄存器，紫色指令从寄存器读取绿色指令执行的结果，进入执行单元执行，在第 6 个时钟周期，管线气泡被挤出指令管线。

操作数前移：当发生并行障碍时，后一条指令依赖前一条指令将执行结果回写到寄存器，再从寄存器读取结果才能执行。如果前一条指令在执行后需要内存访问，再写回寄存器，那么后续指令等待的时钟周期将不止一个。如果前一条指令能直接将执行结果直接传递给后一条指令，不经过寄存器，将大大减少等待的时间。操作数迁移技术需要改进硬件，使解码器能探测这种依赖性，并增加一条电路直接获取前一条指令的值。

乱序执行：乱序执行允许指令执行的顺序与程序编写时的顺序不一样，但执行结果依然正确。指令乱序执行的前提是，该指令所需的数据已经计算出来，而且它不依赖前一条（或多条）指令的结果，那么它可以先于前一条（或多条）指令执行。那么乱序执行的步骤为：

获取指令
将指令分配到一个指令队列
指令在指令队列中等待，直到其输入操作数可用，此时它可以早于自己前面指令被执行
执行指令
将指令输出结果保存在一个队列中
只有当一个指令之前所有指令被执行完毕并将结果写回寄存器后，才将该指令的结果写回寄存器，以保证执行结果的顺序一致性

超长指令字：不管是 Scalar Processor 还是 Superscalar Processor，都是通过增加硬件的复杂度，决定哪些指令能在一个时钟周期并行执行。另一种不增加硬件复杂度的前提下，依然能使多条指令在一个时钟周期同时执行的架构称为超长指令字（Very Long Instruction Word，VLIW）。VLIW 是不同于 CISC 和 RISC 的第三种指令集架构，它将多个相互无依赖的指令由编译器打包成一条超长指令，交由 CPU 核心中对应数量的执行单元并行执行，指令级并行的发现和指令执行顺序的调度完全由编译器完成，处理器只负责指令的执行。AMD TeraScale 架构 GPU 的流处理器就是 VLIW 架构，一个 TeraScale 流处理有 5 个 ALU：

4.2 数据级并行

Scalar Processor 和 SuperScalar Processor 都是 SISD，也即单指令、单数据，适合标量运算。在数学领域，除了标量运算，还有向量运算。如果用 SISD 处理器执行一个四维向量的加法，它需要八个内存访问指令取出数据，四条加法指令，四条寄存器写回指令。

向量运算天然适合并行执行，四个分量的互相独立，SuperScalar Processor 因为有多个执行单元，四条加法指令可以在一个指令周期并行完成，勉强可以完成短向量的运算，但读写数据是串行的，是整个指令流水线的瓶颈。如果数据读写也能并行执行那将极大的加速向量运算，这种并行称为数据级并行（Data-Level Parrallelism，DLP）。

向量处理器：在超标量处理器的基础上，为了支持任意维度的向量的运算，我们需要增加更多的执行单元，搭载更大容量的向量寄存器（Vector register），称为向量处理器（Vector Processer）。向量处理器最大的不同是内存访问是流水线化，因此以同时读写多条数据，并将数据同时分发到不同的执行单元。Vector Processor 是一种 SIMD 处理器。那么上面的四维向量加法，只需要两条内存访问指令，一条向量加法指令和一条向量寄存器写回指令。对于长向量或者矩阵运算，一个处理器核心中不可能集成如此多的执行单元和寄存器，需要拆分成多条向量指令，因此向量处理器也支持向量指令流水线并行执行。

数据级并行对数据的局部性要求更高，因为 SIMD 处理器中的执行单元和内存访问单元都是并行执行，如果缓存缺失，会导致更多资源资源闲置。

4.3 线程级并行

进程与线程：在高级编程语言中，一堆指令的集合称为函数（function），一个程序可以只有一个函数，也可以将重复使用的指令“打包”到一个函数中。调用函数意味着执行其中的指令，只需要知道函数的地址就可以调用该函数。如果函数的之间没有依赖关系，那么这些函数可以同时执行。当程序调入内存运行时，称为一个进程（Process），这些可以同时执行的函数称为线程（Thread）。

操作系统允许多道进程并发执行，同一个进程包含一条或多条线程，线程是操作系统调度的最小单位。操作系统会维护一个线程池（Threads Pool），每个线程会赋予一定优先级，分时间片发送到到处理器上执行。软件线程本质上是工作的拆分，在处理器层面，线程中的指令只能在 SISD、SIMD 处理器上分时间片执行，这其实是一种并发（Concurrency）。线程级并行（Thread-Level Parrallelism）要求处理能同时执行来自多条线程的指令，这需要设计更复杂的电路。

同时多线程（Simultaneous Multithreading，SMT）：在超标量处理器的基础上，搭载更多指令获取器和程序计数器，可以在一个时钟从多道线程中获取指令并行执行。同时 SMT 处理器有更多的寄存器，当一条线程遇到内存访问指令，需要多个时钟周期才能返回结果，它就将该线程的上下文用寄存器保存下来，并从另一条线程取指令继续执行。当内存访问结果返回时，可以在一个时钟周期内从寄存器恢复被挂起的线程。SMT 技术使处理器保持忙碌，隐藏内存访问时延。

超标量处理器与 SMT 处理器的区别在于，超标量处理器只能从一个线程中取多道指令并行执行，而 SMT 处理器可以从不同线程中取多道指令并行执行。因此 SMT 处理器是一种 MIMD 处理器。Intel 的超线程技术（Hyper threading）也是一种 SMT

还有一种多线程技术称为时分多线程（Temporal Multithreading，TMT），它一个时钟周期只允许来自一条线程的一个指令执行，同时它拥有更多的寄存器，方便保存线程上下文。

从标量处理器到超标量处理器，再从超标量处理器到向量处理器，最后从向量处理器到多线程处理器。单核处理器的并行潜力被充分挖掘后，如果希望同时完成更多的任务，只有在一块芯片上集成更多的核心，也就是多核处理器。

多核处理器（Multi-Core Processor）：多核处理器能在一个时钟周期，同时执行来自不同线程的指令，属于 MIMD 处理器。操作系统负责将用户线程分发到不同处理器核心上执行，处理器的核心数通常少于用户的线程数，因此多道线程依然是分时间片在单个核心上执行。

4.4 GPU 并行计算

在图形渲染中，每个像素可以独立渲染，渲染过程中涉及非常多的向量/矩阵运算，因此可以把渲染任务拆分成不同的阶段（线程），交由一个对称多核 SIMD 处理器并行执行，这个处理器就是 GPU。GPU 指令也会划分出取指令、指令解码、指令执行等基本阶段，下图来自《General-Purpose Graphics Programming Archtecture》

GPU 指令执行过程是单指令流多数据流，NVIDIA 称其 GPU 是单指令多线程（Single Instruction Multiple Threads，SIMT），其实本质与 SIMD 差不多。GPU 将一条指令分发到多个流处理器上同时执行，不同的流处理器执行相同的指令处理不同的数据，每个流处理器就是一个线程。

NVIDIA GPU 将 32 个线程为一组，称为一个 Warp；AMD GPU 将 64 个线程为一组，称为 Wavefront。Warp 或者说 Wavefront 就是 GPU 调度的最小单位。在编写 GPGPU 程序时，首先需要为程序分配线程，分配线程的数量最好是 32 的整数倍。如果一个作业需要多于 32 个线程，那么会把这个作业拆分到多个 Warp 中执行；如果一个作业需要不足 32 个线程，那么依然会为它分配一个 Warp，用不到的线程会被遮掩（Mask Out），直白地说就是“闲着（Stall）”，等待其他线程任务的完成。

一个 Warp 的线程会以锁步（Lock-Step）的方式执行这些指令。所谓的锁步就是一起开始，一起结束，每个流处理器都执行相同的指令，但处理不同的数据。锁步的工作方式就是为实时渲染管线设计的，比如一个 SM 分配到 1000 个顶点着色的任务，所有顶点执行相同的着色程序因此每个流处理接受到的指令是相同的，每个流处理器处理不同的顶点，因此数据是不同的。处理这 1000 个顶点需要 floor(1000/32) + 1 个 Warp。NVIDIA 2018 年推出的消费级旗舰显卡 RTX 2080 ti 有 4352 个 CUDA Cores，同时可以分出 136 个 Warp。

分支语句于循环语句：现代 GPU 都支持分支语句与循环语句，但分支语句和循环语句的引入会影响 GPU 执行的效率。假设一个 Warp 需要为 8 个顶点进行着色，如下图左，顶点着色器代码如下图右。该代码存在两个分支，那么这 8 个线程有的会进入 true 分支，有的会进入 false 分支。如果此时执行 true 分支的指令，那么进入 false 分支的线程将会被遮掩，等待 true 分支指令的完成。当 true 分支的指令执行完之后，遮掩进入 true 分支的线程，激活进入 false 分支的线程，执行 false 分支的指令。Warp 中有的线程进入 true 分支，有的进入 false，那么线程被遮掩的时钟周期将会被浪费。同理循环语句的也是一样，当不同线程的循环次数不同时，循环次数少的线程会被遮掩，等待循环次数长的线程指令的完成。这就是不推荐 Shader 中使用控制流语句的原因。但如果一个 Warp 都进入相同的分支或者循环的次数都一样，那么将不会有线程被遮掩，也就不会影响性能。

时延隐藏：当缓存缺失时，GPU 访问显存的时延是非常高的，当一个 Warp 所有线程遇到线程读写指令时，可能需要数百个时钟周期才会把数据返回。因此，Warp 调度器会在寄存器中保存当前 Warp 的上下文，然后迅速把这 32 个流处理器切换到另一个 Warp 上继续执行。当数据返回时，可以从寄存器中恢复上下文，继续执行。GPU 通过保持忙碌，隐藏时延。因为上下文保存在寄存器中，所以上下文切换可以在一个时钟周期内完成。但寄存器是一个 GPU 中非常珍贵的资源，当有大量寄存器用于保存上下文时，就没有足够的寄存器去执行计算任务，仍然会使处理器闲置（Stall）。