第六章(P391)
6.6（注意阅读P372倒数第9行－倒数第6行）
已知n=32，k加=6，k乘=7，k访存=6，k倒数=14，启动、输出延迟各1。求各小题总拍数。
(1) V0 ← 存储器 V1 ← V2 + V3 并行 V4 ← V5 * V6 访存 加 乘 9 31 总拍数=40（并行执行，以最长指令为准）(3) V0 ← 存储器
并行
V3 ← V1 + V2 链接
V4 ← V0 * V3 V6 ← V4 + V5 串行 访存 加 乘
8 9 31 8 31
总拍数=87（第4条功能部件冲突）
(2) V2 ← V0 * V1
并行
V3 ← 存储器
V4 ← V2 + V3 串行（P372） 乘 访存 加 9 31 8 31 总拍数=79（第3条错过时机，不能链接） (4) V0 ← 存储器 链接 V1 ← 1 / V0
链接
V3 ← V1 + V2 链接
V5 ← V3 * V4 访存 倒数
加 乘
8 16 8 9 31
总拍数=72（各条依次链接）
(5) V0 ← 存储器 V1 ← V2 + V3 并行 V4 ← V5 * V6 s0 ← s1 + s2 访存 加 乘 9 31 8 总拍数=48（标量看成1个分量的向量） (7) V3 ← 存储器 V4 ← V2 * V3 存储器 ← V4 访存 加 乘
8 9 31 8 31
总拍数=87（第4条功能部件冲突）
串行
并行
串行
(6) V3 ← 存储器 s0 ← s2 + s3 V3 ← V1 * V4 访存 加 乘 8 31 9 31 总拍数=79（标量看成1个分量的向量） (8) V0 ← 存储器 V2 ← V0 + V1 V3 ← V2 * V1 V5 ← V3 * V4 访存 加 乘
8 8 31 9 31 9 31
总拍数=127（Vi冲突，功能部件冲突）
串行 串行
链接
并行 并行
串行
6.10 已知向量速率Rv = 10MFLOPS，标量速率Rs = 1MFLOPS，并记α为可向量化百分比。 (1) 推导法1：使用Amdahl定律，在这里可将标量速率Rs作为原速率，局部加速后的速率为向量速率Rv，于是局部加速比Se=10，全局加速比为
V2 ← V0 + V1 链接
V2 ← V0 + V1
Sn?1(1??)??Se
再根据加速比的定义，
Sn?R?Rs，所以有
R??Rs?Sn?Rs(1??)??Se?。
（若将向量速率Rv作为原速率，局部减速后的速率为标量速率Rs，则局部加速比Se=0.1，推出的全局加速比Sn同上式。） 推导法2：为了推导，定义T为总时间，N为总任务数。于是有平均速率Ra = 吞吐率TP = N/T。记N = Nv + Ns，且??NvNv?NNv?Ns，
则1???NsNs?NNv?Ns，于是有Nv = α·N和Ns = (1-α)·N 显然：总时间T?Tv?Ts?NvNs??N(1??)?N???RvRsRvRs 所以：Ra?NN1??11T??N(1??)?N????(1??)?RvRsRvRs
或者：
111????(1??)?RaRvRs(2) 已知Rv = 10MFLOPS，Rs = 1MFLOPS，
Ra (MFLOPS) 10 1 0
1 α
110Ra?MFLOPS?MFLOPS
0.1??(1??)10?9?Ra与α的关系图如右图所示。
(3) 已知Ra = 7.5MFLOPS，解出
??1011013(1?)???0.96?96% 97.5915(4) 已知Ra = 2MFLOPS，α = 0.7，解出
Rv??11?(1??)?RaRs?0.71?0.3?12?3.5(MFLOPS)
第七章(P446)
7.3 已知输入端编号13 = 1101B。 (1)Cube3(1101B) = 0101B = 5
(2)PM2+3(13) = (13 + 2)mod 16 = 21 mod 16 = 5 (3)PM2+0(13) = (13 - 2)mod 16 = 12 (4)Shuffle(1101B) = 1011B = 11
(5)Shuffle(Shuffle(1101B)) = Shuffle(1011B) = 0111B = 7
7.4 用多级混洗―交换网络，n = 4，拓扑结构同教材P410图7.21(e)，控制信号=1010B，自左向右各级交换开关状态依次为交换―直连―交换―直连。
7.5 输入结点编号j = 9，f(j) = j⊕控制信号 = 1001B⊕1100B = 0101B = 5，答为5号处理机。
7.6 直连状态时：编号在第i位不同的结点之间不能通信；
7.7 用单级混洗―交换网可实现，总共混洗3步。
证：设矩阵A = (aij)8×8按行展开依次存放在64个单元中，则任意元素aij的地址为8i + j，而aji的地址为8j + i。按混洗函数的定义，3次混洗后，shuffle(8i + j) = 8×(8i + j) mod 63 = i + 8j，也就说将元素aij地址变换成aji的地址。由于aij是矩阵中的任意元素，所以3次混洗可实现矩阵转置(aij)8×8=(aji)8×8。
7.8 最多5级，因为对于任给的输入结点编号j=X6X5X4X3X2X1X0，PM2I多级网络中i=2级的功能是PM2±2(j)=j±2 mod 128，±2运算只有可能改变j中的X6～X2，所以最多使用Cube6～Cube2就能实现代换了。
7.9 由于N = 16，即n = 4，每个结点编号用4位二进制数表示。PM2±0函数功能是对结点编号加1或减1，其结果最多可将编号的4位都取反（如1111B + 1 = 0000B），所以用每步只能对1位取反的单级立方体网络来模仿，最差情况下要4步。
7.10 用混洗―交换网络模拟Cube网。
当模拟Cube0功能时，只需一次交换即可完成；而模拟Cubei且i≠0时，需先作n – i步混洗，再作1步交换，最后作i步混洗才能完成，共计n + 1步。
综上所述，下限为1步，上限为n + 1步。
2
2
T
3
03
交换状态时：编号在第i位相同的结点之间不能通信。
7.11 求单级立方体网络和单级混洗―交换网络的最大广播步数，这两种网络的最大广播步数与最大距离（即直径）相同。 (1)单级立方体网络直径 = n（Cuben-1～Cube0各1次）； (2)单级混洗―交换网络直径 = 2n-1（n-1次混洗，n次交换）。
7.12 已知N = 16，用多级立方体网络或者多级混洗―交换网络均能实现，两者可以互相模拟，对同一置换的寻径算法相同，控制信号也相同，下面以多级立方体网络为例分析。
4组4元交换：f1 = Cube1Cube0； 2组8元交换：f2 = Cube2Cube1Cube0； 1组16元交换：f3 = Cube3Cube2Cube1Cube0； f = f1f2f3 = Cube3Cube1Cube0
利用Cube函数的结合律、交换律以及同一律（又称自反律）可以推得 拓扑结构图略（可参考7.26题的多级混洗―交换网络拓扑结构图）。
网络开关使用级控方式，控制信号为1011B（其中biti控制级i，“0”表示直连，“1”表示交换）。
7.13 N = 8的蝶式置换。 (1) f(X2X1X0) = X0X1X2；
(2) 至少需2次通过，每次都是N个数据同时发送，同时接收，中途不储存； (3) 控制信号的设置有4种方案，如下所示。其中“0”表示直连，“1”表示交换。 7.14
(1) 共N!种； (2) 一次通过有NN2 101 100 000 000 000 000 101 100
001 101 000 000 000 000 001 101
000 000 101 100 101 100 000 000
000 000 001 101 001 101 000 000 种不同；
N2N84?100%??100%?10.16% (3) N = 8时，百分比 =
N!8!
7.26(1)～(3)； (1)见下图实线。
(2)见下图虚线；不会阻塞，因为两条路径的控制信号都是1110，形成级控模式，所以不会阻塞。
(3)一次通过实现的置换数为16 = 4294967296，全部置换数为N! = 20922789888000，前者约占后者的0.02%。
8
相关推荐：
loading