Parallel Programming | 第二章消息传递计算

Parallel Programming系列为本学期（2020春季）并行程序设计课程笔记整理~

本章目录

一、消息传递程序设计基础

二、机群进行消息传递

三、并行程序评估

四、经验方法对并行程序的调试和评估

一、消息传递程序设计基础

1.消息传递多计算编程的方法

专用的并行程序设计语言：如occam语言
对顺序高级语言的语法/保留字扩展-->处理消息传递：如Fortran M
为顺序高级语言配备进行消息传递的外部过程库
- 显示说明执行哪些进程何时在并发进程间传递消息传递什么消息
- 两个基本方法：创建独立进程使其在不同计算机上执行的方法、发送和接收消息的方法

本章主要研究：使用通常的高级语言程序设计，使其能进行消息传递库的调用-->完成进程对进程的直接消息传递

2.进程的创建（假设只有一个进程映射到一个处理器）

静态进程创建 static process creation
- 进程在执行前说明，系统执行固定数目的进程，使用命令行显示标识
动态进程创建 dynamic process creation
- 在其他进程执行期间可创建并执行进程

3.程序设计模型

多程序多数据模型（multiple-program,multiple-data,MPMD）
- 为不同的处理器编写完全独立和不同的程序，通常只需要编写主程序和从程序：一个处理器执行主程序，由多处理机执行相同的从程序

单程序多数据模型（single-program, multiple-data,SPMD）-->是常用的消息传递系统之一MPI中采用的主要方法
- 用于静态进程的创建
- 不同的进程融合到一个程序控制语句为每个进程选择程序的不同部分

4.消息传递例程

基本发送和接收例程
- 发送：send(&x, destination_id)-->出现在源进程中-->参数为消息和目的ID-->发送消息
- 接收：recv(&y, source_id)-->出现在目的进程中-->参数为接收消息的地点名和源ID-->接收消息
- 传递一个消息：

发送/接收机制
- 同步消息传递
  - 同步synchronous:在消息传递已经结束时确实已经返回的例程
  - 同步发送例程：返回前处于等待状态至所发送的完整消息已经被接收
  - 同步接收例程：返回前处于等待状态至期待的消息到达存储
  - 一对进程同步：消息从源进程传送给目的进程之间，任何一个都不能继续执行
  - 同步例程的动作：传送数据、同步
  - 三路协议

阻塞/非阻塞消息传递
- 阻塞blocking：传送完成前不允许进程继续执行的例程；非阻塞nonblocking：不管消息是否已收到，例程马上返回
- MPI中：
  - 阻塞：使用消息缓冲区并且在它们的本地操作完成后就返回的例程；立即返回的例程-->非阻
  - 同步：直到发送例程、接收例程都已经到达且消息已经从源向目的传送时，发送和接收例程才返回

消息选择
- 目的进程recv()只接收send()指明的源进程所发的消息
- 源ID通配符：允许目的进程接收来自任何源进程的消息
- 消息标记message_tag
  - 对发送的不同类型的消息加以区分
  - send(&x, destination_id,message_tag)
  - recv(&y, source_id, message_tag)

一些概念
- 广播broadcast：向所有与问题求解有关的进程发送相同的消息
  - 标识：生成进程组-->添加到广播例程参数中

多播multicast：向进程组中的每个进程发送相同消息
分散scatter：根进程的数据数组中每个元素分别发送给各个进程

集中gather：从一组进程中的每一个进程处收集一个值，是分散的逆操作

规约reduce：将各个值进行集中，然后对其进行算术或者逻辑操作

二、机群进行消息传递

1.并行程序设计软件-->PVM（并行虚拟机）：为同构或异构的计算机间的消息传递提供了软件环境使用C、Fortran调用其库例程集

2.MPI-(Message-Passing Interface,消息传递接口):为消息传递和相关操作提供库例程

（1）进程的创建和执行

启动可执行的MPI程序通过命令行实现
- eg:mpirun progl-np 4 或者 progl-np 4-->相同的可执行程序同时在4个处理器上被启动，并未说明prog1的拷贝在何处执行
- 使用MPI_Init()例程将代码初始化；使用MPI_Finalize()例程结束

（2）使用SPMD计算模型

SPMD模型不排斥主-从方法，只是必须将主代码和从代码放在同一程序中

SPMD模型的一个优点：可以将命令行参数传递给每个进程
全部变量声明将在每个进程内被复制，不被复制的变量需要局部地加以说明

（3）消息传递例程

消息传递是错误操作的源头，通配符的使用更增加了出现错误操作或者死锁的可能

通信子：
- MPI为所有点对点和集合的MPI消息传递通信使用通信子
- 通信子：定义一组只允许组内进程相互通信的进程通信域communication domain-->使库的通信域与用户程序分隔开
- p个进程：每个进程使用0——p-1的序号
- 两类通信子：
  - 内通信子 intracommunicator 组内通信
  - 外通信子 intercommunicator 组间通信
  - 组：定义参与通信的进程集合
