4.2 向量体系结构

执行可向量化应用最高效的方式，就是使用向量处理器。

——Jim Smith，ISCA，1994 年

向量体系结构先把分散在内存中的数据元素收集到大型、顺序组织的寄存器堆中，在这些寄存器上执行操作，再把结果分散写回内存。一条指令可以对独立的数据元素执行几十次寄存器到寄存器的操作。

这些大型寄存器堆起着由编译器控制的缓冲区的作用，既能隐藏内存延迟，又能有效利用内存带宽。所有向量加载和存储操作都采用深流水线，因此每个向量只需支付一次较长的内存延迟，而不必让每个元素分别承担这一延迟。例如，加载一个含 32 个元素的向量时，较长的内存延迟可以分摊到这 32 个元素上。向量程序力求使存储系统持续保持忙碌。

随着功耗限制的重要性日益增加，向量体系结构能够在不承担乱序超标量处理器的能耗与设计复杂度的情况下提供良好性能，这使它更具吸引力。向量指令能够提高简单顺序标量处理器的性能，而不显著增加能耗需求和设计复杂度。许多在复杂乱序设计上运行良好的程序，如果直接用向量指令表达其中的数据级并行性，执行效率会更高（Kozyrakis and Patterson, 2002）。

RV64V 扩展

我们先介绍一个简单的向量处理器，如图 4.1 所示。它大体借鉴了近 50 年前的早期超级计算机之一 Cray-1，但指令集采用 RISC-V 的向量扩展 RVV。我们称它为 RV64V：RV64 表示 64 位 RISC-V 基础指令集，V 表示向量扩展。下面使用 RV64V 的一个简化子集来说明向量处理器的工作原理。

RV64V 的主要组成部分如下。

• 向量寄存器。 RV64V 有 32 个向量寄存器，每个保存一个向量。向量寄存器堆必须有足够多的端口，才能向所有向量功能单元提供数据。

图内术语：Main memory＝主存；Vector registers＝向量寄存器；Scalar registers＝标量寄存器；FP add/subtract＝浮点加／减；FP multiply＝浮点乘；FP divide＝浮点除；Integer＝整数；Logical＝逻辑；Vector load/store＝向量加载／存储。

这些端口使针对不同向量寄存器的操作能够高度重叠。向量寄存器堆至少需要 16 个读端口和 8 个写端口，并通过一对交叉开关将这些端口连接到各功能单元的输入和输出。增加寄存器堆带宽的一种方法，是采用多个存储体；对于较长的向量，这种方法很有效。

• 向量功能单元。 每个单元都采用完整的流水线，每个时钟周期可以开始一次新操作。控制逻辑需要检测功能单元的结构冒险，以及寄存器访问的数据冒险。图 4.1 包含 5 个功能单元。为简化讨论，本节主要考虑浮点功能单元。
• 向量加载／存储单元。 向量存储单元负责向量在内存与寄存器之间的传送。在最初的延迟之后，这个单元可以每个时钟周期加载或存储一个字。通常，标量加载和存储也由它完成。
• 标量寄存器。 与 RV64G 相同，RV64V 有 31 个通用寄存器和 32 个浮点寄存器。它们可以向向量功能单元提供数据，也可以提供传送给向量加载／存储单元的地址。功能单元在读入标量操作数时，会将其锁存到输入端。
• 最大向量长度。 与下一节介绍的 SIMD 扩展不同，每条向量指令处理的元素个数并不由操作码指定。最大向量长度 VLMAX 取决于具体实现，因此不同实现可以在采用同一指令集的同时，支持不同的最大向量长度。

图 4.2 列出了 RV64V 向量指令。指令的输入可以来自向量寄存器，也可以来自标量整数寄存器 xi 或标量浮点寄存器 fi。后缀 .vv 表示两个向量操作数；.vx 表示一个向量和一个标量整数寄存器；.vi 表示一个向量和一个立即数；.vf 表示一个向量和一个标量浮点寄存器。汇编器通常能根据操作数推断后缀。在指令发射时，标量操作数会被复制到相应的功能单元。

