向量处理器（9）

4.4 多道向量处理器

向量指令集的一个最大的优点是它能够允许软件传递大量的并行任务给硬件，而只需要一条很短的指令即可。一条向量指令可以包括数十上百个独立的操作，但是仍然和通常的标量指令一样译码为相同的长度。向量指令的并行语义使得执行这些元素操作有两种方法。第一是使用深度流水化的功能单元，就像我们研究的 VMIPS 一样；或者通过一组并行的功能单元，或者是并行单元和流水化单元的组合。图 F.11 展示了如何通过使用并行流水线执行向量 add 指令来提升向量性能。

图 F.11 使用多个功能单元来改进 add 向量指令C = A + B 的性能。（a）中的机器有一条 add 流水线，可以在每个周期完成一次加法。（b）中的机器有四个加法流水线，并且在每个周期可以完成 4 个加法才做。一个向量加法操作涉及到的那些元素被分散分布在四条流水线上。一起通过这些流水线的那组元素被称为元素组（element group）。

VMIPS 指令集设计的特点是所有的向量指令只允许一个向量寄存器的 N 个元素和另一个向量寄存器的 N 个元素参与运算。这极大地简化了可被组织成多个并行道（lane）的高度并行的向量单元的设计。就像一个高速公路一样，我们可以通过增加更多的 lane 来提升一个向量单元的峰值吞吐率，如图 F.12 所示。

图 F.12 一个包含有 4 个道的向量单元的结构。向量寄存器的存储被分布在各 lane 之间，每个 lane 包含有每个向量寄存器的 4 个元素。图中展示了 3 个向量功能单元，一个浮点加法单元，一个浮点乘法单元，以及一个 L/S 单元。每个向量算术单元包含有 4 个执行流水线，每个 lane 一个。他们协同共组去完成每一条向量指令。注意向量寄存器的每一个部分是如何只需要提供本地的 lane 访问的足够端口即可的。这极大减少了提供多端口的开销。提供向量-标量指令（vector-scalar instruction）中标量操作数的通路并没有在这张图中显示出来，但是标量值必须被广播到所有的 lane 中。

每一个 lane 包含了向量寄存器文件的一部分以及每个向量功能单元中的一条流水线。每个向量功能单元通过多个流水线（每个 lane 一个）以每个周期一个 element group 的速率来执行向量指令。第一个 lane 包含有所有向量寄存器的第一个元素，因此任何有关第一个元素的向量指令的源操作数和目的操作数都在第一个 lane 中。这使得一个算术运算的流水线的操作能在一个 lane 内部完成而不需要和其他 lane 通信。Lane 间互联只是在访存的时候才需要。缺少 lane 间通信能够降低互联导线开销和用于高度并行执行单元的寄存器文件的端口，并且解释了为什么当前的超级计算机可以在每个周期完成至多 64 个操作（16 个 lane，每个有 2 个算术单元和 2 个 L/S 单元）。

增加多个 lane 是一种很通用的提升向量性能的技术，因为它只需要很小的控制复杂度上的靠小，并且不需要改动现有的代码。有一些向量超级计算机以 lane 数目可变的系列方式进行销售。这使得用户能够自行权衡价格和峰值性能。Cray SV1 和 X1 允许 4 个 2 道的向量 CPU 组合在一起形成一个单个更大的 8 道 CPU，具体在第七小节讨论。

4.5 流水化指令的启动

增加多条道能够提升峰值性能，但是却不能改变启动延迟，所以通过允许一条向量指令的开始与之前一条指令的完成想重合来降低启动开销就变得很关键了。最简单的情形是当两个向量指令访问不同的向量寄存器的时候。比如，在下面的代码段中：

                                                              ADDV.D                       V1, V2, V3

                                                              ADDV.D                       V4, V5, V6

一种实现方式是允许第二条指令中的第一个元素紧跟着第一条指令的最后一个元素在浮点加法流水线中执行。为了减少控制逻辑的复杂度，有些向量机器在分发（dispatch）到同一向量单元上的两条向量指令之间需要一些恢复时间（recovery time）或死时间（dead time）图 F.13 展示了一条流水线的启动延迟和死时间。

