MPI（1）－－消息传递基础

问题分解

设计并行算法的第一步是把问题分解成更小的问题。粗略来看，有两种分解方式：

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）”来衡量。潜在时间用 于设置通信所需的信封，而带宽是传输的真正速度，即每单位时间传送的位数。串行程序不需要使用进程间通信。因此，你必须最小化这个时间的使用，来得到最好 的性能提升。

重叠通信与计算：有几种方式可以最小化进程的空闲时间，一个例子是重叠通信与计算。当某一进程等待通信完成时，它被分配一个或多个新的任务，所以它可以在等待时处理另一个任务。对非阻塞通信和非特定数据的计算的谨慎使用可以实现这种场景。在实践中交叉计算与通信其实是非常难的。