第2章 并行编程基础.ppt

1、分布与并行计算,Distributed and ParallelComputing 主讲 庄毅 ,第2章 并行编程基础,2.1 并行编程综述 2.2 进程、任务和线程 2.3 并行性问题 2.4 交互/通信问题 2.5 并行程序中的语义问题,并行编程基础,并行编程综述 并行编程缘何艰难 1、并行软件一直落后的主要原因是并行编程比起顺序编程来是一个更复杂的智力活动。它包含了顺序编程中的所有问题，还要加上在智力上更具挑战性的许多其他问题。 2、顺序编程只有一个基本模型（冯诺依曼模型），而并行编程中却有许多不同的模型。 3、开发顺序程序的软件环境工具，如编译器、调试程序、以及特征分析器，要比并行程序

2、的先进得多。 4、比起并行编程来，有更多的人一直在从事顺序编程而且已有长得多的时间。对顺序编程由于已积累了大量知识，包括过去所发现的错误以及所得到的教训，因此更为成熟。,2.1 并行编程综述,并行编程进展 面向超级计算机的编程模型正集中趋向于两种模型： 1）适用于PVP、SMP、DSM的单地址空间的共享变量模型； 2）适用于MPP和机群的多地址空间的消息传递模型。 SIMD模型原已从主流超级计算机中淡出，但对于如同语言、图象和多媒体处理的专用嵌入式那些应用仍非常有用。 -尤其是多核芯片的问世，以SIMD模型为基础，未来的通用计算机编程将带来很大的改进。,并行编程综述,并行编程进展 高层并行编程

3、模型正集中趋向于4种标准模型： 1）数据并行（如HPF） 2）消息传递（如PVM和MPI） 3）共享变量（如ANSI X3H5） 4）蕴式并行模型，用户只需编写顺序程序，其中的蕴式并行性由并行化编译器（如Kap）进行析取。 图1 吞吐率处理 减少单个并行应用的响应时间 增加多个独立顺序作业的系统吞吐率,并行编程基础,并行编程环境 并行处理系统的组成部分 图2 并行编程环境工具： 作业管理工具 调试工具 性能工具,并行编程基础,并行编程方法 目前在实际的并行计算中广泛使用的并行编程模型有4种： 蕴式并行模型、数据并行、 消息传递、共享变量 这些并行编程模型均已在实际的并行编程系统中得到实现，绝大

4、部分为扩展的Fortran或扩展C。 对于顺序编程有三种扩展并行性的方法： 库子程序、新语言构造、编译器命令。,并行编程基础,库子程序：除了在顺序语言中可用的标准库外，加入一组新的库函数，以支持并行化和交互操作。这种库的实例包括: 消息传递(MPI) 和 多线程库 (POSIX Pthreads)。 新构造：扩展程序设计语言使其具有某些新构造，以支持并行化和交互。例如Fortran 90中密集数报操作。 编译器命令：程序设计语言不变，但加入称为编译器命令（或pragmas）的格式化注解。,三种并行化方式举例: for(i=0;iN;i+) Ai = bi*bi+1; for(i=0;iN;i+

5、) ci = Ai+Ai+1; (a) 串行代码段,三种并行化方式举例,并行编程基础,所有3个程序均执行相同的如图a所示的串行C代码的计算。 （1）图b说明了库方法 其中两个循环被分配到P个过程并行执行。由两个库函数：my_process_id() 和number_of_processes()开发并行性。 路障barrier()函数保证在第1个循环后，所有进程同步，这样第2个循环将使用在第一个循环中已更新的数组A的正确值。,id = my_process_id(); p = number_of_processes(); for (i = id;iN;i=i+p) Ai = bi*bi+1; b

6、arrier(); for(i = id;iN;i=i+p) ci = Ai+Ai+1; (b) 使用库例程的等效并行代码,三种并行化方式,并行编程基础,（2）若使用新的语言构造 使用新的语言构造,上述的这些并行操作就可变得相当简单，如图c所示。 Fortran 90的数组赋值构造A(0:N-1) = b(0:N-1)*b(1:N)可在1条数组赋值语句中完成N个元素乘法和赋值。在两个数组赋值之间，不需要显式同步，因为Fortran 90语句是松散同步：在下一语句开始执行前，前一语句中的操作必须都已完成。,my_process_id()，number_of_processes()，and; ba