图 F.13 一条向量流水线的启动延迟和死时间。每个元素操作有 5 个周期的延迟：1 个周期去读向量寄存器文件，3 个执行周期，然后一个周期写回寄存器文件。同一个向量指令中的元素可以连续在流水线中执行，但是这个机器在两个向量指令之间插入了 4 个周期的 dead time。这个 dead time 可以利用更复杂的控制逻辑来减少。

下面的例子展示了死时间对于向量处理器性能的影响。

_____________________________________________________

例题：Cray C90 有两个 lane，但是在任何同一个功能单元上执行的两个向量指令之间需要 4 个周期的 dead time，即使他们之间没有数据依赖。对于最大向量长度为 128 的情形而言，由 dead time 导致的峰值性能的减少是多少？如果 lane 的数目增加到 16，那性能折扣又是多少？

解答：最多 128 个元素被划分到 2 个道上，并且占据一个向量功能单元 64 个时钟周期。Dead time 另外增加了 4 个周期的占用，使得峰值性能降为没有 dead time 的 64/(64 + 4) = 94.1%。如果 lane 的数目增加为 16，那么 128 个元素占用一个功能单元的时间只需要 128/16 = 8 个周期，这样 dead time 会导致 8/(8 + 4) = 66.6% 的峰值性能降低。在第二种情况下，向量单元永远不会有超过 2/3 的忙碌时间。

_____________________________________________________

流水化指令的启动在多条指令可以读写同一个向量寄存器或者一些指令不可预期地停顿比如 load 指令遇到 bank conflict 的时候变得更复杂了。但是，因为 lane 的数目和流水线的延迟增加了，现在完全流水化指令的启动时间变得越来越重要了。

向量处理器（8）

4.3 稀疏矩阵

存在一些能够使得基于稀疏矩阵的程序在向量模式下运行的技术。在一个稀疏矩阵中，向量的元素通常是以紧凑的形式储存，并且以间接的方式被访问。我们会看到以下一个简化了的稀疏矩阵的代码：

                                                         do 100 i = 1, n

                     100                                    A(K(i)) = A(K(i)) + C(M(i))

这段代码利用 K 和 M 作为索引向量来给出 A 和 C 中的非零元素实现了数组 A 和 C 的稀疏向量求和和。（A 和 C 必须有相同数目个非零元素--本例中的 n）另外一个常见的稀疏矩阵的表示形式是用一个位向量来表示哪些位是非零元素以及一个稠密向量包含所有的非零元素。通常这两种表示形式会同时在一个程序里出现。在很多代码里都能看到稀疏矩阵的影子，并且根据不同的数据结构有很多中实现方法。

支持稀疏矩阵的最主要的机制是利用索引向量（index vector）的 scatter-gather 操作。这类操作的目标是支持在稠密表示（即没有非零元素）和正常表示（即包括非零元素）之间进行数据迁移。Gather 操作根据一个索引向量，通过把索引向量给出的偏移值加到基地址上来取出向量的元素。其输出是在一个在向量寄存器里的稀疏向量。在这些元素以稠密的形式被处理之后，稀疏向量要以扩展的形式通过 scatter 操作存回内存，使用同样的索引数组。对于这两个操作的硬件支持称之为 scatter-gather，并且在几乎所有的现在向量处理器上都能看到。VMIPS 提供了 LVI（load vector indexed）和 SVI（store vector indexed）指令来实现这两个操作。比如，假定 Ra，Rc，Rk 和 Rm 分别有前例中四个向量的起始地址，那么彼代码段的内层循环可以用以下的向量指令实现：

                                         LV                        Vk, Rk                       ;load K

                                         LVI                       Va, (Ra + Vk)          ;load A(K(I))

                                         LV                        Vm, Rm                    ;load M

                                         LVI                       Vc, (Rc + Vm)         ;load C(M(I))

                                         ADDV.D              Va, Va, Vc              ;add them

                                         SVI                       (Ra + Vk), Va          ;store A(K(I))

