335 lines
35 KiB
Markdown
335 lines
35 KiB
Markdown
# 第4章 数据级并行 - 各老师章节总结
|
||
|
||
## 曲冠南老师（qgn）
|
||
|
||
### 4.1 什么是数据级并行
|
||
|
||
本章首先引入数据级并行（Data-Level Parallelism, DLP）的概念。数据级并行的任务场景包括科学计算（矩阵运算）、三维渲染和图像处理，这些应用的核心共性是对大量的数据施加同种变换。从软件编程模型的角度，数据级并行期待SPMD（Single Program Multiple Data）模式，即单程序多数据。
|
||
|
||
思考题：一个SPMD程序如何运行在SISD或MIMD上？曲老师通过图示说明：单核单线程串行化执行时，把MD拆成多次SD变为SISD；多核多线程并行化执行时，把SP的每条指令多次重复变为MIMD。但这两种方式都存在问题——排队、耗时、耗电。
|
||
|
||
传统标量CPU流水线的取址、译码等操作逻辑复杂且开销不低，对于SPMD任务，无论在SISD还是MIMD器件上运行，取址、译码操作都是有冗余的。由此引出SIMD器件的设计思路：更多的ALU，更少的Fetch和Decode。更少的Fetch和Decode意味着更少的器件、更低的能耗和时间开销；更多的ALU意味着一次流水能处理更多数据、速度更快；同时增加数据寄存器的数量来一次存储更多数据，以减少存储器访问延迟。
|
||
|
||
数据级并行主要有两种实现架构：向量体系结构和GPU。向量体系结构"窄而深"——指令流水线深，ALU宽度窄，单次指令流水后能处理更多数据，掩盖不必要的流水线时间；GPU"宽而浅"——指令流水线浅，ALU宽度宽，流水本身比较简单，直接对更多的数据进行并行计算，同一时刻处理更多数据。
|
||
|
||
### 4.2 向量体系结构
|
||
|
||
向量这种数据结构及其运算与SIMD的期待不谋而合。曲老师详细讲解了向量的三种计算方式：
|
||
|
||
**横向计算方式**：向量计算按行从左到右横向进行，需要组成循环程序处理。每一对数据相关N次，功能切换2N次。这种方式是在标量处理器上对向量的一般计算方式，不适合于向量处理机的并行处理。
|
||
|
||
**纵向计算方式**：向量计算按列从上到下纵向进行，用两条向量指令K=B+C和D=K×A表示。两条向量指令之间数据相关仅1次，功能切换也仅1次。纵向计算方式更适合于进行向量计算。
|
||
|
||
**纵横（分组）计算方式**：由于存储结构层次化和寄存器数量有限，需要将向量分成若干组，组内按纵向方式处理，依次处理各组。设N=S×n＋r（N为向量长度，S为组数，n为每组长度，r为余数），若余下的r个数也作为一组处理，则共有S+1组。每组内各用两条向量指令，数据相关1次，功能切换2次。
|
||
|
||
由此引出向量体系结构Vector Architecture。向量体系结构应当具有很大的顺序寄存器堆（Register File），可加载更多向量元素以支持纵向计算。向量体系结构从内存中收集散落的数据，将其放入寄存器堆中，进行操作后放回内存（一次传输一组数据，LD/ST流水化）。一条指令能够对一个向量的数据进行操作，也就对向量中诸多独立数据元素进行了操作（纵向计算，功能单元流水化）。
|
||
|
||
向量体系结构的优势在于：向量的Load与Store是深度流水线化的，大型寄存器堆充当Buffer的作用，能够掩盖访存延迟并充分利用内存带宽；乱序超标量处理器复杂度和功耗高，容易触及Power Wall；而将顺序标量处理器扩展为向量处理器则不会带来复杂度和功耗的大幅升高，开发者也容易适应和转换到向量指令。
|
||
|
||
实例：VMIPS=标量MIPS+逻辑向量扩展。向量寄存器：64bit×64元素×8个VR，足够多读写口；向量功能单元：全流水化，每周期1操作，需要控制单元检测结构冒险和数据冒险；向量load/store单元：全流水化，每周期1个字，可操作标量；标量寄存器集合：32通用，32浮点，可存地址和数据。
|
||
|
||
向量专用特殊寄存器包括向量长度寄存器VL（64位，每位对应向量寄存器一个单元，作用是将软件层程序中实际向量长度N与硬件层向量寄存器中元素数目64相适配）和向量屏蔽寄存器VM（当向量长度小于64时，或条件语句控制下对向量某些元素进行单独运算时使用，即使maskcode中有大量0，使用VM的向量指令速度依然远远快于标量计算模式）。
|
||
|
||
VMIPS向量指令格式为：VMIPS指令=MIPS指令+Op1类型+Op2类型.精度。比较MIPS和VMIPS代码可以看出，向量指令大大减少了代码行数，更关键的是减少了指令条数，大量节约了取指令和指令译码所消耗的时间。
|
||
|
||
向量体系结构的相关概念包括：循环间相关（对一个循环来说，如果各轮迭代之间存在相关性则称为循环间相关，否则为循环间无关）、可向量化（针对一组MIPS指令描述的循环，如果满足循环间无关则循环称为可向量化的，编译器可为其生成向量指令）、指令编队（由一组不包含结构冒险的向量指令组成，一个编队中的所有向量指令在硬件条件允许时可以并行执行）。
|
||
|
||
向量体系结构的性能优化技术包括：**多车道技术**——增加功能单元ALU的数量提升向量计算速度，如同将单车道的窄巷扩宽成四车道的公路；**链接技术**——当两条指令出现"写后读"相关时，若不存在功能部件冲突和向量寄存器冲突，可以将功能部件头尾相接形成链接长流水线进行流水处理。无链接时后面的功能需等前一个功能的n个结果都产生才能开始，而链接时后面的功能只需等前一个功能的第一个结果产生就可以开始，实现了向量数据的生产与消费进行延迟重叠。链接实质是把流水线定向的思想引入到向量执行过程，对两条流水线进行联合控制，没有改变寄存器和运算电路。
|
||
|
||
链接技术例题中，曲老师分析了非链接执行和链接执行两种情况下的执行时间（假设向量长度为N）：（1）三条指令串行执行，执行时间为3N+22拍；（2）前两条并行再串行第三条，执行时间为2N+15拍；（3）前两条并行并与第三条链接执行，链接流水线建立时间为17拍，生成所有结果的执行时间为N+16拍。
|
||
|
||
进行向量链接的要求：保证无向量寄存器使用冲突和无功能部件使用冲突；只有在前一条指令的第一个结果元素送入结果向量寄存器的那一个时钟周期才可以进行链接；当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时，要求先行的两条指令产生运算结果的时间必须相等；进行链接执行的向量指令的向量长度必须相等；一次链接行为通常仅发生在分组内部。
|
||
|
||
**编队技术**：几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。同一个编队中的向量指令之间不存在结构冲突，不存在数据冲突，或存在数据冲突但可以链接。
|
||
|
||
编队技术例题中给出了使用链接技术分为3个编队、不使用链接技术分为4个编队的分析。
|
||
|
||
**分段开采技术**：当向量长度N大于向量寄存器长度n时，必须把长向量N分成长度固定为n的段，然后循环分段处理，每一次循环只处理一个向量段。该技术由系统硬件和编译软件合作完成控制，对程序员是透明的。
|
||
|
||
向量体系结构的性能影响因素包括：操作数向量的长度、向量启动时间、操作之间的数据相关/是否采用链接、操作之间的结构性相关/发射限制/车道数量/是否采用编队。
|
||
|
||
### 4.3 GPU结构
|
||
|
||
GPU（Graphics Processing Unit）为并行而生。发展历程：从pixel parallelism加速图像构建，到Computing: Graphics oriented -> General Purpose，再到Programmable: Graphic API -> Computing API (如OpenGL到OpenCL)。使得程序不需要用顶点坐标、纹理和着色器程序来表达，大大降低了程序复杂性。
|
||
|
||
晶体管分配方面存在不同的设计选择：控制逻辑 vs 算术逻辑。
|
||
|
||
采用CPU+GPU架构（异构）：CPU擅长执行少量串行线程，快速顺序执行，低延迟缓存存储访问；GPU擅长执行大量并行线程，可扩展的并行执行，高带宽并行存储访问。
|
||
|
||
GPGPU的优势：解放了程序员对图形API和GPU架构的深入了解；问题不需要用顶点坐标、纹理和着色器程序来表达，大大降低了程序复杂性；支持随机读写内存等基本编程特性，大大开发了编程模型；引入双精度支持使GPU上的科学应用能够获得高性能。
|
||
|
||
曲老师还介绍了GPGPU的层次结构、GPU级别的结构、SM级别结构、SM Details、存储层次、调度层次、软硬件自相似性、代码模式、编译与执行、内核调用、宏并行性、计算层次、SIMD/SIMT微并行性、SIMT实现、Warp调度、Warps/Wavefront等概念，以及GPGPU虚拟化的思想。
|
||
|
||
---
|
||
|
||
## 李宏图老师（lht）
|
||
|
||
*（以下内容综合自20220526和20230331两个版本的PPT）*
|
||
|
||
### 4.1 数据级并行
|
||
|
||
李老师从任务场景出发，介绍数据级并行的应用场景包括科学计算（矩阵运算）、三维渲染和图像处理。无论是矩阵运算还是图形图像处理，其共性是对大量的数据施加同种变换——数据级并行（DLP）。从软件角度，在编程模型上期待SPMD（Single Program Multiple Data）模式。
|
||
|
||
李老师通过具体代码示例展示了串行执行与并行执行的区别：
|
||
```c
|
||
for (i=0; i < N; i++)
|
||
C[i] = A[i] + B[i];
|
||
```
|
||
串行执行时迭代1和迭代2顺序执行，而并行执行时迭代1和迭代2可以同时进行。
|
||
|
||
思考题：一个数据并行程序如何运行在SISD或MIMD上？通过图示说明：单核单线程串行化执行时，把MD拆成多次SD变为SISD；多核多线程并行化执行时，把SP的每条指令多次重复变为MIMD。但这会导致排队、耗时、耗电的问题。
|
||
|
||
分析传统标量CPU流水线可知，取址、译码等操作逻辑复杂且开销不低。对于数据级并行任务，无论在SISD还是MIMD（多核）器件上运行，其取址、译码操作都是有冗余的。由此引出对于数据级并行场景如何设计一种新型器件的问题。
|
||
|
||
SIMD器件的设计思路：更多的ALU（Execute），更少的Fetch和Decode。更少的Fetch和Decode意味着更少的器件、更低的能耗和时间开销；更多的ALU意味着一次流水能处理更多数据、速度更快；增加数据寄存器的数量，一次存储更多数据，以减少存储器访问延迟。
|
||
|
||
李老师在20230331版本中更详细地介绍了**单指令多数据（SIMD）处理**：一条指令处理多个不同的数据，有多个处理单元PE（Processing Elements）。其中阵列处理机（Array Processor）：同一指令在同一时间处理不同空间上的不同数据元素；向量处理机（Vector Processor）：同一指令在连续的时间内在同一空间上处理不同的数据元素。
|
||
|
||
两种执行方式的对比图示清晰展示了ARRAY PROCESSOR（同一操作同一时间，不同空间）和VECTOR PROCESSOR（不同操作同一空间，不同时间）的区别。
|
||
|
||
SIMD vs VLIW的对比：阵列处理机对不同数据进行同一操作；VLIW则是多个独立操作由编译器捆绑在一起。
|
||
|
||
数据级并行有两种主要架构：**向量体系结构**（"窄而深"——指令流水线深，ALU宽度窄，单次指令流水后能处理更多数据，掩盖不必要的流水线时间）和**GPU**（"宽而浅"——指令流水线浅，ALU宽度宽，流水本身比较简单，直接对更多的数据进行并行计算，同一时刻处理更多数据）。
|
||
|
||
### 4.2 向量体系结构
|
||
|
||
向量这种数据结构及其运算与SIMD的期待不谋而合。
|
||
|
||
**向量的三种计算方式**：
|
||
|
||
横向计算方式：向量计算按行从左到右横向进行，需要组成循环程序处理。数据相关N次，功能切换2N次。这种方式不适合于向量处理机的并行处理。
|
||
|
||
纵向计算方式：向量计算按列从上到下纵向进行，用两条向量指令K=B+C和D=K×A表示。两条向量指令之间数据相关仅1次，功能切换仅1次。适合向量处理机的并行处理。
|
||
|
||
对处理机结构的要求——存储器-存储器结构：向量指令的源向量和目的向量都存放在存储器中，运算的中间结果需要送回存储器。例如STAR-100、CYBER-205。
|
||
|
||
纵横（分组）计算方式：结合存储结构层次化和寄存器数量有限的现实，将向量分成若干组，组内按纵向方式处理。设N=S×n＋r，若余下的r个数也作为一组处理，则共有S+1组。每组内各用两条向量指令，数据相关1次，功能切换2次。
|
||
|
||
对处理机结构的要求——寄存器-寄存器结构：设置能快速访问的向量寄存器，用于存放源向量、目的向量及中间结果，让运算部件的输入、输出端都与向量寄存器相联，构成寄存器-寄存器型操作的运算流水线。典型的寄存器-寄存器结构的向量处理机包括美国的CRAY-1、我国的YH-1巨型机。
|
||
|
||
**向量体系结构Vector Architecture**：应当具有很大的顺序寄存器堆（Register File），可加载更多向量元素以支持纵向计算；从内存中收集散落的数据放入寄存器堆中，进行操作后放回内存（一次传输一组数据，LD/ST流水化）；一条指令能够对一个向量的数据进行操作，也就对向量中诸多独立数据元素进行了操作（纵向计算，功能单元流水化）。
|
||
|
||
**向量体系结构的优势**：向量的Load与Store是深度流水线化的，大型寄存器堆充当Buffer的作用，能够掩盖访存延迟并充分利用内存带宽；乱序超标量处理器复杂度和功耗高，容易触及Power Wall；而将顺序标量处理器扩展为向量处理器不会带来复杂度和功耗的大幅升高，开发者也容易适应和转换到向量指令。
|
||
|
||
**实例：VMIPS=标量MIPS+逻辑向量扩展**详细描述了向量寄存器（64bit×64元素×8个VR）、向量功能单元（全流水化，每周期1操作）、向量load/store单元（全流水化，每周期1个字）、标量寄存器集合的配置。
|
||
|
||
**Vi冲突和功能部件冲突**：只要不出现Vi冲突和功能部件冲突，各Vi之间和各功能部件之间都能并行工作，大大加快了向量指令的处理。Vi冲突是指并行工作的各向量指令的源向量或结果向量使用了相同的Vi；功能部件冲突是指并行工作的各向量指令要使用同一个功能部件。
|
||
|
||
**向量专用特殊寄存器**：向量长度寄存器VL（64位，每位对应向量寄存器一个单元，作用是将软件层程序中实际向量长度N与硬件层向量寄存器中元素数目64相适配）和向量屏蔽寄存器VM（当向量长度小于64时，或条件语句控制下对向量某些元素进行单独运算时使用，即使maskcode中有大量0，使用VM的向量指令速度依然远远快于标量计算模式）。
|
||
|
||
**CRAY-1的基本结构**（20230331版本补充）：共有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。其中6个单功能流水部件进行向量运算：整数加（3）、逻辑运算（2）、移位（4）、浮点加（6）、浮点乘（7）、浮点迭代求倒数（14），括号中的数字为其流水经过的时钟周期。
|
||
|
||
**VMIPS向量指令格式**：VMIPS指令=MIPS指令+Op1类型+Op2类型.精度。代码对比展示了MIPS循环与VMIPS向量代码的巨大差异，后者大大减少了代码行数，更重要的是减少了指令条数。
|
||
|
||
**向量体系结构的相关概念**：循环间相关、可向量化、指令编队（convoy）。
|
||
|
||
**向量体系结构的性能优化技术**：多车道技术、链接技术、编队技术、分段开采技术。
|
||
|
||
**链接技术**详细讲解：当两条指令出现"写后读"相关时，若不存在功能部件冲突和向量寄存器冲突，可以将功能部件头尾相接形成链接长流水线。无链接时后面的功能需等前一个功能的n个结果都产生才能开始，链接时后面的功能只需等前一个功能的第一个结果产生就可以开始。链接实质是把流水线定向的思想引入到向量执行过程。
|
||
|
||
链接技术例题中分析了三种情况的执行时间（假设向量长度为N）：（1）三条指令串行执行3N+22拍；（2）前两条并行再串行第三条2N+15拍；（3）前两条并行并与第三条链接执行，链接流水线建立时间17拍，生成所有结果执行时间N+16拍。
|
||
|
||
**进行向量链接的要求**：保证无向量寄存器使用冲突和无功能部件使用冲突；链接时机在第一个结果元素送入结果向量寄存器的那一个时钟周期；两条先行指令产生运算结果的时间必须相等；向量长度必须相等；一次链接行为通常仅发生在分组内部。
|
||
|
||
**编队技术**：几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。同一个编队中的向量指令之间不存在结构冲突，不存在数据冲突，或存在数据冲突但是可以链接。
|
||
|
||
**分段开采技术**：当向量长度N大于向量寄存器长度n时，必须把长向量N分成长度固定为n的段，循环分段处理。由系统硬件和编译软件合作完成控制，对程序员透明。
|
||
|
||
**例3.4分段开采实例**详细展示了当N≤64和N＞64时的不同处理方式，包括循环次数K和余数L的计算，以及处理余数部分和循环K次分段处理的代码。
|
||
|
||
**向量体系结构的性能影响因素**：操作数向量的长度、向量启动时间、操作之间的数据相关/是否采用链接、操作之间的结构性相关/发射限制/车道数量/是否采用编队。
|
||
|
||
### 4.3 GPU结构
|
||
|
||
**GPU和GPGPU的定义**：GPU=Graphics Processing Unit，图形处理器，具有极高的计算吞吐率和内存带宽，适合纹理图像处理；GPGPU=General-purpose computing on GPUs，通用图形处理器，可进行通用计算编程（如CUDA, OpenCL），适合处理SIMD程序。
|
||
|
||
**CPU vs GPU**：多核vs众核（几个核vs上千个核），GPU将芯片中更多的晶体管用于计算。GPU处理模式是流水线vs并发执行。
|
||
|
||
**SPMD编程模型**：Single Program Multiple Data，单程序多数据。程序采用多线程模型，与SIMD编程模型不同。不同的进程/线程运行同一个程序源代码（SP），但是分别使用不同的输入数据进行各自的计算（MD）。不同进程/线程相互独立，没有执行顺序的要求。常用并行编程模型多数采用SPMD模式，如CUDA、MPI、openMP。
|
||
|
||
**CUDA编程模型**：CUDA=Compute Unified Device Architecture，统一计算设备架构，由NVIDIA提出，采用SPMD编程方式，软件环境使用C++作为高级编程语言。
|
||
|
||
**异构编程**：Host（主机CPU，运行C++程序）和Device（物理上分离的协处理器GPU，运行kernel程序）。
|
||
|
||
**CUDA程序示例**展示了向量加法的实现，包括kernel定义和调用方式。
|
||
|
||
**Host-Device数据传输**的代码示例展示了完整的内存分配、数据传输和释放过程。
|
||
|
||
**GPU执行方式**：Single Instruction Multiple Thread（单指令多线程），SIMD与多线程相结合，线程按照固定方式运行（与传统SPMD不同），固定个数的线程一起执行（SIMD），使用标量指令（与传统SIMD不同）。
|
||
|
||
**SPMD, SIMT, 和SIMD的关系**：SPMD是GPU的编程模型，SIMT是GPU的执行方式，SIMD是GPU计算单元的处理方式。
|
||
|
||
**SIMT的优点**：编程灵活，任意大小的工作量vs任意硬件SIMD宽度，每个线程可以被单独对待，Warp细节对程序员透明。
|
||
|
||
**NVIDIA H100 GPU** specs（20230331版本）：16896 FP32 CUDA cores，66.9 TFLOPS (FP64 Tensor core)，33.5 TFLOPS (FP64)，3352 GB/s memory bandwidth，700W TDP。
|
||
|
||
**GPGPU微体系结构**：线程以warp为单位进行调度，同一warp中的不同线程按照SIMT方式执行，大容量寄存器组用于存放所有线程的数据，SP（Streaming Processor）进行数据的并行计算。标量指令处理和SIMD数据访问及计算。
|
||
|
||
**Warp的定义**：在Nvidia GPU中，warp为32个标量线程构成的SIMT执行单位。GPU SM中以warp为最小单位进行调度和执行。GPU无法控制单独执行某一个thread。Warp中不同的Thread在执行时保持同步，所有Thread永远执行相同PC所对应的指令。
|
||
|
||
**通过细粒度多线程并行掩盖延迟**：细粒度多线程执行。
|
||
|
||
**Warp调度**：当访存时间长时，GPU将大量warp交替调度执行，可以一定程度上掩盖长时间访存。
|
||
|
||
**Warp执行**：32-thread warp executing ADD A[tid],B[tid] → C[tid]。
|
||
|
||
**Streaming Processor (SP)**：CUDA core，SIMD执行，大量SP提供极高并行算力。
|
||
|
||
**Warp指令级的并行执行**：可以将不同指令交替执行，假设机器中有8个通道，1个warp中有32个线程，每周期完成24个操作，但每周期流出1个warp。
|
||
|
||
**SIMT的访存模式**：执行同一指令的不同线程使用线程ID来访问不同的数据。
|
||
|
||
**Coalescing**：将一个warp中不同thread的内存访问合并成更少的访问次数。如果warp中的32个thread访问内存中连续的4B大小的位置，合并成一个128B的访存请求，有效降低SM和DRAM之间的访存次数。
|
||
|
||
**GPU程序层次模型**：kernel grid→block→thread。一个程序kernel grid由多个block组成，一个block由多个thread组成，Thread为标量线程，执行完整的程序源代码。一个kernel以block为单位分配到硬件中，多个block可以分配到同一个SM中。在SM内部，来自同一个block中的不同线程（编号相邻）组成一个warp（例如1 warp = 32 thread）。Block和thread对程序员可见，warp对程序员不可见，由硬件控制。
|
||
|
||
**GPU程序层次例子**：Block与向量处理循环中的向量长度为32的分段开采类似。
|
||
|
||
**GPU与传统SIMD的区别**：传统SIMD采用单线程，向量指令之间锁步执行，编程方式为SIMD，软件需要知道向量长度，ISA中有向量/SIMD指令；GPU以SIMD方式执行大量标量线程，可以非锁步执行，每个线程可以被独立看待，编程方式为SPMD，ISA是标量的。
|
||
|
||
**Nvidia ISA**：PTX（Parallel Thread Execution）是NVIDIA编译器的指令集目标抽象，可实现各代GPU的兼容性，使用虚拟寄存器，由软件将其翻译成机器语言。
|
||
|
||
**Nvidia机器指令**：PTX在运行时转换成SASS，SASS与GPGPU计算能力对应。
|
||
|
||
**分支处理**：GPU分支硬件使用掩码，类似向量处理机中的向量屏蔽寄存器，并使用硬件栈处理分支（分歧后push，汇聚后pop）。
|
||
|
||
**分支分歧(branch divergence)**：当同一warp中的不同线程在遇到分支指令时执行不同的路径。GPU使用简化的控制逻辑来减少控制部分所占的面积，thread无法单独控制和调度，并行的处理单元同一个时钟周期只能处理相同的操作。
|
||
|
||
**分支分歧处理**：每个warp使用一个栈来处理分支分歧的执行。
|
||
|
||
**存储层次**：Local memory（一个thread）、Shared memory（一个block中的所有thread）、Global memory（所有thread）、Texture memory（只读，适合特定地址访问模型）、Constant memory（只读）。
|
||
|
||
**AMD GPU**（20230331版本补充）：AMD TeraScale Architecture使用VLIW，CU = SM, Work group = block (CTA), work item = thread, wavefront = warp (64)；AMD GCN Architecture，Wavefront size = 64，每个SIMD Unit中有16 ALU；AMD RDNA Architecture，Wavefront size = 32，每个SIMD unit中有32个ALU。
|
||
|
||
**GPGPU虚拟化**：企业级做云计算时采用虚拟化技术。硬件上把多个SM进行分割成多个切片，软件上为每个用户分配一个SM切片，使得每个用户都能满负荷使用SM，每个用户感觉自己拥有了一个GPU。
|
||
|
||
---
|
||
|
||
## 谭婧炜佳老师（tjwj）
|
||
|
||
### 本章内容概览
|
||
|
||
本章围绕数据级并行展开，内容包括三个主要部分：数据级并行的概念、向量体系结构、GPU体系结构。
|
||
|
||
### 4.1 数据级并行的概念
|
||
|
||
谭老师从任务场景出发，介绍数据级并行的应用场景：对大量不同数据执行相同操作。典型应用包括科学计算（矩阵运算）、三维渲染和图像处理。
|
||
|
||
通过代码示例对比串行执行与并行执行：
|
||
```c
|
||
for (i=0; i < N; i++)
|
||
C[i] = A[i] + B[i];
|
||
```
|
||
串行执行时迭代1和迭代2顺序执行，而并行执行时可以同时进行。
|
||
|
||
**存在的问题**：单核单线程串行化执行（把MD拆成多次SD，变为SISD）和多核多线程并行化执行（把SP的每条I多次重复，变为MIMD）都存在取址、译码冗余的问题，导致排队、耗时、耗电。
|
||
|
||
**SIMD处理器**：更多的ALU（Execute），更少的Fetch和Decode。更少的Fetch和Decode意味着更少的器件、更低的能耗和时间开销；更多的ALU意味着同时能处理更多数据、速度更快；增加数据寄存器的数量来一次存储更多数据，以减少存储器访问延迟。
|
||
|
||
**单指令多数据（SIMD）处理**：一条指令处理多个不同的数据，有多个处理单元PE。阵列处理机：同一指令在同一时间处理不同空间上的不同数据元素；向量处理机：同一指令在连续的时间内在同一空间上处理不同的数据元素。
|
||
|
||
两种执行方式的对比图示展示了ARRAY PROCESSOR（同一操作同一时间，不同空间）和VECTOR PROCESSOR（不同操作同一空间，不同时间）的时序差异。
|
||
|
||
SISD、MIMD与SIMD的对比图示清晰地展示了三种架构在时间维度上的差异。
|
||
|
||
**向量体系结构和GPU**：向量体系结构"窄而深"——指令流水线深，ALU宽度窄，单次指令流水后能处理更多数据，掩盖不必要的流水线时间；GPU"宽而浅"——指令流水线浅，ALU宽度宽，流水本身比较简单，直接对更多的数据进行并行计算，同一时刻处理更多数据。
|
||
|
||
### 4.2 向量体系结构
|
||
|
||
**向量概念**：科学计算领域的很多问题需要处理大批量操作重复且互相没有关联的计算。向量是一组由一维数组所组成的数据，标量是单个数据。在流水线处理机中，设置向量数据表示及相应的向量指令，称为向量处理机；不具有向量数据表示和相应的向量指令的流水线处理机，称为标量处理机。
|
||
|
||
**三种向量处理方式**：
|
||
|
||
横向（水平）计算：向量计算按行从左到右横向进行，数据相关N次，功能切换2N次，不适合于向量处理机的并行处理。
|
||
|
||
纵向（垂直）处理方式：向量计算按列从上到下纵向进行，数据相关1次，功能切换1次，适合于向量处理机的并行处理。纵向处理方式N的大小不受限制，但对处理机结构要求是存储器-存储器结构，向量指令的源向量和目的向量都存放在存储器中。
|
||
|
||
纵横（分组）处理方式：把向量分成若干组，组内按纵向方式处理，依次处理各组。设N=S×n＋r，若余下的r个数也作为一组处理，则共有S+1组。每组内各用两条向量指令，数据相关1次，功能切换2次，适合于向量处理机的并行处理。纵横处理方式N的大小不受限制，但n值固定，对处理机结构要求是寄存器-寄存器结构。典型的寄存器-寄存器结构的向量处理机包括美国的CRAY-1、我国的YH-1巨型机。
|
||
|
||
**功能部件流水化**：把流水线技术应用于运算的执行过程，形成运算操作流水线（部件级流水线）。例如浮点加法流水线，把浮点加法的全过程分解为求阶差、对阶、尾数相加、规格化4个子过程。
|
||
|
||
**向量体系结构Vector Architecture**：具有很大的顺序寄存器堆（Register File），可加载更多向量元素以支持纵向计算；从内存中收集散落的数据放入寄存器堆中，进行操作后放回内存（一次传输一组数据，LD/ST流水化）；一条指令能够对一个向量的数据进行操作，也就对向量中诸多独立数据元素进行了操作（纵向计算，功能单元流水化）。
|
||
|
||
**向量体系结构的优势**：向量的Load与Store是深度流水线化的，大型寄存器堆充当缓冲的作用，能够掩盖访存延迟并充分利用内存带宽；乱序的超标量处理器复杂度和功耗高，容易触及功耗墙；将顺序标量处理器扩展为向量处理器不会带来复杂度和功耗的大幅升高，开发者也容易适应和转换到向量指令。
|
||
|
||
**实例：VMIPS**详细描述了向量寄存器、向量功能单元、向量load/store单元、标量寄存器集合的配置。
|
||
|
||
**向量专用特殊寄存器**：向量长度寄存器VL（值≤64，作用是将软件层程序中实际向量长度N与硬件层向量寄存器中元素数目64相适配）和向量屏蔽寄存器VM（当向量长度小于64时，或条件语句控制下对向量某些元素进行单独运算时使用，即使maskcode中有大量0，使用VM的向量指令速度依然远远快于标量计算模式）。
|
||
|
||
**VMIPS向量指令格式**：VMIPS指令=MIPS指令+Op1类型+Op2类型.精度。
|
||
|
||
**代码对比**：MIPS循环代码需要多条指令和循环控制，而VMIPS向量代码大大简化。谭老师特别指出：减少的不仅仅是行数，更重要的是减少了指令条数，大量节约了取指令和指令译码所消耗的时间。
|
||
|
||
**向量体系结构的相关概念**：循环间相关、可向量化、指令编队（convoy）。
|
||
|
||
**向量体系结构的性能优化技术**：多车道技术、链接技术、编队技术、分段开采技术。
|
||
|
||
**冲突例子**：Vi冲突（并行工作的各向量指令的源向量或结果向量使用了相同的Vi）和功能部件冲突（并行工作的各向量指令要使用同一个功能部件）。
|
||
|
||
**链接技术**：当两条指令出现"写后读"相关时，若不存在功能部件冲突和向量寄存器冲突，可以将功能部件头尾相接形成链接长流水线。链接实质是把流水线定向的思想引入到向量执行过程。
|
||
|
||
**链接技术例题**：详细分析了三种情况的执行时间（假设N≤64）：（1）三条指令串行执行3N+22拍；（2）前两条并行再串行第三条2N+15拍；（3）前两条并行并与第三条链接执行，链接流水线建立时间17拍，生成所有结果执行时间N+16拍。
|
||
|
||
**进行向量链接的要求**：保证无向量寄存器使用冲突和无功能部件使用冲突；链接时机在第一个结果元素送入结果向量寄存器的那一个时钟周期；两条先行指令产生运算结果的时间必须相等；向量长度必须相等；一次链接行为通常仅发生在分组内部。
|
||
|
||
**编队技术**：几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。
|
||
|
||
**分段开采技术**：当向量长度N大于向量寄存器长度n时，把长向量N分成长度固定为n的段，循环分段处理。由系统硬件和编译软件合作完成控制，对程序员透明。
|
||
|
||
**向量体系结构的性能影响因素**：操作数向量的长度、向量启动时间、操作之间的数据相关/是否采用链接、操作之间的结构性相关/发射限制/车道数量/是否采用编队。
|
||
|
||
### 4.3 GPU体系结构
|
||
|
||
**GPU定义**：GPU=Graphics Processing Unit，图形处理器，具有极高的计算吞吐率和内存带宽，专用图形图像处理器，适合纹理图像处理；GPGPU=General-purpose computing on GPUs，通用图形处理器，可进行通用计算编程（如CUDA, OpenCL），适合处理SIMD程序。
|
||
|
||
**CPU vs GPU**：多核vs众核（几个核vs上千个核），GPU将芯片中更多的晶体管用于计算。
|
||
|
||
**SPMD编程模型**：Single Program Multiple Data，单程序多数据。程序采用多线程模型，与SIMD编程模型不同。不同的进程/线程运行同一个程序源代码，但是分别使用不同的输入数据进行各自的计算。不同进程/线程相互独立，没有执行顺序的要求。常用并行编程模型多数采用SPMD模式，如CUDA、MPI、openMP。
|
||
|
||
**CUDA编程模型**：CUDA=Compute Unified Device Architecture，统一计算设备架构，由NVIDIA提出，采用SPMD编程方式。
|
||
|
||
**异构编程**：Host（主机CPU）和Device（物理上分离的协处理器GPU）。
|
||
|
||
**CUDA程序示例**展示了向量加法的kernel定义和调用方式。
|
||
|
||
**GPU执行方式**：Single Instruction Multiple Thread（单指令多线程），SIMD与多线程相结合，线程按照固定方式运行，固定个数的线程一起执行（SIMD），使用标量指令。
|
||
|
||
**SPMD, SIMT, 和SIMD的关系**：SPMD是GPU的编程模型，SIMT是GPU的执行方式，SIMD是GPU计算单元的处理方式。
|
||
|
||
**SIMT的优点**：编程灵活，任意大小的工作量vs任意硬件SIMD宽度，每个线程可以被单独对待，Warp细节对程序员透明。
|
||
|
||
**NVIDIA H100 GPU** specs：16896 FP32 CUDA cores，66.9 TFLOPS (FP64 Tensor core)，33.5 TFLOPS (FP64)，3352 GB/s memory bandwidth，700W TDP。
|
||
|
||
**GPGPU微体系结构**：线程以warp为单位进行调度，同一warp中的不同线程按照SIMT方式执行，大容量寄存器组用于存放所有线程的数据，SP进行数据的并行计算。
|
||
|
||
**Warp**：32个标量线程构成的SIMT执行单位，以warp为最小单位进行调度和执行。Warp中不同的Thread在执行时保持同步，所有Thread永远执行相同PC所对应的指令。
|
||
|
||
**通过细粒度多线程并行掩盖延迟**：细粒度多线程执行。
|
||
|
||
**Warp调度**：当访存时间长时，GPU将大量warp交替调度执行，可以一定程度上掩盖长时间访存。
|
||
|
||
**Warp执行**：32-thread warp executing ADD A[tid],B[tid] → C[tid]。
|
||
|
||
**Streaming Processor**：CUDA core，SIMD执行，大量SP提供极高并行算力。
|
||
|
||
**Warp指令级的并行执行**：可以将不同指令交替执行。
|
||
|
||
**SIMT的访存模式**：执行同一指令的不同线程使用线程ID来访问不同的数据。
|
||
|
||
**Coalescing**：将一个warp中不同thread的内存访问合并成更少的访问次数。
|
||
|
||
**GPU程序层次模型**：kernel grid→block→thread。Block和thread对程序员可见，warp对程序员不可见，由硬件控制。同一kernel中的所有线程都共享相同的代码，不同线程执行进度可能不同，但同一warp中的线程一同执行，可以在Block级别进行同步。
|
||
|
||
**GPU程序层次例子**：Block与向量处理循环中的向量长度为32的分段开采类似。
|
||
|
||
**GPU与传统SIMD的区别**：传统SIMD采用单线程，向量指令之间锁步执行，编程方式为SIMD，软件需要知道向量长度，ISA中有向量/SIMD指令；GPU以SIMD方式执行大量标量线程，可以非锁步执行，每个线程可以被独立看待，编程方式为SPMD，ISA是标量的。
|
||
|
||
**Nvidia ISA**：PTX（Parallel Thread Execution）是硬件指令集抽象，可实现各代GPU的兼容性。
|
||
|
||
**分支处理**：GPU分支硬件使用掩码，类似向量处理机中的向量屏蔽寄存器，并使用硬件栈处理分支。
|
||
|
||
**分支分歧处理**：每个warp使用一个栈来处理分支分歧的执行。
|
||
|
||
**存储层次**：Local memory（一thread）、Shared memory（一block中的所有thread）、Global memory（所有thread）、Texture memory（只读，适合特定地址访问模型）、Constant memory（只读）。
|
||
|
||
**GPGPU虚拟化**：企业级做云计算时采用虚拟化技术，硬件上把多个SM进行分割成多个切片，软件上为每个用户分配一个SM切片，使得每个用户都能满负荷使用SM。 |