当前位置：文档之家 › 2014并行计算的复习思考题2

2014并行计算的复习思考题2

  • 格式：docx
  • 大小：20.38 KB
  • 文档页数：4

并行计算的复习思考题：1总结串行计算和并行计算在算法设计中的特点，并给出奇、偶排序的串行和并行算法掌握各种并行设计，并应用流水线设计技术给出冒泡排序的并行算法通过查资料掌握Amdahl定律的主要内容、应用范围及主要结论。

总结并行计算中的计算模式，分析各自的特点。

并列举1-2个你的研究领域里应用了哪些并行计算模式。

掌握MPI中消息传递的模式，并分析各自的特点复习各种排序算法的并行化并行算法设计技术：①平衡树方法、②倍增技术、③分治策略、④划分、⑤流水线技术。

①应用1——求最大值输入：n=2m 个数存在数组A（n:2n-1)中输出：最大数置于A(1)中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应用2——求N个数之和输入：数组A（1:n)，N=2K输出：数组值的总和存储于A(1)中begin1. p=n/22.while p>0 do3.for i=1 to p do in parallel4.A(i)=A(2i-1)+A(2i)5.end parallel6.p=p/27.end whileEnd应用3：SIMD-TC模型上非递归求前缀和参看笔记②应用2——列表排序：输入：数组A(1:n)，LINK(1:n),HEAD输出：RANK(1:n)begin1. for i=1 to n do in parallelRANK(i)=1NEXT(i)=LINK(i)end parallel2 .for k=1 to logn do(2) for i=1 to n in parallelif NEXT(i) is not zeroRANK(i)= RANK(i)+ RANK(NEXT(i) )NEXT(i) =NEXT(NEXT(i) )end ifend parallelend forend③SIMD模型上的分治算法输入：问题的输入集合I输出：问题的解输出Oprocedure D &C(I,O)BEGINIF small(I,O) Then return(ANSWER(I,O))ELSE(1)SPLIT INPUT(I:S1,S2,S3,....,SK)(2) FOR i= 1 to k par-doD & C(Si,Ti)end for(3)COMBINE(T1,T2....,TK,I,O)END IFEND④应用——归并算法均匀划分技术，应用——PSRS排序过程A.均匀划分 b.局部排序 c.正则采样d.采样排序e. 选择主元f.主元划分g.全局交换h.归并排序3、描述：系统中某部件由于采用某种方式使系统性能改进后，整个系统性能的提高与该方式的使用频率或占总的执行时间的比例有关。

主要应用：改善“系统瓶颈”性能。

Amdahl定律定义了加速比：加速比=采用改进措施后性能/未采用改进措施前的性能=未采用改进措施前执行某任务时间/采用改进措施后执行某任务的时间n个处理器加速因子S=n/[1+(n-1)f]:f为非平行百分比，n越大，S不能超过1/f阿姆达尔定律不可并行计算的存在是很重要的，因为它将限制并行化的潜在好处。

阿姆达尔定律指明如果一个计算的1/S本质上是顺序的，那么最大的性能改进将受限于因数S。

其论证如下，一个并行计算的执行时间TP将是顺序部分计算时间和可并行化部分计算时间两者的和。

如果该计算顺序地执行需要花费的时间是TS，则当有P个处理器时，TP可表示为S=n/[1+(n-1)f]假想P值非常大，使得可并行化部分的执行时间可以忽略不计，则最大可改进的性能将是因数S。

也就是说，顺序执行代码在计算中所占的比例决定了使用并行手段所能改进性能的潜力。

什么是计算模型？——抽象的，是硬件和软件之间的桥梁。

很明显，如果算法的性能在抽象系统中都不能满足要求，那么在实际系统中实现就毫无意义。

计算模型只关注算法复杂性方面。

冯·诺依曼结构是一种理想的串行计算模型，在并行计算中，没有一个真正通用的并行计算模型。

目前常见的并行计算模型：PRAM模型、BSP模型、logP模型、C3模型。

①Parallel Random Access Machine（并行随机存取机器），有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。

优点：使用简单，处理器间通信，存储管理，进程同步等隐含于模型中。

缺点：共享单一存储器的假定，不适合于分布存储的异步的MIMD机器PRAM-CRCW并发读并发写CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入PRAM-CREW并发读互斥写PRAM-EREW互斥读互斥写②异步APRAM模型，又称分相（Phase）PRAM或MIMD-SM。

每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。

优缺点：易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。

③BSP模型是个分布存储的MIMD计算模型，特点是：它将处理器和路由器分开，这样做既掩盖具体的互连网络拓扑，又简化了通信协议；采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级；为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。

④LogP模型是一种分布存储的、点到点通信的多处理机模型，特点是：抓住了网络与处理机之间的性能瓶颈；处理机之间异步工作，并通过处理机间的消息传送来完成同步；对多线程技术有一定反映；消息延迟不确定；可以预估算法的实际运行时间。

