并行计算 - 练习题

并行计算期末试题及答案1. 基础概念部分并行计算是一种计算模式，它使用多个处理单元同时执行计算操作，以加快计算速度。

在现代计算机系统中，我们常常使用多核处理器、图形处理器（GPU）或者分布式系统来实现并行计算。

1.1 并行计算的优势并行计算具有以下几个优势：加速计算速度：通过同时执行多个计算任务，可以极大地提高计算效率。

解决大规模问题：并行计算可以处理大规模和复杂的问题，提供更精确的结果。

降低能耗：通过合理利用处理器资源，可以降低计算任务的能耗。

应用广泛：并行计算可以应用于各个领域，如科学计算、大数据分析、机器学习等。

1.2 并行计算的分类并行计算按照任务之间的关系可以分为两类：数据并行：将数据划分为多个子集，同时在不同的处理器上进行计算，然后将计算结果汇总。

常见的应用包括矩阵运算、图像处理等。

任务并行：将任务划分为多个子任务，每个子任务由一个独立的处理器执行，最后将各个子任务的结果合并。

常见的应用包括并行搜索算法、并行排序等。

2. 并行计算的算法设计2.1 并行算法设计要点在设计并行算法时，需要考虑以下几个要点：任务划分：将计算任务划分为多个子任务，确保各个子任务之间的计算工作均衡，并保持任务之间的独立性。

任务调度：合理安排各个处理器上的任务执行顺序和时间，最大程度地减少通信开销和等待时间。

数据通信：处理器之间需要进行数据交换和通信，应选择合适的通信方式，并考虑通信延迟和带宽等因素。

数据同步：在多个处理器之间，可能需要进行数据同步操作，确保各个处理器之间的数据一致性。

2.2 并行算法实例：并行矩阵乘法并行矩阵乘法是一个常见的数据并行算法，可以有效地利用多核处理器加速大规模矩阵运算。

具体算法如下：步骤1：将输入矩阵划分为若干个小矩阵，每个小矩阵分配给一个处理器。

步骤2：每个处理器计算相应小矩阵的部分结果。

步骤3：将各个处理器计算得到的部分结果进行求和，得到最终的矩阵乘积结果。

3. 并行计算的应用举例3.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)有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%。