这个技术使得稀疏矩阵的代码可以以向量模式执行。简单的向量编译器不能自动向量化以上代码，因为编译器不会知道 K 中的元素的值互相是不相同的，因此不存在任何依赖关系 [1]。因此，程序员需要告诉编译器该循环可以以向量模式运行。

更为复杂的向量编译器可以自动向量化以上循环而不需要程序员的干预。这是通过插入运行时对于数据 dependency 的检查实现的。这种运行时检查是通过  Itanium 处理器中的 Advanced Load Address Table（ALAT）硬件机构的向量化软件版本实现的。ALAT 在 附录 G 中有描述。ALAT 硬件被一个软件哈希表所代替。该哈希表能够检测出在同一个 strip-mining 的迭代循环中的两个元素是否指向同一个地址。如果没有检测到 dependency，该 strip-mining 循环则可以以长度 MVL 来完成。如果检测到了 dependency，向量的长度则被重置为较小的一个可以避免 dependency 的值，而留下剩下的部分给下一个循环执行。虽然这种机制给执行循环增加了很多软件开销，但是这种开销还是会被更为常见的没有依赖的情况所均摊，因此这个循环仍然会比标量代码快得多（当然会比程序员直接指出可以向量化的情况慢得多）。

近来大多数的超级计算机都有 scatter-gather 的能力。这种操作比有跨度的操作更为之慢因为实现起来更复杂，而且更容易出现 bank 冲突，但是比之标量版本，则要快很多。如果一个矩阵的稀疏程度改变了，必须重新计算索引向量。很多处理器提供了快速计算所以向量的方法。VMIPS 中的 CVI 指令可以根据一个给定的跨度值（m）来创建一个所以向量。其各个元素值为0，m，2×m，...，63×m。一些处理器提供一条创建压缩形式的索引向量的指令。该向量中各元素值对应于掩码寄存器中相应位置为 1 的元素。另外一些则提供压缩向量的指令。在 VMIPS 中，我们定义 CVI 指令为总是根据向量掩码来创建一个压缩过的索引向量。当所有的掩码都为 1 的时候，则创建一个标准的索引向量。

索引化的 L/S 操作以及 CVI 指令提供了支持条件向量执行的一种新方法。以下是我们在上一小节中循环的另一种实现：

                                         LV                        V1, Ra                     ;load vector A into V1

                                         L.D                       F0, #0                      ;load FP zero into F0

                                         SNEVS.D             V1, F0                    ;sets the VM to 1 if V1(i) != F0

                                         CVI                      V2, #8                      ;generates indices in V2

                                         POP                     R1, VM                   ;find the number of 1's in VM

                                         MTC1                  VLR, R1                   ;load vector-length register

                                         CVM                                                      ;clears the mask

                                         LVI                       V3, (Ra + V2)         ;load the nonzero A elements

                                         LVI                       V4, (Rb + V2)         ;load corresponding B elements

                                         SUBV.D               V3, V3, V4             ;do the subtract

                                         SVI                       (Ra + V2), V3         ;store A back

至于究竟是使用 scatter-gather 的版本更好还是使用条件执行的版本更好取决于该条件测试满足的频率以及这些操作的开销。不考虑 chaining 的话，第一个版本（前一小节）的耗时是 5n + c1。第二个版本，也即采用每一个周期能执行对于一个元素索引化 L/S 的版本，的执行时间是4n + 4fn + c2 [2]，其中 f 是条件测试满足（也即A(i) != 0）的比率。如果我们假设 c1 和 c2 差不多，或者说他们都远小于 n，我们可以求出什么时候第二个版本会更好。

                                         Time1 = 5n

                                         Time2 = 4n + 4fn

如果我们要 Time1 > Time2，那么

                                         5n > 4n + 4fn

                                         1/4 > f

也就是说，如果小于 1/4 的元素是非零元素，那么第二个版本更好。在很多情况下，条件满足的比率要小得多。如果可以索引向量可以被重用，或者在 if 语句下的向量语句 [3] 的数目增加，scatter-gather 的优势会显著增加。

---------------大家好，我是分割线---------------

