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

1常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计9.1 并行算法的基本概念并行算法的基本概念 并行计算机系统结构模型并行计算机系统结构模型 并行计算性能评价并行计算性能评价9.2 并行算法设计并行算法设计 SIMD共享存储模型共享存储模型 SIMD互连网络模型互连网络模型 MIMD共享存储模型共享存储模型 MIMD异步通信模型异步通信模型9.3 并行程序开发并行程序开发 并行程序设计的概念并行程序设计的概念 共享存储系统并行编程共享存储系统并行编程 分布存储系统并行编程分布存储系统并行编程 2常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计9.1并行算法的基本概念并行算法的基本概念9.1.1 并行计算机系统结构模型并行计算机系统结构模型1.1.SISD:单指令流单数据流。2.2.SIMD:单指令流多数据流。3.3.MISD:多指令流单数据流。4.4.MIMD:多指令流多数据流。3常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计9.1.2 并行计算性能评价并行计算性能评价1.并行算法的成本并行算法的成本C（n）成本成本C C（n n）定义为并行算法的运行时间）定义为并行算法的运行时间T T（n n）与其所需的处理器数与其所需的处理器数P P（n n）的乘积，即）的乘积，即C C（n n）T T（n n）*P P（n n）它相当于在最坏的情况下求解某一问题的总执行步它相当于在最坏的情况下求解某一问题的总执行步数。如果求解一个问题的并行算法的成本，在数量数。如果求解一个问题的并行算法的成本，在数量级上等于最坏情况下的串行求解此问题所需的执行级上等于最坏情况下的串行求解此问题所需的执行步数，那么称此并行算法是成本最优的。步数，那么称此并行算法是成本最优的。4常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 2.加速比加速比Sp（n）并行算法的加速比并行算法的加速比SpSp（n n）可定义为）可定义为SpSp（n n）TsTs（n n）/Tp/Tp（n n）式中，式中，TsTs（n n）是最快的串行算法在最坏的情况）是最快的串行算法在最坏的情况下的运行时间，下的运行时间，TpTp（n n）是求解同一问题的某并）是求解同一问题的某并行算法在最坏情况下的运行时间行算法在最坏情况下的运行时间。SpSp（n n）越大，则并行算法越好。）越大，则并行算法越好。5常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 3.并行算法的效率并行算法的效率Ep（n）并行算法的效率可定义为算法的加速比与处理并行算法的效率可定义为算法的加速比与处理器数目之比，即器数目之比，即 EpEp（n n）SpSp（n n）/P(n)/P(n)并行算法的加速比不能反应处理机的利用率，并行算法的加速比不能反应处理机的利用率，一个并行算法的加速比可能很大，但是处理机一个并行算法的加速比可能很大，但是处理机的利用率却可能很低。并行算法的效率反映了的利用率却可能很低。并行算法的效率反映了在执行算法时处理机的利用情况。在执行算法时处理机的利用情况。6常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 并行程序设计包括将一个问题分解成若干部分，并行程序设计包括将一个问题分解成若干部分，然后由各个处理器对各个部分分别进行计算。然后由各个处理器对各个部分分别进行计算。一个理想的并行计算是能被立即分解成许多完全一个理想的并行计算是能被立即分解成许多完全独立部分且它们能同时执行的计算，可以贴切地独立部分且它们能同时执行的计算，可以贴切地称为自然并行称为自然并行 。许多问题不是自然并行的，需要使用一些技巧来许多问题不是自然并行的，需要使用一些技巧来解决。解决。9.2 并行算法设计并行算法设计7常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 SIMD共享存储模型是假定有有限或无限个功能相同的处理器，每个处理器拥有简单的算术运算和逻辑判断能力，在理想的情况下假定存在一个容量无限大的共享存储器，在任何时刻，任意一个处理器均可通过共享存储器的共享单元同其他任何处理器互相交换数据，也称之为PRAM（Parallel Random Access Machine）模型，即并行随机存取机器。9.2.1 SIMD共享存储模型共享存储模型8常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计【例例9.19.1】.广播算法广播算法 （1 1）处理器）处理器）处理器）处理器P1P1将将将将mm复制到自己的存储器中，复制到自己的存储器中，复制到自己的存储器中，复制到自己的存储器中，然后将其写入然后将其写入然后将其写入然后将其写入B B（1 1）（2 2）for(i=0;i log N for(i=0;i log N 1;i+)1;i+)for j=2i+1 to 2 i+1 par-dofor j=2i+1 to 2 i+1 par-do 处理器处理器处理器处理器PjPj将将将将B B（j j 2i2i）复制）复制）复制）复制到自己的存储器中；然后将其写入到自己的存储器中；然后将其写入到自己的存储器中；然后将其写入到自己的存储器中；然后将其写入B B（j j）;end forend for（3 3）for i=1 to N par-dofor i=1 to N par-do 处理器处理器处理器处理器PiPi从从从从B B（i i）中读取数据）中读取数据）中读取数据）中读取数据m;m;end for end for 9常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 SIMD互连网络模型，简记为SIMD-IN，也称为分布存储的SIMD模型，简记为SIMD-DM。在这种模型中，每个处理器在控制器控制下或处于活动状态，或处于不活动状态。活动状态的处理器都执行相同的指令，处理器之间的数据交换是通过互连网络进行的。其中各处理器（包括算术逻辑单元和本地存储器）可以通过多种互连方式连接。9.2.2 SIMD互连网络模型互连网络模型10常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计【例例9.29.2】一维线性模型上的并行排序算法一维线性模型上的并行排序算法 for(k=1;k ;k+)for each Pi:i=1,3,2-1 par-do if XiXi+1 then XiXi+1;end for for each Pi:i=2,4,2 par-do if XiXi+1 then XiXi+1 ;end for 11常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 共享存储的MIMD计算模型是一个异步的PRAM模型，系由多个处理器组成，它的特点是每个处理器都有自己的本地存储器、局部时钟和局部程序；处理器间的通信经过共享全局存储器；没有全局时钟，各个处理器异步地执行各自的指令；处理器任何时间依赖关系必须明确地在各处理器的程序中加入同步（路）障（Synchronization Barrier）；一条指令可在非确定但有限的时间内完成。9.2.3 MIMD共享存储模型共享存储模型12常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计【例例例例9.39.39.39.3】并行求和算法并行求和算法并行求和算法并行求和算法 g=0;g=0;for each Pifor each Pi：0 i 0 i p par-dop par-do li=0;li=0;for(j=0;j n;j+=p)for(j=0;j n;j+=p)li=li+aj;li=li+aj;lock(g);lock(g);g=g+li;g=g+li;unlock(g);unlock(g);end forend for13常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 MIMD异步通信计算模型可以抽象为一个无向图，其中顶点集对应处理器集合，边集对应处理器间的双向通信链集合。每个处理器都赋予惟一的编号，且只具有知晓与其有线相连的近邻处理器的局部知识。系统中并无共享存储器，各处理器之间的通信是通过发送和接受消息完成的。在算法运行期间，每个处理器除了执行自己的计算任务外，还向邻近的处理器发送消息和接受并处理来自邻近处理器的消息。9.2.4 MIMD异步通信模型异步通信模型14常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计【例例例例9.49.49.49.4】MIMD-ACMIMD-AC模型上的随机模型上的随机模型上的随机模型上的随机k k选择算法选择算法选择算法选择算法 (1(1(1(1）通过对有根生成树的一次扫描，根节点就可计算出总的）通过对有根生成树的一次扫描，根节点就可计算出总的）通过对有根生成树的一次扫描，根节点就可计算出总的）通过对有根生成树的一次扫描，根节点就可计算出总的元素数元素数元素数元素数B B B B。如果。如果。如果。如果B B B B1 1 1 1，则根节点通知该元素所在节，则根节点通知该元素所在节，则根节点通知该元素所在节，则根节点通知该元素所在节点将此元素送往根节点，算法结束；否则执行以下各步；点将此元素送往根节点，算法结束；否则执行以下各步；点将此元素送往根节点，算法结束；否则执行以下各步；点将此元素送往根节点，算法结束；否则执行以下各步；（2 2 2 2）分布随机地从）分布随机地从）分布随机地从）分布随机地从B B B B个元素中挑选出一个元素个元素中挑选出一个元素个元素中挑选出一个元素个元素中挑选出一个元素m m m m（划分（划分（划分（划分元素）送到根节点。其过程是：假定每个进程（节点）给其元素）送到根节点。其过程是：假定每个进程（节点）给其元素）送到根节点。其过程是：假定每个进程（节点）给其元素）送到根节点。其过程是：假定每个进程（节点）给其元素和其孩子都赋予一个固定的序号，并且还假定每个节点元素和其孩子都赋予一个固定的序号，并且还假定每个节点元素和其孩子都赋予一个固定的序号，并且还假定每个节点元素和其孩子都赋予一个固定的序号，并且还假定每个节点都知道都知道都知道都知道t t t t（1 1 1 1），），），），t t t t（p p p p）。其中）。其中）。其中）。其中t t t t（i i i i）是它的第）是它的第）是它的第）是它的第i i i i个子树个子树个子树个子树中所有元素的数目（中所有元素的数目（中所有元素的数目（中所有元素的数目（1ip1ip1ip1ip）。根节点在区间）。根节点在区间）。根节点在区间）。根节点在区间1 1 1 1到到到到n n n n随机地随机地随机地随机地选择一整数选择一整数选择一整数选择一整数i i i i，为了找相应的元素，它首先检查驻留在自己，为了找相应的元素，它首先检查驻留在自己，为了找相应的元素，它首先检查驻留在自己，为了找相应的元素，它首先检查驻留在自己局部存储器中局部存储器中局部存储器中局部存储器中t t t t个元素是否是此元素；如果个元素是否是此元素；如果个元素是否是此元素；如果个元素是否是此元素；如果itititit，则说明有，则说明有，则说明有，则说明有此元素，否则根节点发送命令此元素，否则根节点发送命令此元素，否则根节点发送命令此元素，否则根节点发送命令LOCATELOCATELOCATELOCATE（j j j j）给第）给第）给第）给第f f f f个孩子，其个孩子，其个孩子，其个孩子，其中中中中j j j ji i i it t t tt t t t（1 1 1 1）-t-t-t-t（f-1f-1f-1f-1）（取最小正整数）。根据）（取最小正整数）。根据）（取最小正整数）。根据）（取最小正整数）。根据接受的接受的接受的接受的LOCATE(j)LOCATE(j)LOCATE(j)LOCATE(j)信息，接收进程就像根节点一样作出类似信息，接收进程就像根节点一样作出类似信息，接收进程就像根节点一样作出类似信息，接收进程就像根节点一样作出类似的反应。当已经定位到一个元素时，它就被发送至根并作为的反应。当已经定位到一个元素时，它就被发送至根并作为的反应。当已经定位到一个元素时，它就被发送至根并作为的反应。当已经定位到一个元素时，它就被发送至根并作为k k k k选择算法的划分元素，发送给所有其他节点。选择算法的划分元素，发送给所有其他节点。选择算法的划分元素，发送给所有其他节点。选择算法的划分元素，发送给所有其他节点。15常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计（3）每个进程i将其局部存储器中的元素按m划分成三个子集合BLi，BEi，BGi，它们分别包含、m的那些元素。通过对生成树从叶子到根的一次扫描，在根节点可计算出BL，BE，BG。一旦计算出BL、BE、BG，根节点就可以根据B和k决定算法是以选中m而结束，还是继续递归调用。根节点向所有其他节点广播这一决定，以便让每个节点i知道集合BLi和BGi中哪一个应作为下一次递归调用的参数，这一步需要交换的消息数为O（p）。（4）根据新的参数B和k，算法就可自动递归调用算法了。在分布式环境中，递归调用时其入口和出口均由根节点完成。它分布地计数现有活跃元素的数目。如果很多，则根节点通知所有其他节点，它们都递归调用它们局部的程序。当只剩下一个元素时，根节点就令其它节点将此元素发送给它，从而得到了第k个元素。此时每个进程都可以从递归调用中退出而无需与根节点进一步通信就可结束。16常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 9.3.1 并行程序概念并行程序概念目前两种最重要的并行编程模型是数据并行和消息目前两种最重要的并行编程模型是数据并行和消息目前两种最重要的并行编程模型是数据并行和消息目前两种最重要的并行编程模型是数据并行和消息传递。数据并行编程模型的编程级别比较高，编程传递。数据并行编程模型的编程级别比较高，编程传递。数据并行编程模型的编程级别比较高，编程传递。数据并行编程模型的编程级别比较高，编程相对简单，但它仅适用于数据并行问题；消息传递相对简单，但它仅适用于数据并行问题；消息传递相对简单，但它仅适用于数据并行问题；消息传递相对简单，但它仅适用于数据并行问题；消息传递编程模型的编程级别相对较低，但消息传递编程模编程模型的编程级别相对较低，但消息传递编程模编程模型的编程级别相对较低，但消息传递编程模编程模型的编程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。型可以有更广泛的应用范围。型可以有更广泛的应用范围。型可以有更广泛的应用范围。9.3 并行程序开发并行程序开发 17常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 9.3.2 共享存储系统并行编程共享存储系统并行编程 在一个共享存储器系统中，任一个处理器都可以在一个共享存储器系统中，任一个处理器都可以在一个共享存储器系统中，任一个处理器都可以在一个共享存储器系统中，任一个处理器都可以访问全部的存储单元。所谓单一编址空间就是每访问全部的存储单元。所谓单一编址空间就是每访问全部的存储单元。所谓单一编址空间就是每访问全部的存储单元。所谓单一编址空间就是每一个存储单元都由一个单地址范围内的某个特定一个存储单元都由一个单地址范围内的某个特定一个存储单元都由一个单地址范围内的某个特定一个存储单元都由一个单地址范围内的某个特定地址所指定。地址所指定。地址所指定。地址所指定。OpenMpOpenMp是一个共享存储器标准，是为在多处理是一个共享存储器标准，是为在多处理是一个共享存储器标准，是为在多处理是一个共享存储器标准，是为在多处理机上编写并行程序而设计的一个应用编程接口，机上编写并行程序而设计的一个应用编程接口，机上编写并行程序而设计的一个应用编程接口，机上编写并行程序而设计的一个应用编程接口，得到许多硬件和软件供应商的支持得到许多硬件和软件供应商的支持得到许多硬件和软件供应商的支持得到许多硬件和软件供应商的支持 18常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计“Hello World”程序#include#include int main()#pragma omp parallelprintf(“Hello World n”);19常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 9.3.3 分布存储系统并行编程分布存储系统并行编程 对于分布存储系统来说，单一编址空间的假设不对于分布存储系统来说，单一编址空间的假设不对于分布存储系统来说，单一编址空间的假设不对于分布存储系统来说，单一编址空间的假设不成立，组成系统的各计算机有自己的处理器和本成立，组成系统的各计算机有自己的处理器和本成立，组成系统的各计算机有自己的处理器和本成立，组成系统的各计算机有自己的处理器和本地主存储器，不能相互访问各自的主存储器，只地主存储器，不能相互访问各自的主存储器，只地主存储器，不能相互访问各自的主存储器，只地主存储器，不能相互访问各自的主存储器，只能通过传递消息来进行交互能通过传递消息来进行交互能通过传递消息来进行交互能通过传递消息来进行交互 通过在通过在通过在通过在C C或者或者或者或者FortranFortran语言中增加进程间消息传递语言中增加进程间消息传递语言中增加进程间消息传递语言中增加进程间消息传递函数，可以完成大多数的并行程序设计。函数，可以完成大多数的并行程序设计。函数，可以完成大多数的并行程序设计。函数，可以完成大多数的并行程序设计。MPIMPI标标标标准是最流行的并行编程消息传递规范。几乎所有准是最流行的并行编程消息传递规范。几乎所有准是最流行的并行编程消息传递规范。几乎所有准是最流行的并行编程消息传递规范。几乎所有商业的并行机都支持它，同时也有众多支持商业的并行机都支持它，同时也有众多支持商业的并行机都支持它，同时也有众多支持商业的并行机都支持它，同时也有众多支持MPIMPI标准的开放软件库可供使用。标准的开放软件库可供使用。标准的开放软件库可供使用。标准的开放软件库可供使用。20常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计“Hello World”程序#include“mpi.h”#include#includevoid main(argc,argv)int argc;char*argv;int myid,numprocs;int namelen;char processor_nameMPI_MAX_PROCESSOR_NAME;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&myid);MPI_Comm_size(MPI_COMM_WORLD,&numprocs);MPI_Get_processor_name(processor_name,&namelen);fprintf(stderr,”Hello World!Porcess&d of%d on%s n”,myid,numprocs,processor_name);MPI_Finalize();21常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计上机：上机：1.1.MPICHMPICH是是是是一一一一种种种种最最最最重重重重要要要要的的的的MPIMPI实实实实现现现现，可可可可以以以以免免免免费费费费从从从从http:/www-unix.mcs.anl.gov/mpi/mpichhttp:/www-unix.mcs.anl.gov/mpi/mpich取取取取 得得得得，请请请请下载并安装；然后编译运行下载并安装；然后编译运行下载并安装；然后编译运行下载并安装；然后编译运行“Hello World”Hello World”程序。程序。程序。程序。2 2.OpenMPOpenMP官官官官方方方方网网网网站站站站的的的的地地地地址址址址试试试试www.OpenMP.orgwww.OpenMP.org。可可可可以以以以从从从从该该该该站站站站点点点点下下下下载载载载C/C+C/C+和和和和FortranFortran版版版版本本本本的的的的OpenMPOpenMP规规规规范与编译器。试编译运行范与编译器。试编译运行范与编译器。试编译运行范与编译器。试编译运行“Hello World”Hello World”程序。程序。程序。程序。作业：作业：1.2.4.6.1.2.4.6.22常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计