译注： 本表按原书保留指令名称和寄存器表达式。原书表内的 setvl 与后文代码中的 vsetvl、图注的 vctype 与正文的 vtype、图注的 .vs/.sv 与正文的 .vx/.vf 并不一致；vpmand 也按表中原样保留。这些是原书对 RV64V 的简化描述，不能直接作为可汇编的现行 RVV 指令规范。

传统向量体系结构在处理窄数据类型时效率不高，而这些类型在实际应用中很常见。同样大小的寄存器既可以保存 32 个 64 位元素，也可以保存 128 个 16 位元素或 256 个 8 位元素。让硬件支持不同数据宽度，对媒体和科学应用都很有价值。

注意，图 4.2 中的 RV64V 指令省略了数据宽度！RV64V 的一项创新，是把数据宽度与每个向量寄存器关联，而不是像通常那样由指令提供。程序在执行向量指令前对所用寄存器进行配置，其中状态寄存器的标准元素宽度（standard element width，SEW）字段指明元素的位数。

例如，SEW 为 64 就表示 64 位元素。图 4.3 列出了支持的宽度。

采用动态寄存器类型（dynamic register typing）的一个原因是：传统向量体系结构需要许多指令才能支持如此多的数据宽度。考虑图 4.3 中的各种宽度，如果没有动态寄存器类型，图 4.2 的指令表就会长得多！类型只需设置一次，不必在每条指令中重复指定。

动态指定类型还允许将向量寄存器重新分组。例如，假设整个寄存器堆有 1024 字节，而计算只需要 4 个由 64 位浮点数组成的向量；便可以将其配置为 4 个各有 256 字节的向量寄存器，每个保存 32 个元素。将长度乘数 LMUL 设为 8，就把每 8 个寄存器组合为一个寄存器组，使有效寄存器数变为 4 个。

向量体系结构受到的一项批评是，更多的状态会拖慢上下文切换。在这里的 RV64V 实现中，状态从 $2\times32\times8=512$ 字节增加到 $2\times32\times8+1024=1536$ 字节，扩大为原来的 3 倍。为了降低切换上下文的代价，处理器记录软件自上次上下文切换以来是否写过向量寄存器。

动态指定寄存器类型的第三个好处是，不同宽度操作数之间的转换，可以根据寄存器配置，作为算术指令的一部分隐式完成，而不必增加显式转换指令。下一节将给出这一优点的例子。

vle 和 vse 分别加载和存储整个向量，其操作数包括一个向量寄存器和一个保存基地址的 RV64G 寄存器。实际向量长度由 vl 给出，不一定等于 VLMAX；vtype 记录向量配置。谓词 pi 则用于对含 IF 语句的代码实施掩码控制。

向量指令可以采用多种实现方式，包括同时处理多个元素。较慢但较宽的功能单元可以降低功耗。由于各元素的操作彼此独立，增加功能单元数量不需要像超标量处理器那样，进行代价高昂的依赖检查。

向量处理器如何工作：一个例子

观察 RV64V 的向量循环，是理解向量处理器最好的方式。考虑本节贯穿使用的典型运算 $Y=a\times X+Y$，其中 X 和 Y 是最初驻留在内存中的向量，a 是标量。单精度形式称为 SAXPY，即单精度 $a\times X$ 加 Y；双精度形式称为 DAXPY。这是 Linpack 基准的内层循环（Dongarra et al., 2003）。Linpack 是一组线性代数例程，而 Linpack 基准由执行高斯消元的例程组成。

先假定向量寄存器可保存 32 个元素，正好等于这次运算的向量长度；后面会放宽这一假设。

例题

假定 X 和 Y 各含 32 个元素，x5 和 x6 分别保存它们的起始地址。写出在 RV64G 和 RV64V 上执行上述计算的代码。

解答

RV64G 代码如下：

      fld    f0,a            # 加载 a
      addi   x28,x5,#256     # 计算最后的地址
Loop: fld    f1,0(x5)        # 加载 X[i]
      fmul.d f1,f1,f0        # a * X[i]
      fld    f2,0(x6)        # 加载 Y[i]
      fadd.d f2,f2,f1        # a * X[i] + Y[i]
      fsd    f2,0(x6)        # 存储 Y[i]
      addi   x5,x5,#8        # 递增 X 的索引
      addi   x6,x6,#8        # 递增……（原注未完）

RV64V 代码则为：

