并行计算试题及复习资料.doc

计算机学院研究生《并行计算》课程
考试试题
（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)有个节点及s的距离为i。
证明：由超立方体的性质知：
一个d维的超立方体的每个节点都可由d位二进制来表示，则及某个节点的距离为i的节点必定在这d位二进制中有i位及之不同，那么随机从d位中选择i位就有种选择方式，即及s的距离为i得节点就有个。
2)
证明：由1）所述可知：
节点u及节点v的距离为i则分别表示u、v节点的二进制位数中有i位是不同的。设节点u表示为：，节点v表示为：，则现在就是要求得从变换到 的途径有多少种。那么利用组合理论知识可知共有即中途径。所以存在i！条从u到v的长度为i的路径。
2．（18分）6个并行程序的执行时间，用I-VI表示，在1-8个处理器上执行了测试。下表表示了各程序达到的加速比。
处理器数
加速比
I
II
III
IV
V
VI
1
1.00
1.00
1.00
1.00
1.00
1.00
2
1.67
1.89
1.89
1.96
1.74
1.94
3
2.14
2.63
2.68
2.88
2.30
2.82
4
2.50
3.23
3.39
3.67
2.74
3.65
5
2.78
3.68
4.03
4.46
3.09
4.42
6
3.00
4.00
4.62
5.22
3.38
5.15
7
3.18
4.22
5.15
5.93
3.62
5.84
8
3.33
4.35
5.63
6.25
3.81
6.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定律知：
加速比
依题意知：
代入计算得：
最大加速比为：
2)由题意知：此时的串行时间比例为则：
由式子得：
故至少需要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图表示。
T1
T2
T3
T4
T5
T6
T7
T8
T9
T10
T11
T12

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 for
for (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 for
for ( 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位就有种选择方式，即及s的距离为i得节点就有个。
（2)由(1)所述可知：
节点u及节点v的距离为i则分别表示u、v节点的二进制位数中有i位是不同的。设节点u表示为：，节点v表示为：，则现在就是要求得从变换到 的途径有多少种。那么利用组合理论知识可知共有即中途径。所以存在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：f 3=0.06;
并行程序IV：f 4=0.02;
并行程序V：f5=0.15;
并行程序VI：f6=0.03;
在16个处理器的环境下，根据上图数据计算各并行程序的加速比如下：
并行程序I：S1=4.00
并行程序II：S 2=5.72;
并行程序III：S 3=8.41;
并行程序IV：S 4=10.00;
并行程序V：S 5=4.77;
并行程序VI：S6=10.67;
则个并行程序在16个处理器的环境下及8个处理器的环境下的加速比提高了：
并行程序I：d1=20%;
并行程序II：d2=31%;
并行程序III：d 3=49%;
并行程序IV：d4=60%;
并行程序V：d 5=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定律知：
加速比
依题意知：
代入计算得：
最大加速比为：
2)由题意知：此时的串行时间比例为则：
由式子得：
故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，
1）问环节点31，127，255分别映射到超立方体的哪个节点上？
31:00010000;127:01000000;255:10000000
若超立方体中的结点与进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到0101 1001的？
1011 0011: 221
0101 1001：110
1011 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:
依据任务图与表L，应用Graham表调度算法，调度结果如Gantt图所示。

T8
T6

T3
T4
T9
T11

