第
第PAGE1页共NUMPAGES4页
题：
对于N=2k个节点的deBruijn网络直径为log2N=k
对剖带宽为：O(N/log2N)=O(N/k)
【注】参考附件“lecture18.pdf”。
题：
0 1 2 3 4 5 6 7
实线表示交换，虚线表示洗牌。
交换：二进制地址编号中第0位不同的两个输入的输出互相交换。洗牌：输入端的二进制地址左移一位得到输出端对应的二进制地址。图中：N=8=2n，n=3。
从图中也可以看到，在洗牌交换网络中，最远的两个入、出端号是全“0”和全“1”，它们的连接，需要n次交换和n-1次洗牌，所以其最大距离（直径）为2n-1。节点度恒为3，对剖带宽为N/2。
1.10题：
处理器P1将本地高速缓存X更新为X’。采用写无效协议时，P1通过总线使共享存储器上的和所有在其他处理器上的该缓存块的拷贝实效。采用写更新协议时，P1通过总线使所有在其他处理器的本地高速缓存上的X的拷贝更新为X’，并将共享存储器上的X的拷贝置为无效。
2.1题：
总线带宽=总线宽度×一个时钟周期内交换的数据包个数×总线频率
2.8题：SMP：对称多处理器，共享存储，高速缓存一致性，低通信延迟，不可扩放性SSMP：可扩放共享存储多处理机，共享存储，扩放性好
2.8题：
SMP：对称多处理器，共享存储，高速缓存一致性，低通信延迟，不可扩放性SSMP：可扩放共享存储多处理机，共享存储，扩放性好
CC-NUMA：非均匀存储访问，高速缓存一致性，扩放性好
MPP：大规模处理器数，分布存储，使用物理分布的存储器和I/O，扩放性好
DSM：存储器物理分布，通过目录实现共享存储
3.2题：
由
nT?(CN3/n?bN2/
n
n)s
1T?CN3s
1
得：
f?0
pW?W?(CN3)w
p
oW?(bN2/
o
n)w
当固定负载时，运用Amdahl定律（式3.7）：
S? n
1?nWo/W
?
1?n?
n ?
bN2/ n b
CN3
CNn
n?CN
?CN
b
n当n??时
可见固定负载时具有n加速度
当固定时间时，运用Gustafson定律（式3.11）：
S? n ? n
?CNnn
?n当n??时
1?Wo
W
bN2/ n
1?
CN3
CNn?b
可见固定时间时具有线性加速度
当存储受限时，运用Sun和Ni定律（式3.14）：
当存储容量增加到原来的ｎ倍时，W是原来的n3/2倍。所以G（n）＝n3/2。
S? G(n) ? nn
?CNn2
?n当n??时
G(n)?Wo
bN2/ n
n?
CNn?b
n W CN3
3.9题：
3.9题：
处理器个数为P=2d的超立方多计算机上计算n点FFT的Cormen算法（P277）：第一步：将输入序列进行位反置换操作，每个处理器都必须计算输入元素的目的
处理器号和他在输出序列中的位序号；
第二步：各处理器执行log(n/P)次各自相应的ＦＦＴ蝶式计算，此时处理器间不需要通信；
第三步：各处理器执行logP次各自的蝶式计算，此时处理器间需要进行通信；
参数：
ts通信建立时间
th跨步延时
tb传送单位信包的时间
tc单位计算时间
（1）总的通信延迟
通信开销发生在算法的第三步上：
logP?1
To?P?(ts?th?tbn/P)?(th?ts)PlogP?tbnlogP
i?0
（1）等效率函数
W?fE(p)，由式3.19
随着P增加，为了维持E为一个常量，n也必须增加，因此Te?kTo。
因为E?
1 ，则k?
1?To
Te
E
1?E
Te?tcnlogn
（参考P269），所以：
tcnlogn?k[(tn?ts)PlogP?tbnlogP]
由于nlologP?PlogP，上式的第二项起到主要作用：
c btnlogn?ktnlogP，得n?Pktb/tc
c b
E c cbW?f(p)?tnlogn?tPktb/tclogPktb/tc?ktPktb/tc
E c c
b
（3）讨论
当E0.5时，k1，W?PlogP，如果
tb?tc
则W的增加