向量处理器（5）

3. 两个实际问题：向量长度和跨度

本小节解决两个来源于实际程序的问题：如果一个程序中向量的长度不是 64 的话我们怎么办？我们怎么处理在内存中不相邻的向量元素？让我们首先来考虑一下向量长度的问题。

3.1 向量长度控制

Vector-register 类的处理器有一个天然向量长度值，其取决于每个向量寄存器可容纳的元素个数。这个长度，对于 VMIPS 而言是 64，不太可能正好等于实际程序中的真实向量长度。另外，实际程序中的向量长度通常知道编译时才会知道。实际上，一段简单的代码都可能需要不同的向量长度。比如，考虑以下代码:

                      do 10 i = 1, n

                                             10         Y(i) = a * X(i) + Y(i)

所有的向量操作的长度都取决于 n，而 n 知道运行时才知道！n 甚至可能是一个包含上面代码的函数的参数，因此在执行的过程中其值会变化。

解决这个问题的方法是引入一个向量长度寄存器（vector-length register，VLR）。VLR 控制了任何向量操作的长度，包括向量 L/S 操作。但是 VLR 的值不能比向量寄存器的长度更大。只要实际的向量长度不超过由处理器自己定义的最大向量长度（maximum vector length，MVL），VLR 就可以解决我们的问题。

如果在编译的时候不知道 n 的值，它有可能比 MVL 大。为了解决这个问题，我们引入strip mining 技术。Strip mining 实际上是一个代码生成的技术，它使得每个向量操作都由一系列长度不超过 MVL 的向量子操作完成。我们可以对一个循环采用类似循环展开技术（参考附录 G）的方法进行 strip-mining：生成一个可以反复迭代的循环来处理长度为 MVL 的向量操作和另一个处理剩下部分的循环，后一循环的长度一定比 MVL 小。实际情况中，编译器通常只会生成一个参数化的循环来动态地处理长度的变化以包含上述两种情况。下面给出了 Stripe-mined 的版本的 DAXPY 程序，以 FORTRAN 语言（大多数科学计算程序的主要语言）写成，C 语言风格给出注释：

low = 1

VL = (n mod MVL) /*find the odd-size piece*/

do 1 j = 0, (n / MVL) /*outer loop*/

do 10 i = low, low + VL - 1 /*runs for length VL*/

Y(i) = a * X(i) + Y(i) /*main operation*/

10                   continue

low = low + VL /*start of next vector*/

VL = MVL /*reset the length to max*/

1          continue

n / MVL 这一项代表了截取的整数部分（FORTRAN 就是这么干的）并且在整个程序中都要用到。以上循环的效果是把一个向量分成几段，然后由内循环来处理。第一段的长度是 (n mod MVL)，而所有之后的段长度都是 MVL。参考图 F.8 的图例。

图 F.8 以 strip-mining 技术处理任意长度的向量操作。除了第一段以外所有的分段的长度都是 MVL以充分利用向量处理器的能力。在本图中，变量 m 代替了 (n mod MVL)。

上述代码中的内层循环被向量化成长度为 VL，其值等于 (n mod MVL) 或者 MVL。VLR 必须被设置两次--每次 VL 被赋值的地方。在多个向量操作并行执行的情况下，硬件必须在向量操作发射时把 VLR 的值拷贝多份到不同的向量功能部件处，以应对 VLR 可能在后续的向量操作中改变的情形。

有些向量指令集已经可以支持不同的 MVL。比如 IBM 370 系列大型机的向量扩展支持从8 到 512 之间的任何 MVL。它提供了一条 load vector count and update （VLVCU）指令来控制 strip-mined 的循环。VLVCU 指令用一个标量操作数来指出期望的向量长度。VLR 被设置成期望的向量长度和MVL 中较小的一个，并且这个值要被从一个标量寄存器里面减去从而设置条件码以指示循环是否结束。通过这种方式，目标代码不需要做任何改变就可可以在两种不同的实现之间迁移，并且充分利用可能的最大向量长度。

除了启动延迟外，我们还需要考虑 strip-mining 带来的开销。假定任何 convoy 都不能和其他的指令重叠执行的话，由重新启动向量序列以及设置 VLR 带来的 strip-mining 开销增加了实际的启动开销。如果这个额外开销对于一个 convoy 而言是 10 个周期的话，那么每 64 个向量元素的开销增加了 10 个周期，或者说每个元素 0.15 个周期。

决定一个由一系列 convoy 组成的 strip-mining 循环执行时间的有两个重要因素：

1.  一个循环中 convoy 的个数。它决定了 chime 的个数。我们使用 Tchime 来表示以 chime 表示的执行时间。

2.  执行 convoy 序列的开销。包括执行每个分段中标量代码的开销 Tloop 以及每个 convoy 的启动时间 Tstart。

在第一次建立向量序列的时候可能还会有一些固定的开销。在最近的向量处理器中，这种开销已经很小了，所以我们忽略之。

