习题

以下习题均假设 VMIPS 时钟频率为 500 MHz，且 $T_{\mathrm{loop}}=15$。采用图 G.2 中的启动时间，并假设运行时间始终包含存储延迟。

习题 G.1

[10]〈G.1、G.2〉 编写一段达到处理器峰值 MFLOPS 的 VMIPS 向量指令序列，使用 G.2 节的功能单元和指令说明。假设时钟频率为 500 MHz，峰值 MFLOPS 是多少？

习题 G.2

[20/15/15]〈G.1–G.6〉 考虑下面这段在 500 MHz VMIPS 上执行的向量代码，向量长度固定为 64：

LV      V1,Ra
MULV.D  V2,V1,V3
ADDV.D  V4,V1,V3
SV      Rb,V2
SV      Rc,V4

忽略所有 strip-mining 开销，但假设执行循环所需时间必须包含存储延迟。整个指令序列产生 64 个结果。

a. [20]〈G.1–G.4〉 假定不采用链接，且只有一条存储器流水线，需要多少个 chime？计入启动开销后，这段向量序列每个结果需要多少时钟周期？将两次存储合计为一个结果。

b. [15]〈G.1–G.4〉 如果采用链接，计入开销后，这段序列每个结果需要多少时钟周期？

c. [15]〈G.1–G.6〉 假设 VMIPS 有三条存储器流水线，并支持链接。如果上述循环的访存不存在存储体冲突，这段序列每个结果需要多少时钟周期？

习题 G.3

[20/20/15/15/20/20/20]〈G.2–G.6〉 考虑以下 FORTRAN 代码：

      do 10 i=1,n
          A(i)=A(i)+B(i)
          B(i)=x * B(i)
10    continue

本题始终采用 G.6 节的方法估算性能，假设 VMIPS 的时钟频率为 500 MHz。

a. [20]〈G.2–G.6〉 为循环的内部部分编写最佳的 VMIPS 向量代码。假设 x 存放在 F0 中，A 和 B 的地址分别存放在 Ra、Rb 中。

b. [20]〈G.2–G.6〉 求循环在 VMIPS 上的总执行时间 $T_{100}$。它的 MFLOPS 性能 $R_{100}$ 是多少？

c. [15]〈G.2–G.6〉 求该循环的 $R_\infty$。

d. [15]〈G.2–G.6〉 求该循环的 $N_{1/2}$。

e. [20]〈G.2–G.6〉 求该循环的 $N_v$。假设标量代码已经过流水线调度，每次访存需要六个周期，每次浮点运算需要三个周期；标量开销也为 $T_{\mathrm{loop}}$。

f. [20]〈G.2–G.6〉 假设 VMIPS 有两条存储器流水线。编写能利用第二条存储器流水线的向量代码，并给出编队划分。

g. [20]〈G.2–G.6〉 计算两条存储器流水线的 VMIPS 所对应的 $T_{100}$ 和 $R_{100}$。

习题 G.4

[20/10]〈G.2〉 假设某个 VMIPS 版本有八个存储体，每个存储体宽一个双字，存储器访问时间为八个周期。

a. [20]〈G.2〉 如果以 20 个双字为步长，执行长度为 64 的向量加载，完成加载需要多少周期？

b. [10]〈G.2〉 对 64 个元素的加载，步长为 20 时所达到的存储器带宽，是步长为 1 时的百分之多少？

习题 G.5

[12/12]〈G.5–G.6〉 考虑以下循环：

      C=0.0
      do 10 i=1,64
          A(i)=A(i)+B(i)
          C=C+A(i)
10    continue

a. [12]〈G.5–G.6〉 将它拆成两个循环：一个没有依赖，另一个存在依赖。以源到源变换的方式，用 FORTRAN 写出这两个循环。这种优化称为循环分裂（loop fission）。

b. [12]〈G.5–G.6〉 为没有依赖的循环编写 VMIPS 向量代码。

