计算机学院研究生《并行计算》课程考试试题（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)有id C 个节点与s 的距离为i 。
证明：由超立方体的性质知：一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有id C 种选择方式，即与s 的距离为i 得节点就有id 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 dD 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 ==代入计算得：16.4994%6%10Speedup =≈+最大加速比为：111lim lim16.7(1)/6%p pSpeedupf f p f→∞→∞===≈+-2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%f f pp≤=+-+得：23.5p≥故至少需要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; i<m; i++) {rowterm[i] = 0.0;#pragma omp parallel for reduction(+:rowterm[i])for (j=0; j<p; j++)rowterm[i] += a[i][2*j] * a[i][2*j+1];#pragma omp parallel forfor (j=0; j<p; j++) {a[i][2*j] /= rowterm[i];a[i][2*j+1] /= rowterm[i];}}}#pragma omp sections{#pragma omp parallel for private(j)for ( i=0; i<q; i++) {colterm[i] = 0.0;#pragma omp parallel for reduce(+:colterm [i])for ( j=0; j<p; j++)colterm[i] += b [2*j][i] * b [2*j+1] [i];#pragma omp parallel forfor ( j=0; j<p; j++) {b [2*j][i] /= colterm[i]; b [2*j+1] [i] /= colterm[i];}} } }8．（12分）查阅文献并结合自己的体会，列举1-2个你的研究领域里存在的典型并行计算应用，讨论一下它们适合的并行计算模式（不少于500字）。
答案1. 证明：（1）由超立方体的性质知： 一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有id C 种选择方式，即与s 的距离为i 得节点就有id 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 dD 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. 解： 由题可知计算规模是固定的，所以在并行环境下，根据Amdahl 定律可知： 加速比S=1/(1/p+f(1-1/p))，其中p 为处理器数，f 为串行分量的比例，则，f=(p/s-1)/(p-1)，同时对于固定规模的问题，并行系统所能达到的加速上限为1/f ，即受到串行分量的比例的限制。
在2个处理器的环境下，根据上图数据计算各并行程序的串行分量的比：并行程序I ：f 1=0.20; 并行程序II ：f 2=0.06; 并行程序III ：f 3=0.06; 并行程序IV ：f 4=0.02; 并行程序V ：f 5=0.15; 并行程序VI ：f 6=0.03;在16个处理器的环境下，根据上图数据计算各并行程序的加速比如下： 并行程序I ：S 1=4.00并行程序II ：S 2=5.72; 并行程序III ：S 3=8.41; 并行程序IV ：S 4=10.00; 并行程序V ：S 5=4.77; 并行程序VI ：S 6=10.67;则个并行程序在16个处理器的环境下与8个处理器的环境下的加速比提高了：并行程序I ：d 1=20%; 并行程序II ：d 2=31%; 并行程序III ：d 3=49%; 并行程序IV ：d 4=60%; 并行程序V ：d 5=25%; 并行程序VI ：d 6=64%;根据并行程序I 、V 的串行分量的比和16个处理器的环境下的加速比可知，对并行程序I 、V 在16个处理器上性能的陈述都选(b);根据并行程序II 和III 的串行分量的比和16个处理器的环境下的加速比可知，对并行程序II 在16个处理器上性能的陈述选(c);根据并行程序III 、IV 、VI 在16个处理器的环境下的加速比可知，对并行程序III 、IV 、VI 在16个处理器上性能的陈述都选(a);3. 1）由Amdahl 定律知：加速比1(1)/Speedup f f p=+-依题意知：6%,10f p ==代入计算得：16.4994%6%10Speedup =≈+最大加速比为：111lim lim16.7(1)/6%p pSpeedupf f p f→∞→∞===≈+-2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%f f pp≤=+-+得：23.5p≥故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？31:00010000;127:01000000;255:10000000若超立方体中的结点和进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到0101 1001的？1011 0011: 2210101 1001：1101011 0011(221)->1011 0001(222)->1011 0000(223)->1001 0000(224)->1001 0001->……->1000 0000(255)->0000 0000(0)->0000 0001->…..->0101 1100（104）->0101 1101（105）->0101 1111（106）->0101 1110（107）->0101 1010（108）->0101 1011（109）->0101 1001（110）1011 0011->1011 0001->1011 1001->1001 1001->1101 1001->0101 1001(第一种方法)1011 0011->0011 0011->0111 0011->0101 0011->0101 1011->0101 1001(第二种方法)1101 0011->1001 0011->1101 0011->0101 0011->0101 0001->0101 1001(第三种方法)5.Step1：R=｛T11,T12｝是无直接后继的任务，任取，选T12,有a(T12)<-1；Step2：i从2到12循环，完成对a(Tj)(j=1,2…12)赋值i=2；R=｛T11，T10｝，N(T10)=｛1｝，N(T10)={0}，选T11，则a(T11)<-2；i=3; R=｛T9，T6，T10｝，N(T9)=2,N(T6)={2,1},N(T10)=1,选T10则a(T10)<-3;i=4;R={T9,T6,T7,T8},N(T9)=2,N(T6)={2,1},N(T7)=3,N(T8)=3,T9，T6任选，选T6，a(T6)<-4;i=5;R={T9,T7,T8},N(T9)=2,N(T7)=3,N(T8)=3,选T9，则a(T9)<-5;i=6;R={T4,T5,T7,T8},N(T4)=5,N(T5)=5,N(T7)=3,N(T8)=3,任选T7，T8，选T7，则a(T7)<-6;i=7;R={T4,T5,T8},N(T4)=5,N(T5)=5,N(T8)=3,选T8，则a(T8)<-7;i=8;R={T4,T5,T3},N(T4)=5,N(T5)=5,N(T3)={7,6}，T4，T5任选,选T4，则a(T4)<-8 i=9,R={T5,T3},N(T5)=5,N(T3)={7,6},选T5，则a(T5)<-9;i=10,R={T2,T3},N(T2)={9,8,4},N{T3}={7,6}，选T3，a(T3)<-10;i=11,R={T2},N(T2)={9,8,4}，选T2，a(T2)<-11;i=12,a(T1)<-12;Step3：构造L表：L=｛T1,T2,T3,T5,T4,T8,T7,T9,T6,T10,T11,T12｝；Step4:6. 策略如下：在执行后序遍历时，我们系统地访问树中所有的边，而且每条边要通过两次：一次从父节点到子节点，而另一次从子节点到父节点。