SIMD 指令集与数据并行程序 - 极术社区 - 连接开发者与智能计算生态

本文内容来自《Whole-Function Vectorization》的 Introduction 章节的 SIMD 指令集与数据并行程序小节，为作者的主要工作做知识铺垫，本文不涉及作者的主要工作，仅做 SIMD 概念的基本理解与学习。本文目录：
Amdahl's Law 和 Intel MMX
2. SIMD、数据并行、向量处理器的关系
    2.1 向量处理器的优缺点和限制
SIMD
    3.1 内存访问
    3.2 指针类型于操作
    3.3 掩码类型
    3.4 副作用
4.数据并行程序
    4.1 程序表示
由于原文内容较为薄弱，学习过程中，补充了一些内容，不少来自 ece740 《Computer Architecture: SIMD/Vector/GPU》这一节的幻灯片（见文末参考）。

1.Amdahl's Law 和 Intel MMX

理论是推动技术前进的基石，根据阿姆达尔定律，该定律是由计算机工程师吉恩·阿姆达尔提出的，用来描述在多处理器系统中，程序性能提升的理论上限。下图左是该定律公式：

需要说明的是：

f：程序可并行化的部分的比例
N：处理器的数量

这个定律指出，程序的加速比受到其串行部分的限制。换句话说，程序中不能并行化的部分将决定整个程序性能提升的最大可能值。

实际需求推动技术向前，随着多媒体和通信软件的发展，对性能要求变高，1996 年， Intel 公司发表了一篇名为《MMX Technology Extension to the Intel Architecture》的文章，想要解决现有的 Intel 架构扩展以支持更高效的多媒体处理，同时保持与现有操作系统和应用程序的兼容性。通过设计一种基于 SIMD 名为 MMX 的技术，达到对现有应用程序的增强。

该方法也可以在 C 语言中访问 MMX 指令。让加速多媒体和通信以及其他数值密集型应用程序性能成为可能。

2.SIMD、数据并行、向量处理器的关系

在讲 SIMD（单指令多数据）、数据并行之前，有必要讲一下向量处理器，这三个概念是密切相关的，它们都涉及在计算过程中同时处理多个数据点的能力。简单来说：

数据并行（Data Parallelism）：是一种计算概念，指的是同时对多个数据元素执行相同操作的计算方式。这种方法允许对大规模数据集进行高效处理，因为它可以分摊在多个处理器或处理单元上。
向量处理器（Vector Processor）：一种专门设计来处理向量运算的处理器，它拥有一个或多个向量处理单元（Vector Processing Units, VPUs），能够一次性处理多个数据元素，这些数据元素通常被组织成向量或数组的形式。
SIMD（Single Instruction Multiple Data）
SIMD是一种执行模型，它允许单个指令同时对多个数据点进行操作
SIMD 是数据并行的一种实现方式，它通过在硬件层面上支持数据并行来提高性能。

要说三者的关系，可以这么说：

向量处理器则是实现SIMD操作的硬件基础。
SIMD可以视为数据并行的一种具体实现技术。
在向量处理器中，SIMD指令用于执行数据并行操作，这些指令会作用于处理器中的向量寄存器，这些寄存器可以存储多个数据元素。

总结来说，数据并行是一种概念，SIMD是一种实现数据并行的执行模型，而向量处理器则是具备执行SIMD指令能力的硬件。这三者共同为现代计算提供了强大的并行处理能力。

2.1 向量处理器的优缺点与限制

先提一下硬件的 Vector Processor。这里先给出 Vector Processor 优缺点的对比。

优势有：

无内部依赖：在向量操作中，单个指令可以同时处理多个数据元素，这些元素之间没有依赖关系。这意味着可以有效地使用流水线（pipelining）和并行化（parallelization）技术。
深度流水线：由于没有数据依赖，向量处理器可以设计成具有非常深的流水线，这有助于提高指令吞吐量。
指令生成大量工作：每个向量指令可以处理多个数据点，减少了指令获取带宽的需求。
高度规则的内存访问模式：向量处理器通常具有规则的内存访问模式，这使得可以通过内存银行（memory bank）交错（interleaving）和预取（prefetching）技术来提高内存带宽。
无需显式编码循环：由于向量处理器可以一次性处理多个数据元素，因此编程时不需要显式地编写循环，这减少了指令序列中的分支。

劣势也很明显：