vsetvl a3,a0,e64,m8,ta,ma   # 4 个 64 位向量寄存器（SEW=64，LMUL=8）
fld    f0,a               # 加载标量 a
vle64  v0,(x5)            # 加载向量 X
vfmul  v8,v0,f0           # 向量—标量乘法
vle64  v16,(x6)           # 加载向量 Y
vfadd  v24,v8,v16         # 向量—向量加法
vse64  v24,(x6)           # 存储和

译注： 原页的标量代码到最后一条 addi 即结束，末行注释也不完整，没有列出循环分支。上面的向量代码实际列出 7 条指令，下一页正文却称为 8 条。

在向量代码中，汇编器会把 vfmul 翻译为 vfmul.vf，因为其中一个操作数是标量浮点寄存器；vfadd 则成为 vfadd.vv，因为两个操作数都是向量。开头的配置指令将寄存器堆设置为 4 个元素宽度为 64 位的向量寄存器。

与标量代码动态执行的 258 条指令相比，向量代码只需执行 8 条指令。向量指令每次处理 32 个元素，而且消除了标量循环中占近一半的循环控制开销。

当编译器能产生向量指令，而且程序的大部分时间都用于执行这些向量指令时，就称该程序已经向量化；能够这样转换的程序称为可向量化程序。循环迭代之间的数据依赖（称为循环携带依赖，loop-carried dependence）可能阻止向量化，4.5 节将进一步讨论这一问题。

另一个重要差别是流水线互锁的频率。在标量 RV64G 代码中，fadd 必须等待 fmul，fsd 又必须等待 fadd。向量处理器只需在第一个元素到达之前停顿，之后的元素就可以连续流过流水线。这种逐元素转发称为向量链接（chaining）。因此，标量代码因这些依赖产生的停顿可能是向量代码的 32 倍。通过附录 H 介绍的软件流水线、循环展开或乱序执行，可以减少标量代码的停顿，但不能消除两种代码对指令带宽需求的巨大差别。

向量执行时间

向量指令序列的执行时间取决于三个因素：向量操作的长度、指令之间的结构冒险，以及数据依赖。功能单元接受新操作数并产生新结果的速率称为启动速率（initiation rate）。知道向量长度和启动速率，就可以估计向量指令的执行时间。

现代向量处理器通常有多个通道，每个时钟周期可以产生两个或更多结果；有些功能单元则并未完全流水线化。先考虑简单的 RV64V：它只有一个通道，每个时钟周期处理一个元素。因此，一条向量指令所需的时钟周期数大致等于向量长度。

为了简化对指令序列的分析，可以把那些有可能一起执行的向量指令组成一个编队（convoy）。同一编队内的指令不能发生结构冒险，否则就必须串行执行。在前面的例子中，加载与乘法指令可以放进同一个编队。我们通过统计编队数来估计性能，并暂时假定：一个编队执行完毕后，才开始执行其他标量指令或向量指令。

存在写后读依赖的指令仍可通过链接放进同一个编队。一个元素一旦产生，就可以直接转发给需要它的功能单元，而不用等到整个向量寄存器写完。这样，同一个时钟周期就可以读写同一向量寄存器中的不同元素。早期向量处理器的链接存在时序限制，类似标量流水线中的转发限制；现代处理器通常支持灵活链接，只要没有结构冒险，就可以把任意活动的向量操作链接起来。本章始终假定支持灵活链接。

我们用 chime 作为编队执行的时间单位。含 m 个编队的序列需要 m 个 chime；对于向量长度为 n、每个时钟周期处理一个元素的简单实现，执行时间约为 $m\times n$ 个时钟周期。

chime 模型忽略了依赖具体处理器的若干开销，因此对于某些向量长度，它只是粗略估计；向量越长，估计通常越准确。使用 chime 而不直接使用“每个结果的时钟周期数”，正是为了明确表示我们忽略了这些开销。

例如，实际处理器通常每个时钟周期只能发射一条指令，这会使 chime 模型低估执行时间。只要向量长度远大于编队中的指令数，仍可近似认为一个编队占用一个 chime。

例题

考虑下列向量指令序列。假定每种功能单元各有一个，忽略指令发射开销，给出编队划分、chime 数和每次浮点操作所需的时钟周期数。