[1] 如果 K 中有两个元素的值相等，那么它们会指向对于 A 中同一个元素进行操作。简单的编译器会认为这两个操作之间有相互数据依赖而不能自动并行化。

[2] 为什么是 4n + 4fn？在第二个版本中，需要完全执行（也即需要遍历向量中所有的元素）的向量指令是 LV，SNEVS.D，CVI，POP；需要部分执行（也即只需要对满足条件的向量元素进行操作）的指令是 2 条 LVI，SUBV.D，SVI。条件满足的比率是 f。

[3] 也就是满足条件测试后所需要执行的那部分语句。拿本例来说，如果 A(i) != 0 的情况下不仅仅是做简单的减法而是执行一系列复杂的操作，那么索引化L/S 的优势更明显。原因在于索引化 L/S 相比原来只用掩码的版本的优点正在于减少了 if 语句下的那些指令的执行时间（即只对满足条件的元素执行操作）。如果 if 语句下的那些指令数目增大，这个优势会被扩大。读者可以用上面给出的分析模型定性分析。

向量处理器（7）

4. 改进向量处理器性能

在这一节里我们会展示五种改善向量处理器性能的技术。第一种技术，称之为链接（chaining），能够让一系列相互依赖的向量操作运行得更快。它起源于 Cray-1，但是现在大多数的向量处理器都支持这种技术。接下来两种技术通过引入新的向量指令类型来处理条件执行（conditional execution）和稀疏矩阵从而扩展可以被向量化的循环类型。第四种技术通过以增加道（lane）的方式增加更多的并行执行单元来提升向量处理器的峰值性能。第五种技术通过流水化以及重叠指令的启动来降低启动开销。

4.1 链接（chaining）--前推（forwarding）的概念在向量寄存器上的扩展

考虑一下简单的向量序列：

                                       MULV.D             V1, V2, V3

                                       ADDV.D              V4, V1, V5

在 VMIPS 中，就像我们看到的那样，这两条指令必须放到两个独立的 convoy 中，因为他们是互相依赖的。另一方面，如果我们把向量寄存器，在本例中即 V1，不看成一个单个个体，而是看成一组寄存器，那么所谓前推（forwarding）的概念就可以扩展以作用于向量的每个元素上。这一允许 ADDV.D 更早开始执行的电子称为链接（chaining）。Chaining 允许只要一个向量操作的源操作向量中的某个元素已经准备就绪时就开始执行该元素的操作：在链（chain）中，前一个功能单元的结果被 forward 到后一个功能单元。在实际中，chaining 通常是通过允许处理器同时读写同一个向量寄存器的不同元素来实现的。早期的 chaining 确实是以类似前推的方式工作的，但是这限制了链中源指令和目的指令的时序。近来的实现采用了灵活链接（flexible chaining）的方法，允许一个向量指令和任何别的活跃的向量指令链接，只要没有结构 hazard [1]。Flexible chaining 需要几条指令同时访问一个向量寄存器，这可以通过增加读写端口或者把向量寄存器文件组织成类似于内存系统里 bank 的形式类实现。我们在整个附录里就假定采用这种链接方式。

虽然一组操作互相依赖，但是 chaining 允许对于不同元素的操作并行执行。这使得这一组操作能够被调度到一个 convoy 中，从而减少 chime 的数目。对于前一个例子而言，可以达到持续达到每一个周期 2 个浮点操作，或者一个 chime，的速率（不考虑启动开销），即使他们是互相依赖的！它的总共执行时间为：

向量长度 + ADDV 的启动时间 + MULV 的启动时间

图 F.10 展示了上例链接和没有链接两个版本的情况，其中向量长度为 64。新的 convoy 仍然只需要一个 chime，但是因为他使用了 chaining，启动时间会很显著。在图 F.10 中，链接版本的总共执行时间为 77 个时钟周期，或者说平均一个结果 1.2 个周期。由于有 128 个浮点操作在其间执行，所以我们达到了 1.7 FLOPS 每周期。对于未链接版本，一共要花费 141 个周期，或者说 0.9 FLOPS 每周期。

图 F.10 链接和未链接版本的一个互相依赖的 ADDV 和 MULV 向量操作序列的时序。 图中 6 和 7 个时钟周期的延迟分别是加法和乘法的延迟。

