Lecture #11 & #12

MPI（Message Passing Interface）

高性能计算中标准的并行编程模型，他是通用的，通用也是一把双刃剑，它可以用来解决大部分的并行问题，但是因为通用他很复杂。

并行编程模型

§共享内存地址空间

• 主要用于编程SMP /多核机器，多个线程直接共同访问内存数据。
  §关键属性
• 共享地址空间 - 隐式并行化
  §进程/线程通信 - 内存读取/存储
  §POSIX线程API（Pthread）/ OpenMP
• 创建/删除线程
• 同步（互斥，信号量）
• 线程管理

§分布式内存地址空间

• 最广泛用于编程并行计算机/超级计算机
  §关键属性：
• 分区地址空间
• 显式并行化
  §消息传递编程模型
• 每个处理单元都有自己的私有内存
• 交换用于传递数据的消息
• API：消息传递接口（MPI），MapReduce等。

消息传递模型

§过程（传统上）是程序计数器和地址空间。
§进程可能有多个线程（程序计数器和相关堆栈）共享一个地址空间。
§消息传递模型用于进程之间的通信，这些进程具有单独的地址空间。
§进程间通信包括

• 同步
• 将数据从一个进程的地址空间移动到另一个进程的地址空间

什么是MPI？

§消息传递接口（MPI）
§消息传递库规范

• 不是语言或编译器
• 不是具体的实施或产品, MPI本身是一个标准，OpenMP，MPICH才是具体的实现，是一个库，有C语言的库有java的库
  §适用于并行计算机，集群和异构网络
  §功能齐全，通用库
  §旨在提供对高级并行硬件的访问
• 终端用户
• 库作者，可以写一些通用的类库
• 工具开发人员，并行工具

MPI来自哪里？

§早期的供应商有自己的系统（英特尔的NX，IBM的EUI）不可移植不兼容没有固定的标准（或非常强大）。
§早期的便携式系统（PVM，p4，Chameleon）主要是研究工作。

• 没有解决所有的消息传递问题
• 缺乏供应商支持
• 没有以最有效的水平实施
  §MPI论坛于1992年组织，广泛参与：
• 供应商：IBM，Intel，TMC，SGI，Convex，Meiko
• 可移植性库编写者：PVM，p4
• 用户：应用科学家和图书馆作家
• MPI-1在18个月内完成

什么是MPI-1

§通信的基本功能（100多个功能API）
§阻止发送，接收
§非阻塞发送和接收
§上述变更
§丰富的集体沟通功能

• 广播，分散，聚集等
• 对性能非常重要; 广泛使用
  §描述数据布局的数据类型
  §过程拓扑
  §C和Fortran绑定
  §错误代码和类

什么是MPI-2 / MPI-3

§MPI-2增加了功能，包括

• 并行I / O.
• 远程内存访问，单向通信，put和get 不是send/receive
• 动态流程管理
  §MPI-3增加了功能，包括
• 容错，很弱，需要使用checkpoint机制
• 异步集体沟通
  §MPI-4正在进行中
• 更好地支持混合编程，容错，新的分析界面

使用MPI的原因

§标准化 - MPI是唯一可以被视为标准的消息传递库。 几乎所有并行平台都支持它。 实际上，它已经替换了所有以前的消息传递库。
§可移植性 - 将应用程序移植到支持（并符合）MPI标准的其他平台时，无需修改源代码。
§性能 - 供应商实现应该能够利用本机硬件功能来优化性能。选择正确的API
§功能 - 丰富的功能集
§可用性 - 提供各种实现，包括供应商和
公共区域。

使用MPI时的重要注意事项

§所有并行性都是显式的：程序员负责正确识别并行性并使用MPI构造实现并行算法。
§MapReduce被认为是“简化”的编程模型，但有一个限制，即问题必须具有“MAP”和“Reduce”表达的操作
§MPI是一种通用的并行编程模型，但很复杂

MPI基本发送/接收

§我们需要填写详细代码
§需要指定的事项：

• 如何描述“数据”？什么样的数据，那些数据送，那些数据收
• 如何识别流程？
• 接收器如何识别/屏蔽消息？
• 完成这些操作意味着什么？

一些基本概念

§进程可以收集到组中，COMM_WORLD。
§每条消息都在上下文中发送，并且必须在相同的上下文中接收。
§组和上下文一起形成一个communicator。
§进程由与communicator关联的组中的rank来标识。
§有一个默认的communicator，其组包含所有初始进程，称为MPI_COMM_WORLD。

MPI标签

§如何知道send和receive匹配，消息与附带的用户定义的整数标记一起发送，以帮助接收过程识别消息。
§可以通过指定特定标记在接收端筛选消息，或者不通过默认MPI_ANY_TAG消息接收中的标记。
§一些非MPI消息传递系统称为“消息类型”标签。 MPI将它们称为标记以避免与数据类型混淆。

