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 给出到到达处理器经过互联网络时的耗时。
No comments:
Post a Comment