vle64 v0,x5               # 加载向量 X
vfmul v1,v0,f0            # 向量—标量乘法
vle64 v2,x6               # 加载向量 Y
vfadd v3,v1,v2            # 向量—向量加法
vse64 v3,x6               # 存储和

解答

第一条加载可以与乘法链接。第二条加载与第一条加载存在结构冒险，因此必须开始一个新编队；加法可以与第二条加载链接。存储又与第二条加载存在结构冒险，因此需要第三个编队：

因此，共需 3 个 chime。每个结果需要两次浮点运算，所以平均每次浮点运算需要 1.5 个时钟周期。现实中，第一条加载和乘法通常需要两个时钟周期才能发射，而不是一个周期。若向量长度为 32，估计总时间为 $3\times32=96$ 个时钟周期，这一点发射开销相对较小。

比指令发射开销更重要的是启动时间，即填满流水线所需的延迟。为便于举例，我们采用 Cray-1 的流水线深度；现代处理器的流水线通常更深，尤其是加载流水线。假定所有功能单元都完全流水线化：浮点加法启动时间为 6 个时钟周期，乘法为 7 个时钟周期，除法为 20 个时钟周期，向量加载为 12 个时钟周期。

掌握这些向量基础之后，接下来几个小节将介绍若干优化：它们或是提高性能，或是扩大能够在向量体系结构上良好运行的程序范围。具体来说，要回答以下问题：

• 向量处理器怎样以高于每个时钟周期一个元素的速度执行单个向量？每周期处理多个元素可以提高性能。
• 当向量长度不等于最大向量长度（mvl）时，怎样处理？多数应用中的向量长度与体系结构的向量长度不同，因此必须为这一常见情况提供高效方案。
• 待向量化的代码中含有 IF 语句时怎么办？如果能高效处理条件语句，就能向量化更多代码。
• 向量处理器对存储系统有何要求？缺少足够的存储器带宽，向量执行可能徒劳无功。
• 怎样处理多维矩阵？这种数据结构很常见，必须能对它向量化，向量体系结构才具有广泛适用性。
• 怎样处理稀疏矩阵？这种常见的数据结构也必须能够向量化。
• 怎样为向量计算机编程？如果体系结构创新与编程语言及其编译器不相适应，就可能无法得到广泛使用。

本节其余部分和附录 G 将回答这些问题。

多个通道：每个时钟周期处理多个元素

向量体系结构的一项关键优势是：一条简短的指令就能指定几十个相互独立的操作，所需的指令位数却与标量指令相同。向量指令的语义允许以深流水线、并行功能单元阵列，或者两者的组合来实现这些操作。图 4.4 以向量加法说明了并行执行方式。

RV64V 的向量算术运算具有一个简单性质：向量的第 N 个元素只与其他向量的第 N 个元素进行运算。这使多通道向量单元的实现大为简化。

图内标记 A、B、C 表示向量；Element group＝元素组；加号表示加法功能单元。

就像增加公路车道可以提高车流量一样，增加向量通道（lane）可以提高峰值性能。图 4.5 给出了一个四通道向量单元。对长度为 32 的向量，每个 chime 只需 8 个时钟周期。要充分利用多通道，向量必须足够长；否则，硬件消耗指令的速度会很快，需要更多指令级并行性和足够的指令带宽来供给它。

每个通道包含向量寄存器堆的一部分，以及每种向量功能单元的一条流水线。每个时钟周期，各通道共同处理一个元素组。例如，通道 0 保存所有向量寄存器的第 0 个元素，因此这些元素的源和目的位置都在本通道内。

图内术语：Lane＝通道；FP add pipe＝浮点加法流水线；FP multiply pipe＝浮点乘法流水线；Vector register elements＝向量寄存器元素；Vector load-store unit＝向量加载／存储单元。

避免通道之间的通信，可以减少连线和寄存器端口需求。这解释了向量处理器为何能达到每个时钟周期 64 次操作：例如，16 个通道每个周期分别完成两次算术操作和两次加载／存储操作。

增加通道只需增加少量控制逻辑，而且无须修改已有机器码。设计者可以据此权衡面积、频率、电压和能耗。例如，将时钟频率减半、通道数加倍，可以保持峰值性能不变。

向量长度寄存器：处理长度不等于 32 的循环