7、rrier(); A（0：N1） = b （0：N1） * b （1：N）; C = A （0：N1） + A （1：N）; (c) Fortran 90 中使用数组操作的等效代码,三种并行化方式,并行编程基础,（3） 图d编译器命令方法 由并行pragma指明下一语句（以块形式出现）应并行执行。由共享(shared)pragma说明3个数组变量为并行进程共享，而局部pragma则用来指明每个进程有一个局部的变量。 SGI的pfor pravgma命令系统以并行方式执行下一循环。而由同步pragma产生一个路障同步。,#pragma parallel #pragma shared(A,b,c)

8、 #pragma local(i) #pragma pfor iterate(i=0;N;1) for(i=0;iN;i+) Ai = bi*bi+1; #pragma synchronize #pragma pfor iterate(i=0;N;1) for(i=0;iN;i+) ci = Ai + Ai+1; (d) SGI power C中使用pragma的等效代码,三种并行化方式,并行编程基础,下表中总结了3种方法的优缺点。由于容易实现，库例程是目前使用最广泛的方法所有并行化和交互功能由附加到顺序C或Fortran的一组程序实现。因此就无需实现新的编译器。然而由于没有编译器支持，用户就

9、丧失了编译时间分析、错误检查和优化的机会。,2.2 进程、任务和线程,抽象进程的定义 定义2.1 一个进程P是一个4元组P=（p, C, D, S） 其中p是程序（或代码）， C是控制状态，D为数据状态，S为进程P的状态。 进程是动态的，其中它不单是指代码和数据是动态的，而且还包含正在执行的思想。,进程、任务和线程,任何进程与一个程序相关，作为一个例子，考虑如下的C代码： main（） int i=0; fork(); fork(); printf(“Hello！n”); 我们可如下编译此程序（假设它在文件hello.c中）: cc-o Hi hello.c， 并可用简单命令： Hi 执行它。

10、,进程、任务和线程,操作系统将创建一个输出hello的进程。除了由用户提供的显式代码外，进程还使用运行时间支持、库例程以及系统函数。上述进程称为Printf（），它是C语言标准I/O库中的例程，以及fork(),它是Unix系统的一个调用。 控制和数据状态 大多数程序基于命令式机器模型，其中新概念是状态更新。 一个命令式程序可看成是一个状态机（或一个自动机），它将程序从初始状态映射到一个或多个最后状态。,进程、任务和线程,定义2.2 一个程序使用两个变量集： 数据变量由程序员声明用来保存数据值的变量； 控制变量是保存控制信息的变量，它们不需要显式说明。换言之，控制变量保存的是有关下一步应执行什

11、么操作的信息。 数据变量集和控制变量集两者的合集形成了程序变量集。,进程、任务和线程,定义2.3 在任何时候，一个程序的每个数据或控制变量需与一个值配为一对，该值可能是一个未定义的特殊值。在时间t时所有（数据变量、数据值）的配对集定义了时间t的程序数据状态。类似地，时间t的所有（控制变量，控制值）配对集定义了时间t的程序控制状态。因此，时间t的程序状态是t时间的数据状态和控制状态的和。或者我们可以说t时的程序状态是所有（程序变量、值）的配对集。,进程、任务和线程,定义2.4 程序从初始状态启动。当执行了程序的一个原子操作后，程序就从当前状态转为下一状态。程序不断执行原子操作并不断更新其状态，直