虽然 chaining 通过把两个互相依赖的操作放置到同一个 convoy 的方式减少了以 chime 表示的执行时间，它并没有降低启动延迟。如果我们期望得到一个精确执行时间，我们就必须考虑启动开销。在 chaining 技术中，一个向量序列的 chime 数由不同的功能单元的个数以及程序所需的实际个数所决定。特别注意的是在任何 convoy 中都不能有结构 hazard。这意味着在 VMIPS 这样只有一个向量 load-store 单元的处理器上，如果一个程序有两个向量指令，那它必须至少占据两个 convoy，因此至少花两个 chime 的时间。

我们会在第六小节看到 chaining 对提升性能有极其重要的作用。实际上，chaining 是如此的重要以至于现在每一个向量处理器都支持 flexible chaining。

4.2 条件执行语句

根据 Amdahl 定律，我们知道如果一个程序可向量化部分很少或者不高，那么加速比是非常有限的。两个限制向量化的原因是在循环内部条件代码的存在以及稀疏矩阵的使用。在循环里包含 if 语句的程序不能在向量模式下执行，因为 if 语句引入了循环内部的控制依赖（control dependency）。同样的，稀疏矩阵也不能有效地利用我们之前讨论过的相关技术有效实现。我们在这一小节讨论如何处理条件执行，下一小节讨论稀疏矩阵。

考虑如下循环：

                                         do 100 i = 1, 64

                                              if (A(i).ne. 0) then

                                                  A(i) = A(i) - B(i)

                                              end if

                100                   continue

这个循环由于包含有条件执行而不能正常地向量化。但是如果内层循环可以对 A(i) != 0 的部分进行迭代，那么减法操作就可以被向量化。在附录 G 中，我们看到了条件执行指令不是正常指令集的不一份。它们可以把控制依赖转换成为数据依赖，从而增加了循环的并行度。向量处理器可以类似地获益。

通常我们使用的一种扩展技术称为向量-掩码控制（vector-mask control）。Vector-mask control 利用一个长度为 MVL 的二值向量来控制向量指令的执行，就如同条件执行指令利用一个二值条件来决定一条指令是否执行一样。当向量-掩码寄存器（vector-mask register）被启用的时候，任何向量指令都只作用于向量掩码寄存器中相应元素值为 1 的那些向量元素上。在目的向量寄存器（destination vector register）中那些掩码寄存器里对应位置为 0 的元素不受向量操作的影响。如果向量-掩码寄存器由某个条件语句的结果来设置，那么只有满足条件的元素才会受到影响。把该寄存器清空表示将里面所有元素的值设为 1，使得后续的向量操作作用于所有的向量元素上。下面的代码可以用来实现前面的循环，假定 A 和 B 的起始地址分别在 Ra 和 Rb中。

                                          LV                              V1, Ra                 ;load vector A into V1

                                          LV                              V2, Rb                 ;load vector B

                                          L.D                             F0, #0                  ;load FP zero into F0

                                          SNEVS.D                  V1, F0                 ;set VM(i) to 1 if V1(i) != F0

                                          SUBV.D                    V1, V1, V2         ;subtract under vector mask [2]

                                          CVM                                                       ;set the vector mask to all 1s

                                          SV                              Ra, V1                 ;store the result in A

大多数最近的向量处理器都提供了向量-掩码控制。在这里描述的这种向量-掩码在大多数的处理器里都可以看到，但是另外一些允许向量掩码只作用于一部分的向量指令上。

然而，利用向量-掩码寄存器也有缺点。在讨论条件执行指令时，我们看到即使条件没有满足，该指令仍然需要花时间。但是，消除了分支和相应的控制依赖仍然使得条件指令执行地更快即使它得做一些没用的工作。同样的，应用向量掩码的向量指令即使对那些掩码值为 0 的元素而言也需要一定的执行时间。同理，即使大部分掩码值都为 0，使用向量-掩码控制仍然可能会比标量模式要快得多。实际上，在向量模式和标量模式之间巨大的潜在性能差距使得包含向量-掩码指令非常重要。