- 默认内通信子：MPI_COMM_WORLD -->所有进程的第一个通信子-->可在所有点对点和集合操作中使用
  - 点对点
    - 消息传递由发送和接收调用完成
    - 消息的数据类型在发送/接收参数中加以定义
    - 数据类型：标准MPI数据类型和用户自定义类型（现有类型派生）
    - 声明的数据类型具有数据类型可重用的优点
    - 不需要显式的发送和接收缓冲区
  - 完成：描述接收和发送版本的变化
    - 局部完成locally complete：一个例程完成操作中所有它的部分
    - 全局完成globally complete：当前操作涉及的所有例程都完成了操作中自己的部分
  - 阻塞例程：在局部完成后即可返回
    - 阻塞发送例程
      - 局部完成条件：保存消息的单元可以再次为其他语句或例程所使用或者其内容发生改变但不影响消息发送
      - 阻塞发送发送消息返回并不表明信息已被接收
      - 参数：
    - 阻塞接收例程
      - 局部条件完成时将返回，表明消息已被接收到目的单元
      - 参数：
  - 非阻塞例程：立即返回-->无论例程是否局部完成都会执行下一条语句
    - 非阻塞发送MPI_Isend(buf,count,datatype,dest,tag,comm,request):在源单元安全改变之前即可返回
    - 非阻塞接收MPI_Irecv(buf,count,datatype,source,tag,comm,request)：即使没接收消息也将立即返回
    - 使用MPI_Wait()、MPI_Test()例程-->检查发送或接收操作是否完成，MPI_Wait()会一直等待直至操作完成
    - 非阻塞例程提供了在等待消息达到期间进程继续进行其他活动的能力

（4）发送通信方式

1）标准发送standard：并不假设相应的接收例程已经启动，提供缓冲时发送在接收到达前就可完成

2）缓冲发送buffered：发送在匹配接收之前启动和返回，需要在应用程序中指定缓冲区空间

3）同步发送synchronous：发送和接收两个例程中任一个均可在另一个之前启动，但必须一起完成

4）就绪发送ready：匹配接收例程到达时才可发送

在助记符中使用字母标识：b-->缓冲 s-->同步 r-->就绪 eg:MPI_Issend()-->非阻塞同步发送

阻塞和非阻塞接收例程：只使用标准方式

（5）集合通信Collective Communication-->涉及一组进程（由内通信子所定义）

1）广播集中和分散

Parallel Programming | 第二章消息传递计算

2）障栅停止每个进程直至所有进程都已经到达指定的“障栅”调用

三、并行程序评估

1.并行执行时间

评估时间的假设
- 并行执行时间将被标准化成以算术操作单位来衡量
- 系统假设为同构的：所有处理器相同且以相同速度运行
- 所有算术操作被认为需要相同时间
- 不考虑构成程序的附加操作
- 所有格式被假设需要相同时间

计算时间:（1）通过计数计算步数加以推算，多个进程时只需计算最复杂进程的计算步数（2）计算步数是数据元素n和处理器数p的函数：tcomp=fn,p（3）假设所有处理器均相同且以相同的速度运行
通信时间
- 通信时间与消息的数量、大小、底层的互联结构、传送方式有关
- 消息1的通信时间：
  
  ：启动时间-->不包含数据的消息所需的时间，eg:源进程消息打包、目的进程解包的时间
  
  ：发送一个数据字所需的传送时间
  
  ：数据字的数目
- 通信时间是进程中所有顺序消息的通信时间之和：

加速系数：
计算/通信比：

时延隐藏
- 时延latency:完整的通信延时
- 时延隐藏：使通信与后续的计算重叠-->在等待通信结束时，使处理器忙于有用的工作
- 并行不完善性parallel slackness:p个计算机上实现m个进程，该计算机具有m/p并行不完善性

2.时间复杂度

顺序算法
- O记号：<-->
- ⊖记号：f<-->
- Ω记号：<-->

并行算法
- tp的时间复杂性是计算复杂性和通信复杂性之和
- 针对计算/通信比：理想情况-->计算时间复杂度大于通信时间复杂度，此时增大n可改进性能，但通常通信的代价很高
- 代价=（执行时间）*（使用的处理器总数）
  - 顺序计算：代价为
  - 并行计算：代价为
- 代价优化并行算法
  - 代价正比单处理机的执行时间-->
  - （并行时间复杂性）*（处理器数）=顺序时间复杂性
- 与顺序算法不同：顺序时间复杂度使用渐进方法（变量趋于无穷大），但并行算法中数据的大小和处理器数不可能趋于无穷大