12、至终止。此时程序处在最后状态。 这样一个命令式程序可视为是产生一个或多个序列的原子操作，它们将状态机从初始状态转换到最后状态。 当一个程序进入一个被确认不会终结的状态时，则说该程序进入了发散状态。,进程、任务和线程,我们可把控制变量当作程序计数器。对具有单控制线程的进程来讲，它只有一个控制变量：程序计数器；而对有多控制线程的进程而言，它有多个控制变量，每个线程有一个，它含有该线程的程序计数器值；对于多子进程情况，整个进程可有若干个控制变量，每个子进程有一个。 在用户程序中，数据变量可用蕴式或显式方式说明。例如，Unix进程的数据变量含有隐藏的文件指针stdin、stdout以及stderr各自

13、用作标准输入、标准输出和标准错误，它们可显式地加以说明。,进程状态,在任何时间，进程具有某个状态： 图4 开始时，进程不存在（为不存在状态）。当它的创建者，父进程执行进程创建操作后，它才出现。一个新创建的子进程准备执行，但仅在被调度后，它方可开始运行（执行其代码）。在进程运行中可能发生以下几种情况： 由于页面失挂或其他情况，它无法继续执行时，就被挂起，从而进入挂起状态。,进程状态,在任何时间，进程具有某个状态： 一个正在运行进程可能被具有更高优先级的另一进程抢占，或者它可能已用完分配给它的CPU时间片（到时）。不论是哪种情况，进程本身能（准备）继续执行，但它被强制放弃CPU资源并转换其状态成为

14、就绪。 最后，一个正在运行的进程能终止本身，或是正常地在它完成代码执行后，或是异常地（夭折）终止，并停止存在。 另一个经常使用的操作是进程切换，它是指将一个正常运行的进程转换成或是挂起或是就绪状态，并调度下一个就绪的进程运行。,进程状态, 在实际的操作系统和并行编程环境中，由于还有附加的其他状态，因而情况更为复杂。 以上提及的进程概念很适合于需要使用并行语言的用户。对于那些要实现进程并行概念者，就需要更为详细的进程观。 在实现进程并行运行时，还必须考虑以下各方面：执行方式、地址空间、现场进程描述符和进程控制。,进程状态,寻找工作状态： 一个进程根据其是否已完成执行，可以进入寻找工作状态，若向这

15、个未被雇佣的进程分配某个新工作时，它就被激活了。 可减少由于一个进程结束后接着再被创建去从事一项新工作时所需的开销。 适用于共享存储器模型的并行编程。,线 程 概 念,线 程：指控制线程 逻辑组成由：程序代码、 一个程序计数器、 一个调用堆栈、适量的专用数据（包括通用寄存器）。 线 程共享对存储器的访问，所以线程之间能够通过读或写对它们都可见的存储器互相通信。 线 程也可共享对文件系统的访问。 用线程进行程序设计被称为： 基于线程的并行程序设计； 或被称为：共享存储器并行程序设计,线程,由进程创建的一种轻型进程，线程相对于进程，犹如进程相对于机器。,同一进程的所有线程共享地址空间 有程序计数器

16、和堆栈 像进程一样共享处理机 线程可以创建子线程 当一个线程被阻塞时，可调度运行同一进程中的另一线程 每个线程能读写，甚至清除另一线程的堆栈，线程之间没有保护 线程的状态：运行、阻塞、就绪、结束,下一页,引入线程是为了将并行性引入顺序执行的系统。 下图是线程与进程的三种组织,派遣者/工作者模型团队模型管道线模型,文件服务器进程,工作者线程,共享块cache,工作请求到达,邮箱,派遣者线程,内核,线程的用途,下一页,用线程构造服务器进程的三种方法,与线程相关的用户可得的原语集（即库调用）,线 程 包：,线程管理：,静态设计，程序编写或编译时就确定线程个数。每个线程分配一个固定堆栈。 动态设计，允

17、许线程在运行过程中动态的创建和回收,线程结束：,自己退出 被外界中止,共享数据：, 互斥变量，使用锁解决临界区数据共享问题 条件变量，解决同步问题，避免死锁,全局变量：,分配一块内存给全局变量，并将它作为一个参数传递给线程中的每一个过程 引入新的库过程来创建、设置和读取这些线程全局变量,线程调度：, 优先级法 轮转法,线程包的设计问题,有两种方法：在用户空间实现和在操作系统内核实现,线程包的实现,下一页,在用户空间中实现线程,在用户空间中实现线程：,将线程包完全放到用户空间中去，内核对此一无所知 线程运行在运行期系统的上层，运行期系统是一些管理线程的过程集 线程执行系统调用时进入休眠，由运行期

