第 1 页 共 4 页
1.5 题：
对于 N=2
k
个节点的 de Bruijn 网络
直径为 log
2
N=k
对剖带宽为：O(N/log
2
N)=O(N/k)
【注】参考附件“lecture18.pdf”。
1.6 题：
4 5 6 72 30 1
实线表示交换，虚线表示洗牌。
交换：二进制地址编号中第 0 位不同的两个输入的输出互相交换。
洗牌：输入端的二进制地址左移一位得到输出端对应的二进制地址。
图中：N=8=2
n
，n=3。
从图中也可以看到，在洗牌交换网络中， 最远的两个入、出端号是全“0”和全
“1”，它们的连接，需要 n 次交换和 n-1 次洗牌，所以其最大距离（直径）为 2n-1。
节点度恒为 3，对剖带宽为 N/2。
1.10 题：
处理器 P1 将本地高速缓存 X 更新为 X’。采用写无效协议时，P1 通过总线使共
享存储器上的和所有在其他处理器上的该缓存块的拷贝实效。采用写更新协议时，P1
通过总线使所有在其他处理器的本地高速缓存上的 X 的拷贝更新为 X’，并将共享存
储器上的 X 的拷贝置为无效。
2.1 题：
总线带宽=总线宽度×一个时钟周期内交换的数据包个数×总线频率
=8×(16/8)×100=1.6Gbps
2.8 题：
SMP：对称多处理器，共享存储，高速缓存一致性，低通信延迟，不可扩放性
SSMP：可扩放共享存储多处理机，共享存储，扩放性好
CC-NUMA：非均匀存储访问，高速缓存一致性，扩放性好
MPP：大规模处理器数，分布存储，使用物理分布的存储器和 I/O，扩放性好
评论30