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

1、计算机学院研究生并行计算课程考试试题（2010级研究生，2011.1）1（12分）定义图中节点u和v之间的距离为从u到v最短路径的长度。已知一个d维的超立方体，1）指定其中的一个源节点s，问有多少个节点与s 的距离为i，其中0id。证明你的结论。2）证明如果在一个超立方体中节点u与节点v的距离为i，则存在i！条从u到v的长度为i的路径。1)有个节点与s的距离为i。证明：由超立方体的性质知：一个d维的超立方体的每个节点都可由d位二进制来表示，则与某个节点的距离为i的节点必定在这d位二进制中有i位与之不同，那么随机从d位中选择i位就有种选择方式，即与s的距离为i得节点就有个。2)证明：由1）所述可

2、知：节点u与节点v的距离为i则分别表示u、v节点的二进制位数中有i位是不同的。设节点u表示为：，节点v表示为：，则现在就是要求得从变换到 的途径有多少种。那么利用组合理论知识可知共有即中途径。所以存在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

3、.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%的执行时间花费在一个可

4、以并行化的函数中。现使其并行化，问该并行程序在10个处理机上执行所能达到的加速比是多少？能达到的最大加速比是多少？2）一个并行程序，在单个处理机上执行，6%的时间花费在一个I/O函数中，问要达到加速比10，至少需要多少个处理机？1）由Amdahl定律知：加速比依题意知：代入计算得：最大加速比为：2)由题意知：此时的串行时间比例为则：由式子得：故至少需要24台处理机。4（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？2）若超立方体中的结点10110011和0101

5、1001进行通讯，如果按照环网拓扑结构，从10110011出发，在超立方体中依次经过哪些节点才能把一条消息传递到01011001？如果按照超立方体拓扑结构，又是如何实现从10110011传递一条消息到01011001的？5（16分）已知12个具有单位执行时间的任务，任务图如下。现在3个处理机上处理该任务集，请用Coffman-Graham算法求该任务集的调度优先表L，并用Graham表调度算法调度L，给出任务调度的Gantt图表示。T1T2T3T4T5T6T7T8T9T10T11T126（10分）采用与前序遍历二元树的PRAM算法相同的数据结构，设计一个后序遍历二元树的PRAM算法。7（10分

6、）下面是一个串行程序段，用OpenMP最大限度地开发其并行性。这里假设a、b均为正实值数组，有合法的定义。float rowtermmfloat coltermq;int i, j;#pragma omp parallel #pragma omp sections#pragma omp parallel for private(j)for ( i=0; im; i+) rowtermi = 0.0;#pragma omp parallel for reduction(+:rowtermi) for (j=0; jp; j+) rowtermi += ai2*j * ai2*j+1; #prag

7、ma omp parallel for for (j=0; jp; j+) ai2*j /= rowtermi;ai2*j+1 /= rowtermi;#pragma omp sections#pragma omp parallel for private(j)for ( i=0; iq; i+) coltermi = 0.0;#pragma omp parallel for reduce(+:colterm i) for ( j=0; jp; j+) coltermi += b 2*ji * b 2*j+1 i; #pragma omp parallel for for ( j=0; j10

8、11 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 00

9、11-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,212)赋值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(T

10、9)=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

11、(T5)=5,N(T3)=7,6,选T5，则a(T5)-9;i=10,R=T2,T3,N(T2)=9,8,4,NT3=7,6，选T3，a(T3)-10;i=11,R=T2,N(T2)=9,8,4，选T2，a(T2)-11;i=12,a(T1)5000)for (j=0; jp; j+) for(i=0;im;i+)rowtermi = 0.0;rowtermi += ai2*j * ai2*j+1;for(i=0;i5000)for (j=0; jp; j+) for(i=0;iq;i+)rowtermi = 0.0;coltermi += b2*ji * b2*j+1 i;for(i=0;i

12、q;i+)b2*ji /= coltermi;b2*j+1 i /= coltermi;8我研究生阶段的主要研究方向就是做信息检索。随着计算机的普及和网络的日益发展，数字化信息爆炸式增长。这些海量信息包含了大量宝贵的资源，虽然单台计算机的处理能力不断提高，但是在如此大规模的条件下，要对这样海量的信息进行检索，单台计算机的处理能力毕竟有限，需要多台计算机进行“团队作战”。而并行计算能够利用多台计算机或者多个处理器的计算或存储资源来解决大规模问题。因此，很自然地会想到将并行处理技术引入到信息检索当中，产生了相应的并行信息检索。要实现并行检索，首先让我们考察信息检索的一般过程：图1 一般信息检索的过

13、程如图1所示，用户提交一条查询，代理程序(broker)对原始查询进行处理(如查询的分析转换或格式化处理等等)，然后将处理后的查询发给搜索程序，搜索程序找到结果并进行处理(如排序)后返回给代理，代理经过必要的处理(如结果的归整、合并等)将结果返回给用户。 从以上可以看出，信息检索有并行处理的潜力可以充分挖掘。根据对象的不同，并行检索总体上可通过以下两种方式实现并行：1. 多条查询之间的并行处理一个最自然的想法就是利用MIMD结构对多条查询的处理并行化，即每个处理器处理不同的查询，每个查询的处理之间相互独立，最多只对共享内存内的部分代码或者公有数据实行共享。这种方法也称为任务级的并行检索。它可以

14、同时处理多个查询请求，从而提高检索的吞吐量。图2显示了3条不同查询在3个处理器上的并行处理过程。每条查询通过代理(也可同时运行多个代理程序，每个代理分别处理一条查询)发送到不同搜索程序(每个处理器上运行一个搜索程序)上去执行，每个搜索程序的结果通过代理返回到不同查询的发起者。图2 查询间的并行处理过程如果MIMD由多台具有自身处理器和磁盘的计算机组成，每台机器执行自己的搜索程序，并且只访问本地的磁盘，则没有硬件资源访问冲突问题。但如果多个搜索程序访问的是相同的磁盘资源，则可能存在磁盘存取冲突问题。这时可以通过增加磁盘或采用类似Raid磁盘阵列的方法来减少冲突，但同时不免加大硬件设备的开销。另外

15、一些可能的方法包括复制访问频繁的数据到不同磁盘以降低访问冲突、将数据分割到多个磁盘等等。 查询间并行化策略是从一般检索升级到并行检索的最简单方法。简单地说，就是将检索系统复制多份(数据可以复制也可以不复制)，每份分别处理不同的查询请求。当然，这种升级硬件资源消耗比较高。而且，简单地堆积硬件资源并不一定就可以提高信息检索的效率，必须考虑硬件资源的访问冲突，设计合理的软件结构和访问策略，才能提高信息检索的总体性能。2. 单条查询内部的并行处理即对单条查询的计算量进行分割，分成多个子任务，并分配到多个处理器上的搜索进程上去执行。这种检索也称为进程级并行检索。将单条查询分成多个子任务的方法通常有两种：一种称为数据集分割，它是事先将数据集分割成多个子集合