第一章 消息传递基础
问题分解
设计并行算法的第一步是把问题分解成更小的问题。粗略来看，有两种分解方式：
1、域分解：也称为“数据并行化”。数据被分割成大约相同尺寸的小块，然后被映射到不同的处理器。每个处理器只处理被分配给它的部分数据。当然，处理器之间可能需要周期性地通信以便交换顺序。
数据并行化的优点是维护了单个控制流。数据并行算法由应用到数据的基本指令序列（只在前一个指令完成才开始的指令）组成。单程序多数据（SPMD）遵循这个模型，所有处理器里的代码都相同。
这种策略普遍应用于有限差分算法（finite differencing algorithm），处理器可以独立地操作大块的部分数据，只在每次迭代交换小得多的边界数据。
2、功能分解：域分解策略通常不是一个并行程序的最高效的算法。这种情况下被分配到不同处理器的各个数据片段需要明显不同的处理时间。代码性能的瓶颈在于最慢的进程。剩余的空闲进程没有做有用的工作。在这种情况下，功能分解（也称任务并行化）比域分解更合理。此时问题被分解为很多更小的任务，而任务在可用时会被分配到不同的处理器。更快完成的处理器会被分配更多的任务。
任务并行化由C／S结构实现。任务由主进程分配到一组从进程上，而主进程自身也可能执行一些任务。事实上C／S结构可以在程序的任何层次上实现。例如，你简单地想要运行一个有多个输入的程序。一个并行的C／S实现可能只是运行代码的多个拷贝，服务器串行地把不同的输入分配到每个进程。当各个进程完成了自己的任务，它被分配一个新的输入。除此之外，任务并行话也可以在代码的更深层次实现。
数据并行与消息传递模型
历史上，有两种方式可以写并行程序。
1、使用基于指令的数据并行语言；
2、通过标准编程语言的库调用来显式地传递消息。
在基于指令的数据并行语言里，比如High Performance Fortran(HPF）或OpenMP，通过加入（看起来像注释的）指令来告诉编译器如何跨处理器分发数据和工作，使得串行代码并行化。数据并行化语言通常在共享内存架构上实现，因为全局内存空间极大地简化了编译器的实现。
使用消息传递方式的话，程序员需要显式地把数据和工作分配到多个处理器，并管理它们之间的通信。这种方式非常地灵活。
并行编程需知
因为写并行化程序的主要目的是比串行版本得到更好的性能，所以在设计并行代码时有一些方面需要考虑，以便在解决问题的同时得到最好的效率。这些方面包括：
1、负载平衡（load balancing）；
2、最小化通信（minimizing communication）；
3、重叠通信与计算（overlapping communication and computation）。
负载平衡：把任务平等地分配到可用的进程。当所有进程都执行相同操作（来处理数据的不同片段）时比较容易。但是当处理时间取决于计算的数据值时就没那么简单了。当处理时间会有很大波动时，你可能需要使用不同的方式来解决这个问题。
最小化通信：在并行编程里总的运行时间是一个主要考虑，因为它是比较和提升所有程序的关键部分。执行时间由三个部分组成：
1、计算时间（Computation time）：在数据计算上花费的时间。理想状态下，如果有N个处理器计算一个问题，你可以需要N分之一的串行工作时间来完成这个工作。如果所有的处理器时间都花在计算上时，可以达到。
2、空闲时间（Idle time）：进程等待其它处理器的时间。在等待期间，处理器不做有用的工作。例如用并行程序处理I／O。许多消息传递库都没有解决并行I／O，使得某个进程处理所有的工作，而其它所有处理器都处于空闲状态。
3、通信时间（Communication time）：进程发送和接收消息的时间。执行时间里的通信花费可以用“潜在时间（latency）”和“带宽（bandwidth）”来衡量。潜在时间用于设置通信所需的信封，而带宽是传输的真正速度，即每单位时间传送的位数。串行程序不需要使用进程间通信。因此，你必须最小化这个时间的使用，来得到最好的性能提升。
重叠通信与计算：有几种方式可以最小化进程的空闲时间，一个例子是重叠通信与计算。当某一进程等待通信完成时，它被分配一个或多个新的任务，所以它可以在等待时处理另一个任务。对非阻塞通信和非特定数据的计算的谨慎使用可以实现这种场景。在实践中交叉计算与通信其实是非常难的。
熟悉MPI
消息传递模型
1、平行计算由许多进程组成，每个都计算一些本地数据。每个进程都有纯粹的本地变量，且没有任何机制可以让任何进程直接访问另一个的内存。
2、进程间的共享通过消息传递发生，也就是通过显式地在进程间发送和接收数据。
注意该模型涉及到“进程”，在理论上它们不需要运行在不同的处理器上。我们这里通常假设不同进程运行在不同的处理器上，所以术语“进程”和“处理器”可以交替使用。
这个模型有用的主要原因是它非常具有一般性。本质上讲，任何类型的并行计算都可以转换成消息传递形式。此外，这个模型：
1、可以在许多不同平台上实现，从共享内存多处理器到工作站构成的网络，甚至可以是单处理器的机器。
2、通过并行应用，通常比诸如共享内存模型的模型允许对数据位置和流动的更多控制。因此程序通过使用显式的消息传递，经常可以达到更好的性能。事实上，性能是为何消息传递不太可能从并行编程世界里消失的原因。
消息传递编程接口MPI（Message Passing Interface）被试图作为消息传递模型的一个标准实现，是由全世界工业、科研和政府部门联合建立的一个消息传递编程标准，其目的是为了基于消息传递的并行程序设计提供一个高效、可扩展、统一的编程环境。它是目前最为通用的并行编程方式，也是分布式并行系统的主要编程环境。MPI-1标准定义于1994年春：
1、它分别规范了命名、调用序列、通过Fortran 77和C调用的子例程和函数的结果。MPI的所有实现遵守这些规则，从而保证了兼容性。MPI程序可以在任何支持MPI标准的平台上编译和运行；
2、库详细的实现交给独立的厂商，他们可以自由地针对他们的机器提供优化版本；
3、MPI-1标准的实现对许多平台可用。
MPI-2标准定义了三个单向的通信操作：
1、Put：写入远程内存；
2、Get：读取远程内存；
3、Accumulate：缩减各任务间的相同内存；
MPI-2同时还定义了三种不同的同步方式（全局锁、成对锁、和远程锁）。还有并行I／O、C++和Fortran 90绑定、以及动态进程管理所使用的工具。目前有些MPI实现已经包含了部分MPI-2标准，但完整的MPI-2还不可用。
MPI的主要目标是为了：
1、提供源代码的兼容性。MPI程序应当可以在任何平台上编译和运行；
2、允许不同架构上的高效实现。
MPI也提供了：
1、许多功能，包含许多不同类型的通信、普通“收集”操作的特定指令、和处理用户定义数据类型和拓扑的能力；
2、对异构并行架构的支持。
明显没有包含在MPI-1的有：
1、运行一个MPI程序的精确机制。一般说来，这是平台相关的且你需要翻阅本地文档来找到如何完成这个机制；
2、动态进程管理，也就是在代码运行时改变进程的数量；
3、调试；
4、并行I／O。
使用MPI的时机
当你需要做以下事时应该使用MPI：
1、编写可移植的并行代码；
2、通过并行编程得到高效率，例如编写并行库；
3、处理涉及不适合“数据并行”模型的不规范或动态的数据关系的问题。
以下情况不适合使用MPI：
1、可以通过数据并行（例如High-Performance Fortran）或共享内存的方法（例如OpenMP或基于指令的专利范式）得到足够的性能和可移植性；
2、可以使用已有库里的（本身由MPI实现的）并行例程。
3、根本不需要并行机制！！
消息传递程序的基本特性
消息传递程序由通过函数调用来通信的串行程序的多个实例组成。这些调用大致可以分为四类：
1、用于初始化、管理、最终终止通信的函数；
2、用于处理器对之间通信的函数；
3、执行进程组间通信操作的函数；
4、创建任意数据类型的函数。
第1类函数由以下函数组成：开启通信、标识所使用的处理器的数量、创建子处理器组、以及标识程序的一个特定实例在哪个处理器上运行。
第2类函数被称为点对点通信操作，由不同类型的发送接收操作组成。
第3类函数为收集操作，提供进程组间的同步或特定类型的明确定义的通信操作，并执行通信／计算操作。
MPI系统
除各厂商提供的MPI系统外，一些高校、科研部门也在开发免费的通用MPI系统，其中比较著名的有：
1、MPICH
2、LAM MPI
它们均提供源代码，并支持目前绝大部分并行计算机系统（包括微机和工作站机群）。事实上许多厂商提供的MPI系统是在MPICH的基础上经过针对特定硬件优化形成的。
MPI标准的第一个版本MPI 1.0于1994年公布，最新标准为2.0版，于1998年公布。
一个MPI系统通常由一组库、头文件和相应的运行、调试环境构成。MPI并行程序通过调用MPI库中的函数来完成消息传递，编译时与MPI库链接。而MPI系统提供的运行环境则负责一个MPI并行程序的启动和退出，并提供适当的并行程序调试、跟踪方面的支持。
MPICH是目前使用最广泛的免费MPI系统，它支持几乎所有Linux/Unix以及Windows 9x、NT、2000和XP系统。利用MPICH既可以在单台微机或工作站上建立MPI程序的调试环境，使用多个进程模拟运行计算环境。事实上，它是运行在目前大部分机群系统上的主要并行环境。
在Ubuntu的软件中心搜索mpich，可以找到“Development files for MPICH2 （libmpich2-dev）”，安装它可以得到C、C++、和Fortran程序的mpi编译器，即mpicc、mpicxx、mpif77和mpif90。
第一个程序
#include <stdio.h>
#include <mpi.h>
void main(int argc, char *argv[]) {
int err;
err = MPI_Init(&argc, &argv);
printf("Hello world!\n");
err = MPI_Finalize();
}
使用命令mpicc first_program.c可以得到可执行文件a.out。
可以看到MPI的函数／子例程的名字都以MPI_开头。同时注意到头文件（mpi.h或mpif.h）包含了MPI的函数原型以及定义。MPI函数会返回一个错误码来表明是否有错误发生。
MPICH系统使用ch_p4（CHannel_Portable Programs for Parallel Processors）作为底层通信支持。基于ch_p4的MPICH可以像普通UNIX可执行文件一样直接执行，但默认情况下它只启动一个进程。当需要启动多个进程时，有两个方法来控制启动的进程数目，第一个方法是使用选项-p4pg，第二个方法是利用MPICH提供的一些脚本文件，如mpirun。在单机情况下，最方便的是用命令mpirun来运行MPICH程序。
mpirun最简单、最常用的形式为：
mpirun [-np 进程数] 程序名 [命令行参数]
方括号中为可选参数。
例如：
mpi ./a.out
输出
Hello world!
而mpirun -np 4 ./a.out
输出
Hello world!
Hello world!
Hello world!
Hello world!
点对点通信与消息
MPI里基本的通信是“点对点”通信。也就是两个处理器之间的直接通信，一方发送而另一方接收。
MPI里的点对点通信是双方参与的，也就是说同时需要显式的发送和显式的接收。在没有两个进程同时参与的情况下，数据不能传输。
在通常的发送和接收里，进程间传递由一些块数据组成的消息。一个消息由指明源进程和目标进程的信封和包含要发送的真实数据的主体组成。
MPI使用三部分信息来灵活地描述消息主体：
1、缓冲：内存的起始地址，存储要发送的消息或接收到的消息；
2、数据类型：最简单的例子是基本类型float、int等。更高级的应用里可以是基于基本类型的用户定义类型，类似于C的结构体，但数据可以放置在内存的任何地方，而不必是连续的内存地址。
3、计数器：要发送的数据类型的项数。
注意MPI标准化了基本类型的名称。这意味着我们不必担心异构环境下机器表示的区别。
通信模式和竞争临界区
MPI提供了很大的灵活性来指明消息如何发送。有多种定义了传送消息的过程的通信模式，以及决定通信事件何时结束的一堆临界区。例如：同步发送被定义为只当目的地承认接收到消息时才完成。缓冲发送则在数据拷贝到一个（本地）缓冲区时则完成，而不保证消息到达目的地。在所有的情况下，发送的完成都暗示着可以安全覆盖原有数据的内存区域。
有四种可用的发送通信模式：
1、标准（Standard）；
2、同步（Synchronous）；
3、缓冲的（Buffered）；
4、预备的（Ready）。
对于接收方，只有一种通信模式。当数据真正到达并可用时，接收才算完成。
阻塞与非阻塞通信
阻塞发送／接收直到操作完成才从函数返回。这保证了调用进程继续执行时相关的竞争临界条件已经得到满足。
非阻塞发送／接收立即返回，而不保证竞争条件是否满足。这样的好处是进程可以在后台进行通信，同时还能做其它事情。
集体通信（Collective Communications）
除了点对点通信，MPI还有执行集体通信的函数。它们允许更大的进程组以不同的方式通信，比如一对多或多对一。
相比与点对点通信，使用集体通信函数的好处有：
1、出错的概率大大降低。一行调用集体通信函数的代码，等价于多行点对点通信的调用代码。
2、源代码可读性更高，因而简化了调试和维护。
3、集体通信的优化形式经常比等价的点对点通信更快。
集体通信的例子包括广播操作、收集与散播操作、以及收缩操作。
广播操作（Broadcast Operation）
最简单的集体操作类型。单个进程把一些数据的拷贝发送给一个组的所有其它进程。多个接收进程都收到相同数据。
收集与散播操作（Gather and Scatter Operations）
可能是最重要的收集操作类型。把一个进程的数据分发到一组进程，或反之。MPI提供了两种收集与散播操作，即数据均匀或不均匀地跨进程分发。
在散播操作中，所有的数据（某种类型的数组）初始由单个进程收集，之后数据的各个片段被分发到不同的进程上。这些数据片段可能不是均匀分割的。收集操作是散播操作的逆操作：把分布在多个进程上的数据片段以恰当的顺序聚集到单个进程上。
收缩操作（Reduction Operations）
该操作里，单个进程（根进程）从某个组里的其它进程收集数据，并把它们合并成单个数据项。例如，使用收缩操作来求一个数组分布到各个进程上的元素的和。其它的例子还有求最大值、最小值、各种逻辑或位运算等等。
第三章 MPI程序结构
一般MPI程序
所有的MPI程序有以下通用的结构：
1、包含MPI头文件；
2、变量声明；
3、初始化MPI环境；
4、计算以及MPI通信调用；
5、关闭MPI通信。
MPI头文件包含MPI描述的定义以及函数原型。
之后是变量声明，每个进程调用一个MPI例程来初始化消息传递环境。所有的MPI通信例程的调用必须在初始化之后。
最后在程序结束前，每个进程都必须调用一个例程来终止MPI。在终止例如调用后不能用MPI例程被调用。注意任何进程在执行时不遵循这个约定的话，程序会表现为挂起。
MPI头文件
包含MPI函数／子例程的原型、宏定义、特殊常量、MPI使用的数据类型。C语言中使用#include <mpi,h>来包含该头文件。
MPI命名规范
所有MPI项（例程、常量、类型等）都由MPI_开头来避免冲突。C语言里函数名以大写开头，其余为小写，比如MPI_Init。MPI常量均为大写，例如MPI_COMM_WORLD。特殊定义的类型对应于许多MPI项，类型名和函数命名一样，例如：MPI_Comm对应于一个MPI类型communicator。
MPI例程和返回值
在C里MPI例程被实现为函数。通常一个错误码会返回，用于测试例程是否成功。例如：
int err;
err = MPI_Init(&argc, &argv);
MPI_SUCCESS表示例程成功运行：
if (err == MPI_SUCCESS) {
...
}
MPI句柄
MPI定义并维护与通信相关的它自己的内部数据结构。你通过句柄引用这些数据结构。句柄通过各种MPI调用返回，并可作为其它MPI调用的参数。
在C语言里，句柄是指向特定数据类型的指针。数组以0开始索引。
MPI 数据类型
MIP提供了它自己的引用数据类型，对应于C的各种基本数据类型。变量通常声明为C类型，MPI类型名用于MPI例程的参数。
MPI隐藏了数据类型表示的细节，比如浮点数的表示。这是实现考虑的事情。
MIP允许异构环境下表示的自动转换。
作为一个通用规则，接收的MPI数据类型必须与发送时指定的MPI数据类型匹配。
此外，MPI允许基于基本类型构建任意数据类型。
C语言的基本MPI数据类型
| MPI数据类型 | C类型 |
|---|---|
| MPI_CHAR | signed char |
| MPI_SHORT | signed short int |
| MPI_INT | signed int |
| MPI_LONG | signed long int |
| MPI_UNSIGNED_CHAR | unsigned char |
| MPI_UNSIGNED_SHORT | unsigned short int |
| MPI_UNSIGNED | unsigned int |
| MPI_UNSIGNED_LONG | unsigned long int |
| MPI_FLOAT | float |
| MPI_DOUBLE | double |
| MPI_LONG_DOUBLE | long double |
| MPI_BYTE | (none) |
| MPI_PACKED | (none) |
C语言的特殊MPI数据类型
例如：
1、MPI_Comm：通信者；
2、MPI_Status：MPI调用的状态信息；
3、MPI_Datatype
这些数据类型可以用于变量声明，例如：
MPI_Comm some_comm;
初始化MPI
任何MPI程序里的第一个MPI例程调用必须是初始化例程MPI_Init。它建立MPI环境。出错时会返回一个错误码。它只能被调用一次。
int err;
err = MPI_Init(&argc, &argv);
通信者（Communicators）
表示可以和另一个进程通信的一组进程的句柄。
对于所有点对点通信和收集操作，都需要通信者名：
1、发送和接收调用里指明的通信者必须同意这次通信发生；
2、只当进程共享同一个通信者时，进程才可以通信。
可以有许多通信者，且某个进程可以是许多不同的通信者里的一个成员。在每个通信者里，进程被连续编号（以0开始）。这个标识号作为通信者里的进程的秩（rank）：
1、秩也被用于指明发送和接收调用里的源和目标。
2、如果进程属于多个通信者，它的各个秩可以不同。
MPI自动提供一个基本的通信者MPI_COMM_WORLD。这由所有的进程组成。使用MPI_COMM_WORLD可以让每个进程和任何其它进程通信。你可以定义额外的通信者，包含可用进程的子集。
得到通信者的信息：秩
MPI_Comm_rank用于确定通信者里某个进程的秩。
1、秩是连续的，且从0开始。
2、在不同的通信者里，某个进程可能有不同的秩。
C函数原型：
int MPI_Comm_rank(MPI_Comm comm, int *rank);
参数comm是通信者，你可以使用MPI_COMM_WORLD，也可以使用自己定义的（MPI_Comm some_comm;）。
得到通信者的信息：尺寸
MPI_Comm_size用于获得通信者里的进程数。
C函数原型：
int MPI_Comm_size(MPI_Comm comm, int *size);
1、参数comm为通信者；
2、参数size是返回的整型变量的地址。
终止MPI
MPI_Finalize：
1、清除所有MPI数据结构，取消未完成的操作，等等。
2、必须在所有进程里调用。如果任何进程不遵守这个规则，它将表现为挂起。
一旦MPI_Finalize被调用，（包括MPI_Init在内的）所有其它MPI例程都不能被调用。
例：
int err;
err = MPI_Finalize();
样例程序
#include <stdio.h>
#include <mpi.h>
void main(int argc, char *argv[]) {
int myrank, size;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
printf("Processor %d of %d: Hello World!\n", myrank, size);
MPI_Finalize();
}
上面的代码使用的预定义的通信者MPI_COMM_WORLD；且没有测试例程的错误状态。
编译：
mpicc rank_size.c -o rank_size
运行：
$ mpirun -np 4 ./rank_size
Processor 0 of 4: Hello World!
Processor 3 of 4: Hello World!
Processor 1 of 4: Hello World!
Processor 2 of 4: Hello World!
第四章 点对点通信
点对点通信是MPI库提供的基础通信设施。
点对点通信在概念上很简单：一个进程发送消息，而一个进程接收。但现实中它没那么简单。例如，一个进程可能有许多等待接收的消息。这种情况下，一个关键的问题是MPI和接收进程如何决定要接收什么消息。
另一个问题是发送和接收例程是初始化通信操作并立即返回，还是在返回前等待初始化通信操作完成。在两种情况下底下的通信操作都是相同的，但是编程接口确很不相同。
基础
源和目标：点对点通信设施是双方的，需要双方进程的共同主动参与。一个进程（源）发送，另一个进程（目标）接收。
通常，源和目标进标异步操作。哪怕是单个消息的发送和接收通常也不是同步的。源进程发送消息后，可能要很久之后目标进程才会接收它。或者目标进程可能在消息还未发出时就做好准备接收它。
因为发送和接收通常不是同步的，所以进程可能会有一个或多个已经发送但没有被接收的消息。这些发送了但没被接收的消息被称为待处理的（pending）消息。MPI一个很重要的特性是待处理的消息不是由一个简单的FIFO队列维护，相反，每个待处理消息都有几个属性，同时目标进程（接收进程）可以使用这些属性来决定接收哪些消息。
消息：由信封（envelop）和消息主体（message body）两部分组成。
信封和包装信件的纸质信封相似。它包含目标地址、回信地址、以及任何其它传送和分发信件所需的信息，比如服务类型（如空邮）。
MPI消息的信封有4部分：
1、源：发送进程；
2、目标：接收进程；
3、通信者：指明源和目标同时所属的一个进程组；
4、标签（tag）：用于分类消息。
标签域是必需的，但它的使用交由程序决定。一对通信进程可以使用标签的值来区分消息的类型。例如，一个标签值可以用于包含数据的消息，而另一个标签用于包含状态信息的消息。
消息主体由三部分组成：
1、缓冲区：消息数据；
2、数据类型：消息数据的类型；
3、计数器：缓冲区包含的具有该数据类型的项数。
可以把缓冲区想像成一个数组，维度由计数器决定，数组元素的类型由数据类型给出。使用数据类型和计数器，而不是字节和字节数，可以平滑地处理结构化数据和不连续的数据。同时还允许异构主机间的透明通信支持。
发送和接收消息：发送消息很直接。源（发送者的ID）隐式地被确定，但消息的其它部分（信封和主体）由发送进程显式地给出。
接收消息没有这么简单，一个进程可能有多个待处理的消息。
要接收一个消息，一个进程指明一个消息信封，MPI把它和待处理消息比对。如果匹配，则接收消息。否则，一直等到匹配的消息发送，才结束接收操作。
此外，接收消息的进程必须提供存储，消息的主体可以拷贝入内。接收进程必须小心，要提供足够的存储来存放整个消息在。
阻塞发送和接收
MPI_Send和MPI_Recv两个函数是MPI里基本的点对点通信例程。两个函数都会阻塞调用进程，直到通信操作完成。阻塞可能会造成死锁。
发送消息：MPI_Send
函数原型为：
int MPI_Send(void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm);
所有的参数都是输入参数，前三个是消息主体，后三个是消息信封（源进程隐式定义）。函数返回一个错误码。
接收消息：MPI_Recv
函数原型：
int MPI_Recv(void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Status *status);
前三个参数是消息主体，后三个参数是信封（目标进程隐式定义）。source和tag都可以使用通配符，表示任何进程和任何标签，否则只接收特定发送进程的含特定标签的消息。通信者不能使用通配符。如果收到的消息比接收进程准备接受的数据大时，会出错。
最后一个参数是关于接收的消息的信息。当source或tag使用通配符时，可以从status里获取这些信息。同时还能得到真正接收到的数据的数量。
buf和status是输出参数，其余都是输入参数。
返回值是一个错误码。
示例代码：
#include <stdio.h>
#include <mpi.h>
void main(int argc, char **argv)
{
int myrank;
MPI_Status status;
double a[100];
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank == 0)
MPI_Send(a, 100, MPI_DOUBLE, 1, 17, MPI_COMM_WORLD);
else if (myrank == 1)
MPI_Recv(a, 100, MPI_DOUBLE, 0, 17, MPI_COMM_WORLD, &status);
MPI_Finalize();
}
运行时的行为
根据模型，使用MPI_Send发送消息时，以下事情之一可能会发生：
1、消息被拷贝到MPI内部缓冲，并稍后在后台传送到目标；或者
2、消息原封不动地放在程序的变量里，直到目标准备好接收时，消息才被传送到目标。
第一个选项允许发送进程在拷贝完成时着手做其它事情。第二个选项最小化了拷贝和内存使用，但倒致发送进程的额外延迟。这个延迟可能会很显著。
令人惊奇的是，选项1里，在任何非本地动作发生甚至开始之前，也就是说任何与发送消息相关的事情发生之间，MPI_Send调用可能就返回了。选项2隐含了发送者和接收者之间的同步。
总结起来，根上面的模型草案，当使用MPI_Send发送消息时，消息可能立即被缓冲并稍后异步地分发出去，或者发送与接收进程同步。
阻塞与完成
MPI_Send和MPI_Recv都会阻塞调用进程。两者都在所调用的通信操作完成里返回。
MPI_Recv完成的意思很简单直观－－一个匹配的消息已经到达，消息的数据被拷贝到调用的输出参数里。换句话说，传递给MIP_Recv的变量包含了一个消息并已经可以使用了。
对于MPI_Send，完成的意思简单但不直观。当调用指定的消息已经交给MPI时MPI_Send调用完成。换句话说，传递给MPI_Send的变量现在可以被覆写并重用。前面已经提到有两个选项。
如果传递给MPI_Send的消息比MIP可用的内部缓冲大，那么缓冲不能被使用。在这种情况下，发送进程必须阻塞，直到目标进程开始接收这个消息，或直到有更多可用的缓冲。一般说来，被拷贝进MPI内部缓冲的消息会占用缓冲空间，直到目标进程开始接收这个消息。
注意MPI_Recv调用在匹配的待处理的消息的信封（源、标签、通信者）后会接收消息。对于正确的执行来说数据类型匹配也是需要的，但MPI不会检查它。相反，程序员负责数据类型的匹配。
死锁
当两个或多个进程阻塞并都等待另一个进程的执行时，死锁发生。由于都依赖于对方先开始执行，所以没有一个进程可以继续执行。
下面的代码会造成死锁：
if (myrank == 0) {
MPI_Recv(b, 100, MPI_DOUBLE, 1, 19, MPI_COMM_WORLD, &status);
MPI_Send(a, 100, MPI_DOUBLE, 1, 17, MPI_COMM_WORLD);
}
else if (myrank == 1) {
MPI_Recv(a, 100, MPI_DOUBLE, 0, 17, MPI_COMM_WORLD, &status);
MPI_Send(a, 100, MPI_DOUBLE, 0, 19, MPI_COMM_WORLD);
}
死锁的原因是两个进程都先接收再发送。
通常避免死锁需要在程序中小心地组织通信。程序员应该能够解释程序为何有（或没有）死锁。
下面的代码解决了上面代码的死锁问题：
if (myrank == 0) {
MPI_Recv(b, 100, MPI_DOUBLE, 1, 19, MPI_COMM_WORLD, &status);
MPI_Send(a, 100, MPI_DOUBLE, 1, 17, MPI_COMM_WORLD);
}
else if (myrank == 1) {
MPI_Send(a, 100, MPI_DOUBLE, 0, 19, MPI_COMM_WORLD);
MPI_Recv(a, 100, MPI_DOUBLE, 0, 17, MPI_COMM_WORLD, &status);
}
进程0先接收后发送，而进程1先发送再接收，从而避免死锁。下面的代码略有改动：
if (myrank == 0) {
MPI_Send(a, 100, MPI_DOUBLE, 1, 17, MPI_COMM_WORLD);
MPI_Recv(b, 100, MPI_DOUBLE, 1, 19, MPI_COMM_WORLD, &status);
}
else if (myrank == 1) {
MPI_Send(a, 100, MPI_DOUBLE, 0, 19, MPI_COMM_WORLD);
MPI_Recv(a, 100, MPI_DOUBLE, 0, 17, MPI_COMM_WORLD, &status);
}
两个进程都先发送后接收。当MPI的缓冲可用时，死锁不会出现。但当消息数量增多后，程序迟早会发生死锁。通常，依赖于MPI内部缓冲来避免死锁会使得程序降低可移植性和扩展性。写程序的最好方式是不论MPI内部缓冲如何都能保证运行完成。
非阻塞发送和接收
MPI提供了另一种方式来执行发送和接收操作。我们可以分离发送和接收操作的初始化和它们的完成。这通过两个分离的MPI调用来完成。第一个调用初始化操作，第二个调用完成它。在这两个操作之间，程序可以做任何其它事情。
两个分离的调用的底层的通信操作和单个调用是一样的，但是接口不同。
投递、完成、和请求句柄
每个通信操作的发送和接收的非阻塞的接口需要两个调用：一个初始化操作，第二个完成它。初始化一个发送调用被称为投递一个发送请求。初始化一个接收操作被称为投递一个接收请求。
一旦一个发送或接收操作被投递，MPI提供了两种不同的方式来完成它。一个进程可以测试操作是否完成，而不需要阻塞在完成操作上。另一种方式是，它可以等待操作完成。
在调用一个非阻塞例程投递一个发送或接收操作后，投递进程需要某种方式来引用被投递的操作。MPI使用请求句柄来达到这个目的。非阻塞发送和接收例程都返回请求句柄，它可用来标识被投递的操作。
总而言之，发送和接收操作可以通过非阻塞例程被投递（初始化）。投递操作由请求句柄标识。通过请求句柄，进程可以检查已投递的操作的状态或等待它们的完成。
非阻塞地投递发送请求
MPI_Isend可以投递一个发送请求而不会阻塞在等待完成上。
函数原型：
int MPI_Isend(void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm, MPI_Request *request);
参数与MPI_Send相似，但多了request的输出参数。参数被传递给MPI_Isend后不能被读写，直到发送操作完成。
返回值为错误码。
非阻塞地投递接收请求
MPI_Irecv可以投递一个接收请求而不会阻塞在等待完成上。
函数原型：
int MPI_Irecv(void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Request *request);
参数与MPI_Recv相似，但多了request的输出参数。参数被传递给MPI_Irecv后不能被读写，直到接收操作完成。
返回值为错误码。
完成：等待或检测
投递的发送和接收必须完成。如果发送和接收操作由一个非阻塞例程投递，那么它的完成状态可以通过调用一组完成例程来检查。MPI同时提供了阻塞和非阻塞完成例程。阻塞例程为MPI_Wait以及它的变体。非阻塞例程为MPI_Test以及它的变体。
等待：
MPI_Wait的函数原型：
int MPI_Wait(MPI_Request *request, MPI_Status *status);
reuest参数为已投递的发送和接收操作的请求句柄。status为输出参数，接收操作时包含接收到的消息的信息（源、标签、真实接收的数据数量等），发送操作时可能包含一个错误码（表示发送是否出错，而MPI_Wait本身返回的错误码不同）。
返回一个错误码。
检测：
MPI_Test的函数原型：
int MPI_Test(MPI_Request *request, int *flag, MPI_Status *status);
request和status参数和MPI_Wait基本相同。flag为输出参数，如果发送或接收完成时值为true。当flag值为false时status的值没有定义。
非阻塞发送和接收的优缺点：
非阻塞例程可以更容易地写出无死锁的程序。
在延迟很大的系统上，很早地投递接收操作经常是高效简单的方法，来掩盖通信的开销。在物理分布的主机群（比如工作站簇）上延迟会很大，而共享内存的多处理器会相对较小。一般来说掩盖通信的开销需要在算法和代码结构上很小心。
从坏的方面来说，非阻塞发送和接收例程会增加代码复杂性，这让代码更难调试和维护。
示例代码：
#include <mpi.h>
void main(int argc, char **argv)
{
int myrank;
MPI_Request request;
MPI_Status status;
double a[100], b[100];
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank == 0) {
MPI_Irecv(b, 100, MPI_DOUBLE, 1, 19, MPI_COMM_WORLD, &request);
MPI_Send(a, 100, MPI_DOUBLE, 1, 17, MPI_COMM_WORLD);
MPI_Wait(&request, &status);
} else if (myrank == 1) {
MPI_Irecv(b, 100, MPI_DOUBLE, 0, 17, MPI_COMM_WORLD, &request);
MPI_Send(a, 100, MPI_DOUBLE, 0, 19, MPI_COMM_WORLD);
MPI_Wait(&request, &status);
}
MPI_Finalize();
}
上面的代码没有死锁。
发送模式
MPI提供了以下四种发送模式：
1、标准模式发送；
2、同步模式发送；
3、预准备模式发送；
4、缓冲模式发送。
标准模式是最广泛使用的。
接收模式只有一种。不论发送模式如何，MPI_Recv和MPI_Irecv的调用是相同的。
对于四种发送模式，阻塞和非阻塞调用都可用。
标准模式发送
标准模式是MPI的通用发送模式。其它三个模式在特殊的条件下有用。
如之前所述，标准模式下，消息或拷贝到MPI内部缓冲里并稍后发送，或源和目标进程同步。MPI实现可以自由选择缓冲或同步，或视情况而定，比如消息大小，可用资源，等。
标准模式发送的好处是MPI可以基于情况选择缓冲和同步。通常MPI在进行权衡方面，特别在涉及底层资源和MPI内部资源的时候，会做得更好。
同步模式发送要求MPI同步发送和接收进程。当同步模式发送操作完成时，发送进程可以假设接收进程已经开始接收消息了。目标进程不需要完成接收，但是必须已经开始接收了。
预准备模式需要在发送之前，目标进程已经投递了一个匹配的接收。如果目标没有投递接收，则结果没有定义。你需要保证这个条件得到满足。在某些情况下，不需要额外的工作就可以知道目标进程的状态信息。当知道接收已经被投递时，MPI可以通过在内部使用更短的协议来降低通信开销。
缓冲模式发送要求MPI使用缓冲。这种方式的不足是你必须负责管理缓冲。在任何时候，可用缓冲空间不足以完成调用时，结果没有定义。函数MPI_Buffer_attach和MPI_Buffer_detach为MPI制造可用的缓冲。
各模式对应的函数
| 发送模式 | 阻塞函数 | 非阻塞函数 |
|---|---|---|
| 标准 | MPI_Send | MPI_Isend |
| 同步 | MPI_Ssend | MPI_Issend |
| 预准备 | MPI_Rsend | MPI_Irsend |
| 缓冲 | MPI_Bsend | MPI_Ibsend |
其它模式的函数参数（阻塞与非阻塞）与标准模式的函数参数相同。
第五章 衍生数据类型和相关特性
我们已经知道如何发送与接收由单个MPI内置类型的连续存储在内存的数据组成的消息。但数据很少会这样规则，你很可能需要传送由程序定义的混合类型的数据集合，或分散在内存的数据。
最简单的方式－－多个消息
概念上讲，最简单的方式是标识你数据中最大的属于同构类型的并连续存储在内存里的块，然后把这些块作为单独的消息发送。
例如，一个存储在二维数组里的矩阵，你想要向另一个进程发送它的一个矩形子矩阵。在C语言中，数组的行是连续存储在内存中的。对于m行n列，起始位置为(k, l)的子矩阵，我们可以：
for (i = 0, i < m; ++i) {
MPI_Send(&a[k+i][l], n, MPI_DOUBLE, dest, tag, MPI_COMM_WORLD);
}
如果接收进程不知道N, M, K, 或l的值，那么它们可以通过独立的消息发送。
1、这种方式的最大的好处就是你不需要学习任何新东西就可以应用它。
2、最大的坏处，就是它的开销。发送和接收消息会有固定的开销，如果一个长消息被拆分为多个短消息，那么程序性能会大大降低。
如果相关的代码执行的频度很低，且额外的消息数量很少，那么这些额外的开销就可以忽略不计。但对多数程序而言，限制自己使用这个方式不太带来任何好处。
另一个简单的方式－－把数据拷贝到缓冲
把分散的数据拷贝到连续的缓冲里：
p = &buffer;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
*(p++) = a[i][j];
}
}
MPI_Send(p, n*m, MPI_DOUBLE, dest, tag, MPI_COMM_WORLD);
这种方式消除了前面一种方式的过度消息，但占用了额外的内存和CPU时间来执行到缓冲的拷贝。这种方式的很明显的限制是它一次仍只能处理一种类型。
一种诱人却错误的扩展缓冲的方式
很多时候可以把一种类型的值编码为另一种类型的值。在子矩阵例子里，我们可以把m、n、k、l的值转换成浮点数，以便把它们包含在缓冲里。然而，这样的转换通常比简单的拷贝占用更多的CPU时间。在多数情况下，结果会占用更多的内存。
这时，你可能想用编程花招（比如转型指针类型）来把某个类型的值以位存储的方式放在另一种类型声明的缓冲里。这种方式非常危险。如果你写一个测试程序来试验的话，它很可能会“工作”。但是，如果你广泛使用这种方式，特别在多种不同的环境下运行程序时，最终会不可避免的出错。如果幸运的话，它的错误会很引人注目。但如果不幸运的话，你只是得到不正确的结果，而没有意识到错误的存在。
这里最基本的问题在于MPI传送的是值，而不是“位”。只要你使用一堆以相同方式表示值的处理器，那么MPI会优化传输，简单地用“位”来传输，使得你以为它工作了。如果通信中有处理器使用不同的方式来表示部分或全部的值时，MPI把消息里的值转换成标准的中间格式，传递这些中间格式的位，然后在另一个处理器上把中间格式转换为值。额外的转换保证了接收到的值和发送的值相同。然而，接收处理器的值可能和原始类型的值不再有相同的位表示。
缓冲正确的方式－－打包你的麻烦
MPI_Pack例程允许你用“正确的方式”填充缓冲。MPI_Pack有描述你正填充的缓冲的参数，还有最简单方式里提供给MPI_Send的参数。MPI_Pack把数据拷贝到缓冲里，并在必要时把它转换成标准中间格式。在所有要发送的数据都通过MPI_Pack放入缓冲后，你可以发送这个缓冲（指明类型为MPI_PACKED），而后便不会有转换执行。
MPI_Pack函数的原型：
int MPI_Pack(void *inbuf, int incount, MPI_Datatype datatype, void *outbuf, int outcount, int *position, MPI_Comm comm);
之前的子矩阵例子变为：
int count = 0;
for (i = 0; i < m; ++i) {
MPI_Pack(&A[k+i][l], n, MPI_DOUBLE, buffer, bufsize, &count, MPI_COMM_WORLD);
}
MPI_Send(buffer, count, MPI_PACKED, dest, tag, MPI_COMM_WORLD);
count被初始化为0，在每次打包后它都会增加打包的尺寸。如此便可以把分散的数据打包到连续的缓冲里。
在接收方，你可以用相似的方式指定类型MPI_PACKED来接收一个缓冲而不转换。接着使用MPI_Unpack（与MPI_Recv的关系和MPI_Pack与MPI_Send的关系相同）来翻译并把数据从缓冲拷贝到你真正需要它的地方。
MPI_Unpack的函数原型：
int MPI_Unpack(void *inbuf, int insize, int *position,void *outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm)
由于翻译，数据在缓冲里占用和本地不同的空间量。你可以通过调用MPI_Pack_size例程来计算你想放入缓冲的不同类型的数据所需的缓冲空间，从而保证你的缓冲有足够的大。
消息内容里没有任何东西指明它是或不是由MPI_Pack创建的。如果打包的数据都使用相同的数据类型，那么接收方可以直接接收消息而不必用MPI_PACKED接受再用MPI_Unpack解码。相反，使用原始内置类型发送的数据，在接收时也可以用MPI_PACKED接收再用MPI_Unpacked解码。
MPI_Pack和MPI_Unpack带来很大的灵活性。除了支持任意数据类型混合的数据，它的增量构建和消息解释允许消息的早期数据值来影响稍后在相同消息里出现的数据的类型、尺寸和目标。这种灵活性的主要开销在于缓冲所使用的内存和拷贝到缓冲或从缓冲拷贝的CPU时间。如果构建一条消息需要大量的MPI_Pack调用（或解读一条消息需要大量的MPI_Unpack调用），那么额外的调用开销也是很可观的。
“随意（On-the-fly）”打包－－MPI衍生类型
你可以把MPI衍生类型设施看作把MPI打包和解包作为发送和接收操作的一部分的一种方法。打包和解包可以直接在MPI内部缓冲里完成，从而不需要：
1、用于打包和解包的显式的中间缓冲；
2、中间缓冲和通信缓冲之间的拷贝。
因此，使用MPI衍生类型而不是显式的打包和解包可以让你的程序更高效。
在发送时，你可以构建一个列表包含需要打包的数据的地址，而不是一个已经打包好的数据的列表。这个列表用于定义一个类型和发送时使用的类型。改写子矩阵的例子：
for (i = 0; i < m; ++i) {
len_a[i] = n;
MPI_Address(A[k+i][l], loc_a[i]);
typ_a[i] = MPI_DOUBLE;
}
MPI_Type_struct(m, len_a, loc_a, typ_a, MY_MPI_TYPE);
MPI_Type_commit(MY_MPI_TYPE);
MPI_Send(MPI_BOTTOM, 1, MY_MPI_TYPE, dest, tag, MPI_COMM_WORLD);
MPI_Type_free(MY_MPI_TYPE);
三个数组len_a、loc_a、和typ_a用于记录数据的长度、位置、和数据类型。MPI_Address用于得到和魔地址MPI_BOTTOM相对的数据地址。当三个数组都填满后，MPI_Type_struct用来把消息转换成一个新的MPI类型，并存储在变量MY_MPI_TYPE里。MPI_Type_commit用于告诉MPI使用MY_MPI_TYPE来发送或接收。MY_MPI_TYPE然后在真实的发送操作里作为一个真实的类型使用。
特殊固定地址MPI_BOTTOM是要发送的数据的名义上的地址。这是因为MPI衍生类型规范里的地址总是作为相对地址来解释，而从MPI_Address获得的地址的值是相对于MPI_BOTTOM的。
最终，MPI_Type_free用于告诉MPI你不会再使用这个特殊的类型，所以用于表示这个类型的资源可以被释放或重用。
在接收时，你必须以相似的方式构建一个地址列表来接收消息里的数据，把这些地址转换成被提交的(committed)类型，然后在接收操作里使用这个类型。
注意：
1、作为打包和解包操作的直接替代器，MPI衍生类型操作通常更高效，但更麻烦。这是因为需要显式地创建、提交和释放MPI类型指示器。
2、如果有人对在打包好的缓冲发送时才会存在的数据进行打包（例如后续打包的值被计算到相同的变量里），那么衍生类型就丧失了它的效率优势。这里因为在发送前，你必须建立其它形式的缓冲来保存这些值。
3、相似地，如果数据要解包的地址有交集（例如消息的后续值被处理并放入到相同的变量里），那么衍生类型丧失了它的效率优势。这是因为你需要把这些值缓冲到其它地方，直到它们可以被处理。如果接收数据的地址不能提前确定，则缓冲也同样需要。
4、在消息的前面部分的值决定消息的后面部分的结构的情况下，衍生类型操作不能用来替代解包操作。在这些情况下，显式的类型缓冲将不能工作，你需要MPI_PACKED缓冲的零碎解包的灵活性。
将MPI衍生类型用于用户定义的类型
创建MPI衍生类型，然后在释放它前只使用一次，显得有些累赘。创建MPI衍生类型来描述重复访问的样式，并在之后重用这些类型。典型的例子就是用MPI衍生类型描述用户定义数据类型相关的访问。这种技术称为映射。
例如：
struct SparseElt {
int location[2];
double value;
};
struct SparseElt anElement;
int len_a[2];
MPI_Aint loc_a[2];
MPI_Datatype typ_a[2];
MPI_Aint baseaddress;
MPI_Datatype MPI_SparseElt;
MPI_Address(&anElement, &baseaddress);
len_a[0] = 2; MPI_Address(&anElement.location, &loc_a[0]);
loc_a[0] -= baseaddress; typ_a[0] = MPI_INT;
len_a[1] = 1; MPI_Address(&anElement.value, &loc_a[1]);
loc_a[1] -= baseaddress; typ_a[1] = MPI_DOUBLE;
MPI_Type_struct(2, len_a, loc_a, typ_a, &MPI_SparseElt);
MPI_Type_commit(&MPI_SparseElt);
和早先的例子一样，我们构建三个数组包含要传输的组件的长度、位置、和类型。不同的是，我们把组件的地址减去整个变量的地址，所以地址是相对于变量而不是MPI_BOTTOM的。这允许我们在程序的任何地方使用类型指示器MPI_SparseElt来描述一个SparseElt类型的变量。
一旦类型被创建并被提交，它可以在任何内置指示器使用的地方，而不仅仅在发送和接收操作里。特别地，还包含了用于定义另一个可能包含SparseElt组件的MPI衍生类型，或对SparseElt类型的变量执行打包和解包。
其它定义MPI衍生类型的方式
MPI_Type_struct是构建MPI衍生类型的最通用的方式，因为它允许每个组件的长度、地址、类型都独立指定。有更不通用的过程可以描述访问的普遍样式，主要是使用数组。这些是：
1、MPI_Type_contiguous
2、MPI_Type_vector
3、MPI_Type_hvector
4、MPI_Type_indexed
5、MPI_Type_hindexed
MPI_Type_contiguous是最简单的，描述了内存里的连续的值序列。例如：
MPI_Type_contiguous(2, MPI_DOUBLE, &MPI_2D_POINT);
MPI_Type_contiguous(3, MPI_DOUBLE, &MPI_3D_POINT);
MPI_Type_vecter描述了几个这样均匀存储的但在内存中不连续的序列。它的函数原型为：
int MPI_Type_vector(int count,int blocklength,int stride,MPI_Datatype old_type,MPI_Datatype *newtype_p);
count为块数，blocklength是每块的长度，stride是各个块的起始位置之间的间距。
可以用它来改写子矩阵的例子：
MPI_Type_vector(m, n, N, MPI_DOUBLE, &MY_MPI_TYPE);
MPI_Type_commit(MY_MPI_TYPE);
MPI_Send(A[k][l], 1, MY_MPI_TYPE, dest, tag, MPI_COMM_WORLD);
MPI_Type_free(MY_MPI_TYPE);
N是原矩阵A[M][N]的第二维的维度。m、n是子矩阵的维度。
MPI_Type_hvector和MPI_Type_vector相似，除了后续块之间的距离是由字节指定的而非元素。使用字节而非元素指定距离的最普遍的原因是感兴趣的元素和其它类型的元素散布在一起。例如，你有类型为SpaseElt的数组，你可以使用MPI_Type_hvector来描述value组件的“数组”。
MPI_Type_indexed描述了长度和内存占用都会改变的序列。因为这些序列的地址以元素衡量而非字节，所以它适合于指明单个数组的任意部分。
MPI_Type_hindexed和MPI_Type_indexed相似，除了地址由字节而非元素指定。它可以指明任意数组的任意部分，只要它们都有相同的类型。
消息匹配和不匹配
就像从消息内容里无从知道它是否由MPI_PACKED构建的一样，我们也无法知道在构建时是否使用了MPI衍生类型以及何种类型。唯一要紧的是发送方和接收方在消息的原始值序列的表示上达成共识。因此，使用MPI_PACK构建和发送的消息可以使用MPI衍生类型来接收，或者使用MPI衍生类型发送的消息可以用MPI_PACKED接收并用MPI_UNPACK分发。相似的，消息可以使用MPI衍生类型发送，并用另一种类型接收。
这导致了MPI衍生类型和它的原始类型之间显著区别。如果你使用和接收时使用的相同的MPI衍生类型来发送数据，那么消息需要包含整数个那种类型，而MPI_Get_count将用和原始数据一样的方式来工作。尽管如此，如果类型不同，你可能最后得到一个部分值。例如，如果发送进程发送4个MPI_3D_POINT的数组（或者说总共12个MPI_DOUBLE）而接收进程以MPI_2D_POINT数组的方式接收，MPI_Get_count将会报告有6个MPI_2D_PINT可以接收。如果5个MPI_3D_POINT被发送（15个MPI_DOUBLE），那么在接收方有7个半的MPI_2D_POINT，但是MPI_Get_count不能返回7.5。与其返回7或8，MPI_Get_count返回一个标志值MPI_UNDEFINED。如果你需要关于传送的尺寸的信息，那么你仍然要使用MPI_Get_element来知道有9个原始值被传送。
控制衍生类型的长度
几种在内存里连续的衍生类型的概念在传输任意数据序列的通常情况下可能会有问题。关于这个的MPI规则被设计为和你在映射MPI衍生类型到用户定义类型的通常情况下所期望的那样工作。
首先，MPI计算这个类型的低边界和高边界。默认情况下，更低的边界是首先出现在内存里的组件的起始位置，而高边界是最后出现在内存的组件的末尾（末尾可能包含了反映对齐和填充规则。低边界和高边界之间的距离称作它的长度（extent）。如果该类型的两个元素之间的距离和长度相同，则它们被视为在内存中连续。换句话说，如果第二个元素的低边界和第一个的高边界相同，那么它们连续。这种定义衍生类型长度的方法通常得到“正确”的结果。然而，有些情况也不一定。
1、MPI库可以只实现一组填充和对齐规则。如果你的编译器有选项控制这些规则，或编译器对不同的语言使用不同的规则，那么MPI可能不经意地使用“错误”的填充和对齐规则来计算高边界。
2、如果你的MPI衍生类型只映射用户定义类型的部分组件，那么MPI可能不知道真正的第一个和最后一个元素，因此低估了长度。
3、如果你的衍生类型的组件是任意的存储序列，那么默认的长度将会几乎没有任何用处。
在这些情况下，你可以通过在你的衍生类型定义里插入MPI_LB和MPI_UB类型的组件来控制类型的边界，从而控制类型的长度。这些组件的地址则被视为低边界和高边界，而无视其它组件的地址。一种最简单的解决方案是为你映射的类型的数组的低边界和高边界定基址，指明数组里第一个元素为类型的低边界，元素的第二个元素的地址为类型的高边界。
例如，你的程序里有数组X、Y、Z。有时候你想把X、Y、Z的前N个值发送到另一个进程。如果你以显式的方式，把X的前N个元素发送出去，继而是Y的前N个元素，最后是Z的前N个元素，那么接收进程将无从知道X的元素在何处终止，Y的元素从何处开始，直到它收到所有的值然后使用消息的长度来决定N的值。把N值放在消息的开头并不能解决这个问题，因为接收进程必须在接收消息的任何部分前定义它想把元素接收到哪里。这个问题的解决方案是重新排列消息里的这些值，首先发送第一个X、然后第一个Y、接着第一个Z，之后是第二个X、Y、Z，继而是第三个，等等。这种排列可以让接收进程在不提前知道总元素个数的情况下知道元素出自何处。
len_a[0] = 1;
MPI_Address(X[0], loc_a[0]);
typ_a[0] = MPI_DOUBLE;
len_a[1] = 1;
MPI_Address(Y[0], loc_a[1]);
typ_a[1] = MPI_DOUBLE;
len_a[2] = 1;
len_a[2] = 1;
MPI_Address(Z[0], loc_a[2]);
typ_a[2] = MPI_DOUBLE;
len_a[3] = 1;
MPI_Address(X[0], loc_a[3]));
typ_a[3] = MPI_LB;
len_a[4] = 1;
MPI_Address(X[1], loc_a[4]);
typ_a[4] = MPI_UB;
MPI_Type_struct(5, len_a, loc_a, typ_a, MY_TYPE);
MPI_Type_commit(MY_TYPE);
MPI_Send(MPI_BOTTOM, N, MY_TYPE, dest, tag, MPI_COMM_WORLD);
MPI_Type_free(MY_TYPE);
MY_TYPE的格式可以工作，因为X、Y、Z都是相同的类型，所以Y[1]相对于X[1]的地址和Y[0]想对于X[0]的地址相同。注意N只用来发送，而不在MY_TYPE的定义里，所以你可以只定义MY_TYPE一次而多次发送它，而不是每次发送时都重定义它然后释放它。
得到关于你的衍生类型的信息
一旦你定义了一个衍生类型，有几个工具调用可以给你提供该类型的信息。
1、MPI_Type_lb和MPI_Type_ub可以得到类型的低边界和高边界。
2、MPI_Type_extent可以提供类型的长度。在多数情况下，这是这个类型的一个值将占用的内存量。
3、MPI_Type_size可以提供消息里类型的尺寸。如果类型在内存中分散，那么这可能会比该类型的长度小很多。
第6章 集体通信
集体通信（collective communication）涉及了在多个进程间发送和接收数据。一般来说，数据在多个进程间的流动都可以通过MPI发送和接收例程来完成。然而，一些通信操作的序列非常普遍，导致MPI提供了一堆集合通信例程来处理它们。这些例程通过点对点通信构建起来。即使你可以构建自己的集合通信例程，然而这些“黑盒”例程隐藏了许多杂乱的细节，并经常为那个操作提供最高效的算法实现。
集体通信例如在一个组里的多个进程之间传送数据。要注意集体通信调用没有使用相关的发送／接收调用的标签机制。相反它们和程序执行的顺序关联。因此，用户必须保证所有的处理器执行相同的集合通信调用，并以相同的顺序执行它们。
集合通信例程支持所有进程或只是指定进程集之间的数据动作。通信者用来标识涉及的进程集合。
栅栏同步（Barrier Synchronization）
有些情况一些进程必须等待其它进程完成它们当前的指令后才可以继续执行。一个常见例子是根进程读取数据然后把这些数据发送给其它进程。其它进程必须等待I／O的完成和数据的移动。
MPI_Barrier例程会阻塞调用进程，直到所有组进程调用了这个函数。当MPI_Barrier返回时，所有进程都在这个栅栏上同步了。
MPI_Barrier由软件完成，在一些机器上可能造成显著的开销。通常，你应当只在需要的时候使用栅栏。
MPI_Barrier的函数原型：
int MPI_Barrier(MPI_Comm comm);
广播（Broadcast）
MPI_Bcast例程把根进程内存里的数据拷贝到通信者里的其它进程的相同内存地址里。它的函数原型为：
MPI_Bast(void *send_buffer, int send_count, MPI_Datatype send_type, int root_rank, MPI_COMM comm);
例：
send_count = 1;
root = 0;
MPI_Bcast(&a, &send_count, MPI_INT, root, comm);
缩减（Reduction）
MPI_Reduce例程可以：
1、从每个进程收集数据；
2、把这些数据缩减成单个的值（比如求和或最大值）；
3、把缩减后的值存储到根进程里。
它的函数原型为：
int MPI_Reduce(void *send_buffer, void *recv_buffer, int count, MPI_Datatype datatype, MPI_Op operation, int root_rank, MPI_Comm comm);
所有进程（包括根进程）的send_buffer中的值，缩减成为一个值后，放入根进程的recv_buffer里。send_buffer和recv_buffer的元素个数都为count。
例：
count = 1;
rank = 0;
MPI_Reduce(&a, &x, count, MPI_REAL, MPI_SUM, rank, MPI_COMM_WORLD);
MPI_Reduce的预定义的操作有：
| 操作 | 描述 |
|---|---|
| MPI_MAX | 最大值 |
| MPI_MIN | 最小值 |
| MPI_SUM | 求和 |
| MPI_PROD | 求积 |
| MPI_LAND | 逻辑与 |
| MPI_BAND | 位与 |
| MPI_LOR | 逻辑或 |
| MPI_BOR | 位或 |
| MPI_LXOR | 逻辑异或 |
| MPI_BXOR | 位异或 |
| MPI_MINLOC | 计算一个全局最小值和附到这个最小值上的索引－－可以用来决定包含最小值的进程的秩 |
| MPI_MAXLOC | 计算一个全局最大值和附到这个最大值上的索引－－可以用来决定包含最小值的进程的秩 |
收集（Gather）
有两个收集操作：MPI_Gather和MPI_Allgather。
MPI_Gather例程是一个多对一的通信。MPI_Gather有和对应的分散例程一样的参数。接收参数只对根进程有意义。
当MPI_Gather被调用时，每个进程（包括根进程）把它的发送缓冲的内容发送到根进程。根进程以秩顺序接收并存储它们。
收集操作也可以用一种方式完成：每个进程调用MPI_Send、根进程调用N次的MPI_Recv来接收所有的消息。
函数原型：
int MPI_Gather(void *send_buffer, int send_count, MPI_Datatype send_type, void *recv_buffer, int recv_count, MPI_Datatype recv_type, int rank, MPI_Comm comm);
例：
send_count = 1;
recv_count = 1;
recv_rank = 0;
MPI_Gather(&a, send_count, MPI_REAL, &a, recv_count, MPI_REAL, recv_rank, MPI_COMM_WORLD);
MPI_Allgather相当于MPI_Gather和MPI_Bcast操作的组合。数据从各进程中收集，而后除了根进程外，所有的进程也都会接收收集后的结果。
MPI_Allgather和MPI_Gather的参数一样。
分散（Scatter）
MPI_Scatter是一个一对多的通信。不同的数据由根进程（以秩顺序）发送到每个进程。
当MPI_Scatter调用，根进程把一堆连续的内存分解为相等的块，并把每个块发送到各个进程。结果和根进程执行N次MPI_Send操作以及每个进程执行一个MPI_Recv的结果相同。
发送参数只对根进程有意义。
函数原型：
int MPI_Scatter(void *send_buffer, int send_count, MPI_Datatype send_type, void *recv_buffer, int recv_count, MPI_Datatype recv_type, int root_rank, MPI_Comm comm);
例：
send_count = 1;
recv_count = 1;
send_rank = 0;
MPI_Scatter(&a, send_count, MPI_REAL, &a, recv_count, MPI_REAL, send_rank, MPI_COMM_WORLD);
高级操作（Advanced Operation）
MPI_Allreduce：用于合并每个进程的输入缓冲的元素。
用户定义缩减操作：缩减可以定义为任意操作。
收集／分散矢量操作：MPI_Gatherv和MPI_Scatterv支持各个进程的可变数量的数据的收集和分散。
其它收集／分散变体：
1、MPI_Allgather和MPI_Alltoall。
2、不指定根进程：所有的进程都收集或分散数据。
3、发送和接收参数对所有进程有意义。
MPI_Scan：用于执行贯穿于组的数组上的前缀缩减；返回缩减的结果给所有进程。
MPI_Reduce_scatter：合并了MPI_Reduce和MPI_Scatterv。
第7章 通信者
你已经熟悉了MPI_COMM_WORLD，它是MPI定义的允许程序里所有进程运行期间互相通信的通信者，或者是点对点通信，又或者是集合通信。然而对于一些应用，可能需要在选定的一个子进程组里进行通信。
通信者有两类：内部通信者（intra-communicator）和互联通信者（inter-communicator）。内部通信者处理通信者个体里的进程间的通信，而互联通信者处理内部通信者之间的通信。本质上来说，内部通信者是MPI_COMM_WORLD的进程的子集。我们主要专注于内部通信者。
需要新的通信者的原因经常是因为要处理矩阵的行、列或子块等需求。这些通信者通常和一个虚拟拓扑关联－－比笛卡尔拓扑常用－－来辅助并行操作的实现。此外，通信者的使用，经常和虚拟拓扑一起，通常增强了程序的可读性和可维护性。
MPI_Comm_group
得到一个通信者的组句柄。函数原型：
int MPI_Comm_group(MPI_Comm comm, MPI_Group *group);
例：
#include "mpi.h"
MPI_Comm comm_world;
MPI_Group group_world;
comm_world = MPI_COMM_WORLD;
MPI_Comm_group(comm_world, &group_world);
和通信者关联的是它的组标识，或称为句柄。在上面的例子里，我们使用MPI_Comm_group来得到通信者MPI_COMM_WORLD的组句柄。这个句柄而后可以用作以下例程的输入：MPI_Group_incl、MPI_Comm_create、MPI_Group_rank。
MPI_Group_incl
基于已有的组创建一个新的组，并指明成员进程。incl是include的缩写。函数原型：
int MPI_Group_incl(MPI_Group old_group, int count, int *members, MPI_Group *new_group);
members是原组里挑选出的进程的秩的数组，这些进程以被挑选的顺序放入新的组里。
例：
#include "mpi.h"
MPI_Group group_world, odd_group, even_group;
int i, p, Neven, Nodd, members[8], ierr;
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Comm_group(MPI_COMM_WORLD, &group_world);
Neven = (p+1)/2;
Nodd = p - Neven;
for (i = 0; i < Neven; i++) {
members[i] = 2*i;
}
MPI_Group_incl(group_world, Neven, members, &even_group);
在上例中，创建了一个新的组，它的成员是通信者MPI_COMM_WORLD的偶数编号的进程。在新的通信者里，组的成员以间隔1升序排序。
如果count参数为0，那么new_group的值为MPI_GROUP_EMPTY。
members数组里值的顺序，会影响到新组里各进程的秩。
MPI_Group_excl
基于已有组，创建一个新组，并指明不在新组中的成员。excl是exclude的缩写。函数原型：
int MPI_Group_excl(MPI_Group group, int count, int *nonmembers, MPI_Group *new_group);
和MPI_Group_incl不同，nonmemebers的元素顺序不会影响新组里的进程的秩。各进程在新组里的顺序和在原组的相对顺序相同。
如果count参数为0，那么new_group和old_group相同。
要排除的秩（在nonmembers定义的）必须在原组中存在，而且nonmembers数组的元素必须互不相同，否则会出错。
MPI_Group_rank
查询调用进程在组里的秩。函数原型：
int MPI_Group_rank(MPI_Group group, int *rank);
例：
#include "mpi.h"
MPI_Group group_world, worker_group;
int i, p, ierr, group_rank;
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Comm_group(MPI_COMM_WORLD, &group_world);
MPI_Group_excl(group_world, 1, 0, &worker_group);
MPI_Group_rank(worker_group, &group_rank);
上例中，首先创建一个新的工作组，它的成员是MPI_COMM_WORLD里除了进程0的其它所有进程。之后查询了这个组的秩。MPI_COMM_WORLD的秩的范围是（0,1,2,...,p-1）。对于这个简单的例子，新组worker_group的秩的范围是（0,1,2,...,p-2），因为它比MPI_COMM_WORLD少了一个进程（进程0）。所以，调用进程在新组里对应的秩号会比原来小一。然而对于其它排列，调用进程在新组里的秩没有那么直接。MPI_Group_rank的省去我们跟踪进程秩号的麻烦。
注意，如果调用进程是进程0，它不属于worker_group，所以MPI_Group_rank会返回MPI_UNDEFINED作为group_rank的值，表示它不是worker_group的成员。MPI_UNDEFINED的值由实现决定。比如SGI's MPI里它的值是-3，而在MPICH里是-32766。
MPI_Group_free
当不再需要一个组时，把它归还给系统。函数原型：
int MPI_Group_free(MPI_Group *group);
例：
#include "mpi.h"
MPI_Group group_world, worker_group;
int i, p, ierr, group_rank;
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Comm_group(MPI_COMM_WORLD, &group_world);
MPI_Group_excl(group_world, 1, 0, &worker_group);
MPI_Group_rank(worker_group, &group_rank);
MPI_Group_free(worker_group);
注意：释放一个组并不会释放它所属的通信者。MPI_Comm_free用来释放一个存在的通信者。
MPI_Comm_create
基于一个已有的通信者和组创建一个新的通信者。函数原型：
int MPI_Comm_create(MPI_Comm old_comm, MPI_Group group, MPI_Comm *new_comm);
例：
#include "mpi.h"
MPI_Comm comm_world, comm_worker;
MPI_Group group_world, group_worker;
int ierr;
comm_world = MPI_COMM_WORLD;
MPI_Comm_group(comm_world, &group_world);
MPI_Group_excl(group_world, 1, 0, &group_worker);
MPI_Comm_create(comm_world, group_worker, &comm_worker);
上例中，MPI_COMM_WORLD的组句柄首先被标识。然后一个新的组group_worker被创建。最后MPI_Comm_create用来创建一个新的通信者，它的成员进程和刚刚创建的组的成员一样。通过这个新的通信者，成员进程之间就可以传递消息了。
MPI_Comm_create是一个集合通信例程，它必须被old_comm的所有进程调用，且所有进程的调用的所有参数都必须相同，否则会出错。
对于不在组的进程，MPI_Comm_create会返回MPI_COMM_NULL。
在任务完成后，创建的通信者可以通过调用MPI_Comm_free来释放。
MPI_Comm_split
基于已有的通信者分离出多个新的通信者。
许多科学和工程计算都处理矩阵或网格（特别是迪卡尔网格），它们都由行和列组成。因此需要把进程逻辑地映射到相似的网格几何结构里。此外，可能需要用没那么传统的方式处理它们。例如，处理一组行或其它任意的结构，而非一个个独立的行，会很有好处或甚至是必需的。MPI_Comm_split提供了这样的灵活性来创建新的多个通信者。
函数原型：
int MPI_Comm_split(MPI_Comm old_comm, int color, int key, MPI_Comm *new_comm);
color提供了分组机制，相同颜色的进程在相同的组里。key参数提供了在每个组（颜色）内对秩的选派的控制。
例：对于2D逻辑网格，创建行和列的子网格。
irow = Iam / mcol; /* logical row number */
jcol = mod(Iam, mcol); /* logical column number */
comm2D = MPI_COMM_WORLD;
MPI_Comm_split(comm2D, irow, jcol, row_comm);
MPI_Comm_split(comm2D, jcol, irow, col_comm);
为了证明这个例子的结果，假设我们有６个进程（0, 1, ..., 5）。从数学（和拓扑）的角度，可以把这些进程视为３x２的逻辑网格排列。如下表所示：
| (0) | (1) |
| (2) | (3) |
| (4) | (5) |
秩为Iam的调用进程，使用到的irow和jcol，分别被定义为行号和列号。irow和jcol与Iam的关系如下表：
| Iam | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| irow | 0 | 0 | 1 | 1 | 2 | 2 |
| jcol | 0 | 1 | 0 | 1 | 0 | 1 |
第一个MPI_Comm_split调用把irow规定为“颜色”（或组），把jcol定义为“关键字”（或组里的独特成员）。这导致每行都被分类为不同的组，如下表所示：
| (0) (0) | (1) (1) |
| (2) (0) | (3) (1) |
| (4) (0) | (5) (1) |
另一方面，第二个MPI_Comm_split调用把jcol定义为颜色，把irow定义为关键字。这使得一列里的所有进程都属于一个组，如下表所示：
| (0) (0) | (1) (0) |
| (2) (1) | (3) (1) |
| (4) (2) | (5) (2) |
在上面两个表里，原来的秩号标为黑色，而新的秩号被标为红色。相同的颜色的表格属于同一个组。
MPI_Comm_split和MPI_cart_sub相似，但它比后者更通用。MPI_Comm_split创建一个逻辑网格，并通过它的线性秩号来引用它。MPI_Cart_sub创建一个笛卡尔网格，并用笛卡尔坐标来引用它。例如，在2维的迪卡尔网格里，网格单元由它的(irow, jcol)索引对标识。
MPI_Comm_split是一个集体通信例程，因此old_comm里的所有进程都必须调用这个例程。然而，和许多通信例程不同，关键字和颜色用于区分old_comm里的所有进程。
如果old_comm里有进程不在任何新组里，那么它的颜色必须定义为MPI_UNDEFINED。对于这些进程，对应的返回值new_comm的值为MPI_COMM_NULL。
如果有两个或多个进程有相同的关键字，那么新通信者里的这些进程的秩号以它们在原通信者里的相对顺序来排序。
通信者的示例代码
组例程的使用
这个例子的目的是把MPI_COMM_WORLD的成员进程分成两个新组。一个组由奇数号的进程组成，而另一个由偶数号的进程组成。之后打印一个表来展示一个进程是属于奇数还是偶数组。
#include "mpi.h"
#include "stdio.h"
void main(int argc, char *argv[])
{
int Iam, p;
int Neven, Nodd, members[6], even_rank, odd_rank;
MPI_Group group_world, even_group, odd_group;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &Iam);
MPI_Comm_size(MPI_COMM_WORLD, &p);
Neven = (p+1)/2;
Nodd = p - Neven;
members[0] = 2;
members[1] = 0;
members[2] = 4;
MPI_Comm_group(MPI_COMM_WORLD, &group_world);
MPI_Group_incl(group_world, Neven, members, &even_group);
MPI_Group_excl(group_world, Neven, members, &odd_group);
MPI_Barrier(MPI_COMM_WORLD);
if (Iam == 0) {
printf("MPI_Group_incl/excl Usage Example\n");
printf("\n");
printf("Number of processes is %d \n", p);
printf("Number of odd processes is %d\n", Nodd);
printf("Number of even processes is %d\n", Neven);
printf("\n");
printf(" Iam even odd\n");
}
MPI_Barrier(MPI_COMM_WORLD);
MPI_Group_rank(even_group, &even_rank);
MPI_Group_rank(odd_group, &odd_rank);
printf("%8d %8d %8d\n", Iam, even_rank, odd_rank);
MPI_Finalize();
}
它的输出为：
$ mpirun -np 6 ./odd_even_groups
MPI_Group_incl/excl Usage Example
Number of processes is 6
Number of odd processes is 3
Number of even processes is 3
Iam even odd
0 1 -32766
2 0 -32766
3 -32766 1
4 2 -32766
1 -32766 0
5 -32766 2
其中-32766是mpich里的MPI_UNDEFINED的值。
可以注意到偶数组是用MPI_Group_incl来创建的，所以它的进程的秩和members数组里定义的顺序一样。而奇数组是用MPI_Group_excl来创建的，所以它的进程的秩的相对顺序和它们在MPI_COMM_WORLD里时的相对顺序一样。进程在新组中的秩也是由0开始编号的。
MPI_Comm_split的使用
#include <mpi.h>
#include <stdio.h>
void main(int argc, char *argv[])
{
int mcol, irow, jcol, p;
MPI_Comm row_comm, col_comm, comm2D;
int Iam, row_id, col_id;
int row_group, row_key, map[6];
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &Iam);
MPI_Comm_size(MPI_COMM_WORLD, &p);
map[0]=2; map[1]=1; map[2]=2; map[3]=1; map[4]=0; map[5]=1;
mcol=2; /* nrow = 3 */
if (Iam == 0) {
printf("\n");
printf("Example of MPI_Comm_split Usage\n");
printf("Split 3x2 grid into 2 different communications\n");
printf("which correspond to 3 rows and 2 columns.");
printf("\n");
printf(" Iam irow jcol row-id col-id\n");
}
irow = Iam / mcol;
jcol = Iam % mcol;
comm2D = MPI_COMM_WORLD;
MPI_Comm_split(comm2D, irow, jcol, &row_comm);
MPI_Comm_split(comm2D, jcol, irow, &col_comm);
MPI_Comm_rank(row_comm, &row_id);
MPI_Comm_rank(col_comm, &col_id);
MPI_Barrier(MPI_COMM_WORLD);
printf("%8d %8d %8d %8d %8d\n", Iam, irow, jcol, row_id, col_id);
MPI_Barrier(MPI_COMM_WORLD);
if (Iam == 0) {
printf("\n");
printf("Next, create more general communicator\n");
printf("which consists of two groups :\n");
printf("Rows 1 and 2 belongs to group 1 and row 3 is group 2\n");
printf("\n");
}
row_group = Iam / 4;
row_key = Iam - row_group * 4;
MPI_Comm_split(comm2D, row_group, row_key, &row_comm);
MPI_Comm_rank(row_comm, &row_id);
printf("%8d %8d\n", Iam, row_id);
MPI_Barrier(MPI_COMM_WORLD);
if (Iam == 0) {
printf("\n");
printf("If two processes have same key, the ranks\n");
printf("of these two processes in the new\n");
printf("communicator will be ordered according'\n");
printf("to their order in the old communicator\n");
printf(" key = map[Iam]; map = (2,1,2,1,0,1)\n");
printf("\n");
}
row_group = Iam / 4;
row_key = map[Iam];
MPI_Comm_split(comm2D, row_group, row_key, &row_comm);
MPI_Comm_rank(row_comm, &row_id);
MPI_Barrier(MPI_COMM_WORLD);
printf("%8d %8d\n", Iam, row_id);
MPI_Finalize();
}
输出：
$ mpirun -np 6 ./comm_split
Example of MPI_Comm_split Usage
Split 3x2 grid into 2 different communications
which correspond to 3 rows and 2 columns.
Iam irow jcol row-id col-id
0 0 0 0 0
2 1 0 0 1
4 2 0 0 2
5 2 1 1 2
3 1 1 1 1
1 0 1 1 0
Next, create more general communicator
which consists of two groups :
Rows 1 and 2 belongs to group 1 and row 3 is group 2
0 0
2 2
5 1
3 3
1 1
4 0
If two processes have same key, the ranks
of these two processes in the new
communicator will be ordered according'
to their order in the old communicator
key = map[Iam]; map = (2,1,2,1,0,1)
0 2
2 3
1 0
4 0
5 1
3 1
从输出的最后一段可以看到当关键字相同时的秩的情况。进程1和进程3都有关键字“1”，所以它们在新组里的秩分别为“0”和“1”。进程0和进程2的关键字为“2”，所以它们在新组里的秩分别为“2”和“3”。
第8章 虚拟拓扑