仅在规则并行性下工作：对数据的要求，向量处理器在数据或单指令多数据（SIMD）并行性规则时效果最佳。这意味着数据必须能够以规则的方式被并行处理。
不规则并行性下的低效率：如果数据的并行性不规则，例如在处理不规则数据结构或需要条件执行的情况，可能效率会很低。
1. 典型的例子是搜索链表中的键：例如，在链表中搜索一个特定的键，这通常需要顺序访问和条件分支，这与向量处理器的优势相悖。链表的非连续和不规则特性使得向量处理器难以有效利用其并行处理能力。
2. 某些排序或者难以向量化的深度学习的后处理过程。
3. 在多媒体处理领域， SIMD 扩展是一种成本效益高的处理方式，但对未对齐内存访问的支持较弱，这在视频编解码等应用中可能导致显著的性能损失。《Performance Impact of Unaligned Memory Operations in SIMD Extensions for Video Codec Applications》这篇文章，提出尝试访问未对齐的内存位置时，需要执行重新对齐的过程，这包括读取对齐的内存字、移除不必要的字节、读取相邻的对齐字并丢弃不必要的字节，最后合并提取的部分。这种重新对齐的过程可能会导致性能下降，有时甚至会使向量化处理适得其反。

此外，也存在一些限制：

计算/内存操作平衡无法维持时：向量处理器在执行计算任务时，需要与内存进行数据交换。如果处理器的计算能力很强，但内存的读写速度跟不上，或者反之，内存的带宽很高而处理器的计算速度跟不上，就会造成资源的浪费。这种情况下，内存带宽或处理器的计算能力会成为限制整体性能的瓶颈。
数据未适当映射到内存银行（memory bank）：在向量处理器中，内存通常被划分为多个“内存银行”或“内存模块”，以支持并行访问。如果数据没有被合理地分配到这些内存银行中，就可能导致某些内存银行过载，而其他银行空闲，从而降低内存访问效率，影响整体性能。

3.单指令多数据指令集（SIMD Instruction Sets）

在本节中，我们将讨论 SIMD 指令集设计对数据并行语言实现的影响。

通常， SIMD 单元具有一定位宽的 SIMD 寄存器（例如 SSE 为128 bits 长度），如下图所示，左边是向量寄存器的描述。

对于 Intel AVX，其每个寄存器是 256 bit，可以保存如 8 个 32 bit 的 float32 数或者 int32 数组成的向量。

不同的指令集提供不同的数据类型。例如，SSE 全面支持保存 4 个浮点 float32 数、4个整型 int32 数或 2 个双精度 float64 数。有时，还支持其它数据类型（较小的 int 型，如 8 个 16bit 的 short / ushort，或更小的如 16 个 8 bit 的 char / uchar）。

为了便于表示，我们只考虑固定大小相等（如 4 个字节 byte）的数据类型。在整篇文章中，我们将通过 SIMD 宽度 W 来表示适合单个寄存器的该类型元素的数量。

3.1 内存访问操作（Memory Access）

通常，通过从（到）对齐的地址连续读（或写）元素来加载（或存储）vector 值。有些指令集还允许访问未对齐的地址。

数据访问通常要求地址是“对齐”的，即地址应该是数据类型大小的整数倍。例如，一个整数通常需要在4字节对齐的地址上访问。
如果访问的地址不是对齐的，就称为“未对齐访问”。为了访问未对齐的数据，处理器通常提供了特殊的指令。这些指令专门设计来处理未对齐的数据访问，而不会触发异常。
在某些处理器架构中，如果使用标准的加载（load）或存储（store）指令访问未对齐的地址，处理器会触发一个异常（exception）。异常是一种错误状态，需要操作系统或程序中的异常处理机制来处理。

那么，自然对于未对齐访问通常较慢，因为它们可能涉及到多个 cache line 。此外，对可能未对齐地址的访问通常通过使用特殊指令发出信号，因为对齐的加载/存储指令在未对齐访问时引发异常。使用特殊指令来访问未对齐的数据可以避免异常的发生，从而提高程序的执行效率。然而，这些特殊指令可能在硬件上实现起来更复杂，或者在某些情况下性能不如对齐访问。

现在不少的新架构还支持分散（scatter）或收集（gather）操作，可以使用（可能是非连续的）偏移量向量从（或到）基址加载（存储）。

在没有分散 / 收集指令的架构上，这种非连续访问非常慢。这是因为 vector 元素必须一个接一个地加载到不同的寄存器中，然后增量地移动到目标寄存器中。高效连续访问可以看作是索引向量 {0, 1, …, W - 1} 的一种特殊情况。因此，在我们的矢量化过程中，加载和存储中使用的索引的连续性和对齐是很重要的。