前面假定向量长度恰好等于最大向量长度 32，但实际程序很少如此。向量长度在编译时可能未知，也可能在同一段程序的不同次执行中变化：

for (i = 0; i < n; i = i + 1)
    Y[i] = a * X[i] + Y[i];

所有向量操作的大小都取决于 n，而 n 可能到运行时才知道。它还可能是包含上述循环的过程的一个参数，因此会在执行过程中改变。

向量长度寄存器 vl 控制所有向量操作，包括内存操作。它的值不得超过最大向量长度；最大长度保存在 VLMAX 寄存器中。这样，新一代实现就可以增加向量长度而无须增加指令集。相比之下，SIMD 扩展往往需要扩充指令集，才能利用更宽的硬件。

当 n 大于最大向量长度时，可以采用 strip mining，即把长向量循环分段处理，如图 4.6 所示。循环先后处理多个最大长度的向量，并额外处理一个不足最大长度的余数段。RISC-V 无须为余数单独编写一个循环：setvl 将 vl 和另一个目的寄存器同时设为 VLMAX 与 n 中的较小者。

如果需要执行的迭代数大于 n，就尽可能快地一次处理 VLMAX 个元素，将 vl 设为 VLMAX。如果 n 小于 VLMAX，最后一次只处理剩余的 n 个元素，将 VLMAX 设为 n。setvl 写入另一个标量寄存器的结果，可以用于循环的辅助管理操作。

vsetvl a3,a0,e64,m16,ta,ma  # 2 个 64 位向量寄存器（SEW=64，LMUL=16）
fld    f0,a                # 加载标量 a
loop:
vsetvl t0,a0               # vl = t0 = min(mvl,n)
vle64  v0,x5               # 加载向量 X
slli   t1,t0,3             # t1 = vl * 8（字节）
add    x5,x5,t1            # X 的指针增加 vl * 8
vfmul  v0,v0,f0            # 向量—标量乘法
vle64  v1,x6               # 加载向量 Y
vfadd  v1,v0,v1            # 向量—向量加法
sub    a0,a0,t0            # n -= vl（t0）
vse64  v1,x6               # 将和存入 Y
add    x6,x6,t1            # Y 的指针增加 vl * 8
bnez   a0,loop             # 若 n != 0，则重复

译注： 原文确写“迭代数大于 n”和“将 VLMAX 设为 n”，与前文 vl = min(VLMAX,n) 的定义不一致。按这一定义，前一条件应比较 VLMAX，最后不足一个完整向量时应将 vl 设为 n。

图内的 j 是分段循环索引，i 是原循环索引；MVL／VLMAX 表示最大向量长度。

向量掩码寄存器：处理 IF 语句

根据 Amdahl 定律，如果程序只有一小部分能向量化，或可向量化比例只是中等，整体加速比就会非常有限。向量化程度较低的两个主要原因，是循环内的条件语句（IF 语句）以及稀疏矩阵。IF 语句给循环引入控制依赖，因此，仅用目前介绍的技术，不能让这种循环以向量方式运行。同样，现有功能也无法高效实现稀疏矩阵。本小节先讨论条件执行，稀疏矩阵留待后文。

考虑下面的循环：

for (i = 0; i < 64; i = i + 1)
    if (X[i] != 0)
        X[i] = X[i] - Y[i];

由于循环体有条件地执行，这个循环通常不能向量化。不过，如果只对满足 X[i] 非零的迭代执行循环体，就可以把减法向量化。实现这一能力的常见扩展，是向量掩码控制。

向量掩码是一个布尔向量，决定相应元素的操作是否执行，类似第 3 章的标量谓词执行。掩码元素为 1 时执行相应操作；为 0 时，目的寄存器中的对应元素保持不变。RVV 使用 v0 作为掩码，而不使用单独的掩码寄存器；v0 每个元素的最低有效位（位 63）用于控制相应操作。

假定 X 和 Y 的起始地址分别在 x5 和 x6 中，前面的循环可以写为：

