2.1 向量处理器如何工作：一个实例
要理解向量处理器的工作流程，最好的办法是研究一个向量循环（vector loop）如何在 VMIPS 上工作。让我们使用以下这个典型的向量问题，这个附录的其余部分也会使用它：
Y = a × X + Y
X 和 Y 都是向量，一开始就在内存之中；a 是一个标量。这就是所谓的 SAXPY 或者 DAXPY 循环。（SAXPY 表示 single-precision a × X plus Y；DAXPY 表示 double-precision a × X plus Y。）Linpack 是由一组线性代数例程组成，其中进行高斯消元操作的例程被称为 Linpack Benckmark。这里的DAXPY 例程仅仅代表 Linpack Benchmark 的一小部分，但是其操作占了整个 benchmark 运行时间的绝大部分。
从现在开始，让我们假定向量寄存器的元素的个数，或者说其长度（64）等于我们所关心的向量操作的长度。（我们之后会放宽对此的限制）
————————————————————
————————————————————
例题： 给出 MIPS 和 VMIPS 上 DAXPY 循环的代码。假定 X 和 Y 的起始地址分别在 Rx 和 Ry。
解答：以下是 MIPS 代码:
L.D F0,a ;load scalar a
L.D F0,a ;load scalar a
DADDIU R4,Rx,#512 ;last address to load
Loop: L.D F2,0(Rx) ;load X(i)
MUL.D F2,F2,F0 ;a × X(i)
L.D F4,0(Ry) ;load Y(i)
ADD.D F4,F4,F2 ;a × X(i) + Y(i)
S.D 0(Ry),F4 ;store into Y(i)
DADDIU Rx,Rx,#8 ;increment index to X
DADDIU Ry,Ry,#8 ;increment index to Y
DSUBU R20,R4,Rx ;compute bound
BNEZ R20,Loop ;check if done
以下是 VMIPS 的代码：
L.D F0,a ;load scalar a
L.D F0,a ;load scalar a
LV V1,Rx ;load vector X
MULVS.D V2,V1,F0 ;vector-scalar multiply
LV V3,Ry ;load vector Y
ADDV.D V4,V2,V3 ;add
SV Ry,V4 ;store the result
这两个版本代码之间的比较颇有意思。最显著的区别是，向量处理器极大地减少了动态指令[1]的带宽需求，只需要执行 6 条指令--相对应于 MIPS 的600 条。这是因为向量指令可以同时操作于 64 个元素，并且那些几乎占了一个循环中一半代码的循环冗余指令[2]现在都不存在了。
————————————————————
另一个重要的区别是流水线 互锁（interlock）的频率。在直观的 MIPS 代码中，每个 ADD.D 都要等待 MUL.D，每个 S.D 都要等待 ADD.D。在向量处理器中，每个向量指令只在第一个元素的操作上停顿（stall），之后的元素可以顺利地流过流水线。因此，流水线停顿只在每个向量操作发生一次，而不是每个向量的元素都发生。在这个例子中，MIPS 上流水线停顿的频率大约是 VMIPS 上的64倍。流水线停顿在 MIPS 上可以使用软件流水（software pipeling）或者循环展开（loop unrolling）的技巧来避免（参照附录 G）。然而，巨大的指令带宽的需求仍然存在。
2.2 向量处理器执行时间
一串向量操作的执行时间主要取决于三个因素：每个向量操作的长度，向量操作之间的 structural hazard，以及 data dependency。给定了向量的长度和引发率（initiation rate）即一个向量单元消耗新的操作数产生新结果的速率，我们可以计算出单个向量指令的执行时间。所有的现代超级计算机都拥有由多个并行道（或者叫 lane）组成的向量功能单元。他们可以在每个时钟周期内产生两个或者多个结果，但是同时也会有多个没有完全流水化的功能单元。为了简化讨论，我们的 VMIPS 实现中包括一个 lane，单个操作的 initiation rate 为每个周期一个元素。这样的话，单个向量指令的执行时间大约和向量的长度相等。
为了简化对于向量执行及其执行时间的讨论，我们会使用 convoy 这个概念。它指一组可以在一个时钟周期中同时执行的向量指令。（虽然 convoy 是一个向量编译中的概念，但是其实并不存在一个统一标准的术语。因此，我们创造了 convoy 这个术语。）在一个 convoy 中的指令之间必须不能有任何的 structural 或者data hazard （虽然我们会在后面放宽这个限制）。如果有 hazard 的存在，这些指令必须被串行化，放置到不同的 convoy 中执行。把向量指令放到一个 convoy 中就好比把标量指令放到一条 VLIW 指令中一样。为了让我们的分析简单化，我们假定一个 convoy 中的指令必须在其他任何指令，包括标量指令和下一个 convoy 中的向量指令，开始之前完成执行。我们会在第 4 小节中通过使用一种更宽松的，但是更复杂的指令发射机制从而放宽对此的限制。
和 convoy 相对应的是 chime 这个概念。它可以用来估计一系列由 convoy 组成的向量操作的性能。一个 chime 是执行一个 convoy 所需要的时间。一个 chime 是对一个向量操作序列执行时间的估计。Chime 与向量长度无关。因此，一个由 m 和 convoy 组成的向量序列的执行时间为 m 个 chime。如果向量长度为 n 的话，总共的执行时间大致为 m × n 个时钟周期。用 chime 来做估算忽略了一些与特定处理器相关的开销，很多与向量长度相关。因此，利用 chime 来估算执行时间对于长向量操作比较适用。我们之后会采用 chime 而不是时钟周期来估计执行时间以显式地忽略那些开销。
如果我们知道一串向量操作的 convoy 数目，我们就能知道以 chime 表示的执行时间。用 chime 估算时一个被忽略的因素是对于在一个周期内触发（initiate）多条指令执行的限制。如果在一个时钟周期中只能触发一条指令（这正是在大多数向量处理器中的实际情况），只计算 chime 数其实低估了一个 convoy 的执行时间。但是因为通常向量的长度比一个 convoy 中向量指令的个数来得多得多，我们可以简单地认为一个 convoy 的执行时间就是一个 chime。
————————————————————
————————————————————
例题：给出下面代码的 convoy 形式，假定每一个向量功能单元只有一个拷贝。
LV V1,Rx ;load vector X
MULVS.D V2,V1,F0 ;vector-scalar multiply
LV V3,Ry ;load vector Y
ADDV.D V4,V2,V3 ;add
SV Ry,V4 ;store the result
这个向量程序要花多少 chime？每 FLOP（floating-point operation） 需要多少时钟周期，假定忽略向量指令发射的开销？
解答：第一个 convoy 由第一个 LV 指令占据。 MULVS.D 和第一个 LV 相关，因此不能放在一个 convoy 中。第二个 LV 指令可以和 MULVS.D 在同一个 convoy 中。ADDV.D 和第二个 LV 也有相关性，所以必须放在第三个 convoy 中。最后 SV 依赖于 ADDV.D，所以必须进到下面一个 convoy 里。于是就有下面的 convoy 形式：
1. LV
2. MULVS.D LV
3. ADDV.D
4. SV
这个序列需要 4 个 convoy，因此需要花 4 个 chime的时间。 因为这个序列花 4 个 chime，并且每个结果需要 2 个浮点操作，因此每一个 FLOP 要花 2 个时钟周期 （忽略任何向量指令发射开销）[3]。注意虽然我们允许 MULVS.D 和 LV 在 convoy 2 中同时执行，大多数的向量机器需要2 个时钟周期去触发（initiate）这两条指令。
————————————————————
利用 chime 做估计对于长向量而言是合理的。比如，对于一个 64 个元素的向量而言，上例需要花费 4 个 chime，所以一共需要花费大约 256 个时钟周期。相比而言，在 2 个时钟周期里面发射一个 convoy 的开销就显得微不足道了。
另一个开销比上述的发射限制来得更为重要和显著。Chime 模型忽略的最大的开销是所谓的向量“启动”（start-up）时间。启动时间来源于执行向量指令的流水线延迟，并且由流水线深度主要决定。启动时间增加了执行一个 convoy 所需的实际执行时间，使之超过一个 chime。因为我们假定 convoy 之间互相不重叠，启动时间因此也延长了后续 convoy 的执行。当然因为后续的 convoy 和当前的 convoy 本身就有结构或者数据上的 hazard，不重叠的假定是合理的。完成一个 convoy 所需的时间实际上等于向量的长度加上其启动时间。如果向量的长度是无限的，启动时间的开销可以被均摊；但是有限长度的向量则会暴露启动延时，如下例所示。
————————————————————
————————————————————
例题：假定各功能部件的启动时间如图 F.4 所示。
给出每个 convoy 可以开始的时间以及总共需要的周期数。这个时间和单纯使用 chime 的估计对于向量长度为 64 而言有和区别？
解答：图 F.5 给出了基于 convoy 的解答，假定向量的长度是 n。一个很恼人的问题是我们到底认为何时向量操作序列才算结束？这决定了 SV 的启动时间到底算还是不算。我们假定 SV 之后的指令不能进入其同一个 convoy，并且不同的 convoy 不能互相重叠执行。那么总共的执行时间则需要计算到最后一个 convoy 的最后一个向量指令结束。这仅仅是一个估算，最后一个向量指令的启动时间有时候可见，有时候不可见。为了简化讨论，我们始终计算它。
对于向量长度为 64 的实例而言，平均每出一个结果需要 4 + (42 / 64) = 4.65 个时钟周期，然而需要的 chime 数只是4。考虑了启动开销之后执行时间大约有 1.16 倍的增加。
————————————————————
为了简化讨论，我们使用 chime 作为执行时间的估计，仅仅在我们需要详细的性能数据以展现某些优化技巧时才考虑启动时间。对于长向量而言，启动时间的开销并不大。在本附录稍后章节，我们将讨论如何降低启动开销。
一条指令的启动时间来源于执行该指令的功能单元的流水线的深度。如果我们想保持触发率（initiation rate）在每一个时钟周期给出一个结果，那么：
流水线深度 = [总共需要的执行时间 / 时钟周期长度]
比如，如果一个操作需要花10个时钟周期，那么它必须被划分为 10 级流水进行操作才能保持触发率为平均一个时钟周期。流水线的深度取决于操作的复杂度和处理器的时钟周期长度。功能单元的流水线的深度变化很大--从 2 到 20 都不是不常见的--虽然大多数常用的单元都是 4～8 级流水。
对于 VMIPS 而言，我们采用和 Cray-1 一样的流水线深度，虽然在更多的现代处理器中延迟有所增加，特别是 load。所以的功能单元都是完全流水的。就如图 F.6 所示，浮点加法的流水线的深度是 6 个时钟周期，浮点乘法的深度是 7 个时钟周期。在 VMIPS 上，就如同大多数的向量处理器，互相独立的使用不同的功能单元向量操作可以在一个 convoy 中发射。
---------------大家好，我是分割线---------------
[1] 这里所谓的动态指令是指在运行时实际执行的指令。在 MIPS 中，由于循环的存在，每一次迭代都需要重新取指。
[2] 所谓的循环冗余指令是为了维护循环的控制流而必须的指令，包括自减循环索引，判断是否达到循环边界，跳转等等。这些指令在向量处理器的代码中是不存在的--因为根本就没有循环的存在。
[3] 假定向量长度是 n，一共进行了 2 × n 个浮点操作（每个向量元素需要 2 个浮点操作），花了 4 × n 个时钟周期（假定每个 chime 的周期数等于向量长度），可以得到每 FLOP 需要 2 个时钟周期。或者可以更简单地来考虑：执行完所有的指令需要 4 个 chime，其实等效于每一个向量元素需要 4 个时钟周期来执行完其自身需要的操作。
No comments:
Post a Comment