第二，在有些向量处理器中，向量掩码只用于禁止结果写回目的寄存器，而实际的计算操作会发生。这样的话，如果在前面例子中的操作是除法而不是减法，并且是对 B 而不是 A 进行条件测试，那么由于除数为 0 导致的浮点异常可能会发生。利用掩码同时屏蔽计算和写回的处理器可以避免这个问题。

---------------大家好，我是分割线---------------

[1] Flexible chaining 简单来讲就是放宽了 chaining 的限制。最初的 chaining 只能作用于相邻的两条指令之间。但是很有可能由于写程序的关系，原本可以 chaining 的两条语句被人为地分开了而不能利用 chaining 技术。Flexible chaining 允许这两条不相邻的指令重叠执行。

[2] 想一想这条指令硬件有可能是如何执行的？

向量处理器（6）

3.2 向量跨度

本节的第二个要解决的问题是，一个向量中相邻的元素在内存中的位置不一定是顺序的。考虑以下直观的矩阵相乘的代码：

                                                   do 10 i = 1, 100

                                                       do 10 j = 1, 100

                                                           A(i, j) = 0.0

                                                           do 10 k = 1, 100

                                       10                    A(i, j) = A(i, j) + B(i, k) * C(k, j)

在标号为 10 的这条语句这里，我们可以向量化 B 的一整行和 C 的一整列的相乘，并且以 k 作为下标对内层循环采取 strip-mine 技术。

要能这么干的话，我们必须考虑 B 中相邻的元素和 C 中相邻元素是如何被寻址的。当在内存中为一个数组开辟空间时，它是线性化的，并且必须以或者 row-major 或者 column-major 为准排布数据。这样的线性化意味着一行或者一列的元素在内存中是不相邻的。比如，如果上述循环代码是用 FORTRAN 语言写的，也即是以 column-major 的方式排布数据，那么在内层循环中 B 的相邻元素互相之间将有 8（每个元素的字节大小）倍于行长度的距离，总共是 800 字节。在第五章，我们看到了 blocking 的技术可以用以增加在基于 cache 的系统的局部性。对于向量处理器而言，它没有 cache，我们需要另一种技术来取出那些在内存中不相邻的元素。

我们称把分开两个要被收集（gather）到一个寄存器里的两个元素的距离为跨度（stride）。在这个例子中，用 column-major 的数据排布方式意味着矩阵 C 的 stride 为1，或者说 1 个双字（8 个字节），而矩阵 B 的 stride 为 100，或者说 100 个双字（800 个字节）。

只要一个向量被 load 到向量寄存器之后，它就好像在逻辑上是相邻的元素了。因此一个 vector-register 型的处理器可以处理 stride 大于 1 的情况，称之为非单元化跨度（nonunit stride），只要向量的 L/S 操作有处理 stride 的能力即可。这种访问不连续的内存地址并且把它们重构成为一个紧致的数据结构的能力是向量处理器相比基于 cache 的处理器的一大优点。cache 内在而言是处理单元化跨度（unit stride）的数据的 [1]，所以虽然增加 block 的大小可以降低有单元化跨度访问特性的大规模数据集的缺失率，但是另一方面对于以非单元化跨度模式访问的数据而言有负面影响。虽然 blocking 可以部分解决这些问题（参考 5.2 小节），能够访问不连续的数据的能力仍然是向量处理器在这类问题上的优势。

在 VMIPS 上，可寻址的最小单元是一个字节，因此我们的例子中 stride 是 800。这个值必须动态求得，因为矩阵的大小有可能在编译时并不知道，或者--就像向量的长度一样--可能在执行时因为对同一条语句的多次执行而变化。向量跨度，就和向量的起始地址一样，可以被放入一个通用寄存器中。然后可以使用 VMIPS 的 LVWS （load vector with stride）指令取出某个向量置入向量寄存器中。同样的，当 store 一个非单元化跨度的向量时，可以使用 SVWS （store vector with stride）指令。在有些向量处理器上，L/S 指令总是需要一个存储在寄存器中的 stride 值，所以只需要一条 load 指令和一条 store 指令就够了。单元化跨度的访问比非单元化跨度访问频繁得多，并且可以从内存系统的特别处理中获益，因此就像在 VMIPS 中一样通常是和非单元化跨度访问分开的。