18、系统接管控制权，它负责线程的切换,优点：,能够在不支持线程的操作系统中实现 系统开销小，线程切换可用有限的几条指令完成 允许每一个进程有自己定制的调度算法,难以实现阻塞系统调用 线程调度是非抢先式调度，如果线程一直运行，运行期系统就得不到控制权,缺点：,内核知道并管理线程。当一个线程想去创建一个新线程或撤销已存在的线程时，它发出一个内核的调用，由它完成创建和回收工作 在内核中每个进程都有一张表，每个线程在表中有一个入口，每个入口保存着线程的寄存器、状态、优先权和其他信息 当一线程阻塞时，内核可以调用同一进程中的其它线程，也可以调用另一个进程的线程 按系统调用来实现线程的阻塞调用，但开销较大,在

19、内核中实现线程：,优点：,缺点：,不需要任何新的非阻塞系统调用 不易产生死锁 产生页面错时，系统能很容易地运行另一线程,系统调用耗费大,下一页,在内核中实现线程,模拟内核线程的功能，使用户空间内实现的线程包调度有更好的性能和有更大的灵活性。,目 标：,内核分配一定数量的虚拟处理机给每个进程，并且让运行期系统将线程分配给处理机 当内核知道一个线程已阻塞时，内核将通过将这个线程的号码和所发生事件的描述作为参数传递到堆栈，通知该进程的运行期系统 运行期系统一旦被激活，它就能重新调度线程 当一个用户线程在运行产生一个硬件中断时，被中断的CPU切换进入内核模式处理,实现方法：,下一页,调度者行为,在线程

20、上可以运行更轻量级的RPC。,方法：,当服务器线程S启动时，输出它的接口通知内核 需要服务的客户线程C启动后，从内核中取出S的服务接口，并获得该调用的标识 由内核创建专用数据结构来为调用S做准备。其中包括共享堆栈 线程C将参数压入堆栈，然后自陷进入内核 内核根据参数判断调用是否在本地，如在本地，更改客户内存映像，将客户放入服务器的地址空间，启动客户线程执行服务器过程,思想：,在线程上进行远程过程调用 （RPC）,线 程 概 念,进 程： 拥有私有地址空间 进程之间的互相通信需要借助传递消息； 也可借助文件系统（但很少） 在并行计算中，用进程进行程序设计被称为： 基于传递消息的并行程序设计 或被

21、称为：非共享存储器并行程序设计 进程趋向长期生存，而线程则随着计算的进行动态派生或销毁,2.3并行性问题及解决方法,进程中的同构性-指并行程序中各分进程的相似性。 有3种基本类型： SPMD：在单程序多数据（SPMD）程序中的分进程是同构的。因为多个进程在不同的数据范畴内执行相同代码。程序由数据并行构造，也称SPMD为数据并行程序。（如Fortran 90） MPMD：在多程序多数据（MPMD）程序中的分进程是异构的。因为多个进程可以执行不同代码。也称MPMD为功能并行程序、任务并行、控制并行。 SPMD和MPMD可以混用。,并行性问题及解决方法,有3种基本类型： SIMD： SPMD和MPM

22、D程序，两者都是MIMD类型的程序。因为在同一时间不同指令由不同进程加以执行。而一个SIMD程序比SPMD更加严格，因为多个过程不但必须执行相同代码，而且它们全体必须在同一时间执行相同的指令。换句话说，SIMD程序是 SPMD程序的一个特例。,并行性问题及解决方法, SPMD程序通常用： 并行循环构造、数据并行构造或单代码方式加以说明。 MPMD程序通常用: 并行块构造、多代码方式加以说明。 下面分别介绍这几种并行构造方法,2.3并行性问题及解决方法,1、并行块（parallel block) 表达MPMD程序的一个很自然的方法是使用parbegin和parend构造：Parbegin S1S

