并行程序设计基础PPT讲稿.ppt

《并行程序设计基础PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《并行程序设计基础PPT讲稿.ppt（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、并行程序设计基础第1页，共45页，编辑于2022年，星期六并行程序设计基础 12.1 12.1 并行程序设计概述并行程序设计概述 12.2 12.2 进程进程 12.3 12.3 线程线程 12.4 12.4 同步同步 12.5 12.5 通信通信 12.6 12.6 并行程序设计模型并行程序设计模型2023/4/212第2页，共45页，编辑于2022年，星期六并行程序设计概述1 1并行程序设计难的原因并行程序设计难的原因并行程序设计难的原因并行程序设计难的原因2并行语言的构造方法并行语言的构造方法3 3并行性问题并行性问题并行性问题并行性问题4 4交互交互交互交互/通信问题通信问题通信问题通

2、信问题5五种并行编程风范五种并行编程风范五种并行编程风范五种并行编程风范6计算圆周率的样本程序计算圆周率的样本程序计算圆周率的样本程序计算圆周率的样本程序2023/4/213第3页，共45页，编辑于2022年，星期六1 并行程序设计难的原因并行程序设计难的原因 技术先行技术先行,缺乏理论指导缺乏理论指导 程序的语法程序的语法/语义复杂语义复杂,需要用户自已处理需要用户自已处理 任务任务/数据的划分数据的划分/分配分配 数据交换数据交换 同步和互斥同步和互斥 性能平衡性能平衡 并行语言缺乏代可扩展和异构可扩展并行语言缺乏代可扩展和异构可扩展,程序移植困难程序移植困难,重重写代码难度太大写代码难度

3、太大 环境和工具缺乏较长的生长期环境和工具缺乏较长的生长期,缺乏代可扩展和异构可扩展缺乏代可扩展和异构可扩展2023/4/214第4页，共45页，编辑于2022年，星期六2 并行语言的构造方法并行语言的构造方法串行代码段串行代码段for(i=0;iN;i+)Ai=bi*bi+1;for(i=0;iN;i+)ci=Ai+Ai+1;(a)使用库例程构造并行程序使用库例程构造并行程序id=my_process_id();p=number_of_processes();for(i=id;iN;i=i+p)Ai=bi*bi+1;barrier();for(i=id;iN;i=i+p)ci=Ai+Ai+1

4、;例子例子:MPI,PVM,Pthreads(b)扩展串行语言扩展串行语言my_process_id,number_of_processes(),and barrier()A(0:N-1)=b(0:N-1)*b(1:N)c=A(0:N-1)+A(1:N)例子例子:Fortran 90(c)加编译注释构造并行程序的方法加编译注释构造并行程序的方法#pragma parallel#pragma shared(A,b,c)#pragma local(i)#pragma pfor iterate(i=0;N;1)for(i=0;iN;i+)Ai=bi*bi+1;#pragma synchronize#

5、pragma pfor iterate(i=0;N;1)for(i=0;iN;i+)ci=Ai+Ai+1;例子：例子：SGI power C 2023/4/215第5页，共45页，编辑于2022年，星期六三种并行语言构造方法比较三种并行语言构造方法比较2 并行语言的构造方法并行语言的构造方法2023/4/216第6页，共45页，编辑于2022年，星期六3 并行性问题并行性问题3.1 进程的同构性vSIMD:所有进程在同一时间执行相同的指令vMIMD:各个进程在同一时间可以执行不同的指令SPMD:各个进程是同构的，多个进程对不同的数据执行相同的代码(一般是数据并行的同义语)常对应并行循环，数据并

6、行结构，单代码MPMD:各个进程是异构的，多个进程执行不同的代码（一般是任务并行，或功能并行，或控制并行的同义语）常对应并行块，多代码 要为有1000个处理器的计算机编写一个完全异构的并行程序是很困难的2023/4/217第7页，共45页，编辑于2022年，星期六并行块parbegin S1 S2 S3.Sn parendS1 S2 S3.Sn可以是不同的代码并行循环:当并行块中所有进程共享相同代码时parbegin S1 S2 S3.Sn parend S1 S2 S3.Sn是相同代码简化为parfor (i=1;i=n,i+)S(i)进程的同构性3 并行性问题并行性问题2023/4/218