T1
T2
T5
T7
T10
T12
6. 策略如下：
在执行后序遍历时，我们系统地访问树中所有的边，而且每条边要通过两次：一次从父节点到子节点，而另一次从子节点到父节点。
现将每条边“分成”两条，一条用于从上往下的遍历（向下边），而另一条用于从下往上的回溯（向上边）。这样，后序遍历树问题就可转换为单链表问题。
基于这种面向边的树遍历观点可以设计出一个快速的并行算法求结点编号。该算法由四步完成。具体如下：
Step1. 构造一个单链表（singly-linked List），单链表的每个顶点对应于遍历树时向下边或向上边。
Step2. 给新创建的单链表中的每个结点赋权值。
及向下边相应的顶点赋予权值0，表示当这个边被遍历时，该结点不被计数；
及向上边相应的顶点赋予权值1，表示该结点要被计数。
如图3.3所示。
图3.3 树的后序遍历。
说明:（a）树
（b）增加向上边（虚线边）
（c）对树的边建立联结表，向下边赋权值0，向上边赋权值1
（d）计算各结点到表尾的位置序号（权值的后缀与）。
（e）后序遍历的结点编号
结点的后序遍历数=n-结点的位置序数
Step3 计算节点的位置序号（rank）。
使用及“求单链表中元素位置序号”类似的方法求
singly-Linked List表中每一元素的位置序号。
Step4 及向上边相关联的处理机使用计算出的位置序号计算
结点的后序遍历数并赋给及之相联的树的结点
——该结点是向上边起始点所对应的结点。
7. float rowterm[m];
float colterm[q];
int i, j;
#pragma omp parallel for private(i) if(j>5000)
for (j=0; j<p; j++)
for(i=0;i<m;i++)
rowterm[i] = 0.0;
rowterm[i] += a[i][2*j] * a[i][2*j+1];
for(i=0;i<m;i++)
a[i][2*j] /= rowterm[i];
a[i][2*j+1] /= rowterm[i];
#pragma omp parallel for private(i) if(j>5000)
for (j=0; j<p; j++)
for(i=0;i<q;i++)
rowterm[i] = 0.0;
colterm[i] += b[2*j][i] * b[2*j+1] [i];
for(i=0;i<q;i++)
b[2*j][i] /= colterm[i];
b[2*j+1] [i] /= colterm[i];
8．
我研究生阶段的主要研究方向就是做信息检索。随着计算机的普及与网络的日益发展，数字化信息爆炸式增长。这些海量信息包含了大量宝贵的资源，虽然单台计算机的处理能力不断提高，但是在如此大规模的条件下，要对这样海量的信息进行检索，单台计算机的处理能力毕竟有限，需要多台计算机进行“团队作战”。而并行计算能够利用多台计算机或者多个处理器的计算或存储资源来解决大规模问题。因此，很自然地会想到将并行处理技术引入到信息检索当中，产生了相应的并行信息检索。
要实现并行检索，首先让我们考察信息检索的一般过程：
图1 一般信息检索的过程
如图1所示，用户提交一条查询，代理程序(broker)对原始查询进行处理(如查询的分析转换或格式化处理等等)，然后将处理后的查询发给搜索程序，搜索程序找到结果并进行处理(如排序)后返回给代理，代理经过必要的处理(如结果的归整、合并等)将结果返回给用户。
从以上可以看出，信息检索有并行处理的潜力可以充分挖掘。根据对象的不同，并行检索总体上可通过以下两种方式实现并行：
1. 多条查询之间的并行处理
一个最自然的想法就是利用MIMD结构对多条查询的处理并行化，即每个处理器处理不同的查询，每个查询的处理之间相互独立，最多只对共享内存内的部分代码或者公有数据实行共享。这种方法也称为任务级的并行检索。它可以同时处理多个查询请求，从而提高检索的吞吐量。图2显示了3条不同查询在3个处理器上的并行处理过程。每条查询通过代理(也可同时运行多个代理程序，每个代理分别处理一条查询)发送到不同搜索程序(每个处理器上运行一个搜索程序)上去执行，每个搜索程序的结果通过代理返回到不同查询的发起者。
图2 查询间的并行处理过程
如果MIMD由多台具有自身处理器与磁盘的计算机组成，每台机器执行自己的搜索程序，并且只访问本地的磁盘，则没有硬件资源访问冲突问题。但如果多个搜索程序访问的是相同的磁盘资源，则可能存在磁盘存取冲突问题。这时可以通过增加磁盘或采用类似Raid磁盘阵列的方法来减少冲突，但同时不免加大硬件设备的开销。另外一些可能的方法包括复制访问频繁的数据到不同磁盘以降低访问冲突、将数据分割到多个磁盘等等。
查询间并行化策略是从一般检索升级到并行检索的最简单方法。简单地说，就是将检索系统复制多份(数据可以复制也可以不复制)，每份分别处理不同的查询请求。当然，这种升级硬件资源消耗比较高。而且，简单地堆积硬件资源并不一定就可以提高信息检索的效率，必须考虑硬件资源的访问冲突，设计合理的软件结构与访问策略，才能提高信息检索的总体性能。
2. 单条查询内部的并行处理
即对单条查询的计算量进行分割，分成多个子任务，并分配到多个处理器上的搜索进程上去执行。这种检索也称为进程级并行检索。将单条查询分成多个子任务的方法通常有两种：一种称为数据集分割，它是事先将数据集分割成多个子集合，对同一条查询分别查询多个子集合数据，然后将每个子集合上的结果合并成最终结果；另一种称为查询项分割，它是将查询分解成多个子查询(如将一个多关键词查询分成多个单关键词查询)，对每个子查询分别查询数据集，得到部分结果，并将部分结果合并成最终结果。图3给出了一个单条查询内部并行处理的示意图：查询发送给代理程序，代理程序将一条查询划分成多条子查询，每条子查询分别发送给一个搜索进程进行处理，各进程返回的子结果在代理上进行综合，得到最后的总结果返回给用户。
图3 查询内部的并行处理过程
第 20 页