23、2Sn Parend 它们总是成对使用。 这种结构化的构造也称为：cobegin S1S2Sn coend 它被称为是一个并行块，其中 S1S2Sn 是分进程，可含有不同代码。 当并行块执行时，它的n个分进程S1S2Sn就开始同时执行。它们的执行是互相独立的而且以不同速率进行。 当所有n个分进程终止时，并行块才能终止。 之所以命名为并行块是为了与顺序块相对照，后者在传统的顺序语言中可以找到：begin S1S2Sn end。,并行性问题,2、并行循环（parallel loop） 当并行块中的所有进程共享相同代码时，我们用一个称为并行循环的速记记号来标明如下并行块： Parbegin Proc

24、ess(1) Process(n) Parend 可被简化成如下的并行循环： Parfor (i=1;i=n;i+) Process(i) 并行循环常用来说明SPMD并行程序。,并行性问题,系统程序（如操作系统或网络系统）中的进程通常是异构的。许多并行计算程序，特别是大规模并行计算机中的并行程序，是高度同构的。 要为有1000个处理器的计算机编写一个完全异构的并行程序将是很困难的，因为我们需要为每个处理器写一个不同程序。 对于一个分布/并行编程环境而言，希望能同时提供同构和异构进程。但是对于扩展并行机来讲，通常只要支持SPMD就足够了。在多核时代尤其如此。,并行性问题,当不同的代码数较小时，我

25、们可以用SPMD来伪造MPMD。 如： MPMD代码: parbegin A； B； C； parend 可以等价地表示成一个SPMD的并行循环： parfor（i=0;i3；i） If（i=0）A； if（i=1）B； if（i=2）C； ,并行性问题,3、多代码与单代码（Multi-Code versus Single Code） 在目前的并行计算机，特别是MPP和COW上，许多编程语言不提供并行块或并行循环构造。在这种系统中，MPMD并行性可用多代码方法加以说明来解决。 例如，要说明parbeginA； B； C； parend，用户需编写3个程序,并将它们编译以生成三个可执行程序A、B

26、和C，用shell脚本将它们装载到3个处理结点中： run A on node 1 run B on node 2 run C on node 3 程序A、B和C仅是顺序程序加上进行交互的库调用。,并行性问题,SPMD程序可用单代码方法加以说明来实现多节点并行。 例如，要说明并行循环 parfor（i=0;iN；i+) foo(i), 用户只需编写如下的一个程序： pidmy_process_id(); numproc = number_of_processes(); for (i:=pid;iN;i=i+numproc) foo(i); 此程序经编译后成为可执行程序A，通过执行命令： run

27、 A numnodes n 可将它装到n个结点中。 应注意的是：对用户来讲，单代码方法更加容易，且它允许相同程序在不同的结点数上以SPMD方式重复地加以执行。 在顺序程序的基础上加上进行交互的库调用,并行性问题,4、数据并行构造 在数据并行语言中（如Fortran 90和HPF）， SPMD并行性可用数据并行构造加以说明。 例如，要说明并行循环： parfor (i:=1;i=N;i+) Ci = Ai + Bi; 用户可用1条赋值语句：C = A +B 或 用以下循环来表示： forall( i=1,N) Ci = Ai + Bi;,静态和动态并行性,如果一个程序的结构以及组成进程的个数在运

28、行之前就可确定时，就认为该程序具有静态并行性。 （如在编译时间，连接时间或装载时间）否则就说它具有动态并行性，这就蕴含着哪些进程要在运行时间内创建和终止。 静态并行程序显得需要较少的运行时间开销，因此比动态并行程序有更高的效率。这是因为静态并行程序可免去许多初始化操作（如存储器分配、堆栈分配、系统表初始化等）。但动态并行程序则显得更为灵活,静态和动态并行性,Fork/Join(派生/汇合) 已经存在不同的派生/汇合版本。我们用一个例子来说明它的思路下列程序有3个进程，其中A是主进程，当程序开始执行时，它是自动被创建的：,Process A:Process B:Process C: beginb

