并行程序设计导论.ppt

MessagePassingProgramming LiXiSchoolofInformationScience EngineeringCentralSouthUniversity 消息传递编程 主要介绍采用2个非专利的 广为接受的消息传递系统PVM和MPI的设计思想和功能特点 以及借助其实现并行处理的一般过程 MPI MassagePassingInterfacePVM ParallelVirtualMachine lib org pvm3 index html 消息传递范例 介绍开发分布式并行性的消息传递方法所具有的特征 消息传递软件包研究并推出的基于消息传递的软件包较多 其中包括专有软件和非专利软件 目前 大多数并行计算机供应商已将最流行的PVM和MPI作为对消息传递的自然支持 PVMandMPI MPI 是由MPI论坛开发的有关函数库的标准规范 通过提供一个独立于平台的消息传递库达到其可移植性的目的 PVM 是一个软件系统 主要功能是将网络上各种同构或异构的计算机利用起来 给用户提供一个统一的 灵活的并行计算资源 已被移植到SMP PVP MPP COW和PC上 两者都提供与Fortran和C的捆绑 Massage PassingModes 通信 表示消息传递系统中所有交互操作 包括 通信 Communication同步 Synchronization聚集 Aggregation一般地 通信在同组进程间进行 通信进程需要了解的内容有 参与通信的进程数 采用何种方式保证进程间的同步 如何管理通信缓冲区 例 消息传递中的发送和接收缓冲区 进程PM 10 L1 sendMtoQ L2 M 20 gotoL1 进程QS 100 L1 receiveSfromP L2 X S 1 发送缓冲区 接收缓冲区 说明 同步和锁定方式中 代码执行后X的值为11 非锁定方式中 代码执行后X的值可能为11 21或 99 消息传递系统中的通信方式 同步消息传递 SynchronousMessagePassing发送 接收进程必须等待发送 接收后才能返回 锁定发送 接收 BlockingSend Receive锁定发送时 发送进程只有等待消息发送返回后才能继续 需要临时缓冲区暂存消息 非锁定发送 接收 NonBlockingSend Receive非锁定发送时 发送进程通知系统消息M已经发出后即可返回 此时消息M并不一定已经离开M 因此重写M是不安全的 可能需要一个临时缓冲区 三种通信方式比较 三种通信方式比较 续 同步方式 优点 清晰 可靠 无需系统临时缓冲区 缺点 发送方和接收方互为等待 导致周期浪费 异步方式 该方式几乎存在于所有消息传递系统中 优点 无周期浪费 等待时间少 缺点 需设缓冲 且无法知道缓冲区应设大小 导致结果的不确定性 为正确接收 需附加状态检测或等待函数 需要管理缓冲区 导致系统消耗 Overhead 采用何种算法 机制 如何更有效地隐藏通信时延 是异步方式研究内容之一 下页例 通过等待函数保证消息安全接收 进程PM 10 L1 sendMtoQ 某些不改变Q的计算 WaitforMtobesent L2 M 20 gotoL1 进程QS 100 ReceiveSfromP 某些不使用S的计算 WaitforStobereceived X S 1 MassagePassingInterface MPI是消息传递函数库的标准规范 94年公布 97年推出MPI 2的修订版 增加了动态进程 非阻塞消息等功能 MPI已经在Windows Unix及主要的并行计算机上得到实现 所以 对于用标准C Fortran编程 使用MPI进行消息传递的程序 可不加改变地在PC 工作站 工作站网络 MPP和任何OS上执行 MPI功能设计基础 MPI功能设计 基于4个正交的概念 MassageDataTypes 消息数据类型 Communicator 通信子 CommunicationOperation 通信操作 VirtualTopology 虚拟拓扑 其中 前3个是最基本 最常用的 主要讨论 MPI提供了200多个函数 由于正交性设计 使其较PVM更容易学习 使用 MPI并行性讨论 MPI假设进程是静态的 即所有并行进程在装入时被创建 直到程序结束 MPI设置一个由所有进程组成的缺省进程组 组标识为MPI COMM WORLD MPI由6个函数构成编写完整消息传递程序的最小集 MPI Comm Size MPI Comm rank MPI Send MPI Recv MPI Init MPI Finalize 缺省组大小 每个进程秩 终止MPI环境 MPI消息传递程序示例 例 一个SPMD类型的计算foo i 的消息传递程序 foo i 说明 设共有N个整数 foo i 完成i i操作 最后 汇总 假设有n个结点并行处理 则一般处理方案为 n 3时0123456789 N进程0处理 foo 0 foo n foo 2 n 进程k 0 k n 处理 foo k foo n k foo 2 n k 各进程处理结果发送到0进程 由其完成最后汇总 SPMD类型的MPI程序myprog c include mpi h intfoointi main argc argv intargc char argv inti tmp sum 0 group size my rank N MPI Init 消息标志 目的进程 结构指针 源进程 程序myprog c执行说明 1用并行编译器mpicc编译 mpiccmyprog c omyprog2将可执行文件装到n个结点上运行 MPIRUN npnmyprog3每个结点执行相同的程序代码 构成SPMD方式 MPIMessages MPI中进程的地址空间相互分离 一个进程不能访问另一个地址空间中的数据 所以通信采用消息传递方式完成 消息一般由消息头 Head 及消息正文 Text 组成 MPI中消息发送 接收语句格式 MPI Send address count datatype destination tag communicator MPI Recv address count datatype source tag communicator status 例如 将数组doubleA 100 发送MPI Send A 100 MPI DOUBLE DEST MPI Recv B 100 MPI DOUBLE source 发送A 2 A 3 MPI Send A 16 2 MPI DOUBLE DEST 如何发送A中下标为偶数的元素 双精度每项8字节 MPI设置数据类型的原因 支持异构计算 便于从发送缓冲区中非连续 非均匀地取数据 例 发送不同类型的数据将字符串charString 1000 的前100个字符从洛杉矶的一台工作站发送到北京的一台工作站 若用如下格式 USA send String 100 China China recv String 100 USA 两地的字符表示长度不同 1 2字节 导致结果不正确 改进 USA MPI Send String 100 MPI CHAR China China MPI Recv String 100 MPI CHAR USA MPI CHAR在美国 中国分别以8 16位实现 接收时转换 类型为MPI CHAR的数据项数 MPI附加数据类型 MPI包括C Fortran所有基本数据类型 并增加2个附加类型 MPI BYTE和MPI PACKED 例 利用附加类型完成A 100 中偶数元素发送doubleA 100 MPI Pack size 50 MPI DOUBLE comm 确定打包缓冲区大小 缓冲区大小返回值 打包项计数 MPI派生数据类型 例 发送一个数组中的所有偶数项元素doubleA 100 MPI Data typeEvenElements MPI Type vector 50 1 2 MPI DOUBLE 说明 MPI Type vector count blocklength stride oldtype newtype 派生数据项数 按oldtype的每块长度 块间跨度 MPI数据类型 MassageBuffer 消息缓冲区由系统或程序员说明 用于暂存收发的消息数据值 消息缓冲可以是如下3种之一 用户说明的一个消息变量地址 系统创建管理的一个暂存消息区 用户创建管理的一个暂存消息区 3种缓冲区类型示意 进程P进程QdoubleA 100 doubleB 32 MPI Send A 32 MPI DOUBLE Q MPI Recv B 32 MPI DOUBLE P 优点 消息在2进程间直接同步传递 缺点 接收进程缓冲区容量应足够大 优点 支持异步通信 缺点 使用缓冲区增加系统消耗 若系统缓冲S太大 可能异常 缺点 若系统不能容纳缓冲区T 将产生错误消息通知应用程序 并体面终止 MessageEnvelopeinMPI 消息信封表示一个接收者的信息 MPI中由3部分组成 destination tag和communicator 消息标志tag 整数 标识不同类型消息并限定消息接收 设置原因 避免消息后发先至 造成接收错误 服务进程通过判定消息标志 可完成相应处理 消息标志使用示例 ProcessP send request1 32 Q tag1 ProcessR send request2 32 Q tag2 ProcessQ while true recv received request Any Process 32 Any tag Status if Status Tag tag1 processreceived requestinoneway if Status Tag tag2 processreceived requestinanotherway 通配进程ID 通配标志 MPI Status typedefstructMPI Status intcount intcancelled intMPI SOURCE intMPI TAG intMPI ERROR MPI Status 消息状态status MPI Status类型 存放接收消息的状态信息 包括消息的源进程标识 消息标签 包含的数据项个数等 它是消息接收函数MPI Recv的最后一个参数当一个接收者从不同进程接收不同大小和不同标签的消息时 消息的状态信息非常有用 Communicator 通信子由进程组和一个现场组成 进程组是进程的有限和定序集 有限是指进程组由有限个进程n组成 n为组的大小 定序指n个进程在进程组中的排序值 即进程ID 相关例程 MPI Comm size communicator group size MPI Comm rank communicator my rank 一个进程组可以有多个通信子 不同通信子可包含不同进程 设置通信子好处 不同通信子中通信分离 同一通信子中集合通信与点 点通信分离 每个通信子都有一个不同现场 MPI一个现场中传递的消息不会在另一个现场中被接收 避免了通信子间的干扰 达到通信过程的安全分离 通信子参数 intra communicators组内通信 缺省值 inter communicators组间通信 通信子管理 MPI预定义通信子 MPI COMM WORLD包含所有进程集 用户可通过MPI提供的多个相关例程定义自己的通信子 下列为其中2个 MPI Comm dup communicators new comm 功能 将通信子communicators中的进程复制到new comm通信子中 MPI Comm split 功能 将一个通信子中的进程按参数要求 分解到多个新的通信子中 构造用户定义通信子示例 MPI CommMyWorld SplitWorld intmy rank group size Color Key MPI init 按颜色分组 组内按Key排序 通信子MyWorld分裂结果 Message PassingCodetoCompute defineN1000000Main doublelocal pi w longi taskid numtask w 1 0 N MPI Init DifferentSend ReceiveOperationsinMPI Example ProcessPipelineUsingMessagePassing 3进程流水线 每个进程连续地接收来自左边的输入数据流 计算一个新数据流 发送给右边进程 ProcessQ While Not Done MPI Irecv NextX MPI Isend PreviousY CurrentY Q CurrentX Concurrent Example Cont Awell knowndouble bufferingscheme Example Code ProcessQ While Not Done if X XBuf0 X XBuf1 Y YBuf1 Xin XBuf0 Yout YBuf0 else X XBuf0 Y YBuf0 Xin XBuf1 Yout YBuf1 MPI Irecv Xin recv handle MPI Isend Yout send handle Y Q X overlappingcomputation MPI Wait recv handle recv ststus MPI Wait send handle send status send handle recv handle用于发送 接收是否结束判断 MPI Wait Handle Status 等待直到Handle指明的发送接收结束 并将某些状态信息传给Status 接送区指针 发送区指针 CollectiveCommunication 群集通信 CollectiveCommunications 是一个进程组中的所有进程都参加的全局通信操作 群集通信一般实现三个功能 通信 聚集和同步 通信 communication 主要完成组内数据的传输聚集 aggregation 在通信的基础上对给定的数据完成一定的操作同步 synchronization 实现组内所有进程在执行进度上取得一致 CollectiveCommunication 群集通信 Communication 按照通信方向的不同 又可以分为三种 一对多通信 多对一通信和多对多通信 一对多通信 一个进程向其它所有的进程发送消息 这个负责发送消息的进程叫做Root进程 多对一通信 一个进程负责从其它所有的进程接收消息 这个接收的进程也叫做Root进程 多对多通信 每一个进程都向其它所有的进程发送或者接收消息 CollectiveCommunication CollectiveCommunication 广播 broadcast 是一对多通信的典型例子 其调用格式如下 MPI Bcast Address Count Datatype Root Comm Broadcast的特点标号为Root的进程发送相同的消息给通信域Comm中的所有进程 消息的内容如同点对点通信一样由三元组标识 对Root进程来说 这个三元组既定义了发送缓冲也定义了接收缓冲 对其它进程来说 这个三元组只定义了接收缓冲 CollectiveCommunication include include mpi h intmain intargc char argv intrank value MPI Init BroadcastExample CollectiveCommunication 收集 Gather 是多对一通信的典型例子 其调用格式下 MPI Gather SendAddress SendCount SendDatatype RecvAddress RecvCount RecvDatatype Root Comm Gather的特点在收集操作中 Root进程从进程域Comm的所有进程 包括它自已 接收消息 这n个消息按照进程的标识rank排序进行拼接 然后存放在Root进程的接收缓冲中 接收缓冲由三元组标识 发送缓冲由三元组标识 所有非Root进程忽略接收缓冲 CollectiveCommunication MPI Commcomm intgsize sendarray 100 introot rbuf MPI Comm size comm GatherExample 散播 Scatter 也是一个一对多操作 其调用格式如下 MPI Scatter SendAddress SendCount SendDatatype RecvAddress RecvCount RecvDatatype Root Comm CollectiveCommunication Scatter的特点Scatter执行与Gather相反的操作 Root进程给所有进程 包括它自已 发送一个不同的消息 这n n为进程域comm包括的进程个数 个消息在Root进程的发送缓冲区中按进程标识的顺序有序地存放 每个接收缓冲由三元组标识 所有的非Root进程忽略发送缓冲 对Root进程 发送缓冲由三元组标识 CollectiveCommunication MPI Commcomm intgsize sendbuf introot rbuf 100 MPI Comm size comm ScatterExample 全局收集 Allgather 多对多通信的典型例子 其调用格式如下 MPI Allgather SendAddress SendCount SendDatatype RecvAddress RecvCount RecvDatatype Comm Allgather操作相当于每个进程都作为ROOT进程执行了一次Gather调用 即每一个进程都按照Gather的方式收集来自所有进程 包括自己 的数据 CollectiveCommunication MPI Commcomm intgsize sendarray 100 int rbuf MPI Comm size comm AllgatherExample 全局交换 Alltoall 也是一个多对多操作 其调用格式如下 MPI Alltoall SendAddress SendCount SendDatatype RecvAddress RecvCount RecvDatatype Comm CollectiveCommunication Alltoall的特点在全局交换中 每个进程发送一个消息给所有进程 包括它自已 这n n为进程域comm包括的进程个数 个消息在它的发送缓冲中以进程标识的顺序有序地存放 从另一个角度来看这个通信 每个进程都从所有进程接收一个消息 这n个消息以标号的顺序被连接起来 存放在接收缓冲中 全局交换等价于每个进程作为Root进程执行了一次散播操作 CollectiveCommunication include mpi h include include include includeintmain intargc char argv intrank size intchunk 2 发送到一个进程的数据块的大小 inti j int sb rb intstatus gstatus MPI Init AlltoallExample rb int malloc size chunk sizeof int 申请接收缓冲区 if rb perror can tallocaterecvbuffer free sb MPI Abort MPI COMM WORLD EXIT FAILURE for i 0 i size i for j 0 j chunk j sb i chunk j rank i chunk j 设置发送缓冲区的数据 printf myid d sendtoid d data d d n rank i j sb i chunk j rb i chunk j 0 将接收缓冲区清0 执行MPI Alltoall调用 MPI Alltoall sb chunk MPI INT rb chunk MPI INT MPI COMM WORLD AlltoallExample for i 0 i size i for j 0 j chunk j printf myid d recvfromid d data d d n rank i j rb i chunk j 打印接收缓冲区从其它进程接收的数据 free sb free rb MPI Finalize AlltoallExample 同步 Synchronization 功能用来协调各个进程之间的进度和步伐 目前MPI的实现中支持一个同步操作 即路障同步 Barrier 路障同步的调用格式如下 MPI Barrier Comm 在路障同步操作MPI Barrier Comm 中 通信域Comm中的所有进程相互同步 在该操作调用返回后 可以保证组内所有的进程都已经执行完了调用之前的所有操作 可以开始该调用后的操作 CollectiveCommunication include mpi h include test h include includeintmain intargc char argv intrank size i int table interrors 0 MPI Init BarrierExample Makedatatable table int calloc size sizeof int table rank rank 1 准备要广播的数据 MPI Barrier MPI COMM WORLD 将数据广播出去 for i 0 i size i MPI Bcast BarrierExample 群集通信的聚集 Aggregation 功能使得MPI进行通信的同时完成一定的计算 MPI聚集的功能分三步实现首先是通信的功能 即消息根据要求发送到目标进程 目标进程也已经收到了各自需要的消息 然后是对消息的处理 即执行计算功能 最后把处理结果放入指定的接收缓冲区 MPI提供了两种类型的聚集操作 归约和扫描 CollectiveCommunication 归约 Reduce 的调用格式如下 MPI Reduce SendAddress RecvAddress Count Datatype Op Root Comm Reduce的特点归约操作对每个进程的发送缓冲区 SendAddress 中的数据按给定的操作进行运算 并将最终结果存放在Root进程的接收缓冲区 RecvAddress 中 参与计算操作的数据项的数据类型在Datatype域中定义 归约操作由Op域定义 归约操作可以是MPI预定义的 也可以是用户自定义的 归约操作允许每个进程贡献向量值 而不只是标量值 向量的长度由Count定义 CollectiveCommunication MPI预定义的归约操作 CollectiveCommunication 扫描 Scan 的调用格式如下 MPI scan SendAddress RecvAddress Count Datatype Op Comm scan的特点可以把扫描操作看作是一种特殊的归约 即每一个进程都对排在它前面的进程进行归约操作 MPI SCAN调用的结果是 对于每一个进程i 它对进程0 1 i的发送缓冲区的数据进行了指定的归约操作 扫描操作也允许每个进程贡献向量值 而不只是标量值 向量的长度由Count定义 CollectiveCommunication 所有的MPI群集通信操作都具有如下的特点 通信域中的所有进程必须调用群集通信函数 如果只有通信域中的一部分成员调用了群集通信函数而其它没有调用 则是错误的 除MPI Barrier以外 每个群集通信函数使用类似于点对点通信中的标准 阻塞的通信模式 也就是说 一个进程一旦结束了它所参与的群集操作就从群集函数中返回 但是并不保证其它进程执行该群集函数已经完成 一个群集通信操作是不是同步操作取决于实现 M