MPI Basic（阻止）发送

MPI_SEND（地址，计数，数据类型，dest，标记，comm）
§消息缓冲区由（地址，计数，数据类型）。
§目标进程指定为dest，它等级comm指定的communicator中的目标进程。
§当此函数返回时，数据已传送到系统，缓冲区可以重复使用。 目标进程可能尚未收到该消息。

MPI Basic（阻止）接收

MPI_RECV（地址，计数，数据类型，来源，标签，通讯，状态）
§等待直到从系统接收到匹配（源和标记）消息，并且可以使用缓冲区。
§任意来源是comm或MPI_ANY_SOURCE指定的通信器中的等级。
§多出的参数是，状态，包含更多信息。可以查看收到了多少数据的信息，接受量动态变化，status方便查询。
§接收数量少于计数的数据类型是可以的，但是
收到更多是一个错误。

状态对象

§在完成接收后使用状态对象来查找消息的实际长度，来源和标记
§状态对象是MPI定义的类型，并提供以下信息： - 消息的源进程（status.source）

• 消息标签（status.tag）
  §收到的要素数量由下式给出：
  int MPI_Get_count（MPI_Status * status，MPI_Datatype数据类型，int * count）
  状态返回状态接收操作（状态）
  每个接收缓冲区元素的数据类型数据类型（句柄）计数接收元素的数量（整数）（OUT）

MPI在某种意义上很简单......

§许多并行程序只能使用这六个函数编写：

• MPI_INIT - 初始化MPI库（必须是第一个调用的例程）
• MPI_COMM_SIZE - 获取通信器的大小
• MPI_COMM_RANK - 获取调用进程的等级
  在沟通者中
• MPI_SEND - 向另一个进程发送消息
• MPI_RECV - 向另一个进程发送消息
• MPI_FINALIZE - 清理所有MPI状态（必须是进程调用的最后一个MPI函数）
  §但是，为了提高性能，您需要使用其他MPI功能

MPI数据类型

使用MPI定义的数据格式方便不同平台的迁移性
§要发送或接收的消息中的数据由三元组（地址，计数，数据类型）描述，其中
§MPI数据类型以递归方式定义为：

• 预定义的，对应于来自语言的数据类型（例如，
  MPI_INT，MPI_DOUBLE_PRECISION）
• 连续的MPI数据类型数组
• 数据类型的跨步块
• 数据类型的索引数组块
• 数据类型的任意结构
  §MPI数据类型有两个目的：
• 异构性
• 不连续的数据，一个send可以送很多不连续的数据，如果只使用C语言需要使用很多Send

MPI中的typeMap

§不连续数据可以定义一个新数据类型，在MPI中，数据类型表示为typemap typemap =（type0，disp0），...，（typen-1，dispn-1）
§数据类型的范围
数据类型范围指定的内存位置
§可以使用MPI_UB和MPI_LB设置人工范围

CONTIGUOUS数据类型

MPI_Type_contiguous（count，oldtype，＆newtype）MPI_Type_commit（＆newtype）
§假设原始数据类型oldtype具有typemap（double，0），double是8个字节（char，8），然后重复三遍就是一个新的数据格式。
MPI_Type_contiguous（3，OLDTYPE，＆NEWTYPE）;
§要实际发送此类数据，请使用以下调用顺序：
MPI_Type_contiguous（计数，数据类型，及NEWTYPE）;MPI_Type_commit（＆NEWTYPE）;MPI_SEND（缓冲液，1，NEWTYPE，DEST，标签，COMM）;MPI_Type_free（＆NEWTYPE）;

向量数据类型

索引数据类型

结构数据类型

Non-Blocking非阻塞通信

非阻塞（异步）操作返回（立即）可以等待和查询的“请求handle”（用来check有没有完成）

• MPI_ISEND（start，count，datatype，dest，tag，comm，request）
• MPI_IRECV（start，count，datatype，src，tag，comm，request）
• MPI_WAIT（请求，状态） 阻塞式
  非阻塞操作允许重叠计算和通信。 也可以在不等待使用MPI_TEST的情况下进行测试，就是去检查请求
• MPI_TEST（请求，标志，状态）
  在任何使用MPI_Send或MPI_Recv的地方，您都可以使用这对
  MPI_Isend / MPI_Wait或MPI_Irecv / MPI_Wait。

多次完成

§有时需要等待多个请求：MPI_Waitall（count，array_of_requests，
array_of_statuses）MPI_Waitany（count，array_of_requests，
＆index，＆status）MPI_Waitsome（count，array_of_requests，
array_of indices，array_of_statuses）
§每个都有相应的测试版本。

MPI中的集体通信

大部分可以用send/receive完成，如果想要更好的性能需要使用Collective机制，适合用广播的模式。
§集体操作由communicator中的所有进程调用
§没有使用消息标签
§在许多应用中，点对点可以被集体通信所取代，从而提高了简单性和效率