7、第8页，共45页，编辑于2022年，星期六用单代码方法说明用单代码方法说明SPMD要说明以下SPMD程序:parfor (i=0;i=N,i+)foo(i)用户需写一个以下程序:pid=my_process_id();numproc=number_of _processes();parfor (i=pid;i=N,i=i+numproc)foo(i)此程序经编译后生成可执行程序A,用shell脚本将它加载到N个处理结点上:run A numnodes NSPMD程序的构造方法程序的构造方法用数据并行程序的构造方法用数据并行程序的构造方法要说明以下SPMD程序:parfor (i=0;i=N,i

8、+)Ci=Ai+Bi;用户可用一条数据赋值语句:C=A+B或forall(i=1,N)Ci=Ai+Bi进程的同构性3 并行性问题并行性问题2023/4/219第9页，共45页，编辑于2022年，星期六用用SPMD伪造伪造MPMD要说明以下MPMD程序:parbegin S1 S2 S3 parend 可以用以下SPMD程序:parfor (i=0;i0)beginfork(foo(C);C:=boo(C);end3 并行性问题并行性问题静态并行性:程序的结构以及进程的个数在运行之前(如编译时,连接时或加载时)就可确定,就认为该程序具有静态并行性.动态并行性:否则就认为该程序具有动态并行性.即意

9、味着进程要在运行时创建和终止2023/4/2111第11页，共45页，编辑于2022年，星期六Process A:begin Z:=1fork(B);T:=foo(3);endProcess B:begin fork(C);X:=foo(Z);join(C);output(X+Y);endProcess C:begin Y:=foo(Z);end开发动态并行性的一般方法:Fork/Join静态和动态并行性3 并行性问题并行性问题Fork:派生一个子进程Join:强制父进程等待子进程2023/4/2112第12页，共45页，编辑于2022年，星期六3.3 进程编组目的:支持进程间的交互,常把需要

10、交互的进程调度在同一组中一个进程组成员由：组标识符+成员序号 唯一确定.3.4 划分与分配原则:使系统大部分时间忙于计算,而不是闲置或忙于交互;同时不牺牲并行性(度).划分:切割数据和工作负载分配：将划分好的数据和工作负载映射到计算结点(处理器)上分配方式显式分配:由用户指定数据和负载如何加载隐式分配：由编译器和运行时支持系统决定就近分配原则：进程所需的数据靠近使用它的进程代码3 并行性问题并行性问题2023/4/2113第13页，共45页，编辑于2022年，星期六并行度(Degree of Parallelism,DOP):同时执行的分进程数.并行粒度(Granularity):两次并行或交

11、互操作之间所执行的计算负载.指令级并行块级并行进程级并行任务级并行并行度与并行粒度大小常互为倒数:增大粒度会减小并行度.增加并行度会增加系统(同步)开销 3 并行性问题并行性问题2023/4/2114第14页，共45页，编辑于2022年，星期六4 交互通信交互通信问题问题交互：进程间的相互影响4.1 交互的类型v通信：两个或多个进程间传送数的操作 通信方式：共享变量父进程传给子进程(参数传递方式)消息传递 2023/4/2115第15页，共45页，编辑于2022年，星期六v同步：导致进程间相互等待或继续执行的操作 同步方式:原子同步 控制同步(路障,临界区)数据同步(锁,条件临界区,监控程序,

12、事件)例子:原子同步parfor(i:=1;in;i+)atomicx:=x+1;y:=y-1路障同步parfor(i:=1;in;i+)Pi barrierQi 临界区parfor(i:=1;in;i+)criticalx:=x+1;y:=y+1数据同步(信号量同步)parfor(i:=1;in;i+)lock(S);x:=x+1;y:=y-1;unlock(S)4 交互通信交互通信问题问题2023/4/2116第16页，共45页，编辑于2022年，星期六v聚集(aggregation)：用一串超步将各分进程计算所得的部分结果合并为一个完整的结果,每个超步包含一个短的计算和一个简单的通信或/

13、和同步.聚集方式:归约扫描交互的类型4 交互通信交互通信问题问题例子例子:计算两个向量的内积计算两个向量的内积parfor(i:=1;in;i+)Xi:=Ai*Biinner_product:=aggregate_sum(Xi);2023/4/2117第17页，共45页，编辑于2022年，星期六4.2 交互的方式4 交互通信交互通信问题问题 交互代码交互代码 C P1P2Pn相对于交互代码C,可对进程P定义如下状态:到达(arrived):P刚到达C,但还未进入在内(in):P在代码中完成(finished):P刚完成执行代码C,但还未离开在外(out):P不在代码中(未到达或已离开)同步的交

14、互:所有参与者同时到达并执行交互代码C异步的交互:进程到达C后,不必等待其它进程到达即可执行C2023/4/2118第18页，共45页，编辑于2022年，星期六交互方式与入口/出口条件的组合4 交互通信交互通信问题问题锁定的发送:消息已发完,但不一定已收到锁定的接收:消息已收到非锁定的发/收:只是发出发/收的请求2023/4/2119第19页，共45页，编辑于2022年，星期六4.3 交互的模式按交互模式是否能在编译时确定分为:静态的动态的按有多少发送者和接收者参与通信分为一对一:点到点(point to point)一对多:广播(broadcast),播撒(scatter)多对一:收集(ga

15、ther),归约(reduce)多对多:全交换(Tatal Exchange),扫描(scan),置换/移位(permutation/shift)4 交互通信交互通信问题问题2023/4/2120第20页，共45页，编辑于2022年，星期六1 3 5 P1P2P31 3 5,1 P1P2P31 3 5 P1P2P31,1 3,1 5,1 P1P2P31,3,5 P1P2P31,3,5 3 5 P1P2P31 3 5 P1P2P31,3,5 3 5 P1P2P3(a)点对点(一对一):P1发送一个值给P3(b)广播(一对多):P1发送一个值给全体(c)播撒(一对多):P1向每个结点发送一个值(d

16、)收集(多对一):P1从每个结点接收一个值4 交互通信交互通信问题问题2023/4/2121第21页，共45页，编辑于2022年，星期六1 3 5 P1P2P31,5 3,1 5,3 P1P2P31,2,3 4,5,6 7,8,9 P1P2P31,4,7 2,5,8 3,6,9 P1P2P31 3 5 P1P2P31,1 3,4 5,9 P1P2P31 3 5 P1P2P31,9 3 5 P1P2P3(e)全交换(多对多):每个结点向每个结点发送一个不同的消息(f)移位(置换,多对多):每个结点向下一个结点发送一个值并接收来自上一个结点的一个值.(g)归约(多对一):P1得到和1+3+5=9(

17、h)扫描(多对多):P1得到1,P2得到1+3=4,P3得到1+3+5=94 交互通信交互通信问题问题2023/4/2122第22页，共45页，编辑于2022年，星期六 相并行（相并行（Phase ParallelPhase Parallel）分治并行（分治并行（Divide and Conquer ParallelDivide and Conquer Parallel）流水线并行（流水线并行（Pipeline ParallelPipeline Parallel）主从并行（主从并行（Master-Slave ParallelMaster-Slave Parallel）工作池并行（工作池并行（W

18、ork Pool ParallelWork Pool Parallel）5 五种并行编程风范五种并行编程风范2023/4/2123第23页，共45页，编辑于2022年，星期六相并行（Phase Parallel）一组一组超级步超级步（相）（相）步内各自计算步内各自计算 步间通信、同步步间通信、同步 BSPBSP（4.2.34.2.3）方便差错和性能分析方便差错和性能分析 计算和通信不能重叠计算和通信不能重叠CCCSynchronous Interaction.CCCSynchronous Interaction.2023/4/2124第24页，共45页，编辑于2022年，星期六主从并行（Mas

19、ter-Slave Parallel）主进程：串行、协调任务主进程：串行、协调任务 子进程：计算子任务子进程：计算子任务 划分设计技术（划分设计技术（6.1 6.1）与相并行结合与相并行结合 主进程易成为瓶颈主进程易成为瓶颈MasterSlaveSlaveSlave2023/4/2125第25页，共45页，编辑于2022年，星期六分治并行（Divide and Conquer Parallel）父进程把负载分割并指派给父进程把负载分割并指派给子进程子进程 递归递归 重点在于归并重点在于归并 分治设计技术（分治设计技术（6.26.2）难以负载平衡难以负载平衡2023/4/2126第26页，共45

20、页，编辑于2022年，星期六流水线并行（Pipeline Parallel）一组进程一组进程 流水线作业流水线作业 流水线设计技术（流水线设计技术（6.56.5）P1P2P32023/4/2127第27页，共45页，编辑于2022年，星期六工作池并行（Work Pool Parallel）初始状态：一件工作初始状态：一件工作 进程从池中取任务执行进程从池中取任务执行 可产生新任务放回池中可产生新任务放回池中 直至任务池为空直至任务池为空 易与负载平衡易与负载平衡 临界区问题（尤其消息传递）临界区问题（尤其消息传递）Work PoolP1P2P32023/4/2128第28页，共45页，编辑于2

21、022年，星期六8 计算圆周率的样本程序计算圆周率的样本程序2023/4/2129第29页，共45页，编辑于2022年，星期六计算圆周率的c语言代码段#define define define define N 1000000 N 1000000main()main()doubledoubledoubledouble local,pi=0.0,w;local,pi=0.0,w;longlonglonglong i;i;w=1.0/N;w=1.0/N;for for for for(i=0;iN;i+)(i=0;iN;i+)local=(i+0.5)*w;local=(i+0.5)*w;pi=p

22、i+4.0/(1.0+local*local);pi=pi+4.0/(1.0+local*local);printf(printf(“pi is%f npi is%f n”,pi*w);,pi*w);2023/4/2130第30页，共45页，编辑于2022年，星期六并行程序设计基础 12.1 12.1 并行程序设计概述并行程序设计概述 12.2 12.2 进程进程 12.3 12.3 线程线程 12.4 12.4 同步同步 12.5 12.5 通信通信 12.6 12.6 并行程序设计模型并行程序设计模型2023/4/2131第31页，共45页，编辑于2022年，星期六进程1进程的基本概念进程

23、的基本概念2进程的并行执行进程的并行执行3 3进程的相互作用进程的相互作用进程的相互作用进程的相互作用2023/4/2132第32页，共45页，编辑于2022年，星期六并行程序设计基础 12.1 12.1 并行程序设计概述并行程序设计概述 12.2 12.2 进程进程 12.3 12.3 线程线程 12.4 12.4 同步同步 12.5 12.5 通信通信 12.6 12.6 并行程序设计模型并行程序设计模型2023/4/2133第33页，共45页，编辑于2022年，星期六线程1线程的基本概念线程的基本概念2线程的管理线程的管理3 3线程的同步线程的同步线程的同步线程的同步2023/4/213

24、4第34页，共45页，编辑于2022年，星期六并行程序设计基础 12.1 12.1 并行程序设计概述并行程序设计概述 12.2 12.2 进程进程 12.3 12.3 线程线程 12.4 12.4 同步同步 12.5 12.5 通信通信 12.6 12.6 并行程序设计模型并行程序设计模型2023/4/2135第35页，共45页，编辑于2022年，星期六同步1原子和互斥原子和互斥原子和互斥原子和互斥2 2高级同步结构高级同步结构高级同步结构高级同步结构3 3低级同步原语低级同步原语低级同步原语低级同步原语2023/4/2136第36页，共45页，编辑于2022年，星期六并行程序设计基础 12.

25、1 12.1 并行程序设计概述并行程序设计概述 12.2 12.2 进程进程 12.3 12.3 线程线程 12.4 12.4 同步同步 12.5 12.5 通信通信 12.6 12.6 并行程序设计模型并行程序设计模型2023/4/2137第37页，共45页，编辑于2022年，星期六通信1影响通信系统性能的因素影响通信系统性能的因素2 2低级通信支持低级通信支持低级通信支持低级通信支持3TCP/IPTCP/IP通信协议组简介通信协议组简介通信协议组简介通信协议组简介2023/4/2138第38页，共45页，编辑于2022年，星期六并行程序设计基础 12.1 12.1 并行程序设计概述并行程序

26、设计概述 12.2 12.2 进程进程 12.3 12.3 线程线程 12.4 12.4 同步同步 12.5 12.5 通信通信 12.6 12.6 并行程序设计模型并行程序设计模型2023/4/2139第39页，共45页，编辑于2022年，星期六并行程序设计模型1隐式并行模型隐式并行模型隐式并行模型隐式并行模型2数据并行模型数据并行模型数据并行模型数据并行模型3 3消息传递模型消息传递模型消息传递模型消息传递模型4 4共享变量模型共享变量模型共享变量模型共享变量模型2023/4/2140第40页，共45页，编辑于2022年，星期六并行程序设计模型 隐式并行（隐式并行（Implicit Par

27、allelImplicit Parallel）数据并行（数据并行（Data ParallelData Parallel）共享变量（共享变量（Shared VariableShared Variable）消息传递（消息传递（Message PassingMessage Passing）2023/4/2141第41页，共45页，编辑于2022年，星期六隐式并行（Implicit Parallel）概况：概况：程序员用熟悉的串行语言编程程序员用熟悉的串行语言编程 编译器或运行支持系统自动转化为并行代码编译器或运行支持系统自动转化为并行代码 特点：特点：语义简单语义简单 可移植性好可移植性好 单线程，

28、易于调试和验证正确性单线程，易于调试和验证正确性 效率很低效率很低2023/4/2142第42页，共45页，编辑于2022年，星期六数据并行（Data Parallel）概况：概况：SIMDSIMD的自然模型的自然模型 局部计算和数据选路操作局部计算和数据选路操作 特点：特点：单线程单线程 并行操作于聚合数据结构（数组）并行操作于聚合数据结构（数组）松散同步松散同步 单一地址空间单一地址空间 隐式交互作用隐式交互作用 显式显式数据分布数据分布2023/4/2143第43页，共45页，编辑于2022年，星期六共享变量（Shared Variable）概况：概况：PVP,SMP,DSMPVP,SMP,DSM的自然模型的自然模型 特点：特点：多线程：多线程：SPMD,MPMDSPMD,MPMD 异步异步 单一地址空间单一地址空间 显式同步显式同步 隐式数据分布隐式数据分布 隐式通信隐式通信2023/4/2144第44页，共45页，编辑于2022年，星期六消息传递（Message Passing）概况：概况：MPP,COWMPP,COW的自然模型的自然模型 特点：特点：多线程多线程 异步异步 多地址空间多地址空间 显式同步显式同步 显式数据映射和负载分配显式数据映射和负载分配 显式通信显式通信2023/4/2145第45页，共45页，编辑于2022年，星期六