29、eginbegin Z:=1 fork(C) Y:=boo(Z); fork(B); X:=foo(Z)end T:=foo(3) join(C); end output(X+Y); end,静态和动态并行性, 进程A在执行fork（B）操作后创建一个新进程B,它开始与A井行执行。换句话说，当B在执行时，A可继续执行它后面的语句。这两个进程可异步执行, 父进程必须等所有它的子进程结束后方可终止。 有时我们希望父进程在到达它的某一代码之前，等待子进程结束。要做到这一点可使用汇合语句。在上述的代码中，进程B依次创建了另一进程C。现在因为B中的输出语句需要由C计算的变量Y的值，为此可在输出语句之前插

30、入一条join(C)语句。该语句强制B在继续去执行输出语句之前等待C的终止。 Fork/Join是非常灵活的构造，但它们是非结构化的。它们犹如顺序语言中的goto语句，必须慎用。许多并行计算程序只能用并行循环加以说明。,进程编组, 在并行应用中的进程通常不是独立的。它们之间需要相互交互。应设法将需要交互进程调度在同一组中。 一个进程组是进程的一个有序集。进程中的成员数称为组的大小。每个组有一个组标识符（ID），它唯一地识别并行程序中的组。每个成员进程在组中有一排序，般它是0到n-1之间的一个整数，其中n是组的大小。一个成员进程可由它的排序和组的ID，唯一地加以识别。 为支持组的概念，并行编程语

31、言需要提供管理进程组的功能，如创建和毁灭组、询问组的ID、组的成员以及组员的排序等。,分配问题, 分配是指将数据和工作负载划分到进程中并将进程映射到结点（处理器）上。 一个好的分配方案应使工作负载平衡（即减小/ w）并使开销降为最低，以使系统在大部分时间内忙于计算而不是闲置或忙于交互。但这不应以牺牲并行性为代价。 分割的一个重要任务是选择合适的并行性和颗粒度。,分配问题,并行性 并行程序的并行度（degree of parallelism， DOP）通常定义为可同时执行的分进程数。是平均并行性的量化指标。常用于测量程序的总体DOP。 颗粒度 与并行性相关的概念是颗粒度（granularity）

32、或称为颗粒大小。它的定义是在两次并行性操作或交互操作之间所执行的计算负载。对于阶段并行模型，颗粒度可更精确地定义为在一个超步中一个处理器所执行的计算负载W。 颗粒度的单位可以是指令数、浮点操作数或是秒。粒度大小常可分为细（小）、中、粗（大）3种。虽然对粒度大小无确切定义，粗略地认为小粒度的计算操作数小于100、中粒度的在100到1000之间，而大粒度则超过数千。 颗粒度有时用来表示进程大小，即在一个分进程中的总操作数（不是超步中的操作数）。,分配问题, 用术语操作级（或指令级）并行性来表示当并行程序中的分进程仅为一个或少数几个计算操作或指令的情况。 用术语块级（block-level）并行性来

33、表示当单个过程大小是一个赋值语句块的情况。块级并行性的一个特例是循环级并行性，其中由一个循环创建许多过程，每个进程执行由许多赋值语句组成的一次迭代。当分进程中的每一个由一个过程调用组成时，就称其为过程级并行性，有时也称为任务级并行性。 并行度和颗粒大小常互为倒数，因为若是其他方面都相同时，增加粒度大小就会减少并行度，反之亦然。 并行度和进程及同步开销通常存在一个比例关系。若是其他方面都相同时，增加并行度常会增加开销，而减少并行度将会减少开销。,分配问题, 显式分配时，用户需要显式说明如何分配数据和工作负载。 隐式分配时，将由编译器和运行时间系统来完成分配任务 可以有各种组合分配方式。 例如在对