vsetvl a3,a0,e64,m8,ta,ma # 4 个 64 位向量寄存器（SEW=64，LMUL=8）
vle64  v8,(x5)           # 将向量 X 加载到 v8
vle64  v16,(x6)          # 将向量 Y 加载到 v16
fmv.d.x f0,x0           # 将浮点零放入 f0
vfne   v0,v8,f0          # 若 v8(i) != f0，则 v0<63>(i) = 1
vfsub  v8,v8,v16,v0.t    # 在向量掩码 v0 控制下执行减法
vse64  v8,x5             # 将结果存入 X

译注： 原文写作“least-significant bit (bit 63)”，代码注释也使用 v0<63>。对通常从 0 开始编号的 64 位值，最低有效位应为位 0，因此这里的文字与位号存在矛盾。本文不将该示意描述视为现行 RVV 掩码布局的规范。

将条件分支转换为直线式条件执行代码的编译技术，称为 IF 转换（IF-conversion）。

使用向量掩码寄存器仍有开销。在标量体系结构中，条件执行指令即使条件不成立，也仍需要执行时间。不过，去掉分支及相关控制依赖后，即使有时做了无用功，条件执行指令仍可能更快。同样，采用向量掩码的向量指令，即使某些元素的掩码为零，也仍需同样的执行时间。尽管掩码中可能有大量零，使用向量掩码控制仍可能明显快于标量方式。

4.4 节将说明，向量处理器与 GPU 的一个差别，是处理条件语句的方式。向量处理器把谓词寄存器纳入体系结构状态，依靠编译器显式操作掩码寄存器。GPU 则用硬件操作软件不可见的内部掩码寄存器，达到相同效果。两者都有相同的代价：无论对应掩码位为 0 还是 1，硬件都花时间执行该向量元素，因此使用掩码会降低有效的 FLOP/s。

存储体：为向量存储系统提供带宽

向量加载／存储单元的行为远比算术功能单元复杂。加载的启动时间，是把第一个字从内存送入寄存器所需的时间。如果之后的向量元素能够无停顿地供应，向量启动速率就等于取出或存入新字的速率。与较简单的功能单元不同，这个速率未必能达到每时钟周期一个元素，因为存储体造成的停顿可能降低有效吞吐量。

现代向量处理器的内存启动延迟通常超过 100 个时钟周期，远高于算术单元。前面为 RV64V 使用的 12 个周期来自 Cray-1。较新的向量处理器采用缓存来降低这一延迟。

为了每个时钟周期提供一个字，存储系统通常由多个存储体组成。大量存储体还有助于同时处理按行和按列访问的数组。需要的并不只是简单的交错存储，而是具有独立地址控制的存储体，原因有三点：

1. 许多向量处理器每个时钟周期需要执行多次加载或存储；而单个存储体的周期可能相当于多个处理器时钟周期，因此需要独立的地址和控制。
2. 向量处理器需要支持非顺序访问，这要求各存储体能独立寻址。
3. 多处理器共享同一个存储系统时，各处理器会产生独立的访问流。

例题

Cray T90 的最大配置 Cray T932 有 32 个处理器，每个处理器每个时钟周期可以产生 4 次加载和 2 次存储。处理器时钟周期为 2.167 ns，存储系统所用 SRAM 的周期为 15 ns。要让全部处理器都以完整的存储器带宽运行，至少需要多少个存储体？

解答

每个周期的最大访存次数是 $32\times6=192$。每个 SRAM 存储体会忙碌 $15/2.167=6.92$ 个处理器时钟周期，向上取整为 7。因此，至少需要 $192\times7=1344$ 个存储体！

Cray T932 实际上只有 1024 个存储体，因此早期型号不能同时向所有处理器持续提供满带宽。后来的内存升级用流水线化的同步 SRAM 代替了 15 ns 的异步 SRAM，将存储周期缩短了一半以上，从而提供了足够的带宽。

从更高层次看，向量加载／存储单元与标量处理器中的预取单元具有相似作用：它们都试图通过向处理器持续提供数据流来满足带宽需求。

步长：在向量体系结构中处理多维数组

一个向量中相邻的元素，在内存中的位置未必连续。考虑下面这段直接实现矩阵乘法的 C 代码：

for (i = 0; i < 100; i = i + 1)
    for (j = 0; j < 100; j = j + 1) {
        A[i][j] = 0.0;
        for (k = 0; k < 100; k = k + 1)
            A[i][j] = A[i][j] + B[i][k] * D[k][j];
    }