内存系统因为支持大于 1 的 stride 而变得复杂。在我们之前的例子中，我们看到如果 memory bank 的数目至少和 bank 忙碌时间（bank busy time）的时钟周期数一样的话，单元化跨度访问就可以满速进行。然而，一旦非单元化跨度被引入，很可能访问同一个 bank 的频率会超过 bank 忙碌时间所允许的最大值。当几个访问竞争同一个 bank 的时候，bank 冲突（bank conflict）就会发生，其中的一个访问必须停顿。bank 冲突，也即bank 停顿，满足以下条件就会产生：

bank 数目 / 最小公倍数（跨度，bank 数目） < bank 忙碌时间

_____________________________________________________

例题：假定我们有 8 个 memory bank，每个 bank 的忙碌时间是6 个时钟周期，并且内存的访问延迟是 12 个周期。对 64 个向量元素进行 stride 为 1 的访问需要多少时间？如果 stride 是 32 呢？[2]

解答：对于 stride 为 1 的情形，因为 bank 的数目大于 bank 的忙碌时间，所以 load 操作会花 12 + 64 = 76 个周期，或者说平均每个元素 1.2 个周期。最差的 stride 情况是 memory bank 数目的倍数，就像在本例中，8 个 memory bank，stride 为 32。每个访存操作（除了第一个）都会和前一个操作冲突，因此需要等待 6 个周期的 bank 忙碌时间。总共的时间是 12 + 1 + 6 × 63 = 391 个周期 [3]，或者说平均每个元素 6.1 个周期。
_____________________________________________________

如果 memory bank 的数目和 stride 互素，并且有足够多的 bank 来防止单元化跨度访问的冲突，那么 memory bank 冲突就不会发生。在没有 bank 冲突的时候，多字访问和单元化跨度访问的速度是一样的。增加 bank 的数目超过最少满足单元化跨度访问无冲突的需求会减少可能的停顿的发生频率。比如，对于 64 个 bank 而言，跨度为 32 的访问会每隔一次产生，而不是每次访问都产生。如果我们一开始的时候 stride 是 8， bank 数目是 16，那么同样每隔一次访问会产生一次停顿。但是如果有 64 个 bank，stride 为 8 的访问会每隔 8 个才停顿。如果我们有多条存储流水线（memory pipeline）[4] 或者多个处理器共享一个内存系统，我们就会需要更多的 bank 以避免冲突。即使对于只有一条 memory 流水线并且访存模式为单元化跨度的机器而言，我们仍然会在一条指令的最后几个元素和下一条指令的头几个元素之间遇到冲突。增加 bank 数目有助于降低这种指令间冲突的可能性。在 2006 年，大多数的向量超级计算机都把每个 CPU 的访存请求分布到几百个 memory bank 上。因为 bank 冲突仍然有可能在非单元化跨度访问时发生，程序员无论何时都倾向于单元化访问。

一台现代超级计算机可能有几打 CPU，每个都有好几条存储流水线连接到几千个 memory bank。在每个存储流水线和每个 memory bank 之间都只用专用的通路是不切实际的。所以通常我们会使用一个多级的交换网络（switching network）来连接存储流水线和 memory bank。在不同的向量访问竞争同一条线路时会发生网络的拥挤，导致内存系统额外的停顿。

---------------大家好，我是分割线---------------

[1] unit stride 指的是 stride 为 1 的情形。这段话的基本意思是如果访问的数据不具有很好的局部性，那么 cache 的效果会非常差。

[2] 想一想什么情况下内存的访问延迟会是 bank 的忙碌时间的两倍？

[3] 为什么这里要额外加 1？为什么前一种情况是 12 + 64 而不是 12 + 63？这里额外的 1 可能是数据从 memory system 给出到到达处理器经过互联网络时的耗时。

[4] 我认为存储流水线（memory pipeline）是一个重要但是模糊的概念，参见此专用页面。