34、称式多处理机系统中，通常的分配方法是让数据留驻在一个中央共享存储器中以使所有进程都可以访问。工作负载的分配可以用静态方式或动态方式。当一个进程分得一个工作负载后，它所需的数据可从共享存储器中得到。,隐式和显式分配,分配问题, 在分布式存储器系统中，流行的分配方法是采用 “拥有者计算”（ownercompute）的法则： 首先在进程间分配数据。当进程P分得变量x时， P就被称为x的拥有者。此时有关x的计算，将由拥有者进程P加以执行。 数据和工作负载的分配对性能有很大影响。一个重要的研究主题是：如何恰当地分配数据以使在大部分时间，进程所需的数据就在附近。称这种方法为开发数据局部性，它可减少高速缓存

35、和存储器的不命中率以及通信开销。,隐式和显式分配,2.4交互/通信问题,交互 是指进程所完成的一个活动或操作，它影响进程相互间行为。可简单地把交互操作称作通信。倾向于使用术语交互，因为它被赋有更多含义。 有关交互的几个重要问题是： 在并行系统中需支持的交互操作； 交互方式和模式； 竞争交互和合作交互。,交互/通信问题,有3种最常用的交互类型： 通信 同步 聚集操作。 这些操作常统称为通信。但是对它们加以区别是很重要的，因为它们对体系结构和编程的支持有着不同的要求。,交互/通信问题,通信：通信操作是指在两个或多个进程间传送数据。 有三种同步方式: 在共享存储程序中，一个进程可对一个共享变量值进行

