【课后习题】

一、 问答题


1、（Amdahl定律）如果问题规模为W（固定）的问题的串行部分为Ws，请证明不管用多少处理器，并行系统的加速比上限为W/Ws。



2、（超线性加速比）考虑下图所示的搜索树，其中黑色的节点表示问题的解。
a) 对树的串行搜索采用深度优先（DFS）算法，如果遍历树的每个弧耗费单位时间，那么需要多长时间才能找到解？
b) 将树在两个处理器间进行分布，如图所示，共同完成搜索任务，如果两个处理器都在它们各自的树上进行DFS搜索，那么要找到解需要多长时间，加速比是多少？请解释这个加速比。






3. （考虑各种操作的不同开销）假定完成两个数的相加需要一个单位时间，而直接相连的两个处理器之间传递一个数据需要10个单位时间，那么在4个处理器的超立方体上，用下图所示数据分布方法，完成16个数的加法需要多长的时间（采用的算法为面向16个处理器的超立方体的，具体过程见下面的图，采用四个处理器进行仿真）？请证明，通常来讲，在p个处理器上，采用螺旋数据分布（如本题中所描述的），来对n个处理器上n个数的加法（算法如本题中所描述）进行仿真（n>p），运行时间为 。
图一（螺旋数据分布）

图二（16处理器上16个数的加法，算法示意图）