我们可以把 B 的每一行与 D 的每一列相乘的操作向量化，并对以 k 为索引的内层循环实施 strip mining。

为此，必须考虑怎样寻址 B 中相邻的元素和 D 中相邻的元素。为数组分配内存时，需要将其线性化，按行优先顺序（如 C）或列优先顺序（如 Fortran）布局。这意味着行元素或列元素必有一类在内存中不连续。例如，上面的 C 代码采用行优先顺序，内层循环相邻两次迭代访问的 D 元素间隔为一行的大小乘以 8（每个元素的字节数），共 800 字节。第 2 章说明了分块技术如何改善基于缓存的系统的局部性；对于没有缓存的向量处理器，则需要另一种技术来获取在内存中不连续的向量元素。

要收集到同一个向量寄存器中的相邻元素之间的距离，称为步长（stride）。在这个例子中，矩阵 D 的步长为 100 个双字（800 字节），矩阵 B 的步长为 1 个双字（8 字节）。如果采用 Fortran 的列优先顺序，两者的步长就会互换：D 中相邻元素的步长为 1，即 1 个双字（8 字节）。

B 的步长则为 100，即 100 个双字（800 字节）。因此，如果不重排循环，编译器就无法同时消除 B 和 D 中相邻访问元素之间的较大间隔。

向量一旦加载到向量寄存器中，其元素在逻辑上就连续了。因此，只需提供支持步长的向量加载和存储操作，向量处理器就能处理大于 1 的非单位步长。能够访问不连续的内存位置，并将它们整理成稠密结构，是向量体系结构的重要优势之一。

缓存天然适合单位步长的数据访问。对于按单位步长访问的大型科学数据集，增加缓存块大小可以降低未命中率；但对于非单位步长访问，增加块大小甚至可能产生负面效果。分块技术能够解决其中一些问题（见第 2 章），但对某些问题，高效访问不连续数据仍是向量处理器的优势，4.7 节将给出实例。

RV64V 按字节寻址，因此本例的步长为 800。这个值必须动态计算，因为编译时可能不知道矩阵大小；而且与向量长度一样，同一语句在不同次执行时，矩阵大小也可能改变。向量步长和起始地址都可以放在通用寄存器中，随后用 vlse（带步长的向量加载）把向量读入寄存器。存储非单位步长的向量时，则使用 vsse（带步长的向量存储）。

支持大于 1 的步长会使存储系统复杂化。引入非单位步长后，就可能频繁访问同一个存储体。多个访问争用同一存储体时，会发生存储体冲突，使某个访问停顿。原书给出的冲突条件是：

译注： 原式分母写的是“Least common multiple”，即最小公倍数。若连续元素地址按模 B 映射到 B 个存储体，步长 S 以元素为单位，则再次访问同一存储体的间隔为 $B/\gcd(B,S)$，不是 $B/\operatorname{lcm}(B,S)$。因此，在每周期启动一次访问、忙碌时间以周期计的假设下，相应冲突条件应为 $B/\gcd(B,S)<T_{\mathrm{busy}}$。例如 B = 8、S = 1 时，回到同一存储体应间隔 8 次访问，而原式给出 1；原式不能据以判断冲突。

例题

假设有 8 个存储体，存储体忙碌时间为 6 个时钟周期，总内存延迟为 12 个周期。加载一个含 64 个元素的向量，步长为 1 时需要多久？步长为 32 呢？

解答

因为存储体数大于存储体忙碌时间，步长为 1 时，加载需要 $12+64=76$ 个时钟周期，即平均每个元素 1.2 个周期。最坏的步长是存储体数量的整数倍，步长为 32、存储体数为 8 就属于这种情况。除第一次以外，每次访问都会与前一次访问冲突，必须等待 6 个周期的存储体忙碌时间。总时间为 $12+1+6\times63=391$ 个时钟周期，即每个元素 6.1 个周期，慢了约 5 倍！

聚集与散布：在向量体系结构中处理稀疏矩阵

前面提到，稀疏矩阵十分常见，因此需要让使用稀疏矩阵的程序也能以向量方式执行。稀疏矩阵中的向量元素通常以某种紧凑形式保存，再通过间接寻址访问。考虑一个简化的稀疏结构，代码可能如下：