⑤C3模型假定处理机不能同时发送和接收消息，它对超步的性能分析分为两部分：计算单元CU，依赖于本地计算量；通信单元COU，依赖与处理机发送和接收数据的多少、消息的延迟及通信引起的拥挤量。

该模型考虑了两种路由（存储转发路由和虫蚀寻径路由）和两种发送/接收原语（阻塞和无阻塞）对COU的影响。

MPI最基本的通信模式是在一对进程之间进行的消息收发操作，一个进程发送消息（MPI_Send(void*buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm)），另一个接收消息（MPI_Recv(void*buf,int count,MPI_Datatype datatype,int source,int tag,MPI_Comm comm,MPI_Status*status)）。

这种通信方式成为点对点通信：①标准模式：由MPI系统来决定是先将消息复制至一个缓冲区，然后立即返回，还是等待将数据发送出去后再返回。

②缓冲模式：假设有一定量的缓冲区空间可供使用，发送者把消息拷贝到一个缓存，然后以非阻塞方式发送它。

③同步模式：发送者发一个“请求发送”的消息，接收者存储这个请求。

当一个匹配接收登入时，接收者发回一个“允许发送”的消息，这时发送者才真正发送消息。

④就绪模式：在肯定相应接收已开始后，消息才被发送。

①枚举排序：对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。

输入：无序数组a[1]…a[n]输出：有序数组b[1]…b[n]Begin(1) P0播送a[1]…a[n]给所有Pi(2) for all Pi where 1≤i≤n para-do(2.1)k=1(2.2)for j = 1 to n doif (a[i] > a[j]) or (a[i] = a[j] and i>j) thenk = k+1end ifend for(3) P0收集k并按序定位End②快速排序：基本思想：在当前无序区R[1,n]中取一个记录作为比较的“基准”，用此基准将当前的无序区R[1,n]划分成左右两个无序的子区R[1,i-1]和R[i,n](1≤i≤n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字。

快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。

例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。

当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。

输入：无序数组data[1,n]，使用的处理器个数2m输出：有序数组data[1,n]Beginpara_quicksort(data,1,n,m,0)End假设quicksort(data,i,j)表示快速排序串行算法procedure para_quicksort(data,i,j,m,id)Begin(1) if m=0 then(1.1) Pid call quicksort(data,i,j)else(1.2) Pid: r=patrition(data,i,j)(1.3) Pid send data[r+1,j] to Pid+2m-1(1.4) para_quicksort(data,i,r-1,m-1,id)(1.5) para_quicksort(data,r+1,j,m-1,id+2m-1)(1.6) Pid+2m-1 send data[r+1,j] back to Pidend if。

合集下载

并行计算习题答案

并行计算习题答案

并行计算习题答案并行计算习题答案在计算机科学领域，随着技术的不断发展，计算速度的提升成为了一个重要的课题。

并行计算作为一种有效的解决方案，被广泛应用于各个领域。

本文将通过回答一些并行计算习题，来探讨并行计算的原理和应用。

1. 什么是并行计算？并行计算是指同时执行多个计算任务的一种计算模式。

它通过将一个大问题分解为多个小问题，并在多个处理单元上同时执行这些小问题，从而加快计算速度。

并行计算可以应用于各种领域，包括科学计算、图像处理、人工智能等。

2. 并行计算的优势是什么？并行计算具有以下几个优势：- 加速计算速度：通过同时执行多个任务，可以大大提高计算速度，从而节省时间和资源。

- 处理大规模问题：并行计算可以处理大规模问题，将问题分解为多个小问题，分别在不同处理单元上计算，从而提高计算效率。

- 提高系统可靠性：并行计算中的多个处理单元可以相互协作，当一个处理单元发生故障时，其他处理单元可以继续工作，从而提高系统的可靠性。

3. 并行计算的模型有哪些？并行计算的模型有多种，常见的包括：- SIMD（单指令流多数据流）模型：所有处理单元执行相同的指令，但可以处理不同的数据。

- MIMD（多指令流多数据流）模型：每个处理单元可以执行不同的指令，处理不同的数据。

- SPMD（单程序多数据流）模型：所有处理单元执行相同的程序，但可以处理不同的数据。

4. 并行计算中的通信方式有哪些？并行计算中的通信方式包括：- 共享内存：多个处理单元共享同一块物理内存，通过读写内存来实现数据的传递和共享。

- 消息传递：处理单元之间通过发送和接收消息来进行通信，可以通过直接通信或者通过中间件来实现。

5. 如何评估并行计算的性能？评估并行计算的性能可以从以下几个方面考虑：- 加速比：加速比是指并行计算相对于串行计算的速度提升比例，可以通过计算并行计算时间与串行计算时间的比值得到。

- 效率：效率是指并行计算的实际加速比与理论加速比之间的比值，可以反映并行计算的利用率。

并行计算-习题及答案-第12章 并行程序设计基础

并行计算-习题及答案-第12章 并行程序设计基础

第十二章 并行程序设计基础习题例题：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、讨论某一种算法的可扩放性时，一般指什么？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)将一个大二复杂的问题分解成若干特性相同的子问题分而治之。

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