3.2 指针类型与操作（Pointers）

一般来说，将指针存储在 SIMD 寄存器中是不可移植的。在 SSE 的情况下，可以将 4 个指针以32位模式放入 SIMD 寄存器中。如果处理器以 64 位模式执行，则只能将 2 个指针放入 SSE 寄存器中。因此，在 SIMD 寄存器中使用指针的指令并不常见。

在检索相关内容的时候，发现有一个名为 google/Highway 的 C++ 库，用于 SIMD。这个项目的目的就是为了解决特定平台对 SIMD 代码的移植性的问题。

3.3 掩码类型（Masking）

向量化将控制流转换为数据流。修改后，可能会执行在使用控制流的程序的标量版本中不会执行的代码。在矢量化程序中，控制条件被明确地表示为掩模向量 mask 。

控制流到数据流转换的 select 函数使用该掩码在以前的控制流连接处混合两个值，如下图中间 f‘ 用到了 select(mask, s, t) 方法：

从中间到右边的SSE代码，由 mm_cmpgt_ps 产生掩码替换控制流，变为数据流的 mask：

用于某些程序的执行。通过执行：

最终的结果通过 _ mm_blendv_ps(mask, s, t) 实现对两个分支结果的选择，变量 r 包含每个实例的正确值。

一些架构如 Larrabee （这是一个专为视觉计算设计的多核 x86 架构，采用顺序执行的 CPU 核心），有一个专用的掩码寄存器文件来存储这些掩码。此外，每个指令都可以被赋予一个掩码寄存器，该掩码寄存器控制目标寄存器中的哪些向量元素将受该指令的影响。这使得使用选择指令的显式混合变得不必要（注：这句话就是说，有些指令就本身带 mask ，就不需要在对向量单独做 select/blend 指令了）。

3.4 副作用

对于可能产生副作用的操作，事后使用 mask 来屏蔽结果是不够的：必须防止它们在非活动实例（即数据）中执行。这是通过将操作拆分为由 if 语句保护的标量顺序执行来实现的。这段话关于副作用，我是这么理解的：

在原本的算法逻辑中可能是要求保留原始值，后续有用到，那么这时候你在事后再使用 mask 来取舍就不合适了。
某些操作可能对程序状态产生影响。因此，需要在操作执行之前就确保只有需要的实例（active instances）才会执行该操作。

这两种特殊情况，可能就需要考虑分割 SIMD 向量操作提前做条件语句保护，或者分割向量操作为标量操作，规避副作用。

4.数据并行程序（Data-Prallel Programs）

数据并行性是一种并行计算的形式，其中相同的操作被同时应用于多个数据项。这种并行性是通过使用 SIMD（单指令多数据）架构实现的，它允许一个指令同时对多个数据元素进行操作。例如，在计算两个向量的点积时，可以同时对多个成对的元素执行乘法和加法操作。

数据流并行性则侧重于以数据驱动的方式执行不同的操作，这通常在数据流图中看到，其中数据的可用性决定了操作何时发生。

线程或控制并行性则关注于同时执行多个控制流线程，这在多线程编程中很常见，不同的线程可以独立执行不同的任务。

SIMD 架构特别适合于指令级并行性，因为它可以在不同的数据上并发地应用相同的操作。因为相同的指令被应用于不同的数据。这种并行性在图像处理、信号处理、科学计算等领域中非常有用，可显著提高处理大量数据的效率。

我们的数据并行程序模型接近 CUDA 和 OpenCL 的模型。

计算单元的具体定义因硬件供应商的不同而不同。在 AMD 硬件中，每个计算单元包含许多“流核”（有时称为 SIMD 引擎），然后包含单独的处理元素。每个流内核都执行 VLIW 4或 5 宽度的 SIMD 指令。有关 ATI 硬件的概述，请参见下图。

在 NVIDIA 硬件中，他们称计算单元为 stream multiprocessors（SM），在一些文档中称为 CUDA 核心。反正无论是是 AMD 亦或是 NVIDIA，执行最底层 SIMD VLIW 指令的都是具有很复杂的硬件层次结构。

下面来看一个具体的例子。在我们的设置中，数据并行程序由函数 f 给出如下图。执行数据并行程序 f 执行 N 个 f 的实例，这些实例的时间顺序未指定。