第十二章 并行程序设计基础习题例题：1、假定有n 个进程P(0)，P(1)，…，P(n -1)，数组元素][i a 开始时被分配给进程P(i )。

试写出求归约和]1[]1[]0[-+++n a a a 的代码段，并以8=n 示例之。

2、假定某公司在银行中有三个账户X 、Y 和Z ，它们可以由公司的任何雇员随意访问。

雇员们对银行的存、取和转帐等事务处理的代码段可描述如下：/*从账户X 支取￥100元*/atomic {if (balance[X] > 100) balance[X] = balance[X]-100； }/*从账户Y 存入￥100元*/atomic {balance[Y] = balance[Y]-100；}/*从账户X 中转￥100元到帐号Z*/atomic {if (balance[X] > 100){balance[X] = balance[X]-100；balance[Z] = balance[Z]+100；} }其中，atomic {}为子原子操作。

试解释为什么雇员们在任何时候（同时）支、取、转帐时，这些事务操作总是安全有效的。

3、考虑如下使用lock 和unlock 的并行代码：parfor (i = 0；i < n ；i++){noncritical sectionlock(S)；critical sectionunlock(S)；}假定非临界区操作取T ncs时间，临界区操作取T cs时间，加锁取t lock时间，而去锁时间可忽略。

则相应的串行程序需n( T ncs + T cs )时间。

试问：①总的并行执行时间是多少？②使用n个处理器时加速多大？③你能忽略开销吗？4、计算两整数数组之内积的串行代码如下：Sum = 0；for(i = 0；i < N；i++)Sum = Sum + A[i]*B[i]；试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。

例题习题讲解例1 SIMD-SM上求最大值算法Beginfor k=m-1 to 0 dofor j=2k to 2k+1-1 par-doA[j]=max{A[2j], A[2j+1]}end forend forend时间分析t(n)=m×O(1)=O(logn)p(n)=n/2c(n)=O(nlogn) 非成本最优例2 令n=2k(k>=0)，求n个数和的并行算法算法运行时间：t(n)=O(logn)总运算量: W(n)=W(1)(n)+W(2)(n)+W(3)(n)=n+∑n/2h+1=O(n)由Brent定理知: t(n)=O(n/p+logn)例3 设A为矩阵，有如下串行程序段：f o r i=1t o n d of o r j=1t o n d oa[3i,2j]=a[3i-2,2j-1]e n df o re n df o r其相关方向向量为，可知行和列间同时存在数据相关。

在此我们可以试用行划分、列划分和方块划分.在行划分的情况下令m=┌n/p┐,例1的串行程序段可以转化为如下的并行程序段：f o r k=1t o P P a r-d of o r i1=1t o m d of o r j=1t o n d oa[3(k-1)m+3i1,2j]=a[3(k-1)m+3i1-2,2j-1]e n df o re n df o re n df o r例4 设A为一个n阶方阵，有如下串行程序段：f o r i=1t o n d of o r j=1t o n d oa[i,j]=a[i-1,j]e n df o re n df o r分析矩阵A的元素下标i和j，则i和j的相关方向向量为，各列之间数据无任何相关关系。

因此对矩阵A可按列划分。

串行程序段可转化为如下并行程序段：f o r k=1t o P P a r-d of o r j1=1t o m d of o r i=1t o n d oa[i,(k-1)m+j1]=a[i-1,(k-1)m+j1] e n d f o re n df o re n df o r例5注：本例无链路竞争和死锁现象例6 E立方选路0110(S)1101(D)1011(R)例7 DNS乘法示例C00=1×(-5)+2×7=9C01=1×(-6)+2×8=10C10=3×(-5)+4×7=13C11=3×(-6)+4×8=14例8 上三角方程组的回代解法并行化(1)SISD上的回代算法Begin(1)for i=n downto 1 do(1.1)x i=b i/a ii(1.2)for j=1 to i-1 dob j=b j-a ji x ia ji=0endforendforEnd(2)SIMD-CREW上的并行回代算法- 划分: p个处理器行循环带状划分- 算法Beginfor i=n downto 1 dox i=b i/a iifor all P j, where 1≤j≤p do for k=j to i-1 step p do b k=b k-a ki x ia ki=0endforendforendforEnd // p(n)=n, t(n)=n例9 n=8的BF网络表示P r,i与上层P r-1,i, P r-1,j相连, 这里j与i仅在第r位不同例10 一个在MPI中创建新通信域的例子M P I_C o m m M y W o r l d,S p l i t W o r l d;i n t m y_r a n k,g r o u p_s i z e,C o l o r,K e y;M P I_I n i t(&a r g c,&a r g v);M P I_C o m m_d u p(M P I_C O M M_W O R L D,&M y W o r l d);M P I_C o m m_r a n k(M y W o r l d,&m y_r a n k);M P I_C o m m_s i z e(M y W o r l d,&g r o u p_s i z e);C o l o r=m y_r a n k%3;K e y=m y_r a n k/3;M P I_C o m m_s p l i t(M y W o r l d,C o l o r,K e y,&S p l i t W o r l d);例11 考虑如下程序段：L1:f o r I=1t o50d o...S:X(2*I)=......T:...=...X(3*I+1)......e n df o r这里：f1(I)=2*I；g1(J)=3*J+1。

1、名词解释：（1）等分宽度：把网络划分为两个相等的部分（节点数之多差1），所需要去掉的网络边的条数。

（2）网络直径：网络中两个节点之间的最远的距离（3）并行运行时间：从第一台处理机开始执行任务开始，到最后一台处理机执行完任务所经历的时间。

（4）并行步：能够同时执行的操作数。

（5）加速比：同一任务在串行计算下的运行时间/并行计算下的运行时间。

2、介绍超立方体网络互连方式的性能指标解答：q维超立方体，等分宽度为2q-1，网络直径：q，网络接口数：q3、按照指令流和数据流，并行计算机可以分为哪些类型？各自适合什么样的并行计算？排名在前20的计算机都是什么类型的计算机？它们的区别是什么？解答：（1）SIMD：适合指令/操作级并行（2）MIMD：适合块、回路或子程序级的并行4、并行算法有哪些设计方法？（1）流水线技术（2）分而治之策略（3）平衡二叉树方法（4）倍增技术（5）加速级联策略5、举例说明平衡树方法的原理？参考：使用n/2台计算机，可以在⎡⎤nlog步完成运算。

26、Logp模型有哪些参数？BSP模型有哪些参数？这两个模型之间的关系是什么？（1） L ：源处理机与目标处理机之间进行消息通信所需要等待的延迟时间上限（2） o ：处理机用于发送或接收每个消息的时间开销（3） g ：连续发送/接收消息的时间间隙（4） P ：处理机个数BSP 模型：（1） P ：处理机数（2） g ：选路器吞吐率（3） L ：全局同步之间的时间间隔关系：（1） 本质上等效，可以相互模拟（2） 用BSP 模拟LOGP 所进行的计算时，通常会慢常数倍。

（3） 反之，慢对数倍7、 题目记不清了，只要知道两个公式就可以了，对于logp ：L+2o 对于logGp ：t α+t β8、 计算加速比和效率的题，具体记不清了，只要会使用公式就可以了。

9、 关于群集系统中QR 分解的题目。

将矩阵的行列都分成5等分，得到它的25个任务，按照贪婪算法的调度思想，画出子任务执行的并行步。

并行计算的参考题目1、讨论某一种算法的可扩放性时，一般指什么？88答：讨论某一种算法的可扩放性时，实际上是指该算法针对某一特定机器结构的可扩放性2、使用“Do in Parallel”语句时，表示的是什么含义105答：表示算法的若干步要并行执行3、并行计算机的存储访问类型有哪几种？26答：存储访问类型有：UMA（均匀存储访问）、NUMA（非均匀存储访问）、COMA（全高速缓存存储访问）、CC-NUMA（高速缓存一致性非均匀存储访问）、NORMAl（非远程存储访问）4、什么是同步？它有什么作用？如何实现？107答：同步是在时间上强使各执行进程在某一点必须相互等待。

作用：确保个处理器的正确工作顺序以及对共享可写数据的正确访问（互斥访问）。

实现方法：用软件、硬件和固件的方法实现。

5 在并行加速比的计算中，常用的三种加速比定律分别是哪三种？（P83）答：常用的三种加速比定律分别是：适用于固定计算负载的Amdahl定律，适用于可扩放问题的Gustafson定律和受限于存储器的Sun和Ni定律。

6、试比较Amdahl定律、Gustafson定律、Sun和Ni定律三种加速定律的应用场合。

83 答：Amdahl定律适用于固定计算负载的问题Gustafson定律适用于可扩放性问题Sun和Ni定律适用于受限于存储器的问题。

7.并行算法的基本设计技术有哪些？它们的基本思想是什么？139答：(1)基本技术有：划分设计技术(又分为均匀划分技术、方根划分技术、对数划分技术和功能划分技术)、分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术等。

(2)基本思想分别如下：a.划分设计技术：(P139) 将一原始问题分成若干部分，然后各部分由相应的处理器同时执行。

b.分治设计技术：(P144)将一个大二复杂的问题分解成若干特性相同的子问题分而治之。

若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。

第十一章快速傅里叶变换习题例题：1.试计算下属序列的DFT：(a) (13,17,19,23)(b) (2,1,3,7,5,4,0,6)2.试计算下述序列的逆DFT：(a) ( 16, -0.76 + 8.66i , -6+6i, -9.25+2.66i, 0, -9.25-2.66i, -6-6i, -0.76-8.66i )(b) ( 4-i, 2+i, 2+i, -i 4-i, 2+i, 2+i, -i, )3.参照算法11.1,设计一个单处理机上时间为((nlogn)的离散傅氏逆变换算法;并以n = 8为例。

画出其逆变换蝶氏计算流图。

4.Cormen曾给了另一种形式的FFT递归算法：(a) 试分析此算法的执行过程；(b) 它和算法11.2有何区别？(c) 按此算法画出n = 8的FFT蝶氏计算流图。

算法11.7 SISD上Cormen计算FFT算法输入：a0 , a1 , ... , a n-1输出：b0 , b1 ... , b n-1Begi nif n = 1 then return aelse(1) w = e2πi/n(2) z=1(3) a[0] = (a0 , a2 , ... , a n-2)(4) a[1] = (a1 , a3 , ... , a n-1)(5) b[0] = RECURSIVEFFT(a[0])(6) b[1] = RECURSIVEFFT(a[1])(7) for k=0 to n/2 -1 do(i) b k = b[0]k + zb[1]k(ii)k + n/2 = b[0] k - zb[1] k(iii)= z·wendfor(8) return bendifend5.根据算法11.2，逐步计算 n – 8的FFT，并画出其蝶氏计算流图。

6.令 n = 8 = 2k，在蝶式网络上，按照exp(r,i) = j (0≤i≤n-1,0≤r≤k)的计算方法，试计算分布在蝶形网络中的8点FFT的系数矩阵元素w j。