# G.4 提高向量性能 本节将在第 4 章的基础上，更深入地介绍提高向量处理器性能的技术。 ## 深入探讨向量链接 早期的向量链接实现类似转发，但这会限制链接中源指令和目的指令的执行时序。较新的实现采用**灵活链接**（flexible chaining）：只要不产生结构冒险，一条向量指令基本上可以与任何其他正在执行的向量指令链接。灵活链接要求不同向量指令同时访问同一个向量寄存器。可以通过增加读写端口实现，也可以像存储系统那样，把向量寄存器堆组织为交错存储体。本附录余下部分都假定采用这种链接方式。 即使两个操作互相依赖，链接仍允许它们在向量的不同元素上并行推进。因此，可以将它们调度到同一编队，减少所需的 chime 数。对前述指令序列，即使操作之间有依赖，仍可达到每周期持续执行两次浮点运算的速率（忽略启动时间），也就是一个 chime！整个序列的运行时间变为： $$ \text{向量长度}+\text{启动时间}_{\mathrm{ADDV}}+\text{启动时间}_{\mathrm{MULV}} $$ 图 G.8 给出向量长度为 64 时，这两条向量指令采用链接和不采用链接的时序。该编队只需一个 chime；但由于使用链接，实际编队执行时间中仍会显现启动开销。图中链接执行共需 77 个时钟周期，即每个结果 1.2 个周期。其间完成 128 次浮点运算，所以达到每时钟周期 1.7 次浮点运算。不采用链接时需要 141 个周期，即每时钟周期 0.9 次浮点运算。 ![依赖向量指令采用链接与不采用链接时的执行时序](/figures/app-g/fig-g-8.png) {#fig-G.8 .wide .expand num="G.8" caption="一组存在依赖的 ADDV 与 MULV 向量操作在不链接和链接两种情况下的执行时序。6 周期和 7 周期分别为加法器与乘法器的延迟。"} 图内术语：Unchained＝不链接；Chained＝链接；Total＝总周期数。原图分别给出 141 与 77 个周期。 虽然链接能将两条有依赖的指令放入同一编队，减少执行时间中的 chime 部分，却不能消除启动开销。要准确估计运行时间，就必须同时计算编队内部和编队之间的启动时间。采用链接时，一个序列的 chime 数取决于处理器中不同向量功能单元的数量，以及应用对它们的需求。尤其要注意，任何编队都不能包含结构冒险。例如，在 VMIPS 这样只有一个向量加载—存储单元的处理器上，含两条向量访存指令的序列至少需要两个编队，也就是两个 chime。 链接如此重要，以至于每种现代向量处理器都支持灵活链接。 ## 深入探讨稀疏矩阵 第 4 章介绍了让稀疏矩阵程序以向量方式执行的技术。先简要回顾一下：稀疏矩阵中的向量元素通常以某种紧凑形式保存，再通过间接寻址访问。对于一种简化的稀疏表示，代码可能如下： ```fortran do 100 i = 1,n 100 A(K(i)) = A(K(i)) + C(M(i)) ``` 这段代码对数组 `A`、`C` 执行稀疏向量求和，使用索引向量 `K`、`M` 指定 `A`、`C` 中的非零元素。`A` 和 `C` 必须有相同数量的非零元素，即各有 \(n\) 个。另一种常见的稀疏矩阵表示，用位向量标记哪些元素存在，再用一个稠密向量保存非零元素。同一程序中往往会同时使用两种表示。许多程序都会遇到稀疏矩阵；具体实现方式很多，取决于程序采用的数据结构。 简单的向量化编译器不能自动向量化上述代码，因为它不知道 `K` 中各元素的值互不相同，因而也不知道不存在依赖。程序员需要通过编译指示，告诉编译器可以按向量方式执行该循环。 更先进的向量化编译器，可以插入运行时数据依赖检查，不依赖程序员注释便自动完成向量化。检查采用高级加载地址表（ALAT）的向量化软件实现；ALAT 硬件是附录 H 所述 Itanium 处理器的一项机制。这里用软件哈希表替代相联 ALAT 硬件，检测同一次 strip-mining 迭代中的两个元素访问是否指向同一地址。若未发现依赖，该次迭代就可以按最大向量长度完成；若检测到依赖，则将向量长度调小，使所有依赖约束都不被违反，剩余元素留给下一次 strip-mining 迭代。这个方案确实会增加相当多的软件开销，但在通常没有依赖的情况下，这些额外操作大多也能向量化。因此，循环仍远快于标量代码，不过比程序员提供编译指示时慢得多。 许多较新的超级计算机都具有散布—聚集功能。这些操作实现更复杂，也更容易遇到存储体冲突，因此通常比固定步长访问慢；但它们仍远快于可能采用的另一种实现，即标量循环。矩阵的稀疏性特征若有变化，就必须重新计算索引向量。许多处理器提供快速计算索引向量的支持。VMIPS 的 `CVI`（create vector index，创建向量索引）指令，根据给定步长 \(m\) 生成索引向量，其元素为 \(0,m,2m,\ldots,63m\)。有些处理器提供生成压缩索引向量的指令，只生成对应于掩码寄存器中 1 所在位置的条目；另一些向量体系结构则提供压缩向量的方法。在 VMIPS 中，我们把 `CVI` 定义为始终依据向量掩码生成压缩索引向量。掩码全为 1 时，就生成普通索引向量。 索引加载—存储与 `CVI` 指令，还提供了另一种支持条件向量执行的方法。先回顾第 4 章的代码： ```text low = 1 VL = (n mod MVL) /* 找出不足一整段的部分 */ do 1 j = 0,(n/MVL) /* 外层循环 */ do 10 i = low, low + VL - 1 /* 执行 VL 次 */ Y(i) = a * X(i) + Y(i) /* 主要运算 */ 10 continue low = low + VL /* 下一向量段的起点 */ VL = MVL /* 将长度重置为最大值 */ 1 continue ``` 下面的向量指令序列使用 `CVI` 实现这个循环： ```text LV V1,Ra ; 把向量 A 加载到 V1 L.D F0,#0 ; 把浮点零加载到 F0 SNEVS.D V1,F0 ; 若 V1(i) != F0，则把相应 VM 位设为 1 CVI V2,#8 ; 在 V2 中生成索引 POP R1,VM ; 统计 VM 中 1 的个数 MTC1 VLR,R1 ; 写入向量长度寄存器 CVM ; 清除掩码 ``` ```text LVI V3,(Ra+V2) ; 加载 A 中的非零元素 LVI V4,(Rb+V2) ; 加载 B 中对应的元素 SUBV.D V3,V3,V4 ; 执行减法 SVI (Ra+V2),V3 ; 写回 A ``` > **译注：** 原书在这里给出的高级语言代码是 DAXPY：`Y(i)=a*X(i)+Y(i)`；紧接着的汇编却按 `A(i)≠0` 筛选元素，并计算 `A(i)=A(i)-B(i)`，两段代码并不对应。下文条件的比较符号在原页中排印异常；前面的 `SNEVS.D` 注释和后文“非零”共同表明其含义为 `A(i)≠0`。 散布—聚集实现是否优于条件执行实现，取决于条件成立的频率与各操作的开销。忽略链接时，原版本的运行时间为 \(5n+c_1\)。第二个版本采用索引加载与存储，假设每周期处理一个元素，则运行时间为 \(4n+4fn+c_2\)，其中 \(f\) 是条件成立的元素比例，即 `A(i)≠0` 的比例。假定 \(c_1\)、\(c_2\) 大致相当，或远小于 \(n\)，即可求出第二种方法何时更好： $$ \begin{aligned} \mathrm{Time}_1&=5n\\ \mathrm{Time}_2&=4n+4fn \end{aligned} $$ 希望 \(\mathrm{Time}_1>\mathrm{Time}_2\)，因此： $$ 5n>4n+4fn\quad\Longrightarrow\quad\frac14>f $$ 也就是说，非零元素不足四分之一时，第二种方法更快。许多情况下，实际执行条件内操作的频率远低于这个比例。如果索引向量可以重用，或者 `if` 内向量语句的数量增多，散布—聚集方法的优势还会显著扩大。