习题 G.6

[20/15/20/20]〈G.5–G.6〉 Cray-1 设计于 1976 年；1989 年，一款更好的编译器使它运行编译后 Linpack 的性能几乎翻倍。下面用一个简单例子探究这种提升如何发生。考虑一个类似 DAXPY 的循环，其中 k 是包含该循环的过程的参数：

      do 10 i=1,64
          do 10 j=1,64
              Y(k,j)=a*X(i,j)+Y(k,j)
10    continue

a. [20]〈G.5–G.6〉 只针对内循环，直接用 VMIPS 向量指令写出相应代码序列。

b. [15]〈G.5–G.6〉 用 G.6 节的方法，求以时钟周期计的 $T_{64}$，估算代码在 VMIPS 上的性能。可以假定外循环每次迭代都会产生 $T_{\mathrm{loop}}$ 的开销。什么因素限制了性能？

c. [20]〈G.5–G.6〉 改写 VMIPS 代码，减轻这一性能限制；用 VMIPS 向量指令给出新的内循环。提示：想一想什么决定了 $T_{\mathrm{chime}}$，能否改变它？求新序列的总执行时间。

d. [20]〈G.5–G.6〉 用 G.6 节的方法求 $T_{64}$，估算新版本的性能。

习题 G.7

[15/15/25]〈G.4〉 考虑以下代码：

      do 10 i=1,64
          if (B(i) .ne. 0) then
              A(i)=A(i)/B(i)
10    continue

假设 A 和 B 的地址分别存放在 Ra、Rb 中，F0 保存 0。

a. [15]〈G.4〉 利用向量掩码功能，为该循环编写 VMIPS 代码。

b. [15]〈G.4〉 利用 scatter-gather，为该循环编写 VMIPS 代码。

c. [25]〈G.4〉 假设除法延迟为 20 个周期，估算这两个向量循环的性能，即以时钟周期计的 $T_{100}$。假设所有向量指令每周期产生一个结果，不受向量掩码寄存器设置的影响。假设 B 中 50% 的元素为 0。如果上述循环具有代表性，考虑硬件成本后，你会构建哪一种实现？

译注：原书循环上限为 64，c 小问却要求 $T_{100}$，两者不一致。原代码也未列出 end if，不在译文中补成可编译程序。

习题 G.8

[15/20/15/15]〈G.1–G.6〉 峰值性能与持续性能可能相差很大。对于一个问题，Hitachi S810 的峰值速度是 Cray X-MP 的两倍；但对于另一个更接近实际的问题，Cray X-MP 的速度却是 Hitachi 处理器的两倍。下面用两个版本的 VMIPS 及以下代码序列，分析这种现象的原因：

C     代码序列 1
      do 10 i=1,10000
          A(i)=x * A(i)+y * A(i)
10    continue

C     代码序列 2
      do 10 i=1,100
          A(i)=x * A(i)
10    continue

假设有一个 VMIPS 版本，称为 VMIPS-II，每种浮点功能单元均配有两套，且各单元之间完全支持链接。假设 VMIPS 和 VMIPS-II 都有两个加载—存储单元。由于增加了功能单元，操作到单元的分配也更加复杂，VMIPS-II 的全部开销——$T_{\mathrm{loop}}$ 与 $T_{\mathrm{start}}$——均加倍。

a. [15]〈G.1–G.6〉 求代码序列 1 在 VMIPS 上的时钟周期数。

b. [20]〈G.1–G.6〉 求代码序列 1 在 VMIPS-II 上的时钟周期数，并与 VMIPS 比较。

c. [15]〈G.1–G.6〉 求代码序列 2 在 VMIPS 上的时钟周期数。

d. [15]〈G.1–G.6〉 求代码序列 2 在 VMIPS-II 上的时钟周期数，并与 VMIPS 比较。

习题 G.9

