考试试题三
一、 名词解释（20分，每小题四分）
MPP
NUMA
PRAM
同步
任务并行性
二、 （16分）求下图所示Iliac网当结点数为N时，网络的链路条数、直径、对分宽度。
三、（16分）考虑如下的PRAM-EREW模型：p个处理器，m个存储器。我们可以在一个p个处理器，每个处理器有m/p个存储器的消息传递结构的并行计算机上模拟这个模型。如果一个算法在这种PRAM-EREW上的运行时间是t，请给出这个算法在下面的体系结构上的运行时间上限：
(1) p处理器的环（ring）
(2) p处理器的二维网格（mesh）
(3) p处理器的超立方体（hypercube）
四、（16分）在p个处理器的超立方体上完成n个数的加法（p < n，其中p和n都是2的整数次幂），使用的方法如下图（n=16和p=4时的解题过程）
证明上述使用的算法为开销最优的。
五、对n×n矩阵，在具有p个处理器的超立方体互联结构上实现矩阵转置。基本思路是先将一个n×n的矩阵先分成4个子矩阵，把每个子矩阵看作一个整体对整个大矩阵进行转置；然后每个子矩阵再分成4个更小的矩阵，逐次递归，最后实现了矩阵的转置。分析算法总的运行时间。
六、对于一个赋权图G=(V, E, w)和图G任意一点v，寻找v到图G中其它各点的最短路，最终结果是一个向量。Dijkstra算法是解决一点到其它各点最短路的常用方法，算法如下：
1． procedure DIJKSTRA_SINGLE_SOURCE_SP(V,E,w,s)
2． begin
3． V
T
:={s};
4． for all v∈(V-V
T
) do
5． if (s,v) exists set l[v]:=w(s,v);
6． else set l[v]=∞;
7． while V
T
≠V do
8． begin
9． find a vertex u such that l［u］=min{l[v]|v∈(V-V
T
)};
10． V
T
:=V
T
∪{u};
11． for all v∈(V-V
T
) do
12． l[v]=min{l[v],l[u]+w(u,v)};
13． endwhile
14． end DIJKSTRA_SINGLE_SOURCE_SP
请给出求解一点到其它各点最短路的并行算法在超立方体上的并性性能分析。