此外，它们中的一些可以并行运行。f 的每个实例（即数据）都以实例 ID 如 tid = get_local_id(0) 作为参数获取实例的编号。对于 f 的每个实例，tid 的值是两两不同的，范围从 0 到整个任务需要处理的总元素个数 N。

一个已经利用了一些并行性的直接实现将实例 ID 范围细分为 T 个大小相等的部分，并将它们分配给 T 个线程（内核）。在一个线程内，N / T 个 f 实例依次运行。在本文中，我们还想利用向量指令来开发核内并行性，即图上的函数 f' 和 f_sse 。

在本文中，除了使用上线程特性，还想利用向量指令来开发核内并行性。因此，我们将把 f 转换为同时执行 W 个实例的函数 f'，其中 W 是处理器 SIMD 寄存器的宽度：对整个函数 f 进行矢量化。然后，多线程实现按顺序对每个线程应用 f 函数 ( N / W ) / T 次的代码如下：

请注意，不同内核之间的多线程与 SIMD 向量化是正交的。换句话说，多线程执行（由多个执行线程组成的工作组并行执行内核函数）和SIMD向量化（利用SIMD指令同时处理多个数据元素）这两种并行执行方式可以独立使用，它们之间没有直接的依赖关系，可以组合在一起以提高性能。

4.1 程序表示（Program Representation）

注：这里讲的是数据并行的程序表示，或者说写法或者在编译器中间的一种表达形式。这里可能和本文没有直接关系，可以忽略。

我们认为函数 f 以一种类型的低级表示形式给出。函数表示为指令的控制流图。此外，我们要求 f 是 SSA 形式的，即每个变量都有一个静态赋值，变量的每次使用都受其定义的支配。

这种程序表示的一个突出的例子是 LLVM bit code 如下：

文章作者在研究向量化问题的时候，将类型和指令限制在如下图所示的语言子集中，这也是前文标量程序中所用到的。而其它指令，如跳转或算术和比较操作符都是直接的，可以省略了。

这种程序表示很好地反映了当今指令集架构对 SIMD 支持的共识。

标量数据类型（int和float）也有向量化的形式（σ），我的理解是对其可以做 broadcast 操作变为向量。然而，没有指针的向量。gep 指令（即“get element pointer”获取元素指针）执行地址算术，因此不能被向量化。
load（store）取一个基地址并从这个地址连续地读取（写入）向量的元素。
bool 类型是特殊的（我们不允许对它取指针），因为在具有隐式和显式混合的 SIMD 架构中，它的表示形式不同。
这里我这么理解的：可能有为了效率的专用的 mask 向量寄存器，即在一个寄存器中打包多个布尔值。这就导致了 bool 类型的表示方法在 SIMD 架构中可能与标量架构不同。这种差异可能会影响 bool 类型数据的操作和存储方式。因此不允许对布尔类型取指针。这是为了避免因表示方法的差异而导致的潜在问题或复杂性。
函数 tid 返回运行实例的实例ID。
φ函数（Phi Function）代表 SSA 中的常见 φ 函数。在控制流图中，φ函数是一种特殊的操作，用于在多路径合并点合并变量的值。
arg(i) 访问函数 f 的第 i 个参数。我们假设所有指向函数 f 的指针参数都与 SIMD 寄存器大小对齐。

参考

SIMD Vector GPU, Computer Architecture | course.ece.cmd.edu
https://course.ece.cmu.edu/~e...
Digital Design & Computer Arch. Lecture 20: SIMD Processors | ethz.ch
https://safari.ethz.ch/digita...
Intrinsics for Intel® Advanced Vector | Intel Extensionshttps://portal.nacad.ufrj.br/...
Intel® Intrinsics Guide | Intel https://www.intel.com/content...
MMX Technology extension to the Intel arichtecture | safari.ethz.cn https://safari.ethz.ch/archit...
Memory Accesss | SIMD for C++ Developers
http://const.me/articles/simd...
Larrabee: A Many-Core x86 Architecture for Visual | cs.wisc.edu https://pages.cs.wisc.edu/~ma...
Performance Impact of Unaligned Memory Operations in SIMD Extensions for Video Codec Applications https://upcommons.upc.edu/bit...
Basics of SIMD Programming, Cell programming | cvut.cz https://ftp.cvut.cz/kernel/pe...

作者：开心的派大星
来源：NeuralTalk

推荐阅读

欢迎大家点赞留言，更多Arm技术文章动态请关注极术社区嵌入式AI专栏欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。