36、计算并将结果存回共享存储器。稍后，另一进程在访问该变量时，就可得到此值。这种通信被称为是借助共享变量的通信。 使用任务级/过程级并行性的多处理机程序用派生过程，如执行fork(foo(x)函数的方法，使父进程能创建一个子进程。数据值可像参数一样在子进程和父进程之间进行传送。这种通信被称为是借助参数传递的通信。 在多计算机模型中，进程可通过消息传递加以通信。,交互/通信问题,同步：同步操作将导致进程的相互等待是允许正在等待的进程继续执行。 有三种同步操作：原子性、控制同步和数据同步 原子性：进程常需要以单原子操作方式完成一串操作。如： parfor(i:=1;in;i+) atomic x=x+

37、1; y=y-1; 关键字atomic表示n个进程中的每一个进程必须以原子操作方式执行两条赋值语句。由并行系统以强制原子性方式完成隐式同步。,交互/通信问题,控制同步：执行控制同步操作的进程将处于等待状态，直至程序的执行到达某种控制状态。 控制同步的一个通常方法是路障同步，如以下代码所示： Parfor (i:=1;in;i+) Pi barrier Qi 代码中有n个进程。执行Pi 的第i个进程后跟一个barrier。当执行Pi完并到达barrier语句时，它必须处于等待，直到所有其他进程也到达了它们各自的路障才执行其之后的Qi 。,交互/通信问题,控制同步： 另一种控制同步的构造是临界区。

38、如下所示： parfor(i:=1;in;i+) critical x=x+1; y=y-1; 应注意临界区是互斥的，因为每次只允许一个进程执行这两条语句。,交互/通信问题,数据同步：执行一个数据同步操作的进程将处于等待状态，直至程序执行到达某个数据状态。 例如，执行wait(x0)语句的进程将处于等待，直至变量x变成正值。 数据同步操作的例子包括锁、条件临界区、监控程序等。 在大多数当今的系统中，都用数据同步来实现原子性。如： parfor(i:=1;in;i+) lock(S); x=x+1; y=y-1; unlock(S); 其中锁同步依赖于信号灯S中的数据状态。 控制同步只依赖于程序

39、的控制状态，它不受程序数据状态的影响。控制同步通常要比数据同步更易理解，虽然后者更为灵活。,交互/通信问题,聚集(aggregation): 由并行程序中的各分进程计算所得到的部分结果，需要用聚集操作加以合并以得到一个完整结果。可由一串超步来加以实现。而每个超步包含一个短计算和一个简单的通信和/或同步。 例：考虑下列计算两个向量A和B的内积计算。 parfor(i:=1;in;i+) X(i)Ai*Bi; inner_product:=aggregae_sum(xi); 上例求和操作称为归约(reduction)，因为它将许多值归约成一个值。其他聚集操作类型还有扫描（scan，也称为并行加前缀

40、parallel prefix），降序算法等。,交互/通信问题,例 递归折迭 归约操作 假设有n个进程P(0)，P(1)，P(n-1)。数组元素ai初始化时分配给进程P(i)。a0+an-1可以用下列的求P(i)的单代码程序加以表示，其中i=0 到 n-1； Sum=ai; /每个进程有一个局部变量Sum for(j=1;jn;j=j*2) /log(n)个超步 if(i%j=0) get Sum of process P(i+j) into a local variable tmp; (*将进程P(i+j)的和放到局部变量tmp中*) Sum=Sum+tmp; ,交互/通信问题,求和以类树方

41、式以log n个超步实现，设其中n=8，如下图所示。在每个超步中，进程从另一个进程中得到一个标量，并完成标量加法，求得中间部分和。最后在P(0)中得到最后结果。 图 递归折迭操作 聚集的主要特征是：它由一串超步组成，且每个超步中，每个进程完成一个效粒度计算然后通信一个短消息。,2.4 交互/通信问题,交互方式 下图中n个进程P1，Pn通过执行交互代码C进行交互。称这n个进程为交互的当事人（或参与者）。如果代码C必须当所以参与者都已到达C后方可执行，则称此交互为同步的；如果代码C不必等所有参与者都到达C后就可执行，则称此交互为异步的。 图 n个进程交互,交互/通信问题, n=2时的交互，称为双当

42、事人交互；当一个进程向另一个进程发送消息时，两个当事人的通信就称为是点对点通信。 若n大于2，则称为多当事人交互。多当事人交互常称为集合交互。 同步交互的并行程序较易理解，因为当代码C被执行时，程序处于一个控制状态。许多并行程序只需要多当事人的同步交互。 对含有异步交互的并行程序来讲，当一个进程开始执行交互代码时，程序可能处于不同的控制状态。其他进程中的任一个进程可能还未到达C，可能刚到达C，或者已经通过C。异步交互显得更加灵活。,交互/通信问题,当一个进程P遇到一个交互代码C时，若对入口和出口条件以不同方法加以设置，就可得到多种交户方式。相对于交互代码C，可对进程P定义如下状态： In： 进

43、程P在代码C中，包括刚进入C，刚完成它的代码C，或仍执行C。 Out：进程P不在代码C中，包括还未到达或已离开。 Arrived：进程P刚到达C，但还未进入。 Finished：进程P刚完成它的代码C，但还未离开。 对于双当事人交互，可有44=256种组合。实际上只使用其中的少数几种。表2-3中给出了一些例子，其中表述随意状态。,交互/通信问题,表2-3 入口和出口条件的组合,交互/通信问题,广泛使用的交互方式有以下三种： 同步的交互方式：在交互开始前，所有参与者都必须到达。仅当所有参与者都已完成后，一个参与者进程才能离开交互并继续以后的操作。判断一个交互是否为同步的一种简单方法是使用双路障测

44、试，即在交互代码的前后两处，各设置一个路障。如果合成的并行程序与原来的程序有完全相同的语义，则该交互是同步的，否则它便是异步的。 锁定的交互方式：一旦一个参与者已经到达，它就可进入一个交互，而不用顾及其他当事者在何处，当它完成自己的交互代码后，它才能离开此交互。应注意，此时其他当事者可能还未结束（甚至还未进入）此交互代码。例如锁定发送，它的结束意味着消息已被发出，但目的地可能还未收到。 非锁定的交互方式：一旦一个参与者已经到达，它就可进入一个交互。在完成自己的交互代码前，它就可离开交互。例如非锁定发送，它的完成只意味着进程已请求发送，但消息不一定发出。,交互/通信问题,交互模式 如果交互模式在编译时间就可确定，则就称其为静态的；否则便是动态的。 动态交互的一个特例是如果组成员能动态地发生改变。 例如，进程在运行时可脱离或加入一个组，这也称动态分组。 在一个有