for (i = 0; i < n; i = i + 1)
    A[K[i]] = A[K[i]] + C[M[i]];

这段代码对数组 A 和 C 执行稀疏向量求和，使用索引向量 K 和 M 指定 A、C 中的非零元素。A 和 C 的非零元素个数必须相同，都是 n 个，所以 K 和 M 的大小也相同。

支持稀疏矩阵的主要机制是使用索引向量的聚集／散布操作。这些操作用于在稀疏矩阵的压缩表示（不包含零）与普通表示（包含零）之间转换。聚集操作接受一个索引向量，将基地址与索引向量中的偏移量相加，以这些地址取出元素，形成向量寄存器中的一个稠密向量。完成对稠密向量的操作之后，散布存储使用同一个索引向量，将稀疏向量按展开形式写回内存。支持这种操作的硬件称为聚集／散布硬件，几乎所有现代向量处理器都具有它。RV64V 对应的指令是 vloxe（索引向量加载或聚集）和 vsoxe（索引向量存储或散布）。例如，若 x5、x6、x7 和 x28 保存上述各向量的起始地址，内层循环可以写成：

vsetvl a3,a0,e64,m8,ta,ma  # 4 个 64 位向量寄存器（SEW=64，LMUL=8）
vle64  v0,x7              # 加载 K[]
vloxe64 v8,x5,(v0)        # 加载 A[K[]]
vle64  v16,x28            # 加载 M[]
vloxe64 v24,x6,(v2)       # 加载 C[M[]]
vadd   v8,v8,v24          # 相加
vsoxe64 v8,x5,(v0)        # 存储 A[K[]]

译注： 原页先把 M 加载到 v16，随后访问 C[M[]] 的指令却使用 v2。上面的代码保留原书；按其前后数据流，此处索引寄存器应与保存 M 的寄存器一致。

这种技术允许含稀疏矩阵的代码以向量方式执行。简单的向量化编译器无法自动向量化上述源代码，因为它不知道 K 中的元素是否互不相同，也就不知道迭代之间是否没有依赖。此时需要程序员给出指示，告诉编译器以向量方式执行这个循环是安全的。

虽然索引加载和存储（聚集和散布）能够流水线化，但其速度通常明显低于非索引加载或存储，因为在指令开始时还不知道要访问哪些存储体。

此外，为支持聚集和散布，寄存器堆还必须提供向量单元各通道之间的通信。

聚集或散布的每个元素都有独立地址，因此不能成组处理，而且存储系统的许多位置都可能发生冲突。即使系统采用缓存，每次独立访问仍会产生显著延迟。不过，正如 4.7 节将展示的，针对这种情况专门设计并投入更多硬件资源，比起对这些不可预测的访问放任不管，可以获得更好的存储系统性能。

4.4 节将说明，从没有专门指令把地址限制为连续这一意义上看，GPU 的所有加载都是聚集，所有存储都是散布。为把可能很慢的聚集／散布转换为效率更高的单位步长访存，GPU 硬件会在执行时尝试识别连续地址。

向量体系结构的编程

向量体系结构的一个优势，是编译器能够在编译时告诉程序员某段代码能否向量化，并且常常提示不能向量化的原因。这种直观的执行模型使其他领域的专家也能学会：通过修改代码，或在可以假定操作互相独立时向编译器提供提示，来改进性能；聚集／散布数据传输就是一例。编译器和程序员互相提示如何提高性能，正是这种对话简化了向量计算机的编程。

今天，决定程序能否成功以向量方式运行的主要因素，是程序本身的结构：循环是否有真数据依赖（见 4.5 节）？能否通过重构消除这些依赖？这既受所选算法影响，也在一定程度上受编码方式影响。

为了解科学计算程序能够达到怎样的向量化程度，我们考察 Perfect Club 基准的结果。图 4.7 显示了两个代码版本在 Cray Y-MP 上执行时，以向量方式完成的操作比例。第一个版本仅由编译器优化原始代码，第二个版本则大量使用 Cray Research 程序员团队提供的提示。多项向量处理器应用性能研究表明，不同程序的编译器向量化程度差异很大。

对于编译器自身难以充分向量化的程序，加入大量提示的版本显著提高了向量化程度。所有程序现在都超过 50%，中位数由约 70% 提高到约 90%。