计算机常用算法与程序设计教程 第9章 并行算法

《计算机常用算法与程序设计教程 第9章 并行算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章并行算法1常用算法与程序设计主要内容9.1并行算法的基本概念并行计算机系统结构模型并行计算性能评价9.2并行算法设计SIMD共享存储模型SIMD互连网络模型MIMD共享存储模型MIMD异步通信模型9.3并行程序开发并行程序设计的概念共享存储系统并行编程分布存储系统并行编程2常用算法与程序设计9.1并行算法的基本概念9.1.1并行计算机系统结构模型SISD:单指令流单数据流。SIMD:单指令流多数据流。MISD:多指令流单数据流。MIMD:多指令流多数据流。3常用算法与程序设计9.1.2并行计算性能评价1.并行算法的成本C（n）成

2、本C（n）定义为并行算法的运行时间T（n）与其所需的处理器数P（n）的乘积，即C（n）＝T（n）*P（n）它相当于在最坏的情况下求解某一问题的总执行步数。如果求解一个问题的并行算法的成本，在数量级上等于最坏情况下的串行求解此问题所需的执行步数，那么称此并行算法是成本最优的。。4常用算法与程序设计2.加速比Sp（n）并行算法的加速比Sp（n）可定义为Sp（n）＝Ts（n）/Tp（n）式中，Ts（n）是最快的串行算法在最坏的情况下的运行时间，Tp（n）是求解同一问题的某并行算法在最坏情况下的运行时间。Sp（n）越大，则并行算法越好。5常用

3、算法与程序设计3.并行算法的效率Ep（n）并行算法的效率可定义为算法的加速比与处理器数目之比，即Ep（n）＝Sp（n）/P(n)并行算法的加速比不能反应处理机的利用率，一个并行算法的加速比可能很大，但是处理机的利用率却可能很低。并行算法的效率反映了在执行算法时处理机的利用情况。6常用算法与程序设计并行程序设计包括将一个问题分解成若干部分，然后由各个处理器对各个部分分别进行计算。一个理想的并行计算是能被立即分解成许多完全独立部分且它们能同时执行的计算，可以贴切地称为自然并行。许多问题不是自然并行的，需要使用一些技巧来解决。9.2并行算法

4、设计7常用算法与程序设计SIMD共享存储模型是假定有有限或无限个功能相同的处理器，每个处理器拥有简单的算术运算和逻辑判断能力，在理想的情况下假定存在一个容量无限大的共享存储器，在任何时刻，任意一个处理器均可通过共享存储器的共享单元同其他任何处理器互相交换数据，也称之为PRAM（ParallelRandomAccessMachine）模型，即并行随机存取机器。9.2.1SIMD共享存储模型8常用算法与程序设计【例9.1】.广播算法（1）处理器P1将m复制到自己的存储器中，然后将其写入B（1）（2）for(i=0;i≤logN－1;i++

5、)forj=2i+1to2i+1par-do{处理器Pj将B（j－2i）复制到自己的存储器中；然后将其写入B（j）;}endfor（3）fori=1toNpar-do处理器Pi从B（i）中读取数据m;endfor9常用算法与程序设计SIMD互连网络模型，简记为SIMD-IN，也称为分布存储的SIMD模型，简记为SIMD-DM。在这种模型中，每个处理器在控制器控制下或处于活动状态，或处于不活动状态。活动状态的处理器都执行相同的指令，处理器之间的数据交换是通过互连网络进行的。其中各处理器（包括算术逻辑单元和本地存储器）可以通过多种互连方式

6、连接。9.2.2SIMD互连网络模型10常用算法与程序设计【例9.2】一维线性模型上的并行排序算法for(k=1;k≤;k++){foreachPi:i=1,3,…,2-1par-doifXi＞Xi+1thenXi←→Xi+1;endforforeachPi:i=2,4,…,2par-doifXi＞Xi+1thenXi←→Xi+1;endfor}11常用算法与程序设计共享存储的MIMD计算模型是一个异步的PRAM模型，系由多个处理器组成，它的特点是每个处理器都有自己的本地存储器、局部时钟和局部程序；处理器间的通信经过共享全局存储器；没

7、有全局时钟，各个处理器异步地执行各自的指令；处理器任何时间依赖关系必须明确地在各处理器的程序中加入同步（路）障（SynchronizationBarrier）；一条指令可在非确定但有限的时间内完成。9.2.3MIMD共享存储模型12常用算法与程序设计【例9.3】并行求和算法g=0;foreachPi：0≤i＜ppar-doli=0;for(j=0;j≤n;j+=p)li=li+aj;lock(g);g=g+li;unlock(g);endfor13常用算法与程序设计MIMD异步通信计算模型可以抽象为一个无向图，其中顶点集对应处理器集合

8、，边集对应处理器间的双向通信链集合。每个处理器都赋予惟一的编号，且只具有知晓与其有线相连的近邻处理器的局部知识。系统中并无共享存储器，各处理器之间的通信是通过发送和接受消息完成的。在算法运行期间，每个处理器除了执行自己的