并行计算试题及答案(20011.1)

计算机学院研究生《并行计算》课程考试试题（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)有idC个节点与s的距离为i。证明：由超立方体的性质知：一个d维的超立方体的每个节点都可由d位二进制来表示，则与某个节点的距离为i的节点必定在这d位二进制中有i位与之不同，那么随机从d位中选择i位就有idC种选择方式，即与s的距离为i得节点就有idC个。2)证明：由1）所述可知：节点u与节点v的距离为i则分别表示u、v节点的二进制位数中有i位是不同的。设节点u表示为：121D.........jjijidDDDDD，节点v表示为：''121D.........jjijidDDDDD，则现在就是要求得从121D.........jjijidDDDDD变换到''121D.........jjijidDDDDD的途径有多少种。那么利用组合理论知识可知共有*(1)*(2)*...*2*1iii即!i中途径。所以存在i！条从u到v的长度为i的路径。2．（18分）6个并行程序的执行时间，用I-VI表示，在1-8个处理器上执行了测试。下表表示了各程序达到的加速比。处理器数加速比IIIIIIIVVVI11.001.001.001.001.001.0021.671.891.891.961.741.9432.142.632.682.882.302.8242.503.233.393.672.743.6552.783.684.034.463.094.4263.004.004.625.223.385.1573.184.225.155.933.625.8483.334.355.636.253.816.50对其中的每个程序，选出最适合描述其在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)/Speedupffp依题意知：6%,10fp代入计算得：16.4994%6%10Speedup最大加速比为：111limlim16.7(1)/6%ppSpeedupffpf2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%ffpp得：23.5p故至少需要24台处理机。4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？2）若超立方体中的结点10110011和01011001进行通讯，如果按照环网拓扑结构，从10110011出发，在超立方体中依次经过哪些节点才能把一条消息传递到01011001？如果按照超立方体拓扑结构，又是如何实现从10110011传递一条消息到01011001的？5．（16分）已知12个具有单位执行时间的任务，任务图如下。现在3个处理机上处理该任务集，请用Coffman-Graham算法求该任务集的调度优先表L，并用Graham表调度算法调度L，给出任务调度的Gantt图表示。T1T2T3T4T5T6T7T8T9T10T11T126．（10分）采用与前序遍历二元树的PRAM算法相同的数据结构，设计一个后序遍历二元树的PRAM算法。7．（10分）下面是一个串行程序段，用OpenMP最大限度地开发其并行性。这里假设a、b均为正实值数组，有合法的定义。floatrowterm[m]floatcolterm[q];inti,j;#pragmaompparallel{#pragmaompsections{#pragmaompparallelforprivate(j)for(i=0;im;i++){rowterm[i]=0.0;#pragmaompparallelforreduction(+:rowterm[i])for(j=0;jp;j++)rowterm[i]+=a[i][2*j]*a[i][2*j+1];#pragmaompparallelforfor(j=0;jp;j++){a[i][2*j]/=rowterm[i];a[i][2*j+1]/=rowterm[i];}}}#pragmaompsections{#pragmaompparallelforprivate(j)for(i=0;iq;i++){colterm[i]=0.0;#pragmaompparallelforreduce(+:colterm[i])for(j=0;jp;j++)colterm[i]+=b[2*j][i]*b[2*j+1][i];#pragmaompparallelforfor(j=0;jp;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位就有idC种选择方式，即与s的距离为i得节点就有idC个。（2)由(1)所述可知：节点u与节点v的距离为i则分别表示u、v节点的二进制位数中有i位是不同的。设节点u表示为：121D.........jjijidDDDDD，节点v表示为：''121D.........jjijidDDDDD，则现在就是要求得从121D.........jjijidDDDDD变换到''121D.........jjijidDDDDD的途径有多少种。那么利用组合理论知识可知共有*(1)*(2)*...*2*1iii即!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：f1=0.20;并行程序II：f2=0.06;并行程序III：f3=0.06;并行程序IV：f4=0.02;并行程序V：f5=0.15;并行程序VI：f6=0.03;在16个处理器的环境下，根据上图数据计算各并行程序的加速比如下：并行程序I：S1=4.00并行程序II：S2=5.72;并行程序III：S3=8.41;并行程序IV：S4=10.00;并行程序V：S5=4.77;并行程序VI：S6=10.67;则个并行程序在16个处理器的环境下与8个处理器的环境下的加速比提高了：并行程序I：d1=20%;并行程序II：d2=31%;并行程序III：d3=49%;并行程序IV：d4=60%;并行程序V：d5=25%;并行程序VI：d6=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)/Speedupffp依题意知：6%,10fp代入计算得：16.4994%6%10Speedup最大加速比为：111limlim16.7(1)/6%ppSpeedupffpf2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%ffpp得：23.5p故至少需要24台处理机。4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？31:00010000;127:01000000;255:10000000若超立方体中的结点10110011和01011001进行通讯，如果按照环网拓扑结构，从10110011出发，在超立方体中依次经过哪些节点才能把一条消息传递到01011001？如果按照超立方体拓扑结构，又是如何实现从10110011传递一条消息到01011001的？10110011:22101011001：11010110011(221)-10110001(222)-10110000(223)-10010000(224)-10010001-……-10000000(255)-00000000(0)-00000001-…..-01011100（104）-01011101（105）-01011111（106）-01011110（107）-01011010（108）-01011011（109）-01011001（110）10110011-10110001-10111001-10011001-11011001-01011001(第一种方法)10110011-00110011-01110011-01010011-01011011-01011001(第二种方法)11010011-10010011-11010011-01010011-01010001-01011001(第三种方法)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)-8i=9,R={T5,T3},N(T5)=5,N(T3)={7,6},