[20]〈G.5〉 下面这段涉及二维数组的代码有些棘手。循环中是否存在依赖？能否将这些循环写成可并行执行的形式？如果可以，应如何改写？若能向量化，请改写源代码，使这一点清楚地体现出来。

      do 290 j=2,n
          do 290 i=2,j
              aa(i,j)=aa(i-1,j)*aa(i-1,j)+bb(i,j)
290   continue

习题 G.10

[12/15]〈G.5〉 考虑以下循环：

      do 10 i=2,n
          A(i)=B
10        C(i)=A(i - 1)

a. [12]〈G.5〉 说明这段代码中存在循环携带依赖。

b. [15]〈G.5〉 用 FORTRAN 改写代码，使其可以向量化为两个独立的向量指令序列。

习题 G.11

[15/25/25]〈G.5〉 如 G.5 节所述，有些循环结构不容易向量化。一种常见结构是归约（reduction）：反复应用某个运算，将一个数组归并为一个值的循环。这是递推的一种特殊情况。点积是常见的例子：

      dot=0.0
      do 10 i=1,64
10        dot=dot+A(i) * B(i)

该循环显然存在围绕 dot 的循环携带依赖，无法直接向量化。一个好的向量化编译器首先会拆分循环，将可以向量化的部分与递推部分分离，可能改写为：

      do 10 i=1,64
10        dot(i)=A(i) * B(i)
      do 20 i=2,64
20        dot(1)=dot(1)+dot(i)

变量 dot 被扩展为一个向量；这一变换称为标量扩展（scalar expansion）。可以完全依靠编译器来尝试向量化第二个循环，见 a 小问；也可以借助硬件支持，见 b 小问。利用向量技术进行归约时，有一个重要限制：这要求归约所用的运算满足结合律。然而，由于舍入和有限的数值范围，浮点运算并不严格满足结合律。因此，大多数编译器要求程序员明确指出，是否允许利用结合律来更高效地编译归约操作。

a. [15]〈G.5〉 编译含有递推的循环时，一种简单方案是依次对越来越短的向量相加：先对两个 32 元素向量相加，再对两个 16 元素向量相加，依此类推。这种技术称为 recursive doubling，比全部以标量方式运算更快。请给出用 recursive doubling 执行上述第二个循环的 FORTRAN 代码。

b. [25]〈G.5〉 在某些向量处理器中，向量寄存器可以按元素寻址，而且一次向量操作的两个操作数可以来自同一向量寄存器的不同部分。这允许采用另一种归约方案，称为部分和（partial sums）。其核心思想是将向量归约为 $m$ 个和，其中 $m$ 是通过向量功能单元的总延迟，包括操作数读写时间。假设 VMIPS 向量寄存器可以按元素寻址，例如可用 V1(16) 作为操作数发起向量操作，表示输入操作数从元素 16 开始。另假设加法总延迟（包括操作数读写）为八个周期。编写一段 VMIPS 代码，将 V1 的内容归约为八个部分和；一次向量操作即可完成。

c. [25]〈G.5〉 讨论加入 b 小问中的扩展，会如何影响一台具有多条通道的机器。

习题 G.12

[40]〈G.3–G.4〉 将 MIPS 模拟器扩展为 VMIPS 模拟器，并加入时钟周期计数功能。用 MIPS 和 VMIPS 汇编语言编写一些简短的基准测试程序，测量 VMIPS 上的加速比、向量化比例和功能单元使用情况。

习题 G.13

[50]〈G.5〉 修改 MIPS 编译器，加入依赖检查器。让它处理一些科学计算代码和循环，测量可以向量化的语句比例。

习题 G.14

[讨论] 一些向量处理器的支持者可能认为，向量处理器专注于提升峰值向量性能，为持续增强处理能力提供了最佳路径。另一些人则会认为，强调峰值性能的方向有误，因为越来越多程序的性能由非向量部分主导——还记得 Amdahl 定律吗？支持者会回应说，程序员应努力让程序能够向量化。你如何看待这一争论？