我们用 Tn 来代表一个向量操作序列作用于一个长度为 n 的向量上的总共运行时间：

Tn = [n / MVL] × (Tloop + Tstart) + n × Tchime

Tloop，Tstart 和 Tchime 的值都是和编译器还有处理器相关的。基于对于 Cray-1 的很多测试的结果，我们选择 15 作为 Tloop 的值。乍一看，你可能认为这个值很小。每个循环的额外开销包括设置向量的起始地址和跨度（stride），自增循环计数器，然后执行循环分支指令。织机上，这些标量指令可以全部或者部分地和向量指令重叠，最小化这些额外开销。Tloop 的值当然取决于循环的结构，但是它们之间的依赖性相比向量代码和Tstart 以及 Tchime 的值之间的联系而言就比较小了。

_____________________________________________________

例题：在 VMIPS 上 A= B × s 的执行时间是多少？其中 s 是一个标量，A 和 B 的长度为 200。

解答：假设 A 和 B 的起始地址被初始化在 Ra 和 Rb 中，s 在 Fs 中。另外回忆一下，在 MIPS （因此VMIPS）中，R0 中的值永远是 0.因为 (200 mod 64) = 8，strip-mined 之后的循环的第一次迭代会执行于长度为 8 的向量上，之后的迭代作用于长度为 64 的向量。每个向量的下一个分段的起始地址是向量长度的 8 倍。因为向量长度或者是 8，或者是 64，我们在第一个分段之后把地址寄存器的值加 8 × 8 = 64 而对于后面的几个分段则加上 8 × 64 = 512。每个向量的总字节数是 8 × 200 = 1600。我们通过比较起始地址加上 1600 和下一个向量分段的起始地址来确定循环是否应该结束。以下是实际的代码：

         DADDUI           R2,R0,#1600               ;total # bytes in vector

         DADDU            R2,R2,Ra                      ;address of the end of A vector

         DADDUI           R1,R0,#8                      ;loads length of 1st segment

         MTC1                VLR,R1                          ;load vector length in VLR

         DADDUI           R1,R0,#64                     ;length in bytes of 1st segment

                        DADDUI           R3,R0,#64                     ;vector length of other segments

                        LV                      V1,Rb                             ;load B

         MULVS.D         V2,V1,Fs                       ;vector * scalar

         SV                      Ra,V2                             ;store A

         DADDU            Ra,Ra,R1                       ;address of next segment of A

         DADDU            Rb,Rb,R1                       ;address of next segment of B

         DADDUI           R1,R0,#512                   ;load byte offset next segment

         MTC1                VLR,R3                           ;set length to 64 elements

         DSUBU             R4,R2,Ra                        ;at the end of A?

         BNEZ                 R4,Loop                        ;if not, go back

这个循环中的三条向量指令互相依赖，因为必须进入到三个 convoy 中，因此 Tchime = 3.让我们使用我们的基本公式：

Tn = [n / MVL] × (Tloop + Tstart) + n × Tchime

T200 = 4 × (15 + Tstart) + 200 × 3

T200 = 60 + (4 × Tstart) + 600 = 660  + (4 × Tstart)

Tstart 的值是以下几项的和：

• load 指令的启动时间 12 个时钟周期
• multiply 指令的 7 个周期的启动时间
• store 指令的 12 个周期的启动时间

因此，Tstart 的值由下式给出：

Tstart = 12 + 7 + 12 = 31

所以，总共的执行时间为：

T200 = 660 + 4 ×31 = 784

每个元素的平均执行时间为 784 / 200 = 3.9，而利用 chime 做的估算则为 3。在第 4 小节，我们会更激进一些--允许不同的 convoy 的执行相互重叠。

_____________________________________________________

图 F.9 给出了对于前面的例子（A= B × s）平均每个元素的执行开销随着向量长度的变化。chime 的模型给出的结果是平均每个元素的 3 个时钟周期，不过前述的两个额外开销来源给每个元素增加了 0.9 个时钟周期。

图 F.9 每个元素的平均执行时间和每个元素的平均额外开销随向量长度的变化。对于短向量而言，启动时间超过了总共时间的一半，但是对于长向量而言，这个比例减少到了三分之一。在向量长度穿过 64 的倍数的时候会有一个跳变，因为这产生了一个新的循环迭代和一组新的向量指令的执行。这些操作给 Tn 增加了Tloop + Tstart。

接下来的几节会介绍几个减少这些额外开销的技术。我们会看到如何利用一个被称为 chaining 的方法来减少 convoy 的数目从而减少 chime 的数目。每个循环的开销 Tloop 可以通过进一步重叠向量和标量的执行，允许一个循环中的标量的执行和前一个循环的向量指令的执行的完成，来降低。最后，向量的启动延迟可以通过一个允许不同 convoy 中的向量指令的重叠执行而消除。