计算机学院研究生《并行计算》课程
考试试题
（2010级研究生，2011.1）
1．（12分）定义图中节点u 和v 之间的距离为从u 到v 最短路径的长度。已知一个d 维的超立方体，1）指定其中的一个源节点s ，问有多少个节点与s 的距离为i ，其中0≤i ≤d 。证明你的结论。2）证明如果在一个超立方体中节点u 与节点v 的距离为i ，则存在i ！条从u 到v 的长度为i 的路径。 1)有i
d C 个节点与s 的距离为i 。 证明：由超立方体的性质知：
一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节
点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有i
d C 种选择方式，即与s 的距离为i 得节点就有i
d C 个。 2)
证明：由1）所述可知：
节点u 与节点v 的距离为i 则分别表示u 、v 节点的二进制位数中有i 位是不同的。设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为：
''121D .........j j i j i d
D D D D D +-+，则现在就是要求得从
121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多
少种。那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。所以存在i ！条从u 到v 的长度为i 的路径。
2．（18分）6个并行程序的执行时间，用I-VI 表示，在1-8个处理器上执行了测试。下表表示了各程序达到的加速比。
对其中的每个程序，选出最适合描述其在16个处理器上性能的陈述。 a ） 在16个处理器上的加速比至少比8个处理器上的加速比高出40%。 b ） 由于程序中的串行程序比例很大，在16个处理器上的加速比不会比8
个处理器上的加速比高出40%。
c ） 由于处理器增加时开销也会很大，在16个处理器上的加速比不会比8
个处理器上的加速比高出40%。 给出分析过程和结论。
3. （10分）经测试发现，1）一个串行程序，94%的执行时间花费在一个可以并行化的函数中。现使其并行化，问该并行程序在10个处理机上执行所能达到的加速比是多少？能达到的最大加速比是多少？2）一个并行程序，在单个处理机上执行，6%的时间花费在一个I/O 函数中，问要达到加速比10，至少需要多少个处理机？ 1）由Amdahl 定律知：
加速比1
(1)/Speedup f f p
=
+-
依题意知：6%,10f p ==
代入计算得：1
6.4994%6%10
Speedup =
≈+
最大加速比为：
111
lim lim16.7
(1)/6%
p p
Speedup
f f p f
→∞→∞
===≈
+-
2)由题意知：此时的串行时间比例为6%则：
由式子
11
10
94%
(1)/6%
f f p
p
≤=
+-+
得：23.5
p≥
故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？2）若超立方体中的结点10110011和进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到的？
5．（16分）已知12个具有单位执行时间的任务，任务图如下。现在3个处理机上处理该任务集，请用Coffman-Graham算法求该任务集的调度优先表L，并用Graham表调度算法调度L，给出任务调度的Gantt图表示。
6．（10分）采用与前序遍历二元树的PRAM算法相同的数据结构，设计一个后序遍历二元树的PRAM算法。
7．（10分）下面是一个串行程序段，用OpenMP最大限度地开发其并行性。这里假设a、b均为正实值数组，有合法的定义。
float rowterm[m]
float colterm[q];
int i, j;
#pragma omp parallel {
#pragma omp sections{
#pragma omp parallel for private(j)
for ( i=0; irowterm[i] = 0.0;
#pragma omp parallel for reduction(+:rowterm[i])
for (j=0; jrowterm[i] += a[i][2*j] * a[i][2*j+1];
#pragma omp parallel for
for (j=0; ja[i][2*j] /= rowterm[i];
a[i][2*j+1] /= rowterm[i];
}
}
}
#pragma omp sections{
#pragma omp parallel for private(j)
for ( i=0; icolterm[i] = 0.0;
#pragma omp parallel for reduce(+:colterm [i])
for ( j=0; jcolterm[i] += b [2*j][i] * b [2*j+1] [i];
#pragma omp parallel for