• 让内部实施为您优化沟通
  §三大类：
• 同步：障碍
• 数据移动例程：广播，收集，分散
• 全局计算程序：减少（多个进程合并），扫描

Barrier障碍同步

处理依赖关系。需要同步一下
§用于同步一组进程的执行：
int MPI_Barrier（MPI_Comm comm）;
§障碍是分离两个计算阶段的简单方法，以确保两个阶段的消息不会相互作用

Movement数据移动例程

§广播例程实现一对一广播，其中单个命名进程（根）将相同数据发送到所有其他进程
int MPI_Bcast（void * buffer，int count，MPI_Datatype datatype，int root，MPI_Comm comm）

单纯的挪动，不做计算。
Gather是四个进程的数据移动汇聚成一个进程的数据，
Scatter是一个进程的数据移动分离成四个进程的数据

Reduction操作

§Reduce操作使用指定的操作OP组合每个进程的输入缓冲区中提供的值，并将组合值返回到单个根进程的输出缓冲区或所有进程的输出缓冲区
不但要挪动数据，还要计算。

More on Collective

还有很多的Collective用来提升性能，很多相似的功能非常容易混淆

MPI-IO

§从用户的角度来看：

• 访问数据的并行程序的多个进程或线程，同时读写一个公共文件（共享）
  §在单个文件中生成结果，您可以获得良好的性能

为什么MPI是并行I / O的良好设置

§写数据就像从内存发送和磁盘接收一样，读取就是磁盘发送和内存接收。所以IO实际上就会死MPI的communication
§任何并行I / O系统都需要：

• Collective来提升性能
• 用户定义的数据类型，用于描述内存和文件布局
• 用于分隔应用程序级消息传递的communicator与I / O相关的消息传递
• 非阻塞操作
  §即很多类似MPI的机器

MPI-IO术语

§文件指针：隐式指定读/写的位置

• 个人：本地文件指针
• 共享：全局文件指针
  §偏移：从文件开头的位移
• 明确指定读/写位置
  §文件handle
• 标识文件的不透明对象
• 指向由库例程管理的数据结构的指针
  §访问模式
• 定义文件如何用于读/写
• 打开文件时指定
• 例如 MPI_MODE_RDONLY，MPI_MODE_RDWR（位标志）

并行I / O例程（API）

读写文件的具体实现

File View

多个进程读取一个文件怎么表达这个信息，使用文件视图
§处理对共享文件的读/写操作
§每个进程都会看到文件的一部分
§文件视图：定义文件的区域以分隔进程

§由三元组指定（位移，etype和文件类型）

• displacement：从文件开头跳过的字节数
• etype：数据访问的基本单位（可以是任何基本或派生数据类型）
• filetype：指定文件的哪个部分对进程可见

用于处理不连续IO

§连续的I / O将数据从内存中的连续块移动到单个存储区域
§非连续I / O有三种形式：

• 在内存中不连续
• 文件中不连续
• 两者都不相邻

Ways to Read/Write to a Shared File

从文件的指定的位置去读和写，并且shared，每个进程去读写文件都会有自己的file pointer，shared可以是多个进程使用相同的file pointer，

Collective IO

多个进程读写文件如何优化。内存和文件系统的send和receive也需要使用collective去优化。
许多应用程序都有计算和I / O阶段§在I / O阶段，所有进程都读/写数据

• 我们可以说他们共同访问存储
  §集体I / O由一组进程协调访问存储
• 参与I / O的所有进程必须调用集合I / O函数
• 允许MPI-IO中间件层知道完整的优化访问权限
• §独立I / O不是以这种方式组织的
• 访问没有明显的顺序或结构

Two-Phase Collective IO

最常用的Collective IO
§将不同进程的不连续数据合并为更大的连续数据
§将请求合并为连续的请求
§共享公共块
§两阶段

• I / O阶段，三个进程先读到内存里面去
• 通信（交换）阶段，然后在内存里面进行数据交换变为连续的数据

Collective IO with Aggregation

比如有100个进程，只选其中4个进程去跟文件系统读写，把数据划分为Aggregation，读出来的数据再去进行交互。这四个进程叫中间节点。
§聚合是指通过中间节点移动数据的概念

• 执行I / O的不同节点数
• 也可以应用于独立的I / O.

Nonblocking I/O

IO也有非阻塞式的

实现高I / O性能的一般指南

§拥有足够的I / O硬件
§使用并行/分布式文件系统，而不是NFS安装的home目录
§不要仅从一个进程执行I / O.
§尽可能提出大量请求
§对于非连续请求，请使用派生数据类型和单个集合I / O调用
§任何应用程序都根据其I / O需求具有特定的“I / O访问模式”，并选择正确的API以及向I / O系统表达I / O访问模式的正确方式