考试试题二
一、 名词解释（20分，每小题四分）
DSM
COMA
总线
虫蚀寻径
LogP模型
二、 （16分）设32个处理器编号为0，1，2，…，31，用单级互连网络相连。试问当互连函数分别为
（1）
（2）
（3）
（4）蝶式置换
连接时，第11号处理器与哪一个处理器相连？
三、（16分）假定处理器
开始时存有数据d
i
，所谓的前序累加求和（Prefix-Sum）指用 来代替P
i
中的原始数据d
i
，下面的算法给出了PRAM模型上的前序累加求和的算法：
前序累加求和算法
输入：Pi中保存有di，
输出：Pi中的内容为
Program Prefix_sum
Begin
for j=0 to logn �C 1 do
for k = 2j + 1 to n par-do
（i） Pi = di �C 2j
（ii） di = di + di �C 2j
endfor
endfor
End.
其中，Par-do表示不同的循环变量对应的计算可以并行执行
（1）n = 8为例，按照上面的算法逐步计算出累加和 （2）分析算法时间复杂度
四、（16分）在p个处理器的超立方体上完成n个数的加法（p < n，其中p 和n 都是2的整数次幂）。完成并行计算的解题过程，并分析算法是否为开销最优。
五、（16分）考虑下图所示的搜索树，其中黑色的节点表示问题的解。
a) 对树的串行搜索采用深度优先（DFS）算法，如果遍历树的每个弧耗费单位时间，那么需要多长时间才能找到解？
b) 将树在两个处理器间进行分布，如图所示，共同完成搜索任务，如果两个处理器都在它们各自的树上进行DFS搜索，那么要找到解需要多长时间，加速比是多少？请解释这个加速比。
六、（16分）在并行计算中，如果问题规模为W固定，问题的串行部分为Ws，请证明不管用多少处理器，并行系统的加速比上限为W/Ws。