目录
1 摘要2 概述2.1 什么是并行计算？2.2 为什么要并行计算？2.3 谁都在使用并行计算？科学界和工程界：工业界和商业界：全球应用：(PGAS)）模型。具有如下特点： 地址空间被认为是全局的。 大多数的并行工作聚焦于在数据集上的操作。数据集通常被组织成为常用的结构，例如数组，数立方等。 一系列任务在同一块数据结构上操作，但是每个任务却操作在该数据结构的不同分区上。 每个任务在数据结构的不同分区上执行相同的操作，例如，“给每个数组元素加上4”。
在共享内存的架构下，所有的任务通过全局内存方式来对数据进行存取；在分布式内存架构下，根据任务分配，全局数据结构在物理或者逻辑上被进行分割。
实现： 目前，基于数据并行/PGAS模型，有如下几个相对有名的实现：
Coarray Fortran: 为了支持SPMD并行编程而在Fortran 95上做的一个小的扩展，是编译器相关的，更多信息可以参见： Coarray_Fortran
Unified Parallel C (UPC): 为了支持SPMD并行编程而在C语言基础上做的扩展，也是编译器相关的，更多信息可以参见： The UPC Language
5.6 混合模型
混合模型指的是包含了至少两个我们前面提到的并行计算模型的模型。目前，最常见的混合模型的例子是消息传递模型（MPI）和线程模型（OpenMP）的结合：
线程使用本地数据完成计算密集型的任务； 不同的进程则在不同的结点上通过MPI完成数据通讯。这种混合模型非常适合目前流行的硬件环境——多核计算机组成的集群系统。
另外一种类似的，但原来越流行的例子是采用MPI和CPU-GPU的混合编程：
采用MPI的任务运行于CPU上，使用本地内存上的数据，但是通过网络与其它任务进行数据交换； 而计算密集型的核则被加载到GPU上进行计算； 而结点内部的内存和GPU上的数据交换则通过CUDA（或者类似的东西）进行数据交换。
其它混合模型还包括：
MPI和Pthreads的混合； MPI和non-GPU加速器的混合。 …5.7 单程序多数据模型(SPMD)和多程序多数据模型(MPMD)
单程序多数据模型(Single Program Multiple Data (SPMD))：
SPMD事实上是一种可以架构在其它并行编程模型之上的更“高级”的编程模型：
单程序：所有任务都执行同一个程序的拷贝，而这里的程序可以是线程，消息传递，数据并行甚至混合； 多数据：不同的任务操作于不同的数据。SMPD通常需要指定任务的执行逻辑，也就是不同的任务可能会根据分支和逻辑关系，去执行整个程序的某个部分，也就是说，不是所有的任务都必须执行整个程序——有可能只是整个程序的某个部分。（译者注：如果不强调这一点，SPMD就退化成了数据并行模型了。）
而这种采用消息消息传递或者混合编程的SPMD模型，有可能是今天运行在多核集群系统上的最常见的并行计算模型了。
多程序多数据模型(Multiple Program Multiple Data (MPMD))：
和SPMD一样，多程序多数据模型实际上也是一种可以架构在其它并行编程模型基础上的“高级”并行编程模型：
多程序：任务可以同时执行不同的程序，这里的程序可以是线程，消息传递，数据并行或者它们的混合。 多数据：所有的任务可以使用不同的数据。MPMD应用并不像SPMD应用那么常见，但是它可能更适合于特定类型的程序。
6 并行程序设计
6.1 自动 vs. 手动并行化
设计和实现并行程序是一个非常手动的过程，程序员通常需要负责识别和实现并行化，而通常手动开发并行程序是一个耗时，复杂，易于出错并且迭代的过程。很多年来，很多工具被开发出来，用以协助程序员将串行程序转化为并行程序，而最常见的工具就是可以自动并行化串行程序的并行编译器(parallelizing compiler)或者预处理器 (pre-processor)。
并行编译器通常以如下两种方式工作：
完全自动：
由编译器分析源代码并且识别可以并行化的部分，这里的分析包括识别出哪些部分满足并行化的条件，以及权衡并行化是否真的可以提高性能。循环（包括do, for）通常是最容易被并行化的部分。
程序员指令：
通过采用“编译器指令”或者编译器标识，程序员明确地告诉编译器如何并行化代码，而这可能会和某些自动化的并行过程结合起来使用。
最常见的由编译器生成的并行化程序是通过使用结点内部的共享内存和线程实现的（例如OpenMP）。
如果你已经有了串行的程序，并且有时间和预算方面的限制，那么自动并行化也许是一个好的选择，但是有几个重要的注意事项：1）可能会产生错误的结果；2）性能实际上可能会降低；3）可能不如手动并行那么灵活；4）只局限于代码的某个子集（通常是循环）；5）可能实际上无法真正并行化，由于编译器发现里面有依赖或者代码过于复杂。
接下来的部分仅适用于手动开发并行程序。
6.2 理解问题和程序
毫无疑问，开发并行程序的第一步就是理解你将要通过并行化来解决的问题。如果你是从一个已有的串行程序开始的，那么你需要首先理解这个串行程序。
在开始尝试开发并行解决方案之前，需要确定该问题是否真正可以被并行化。
一个容易被并行化的问题如下。该问题容易被并行化，因为每个分子构象都是独立且确定的。计算最小能量构象也是一个可以被并行化的问题。计算数千个独立分子构象中每一个的势能，完成之后，找出能量构象最小的那一个。
一个不太可能被并行化的问题如下。由于F(n)同时依赖于F(n-1)和F(n-2)，而后者需要提前被计算出来。采用如下公式计算菲波那切数列 （0,1,1,2,3,5,8,13,21,…）：F(n) = F(n-1) + F(n-2)。
识别程序的关键点 (hotspots)：
了解哪个部分完成了程序的大多数工作。大多数的科学和技术程序中，大多数的工作都是在某些小片段中完成的。可以通过剖析器或者性能分析工具来帮助你分析。专注于程序中这些关键点，忽略那些占用少量CPU的其余部分。
识别程序中的瓶颈 (bottlenecks)：
有没有导致程序不成比例地变慢的，或者导致并行程序停止或者延迟的部分？例如有时候输入输出操作会导致程序变慢。 有时候也可能通过重构程序，或者采用不同的算法来降低或者消除这些执行很慢的区域。识别并行化的抑制因素。一个常见的类型是数据依赖性 (data dependence)，例如上面提到的菲波那切数列的例子。
如果可能的话，研究其它算法。这可能是设计并行程序的过程中最重要的一点。
利用成熟的第三方并行软件，或者高度成熟的数学库（例如IBM的ESSL，Intel的MKL，AMD的AMCL等）。
6.3 分割 (Partitioning)
设计并行程序的第一步就是将程序分解成为可以分配到不同任务中去的“块”。这被称为程序的分解 (decomposition) 或者分割 (partitioning)。通常有两种基本方法可以将并行任务进行分解：域分解和功能分解。
域分解： 在这种分割方式中，将数根据问题进行分解。每个并行任务操作数据的一部分。
通常由不同的方式来对数据进行分割：
功能分解：
在这种方法中，重点在于要执行的计算，而不是计算所操纵的数据。问题根据要做的工作进行分解，然后每个任务执行整个工作的一部分。
这种功能分解非常适合于可分为不同任务的问题，例如：
生态系统建模：
每个程序计算给定组的人口，其中每个组的正常取决于其邻居的增长。锁着时间的推移，每个进程计算当前状态，然后与相邻群体交换信息。然后所有任务进行下一步计算。
信号处理：
音频信号数据集通过四个不同的计算滤波器，每个滤波器是一个单独的过程。第一段数据必须通过第一个滤波器，然后才能进入第二个滤波器。当这样做时，第二段数据通过了第一个滤波器。当第四个数据段处于第一个滤波器时（以及之后），四个任务都会变得很忙。
气候建模：
每个模型组件都可以被认为是一个单独的任务。箭头表示计算期间组件之间的数据交换：大气模型需要使用风速数据生成海洋模型；海洋模型使用海面温度数据生成大气模型等。
在实践中将这两种分解方式结合起来是很自然的，也是很常见的。
6.4 通讯 (Communications)
任务之间的通讯需求取决于你的问题：
不需要通讯的情况：
一些程序可以被分解成为并发执行的任务，而这些任务之间不需要共享数据。这类问题往往被称为“尴尬并行”——任务之间不需要数据通讯。例如如果我们需要对下面一副图片的颜色进行取反（黑色的部分变为白色的，白色的变为黑色的），那么图像数据可以被简单地分解为多个任务，并且每个任务可以被独立地执行。
需要通讯的情况：
大多数并行程序并不像上一问题这么简单，任务之间确实需要共享数据。例如下面这幅热度扩散图需要一个任务知道其它任务在它的邻居方格中的计算结果。邻居数据的变化将直接影响到该任务的数据。
设计通讯需要考虑的因素： 在设计程序任务之间的通讯时，有大量的重要因素需要考虑：
通讯开销：
1）任务间通讯几乎总是意味着开销。
2）而可以用于计算的机器周期以及资源会转而用于对数据的封装和传输。
3）频繁的通讯也需要任务之间的同步，这有可能会导致任务花费时间等待而不是执行。
4）竞争通讯流量可能使可用的网络带宽饱和，从而进一步加剧性能问题。
延迟 vs. 带宽：
1）延迟 指的是从A点到B点发送最小量的信息所需要花费的时间，通常以毫秒计。
2）带宽 指的是单位时间内可以传输的数据总量，通常以M/S或者G/S来计。
3）发送大量的短消息可能会导致延迟成为通讯的主要开销。通常情况下将大量小信息封装成为大消息会更加有效，从而提高通讯带宽的利用效率。
通讯可见性：
1）在消息传递模型中，通讯往往是显式和可见的，并且在编程者的控制之下。
2）在数据并行模型中，通讯对编程者来说往往是透明的，尤其是在分布式内存架构中。编程者往往甚至不能明确知道任务之间的通讯是如何完成的。
同步 vs. 异步通讯：
1) 同步通讯需要共享数据的任务之间某种意义上的“握手”。这既可以由编程者显式地指定，也可以在底层被隐式地实现而不为编程者所知。
2）同步通讯业常常被称为“阻塞通讯”，因为一些任务必须等待直到它们和其它任务之间的通讯完成。
3）异步通讯允许任务之间独立地传输数据。例如任务1可以准备并且发送消息给任务2然后立即开始做其它工作，它并不关心任务2什么时候真正受到数据。
4）异步通讯也常常被称为“非阻塞通讯”，因为在通讯发生的过程中，任务还可以完成其它工作。
5）在计算和通讯自由转换是异步通讯的最大优势所在。
通讯的范围：
明确哪些任务之间需要通讯在设计并行代码的过程中是非常关键的。下面两种通讯范围既可以被设计为同步的，也可以被设计为异步的：
1）点对点通讯： 涉及到两个任务，其中一个扮演消息发送者/生产者的角色，另外一个扮演消息接受者/消费者的角色。
2）广播通讯： 涉及到多于两个任务之间的数据共享。这些任务通常处于一个组或者集合中。
通讯的效率：
通常编程者具有影响通讯性能的选择，这里列举其中一些：1）对于一个给定的模型，究竟应该采用哪一种实现？例如对于消息传递模型而言，一种MPI的实现可能在某个给定的硬件下比其它实现要快。2）什么采用什么类型的通讯操作？正如前面所提到的，异步通讯操作往往可以提高程序的整体性能。3）网络结构（network fabric）：某些平台可能会提供多于一个的网络结构。那么究竟哪一个最好？
开销和复杂性：
最后需要意识到，上面提到的仅仅是需要注意的问题的一部分！
6.5 同步 (Synchronization)
管理工作的顺序和执行它的任务是大多数并行程序设计的关键，它也可能是提升程序性能的关键，通常也需要对某些程序进行“串行化”。
同步的类型：
屏障：
1）这通常意味着会涉及到所有任务；
2）每个任务都执行自身的工作，直到它遇到屏障，然后它们就停止，或者“阻塞”；
3）当最后一个任务到达屏障时，所有任务得以同步；
4）接下来可能发生的事情就有所变化了。通常会执行一段串行代码，或者所有的任务在这里都结束了。
锁/信号量：
1）可以涉及任意多个任务；
2）通常用于对全局数据或者某段代码的存取串行化（保护），在任一时刻，只有一个任务可以使用锁/信号量；
3）第一个任务会获得一个锁，然后该任务就可以安全地对该保护数据进行存取；
4）其它任务可以尝试去获得锁，但必须等到当前拥有该锁的任务释放锁才行；
5）可以是阻塞的也可以是非阻塞的。
同步通讯操作：
1）仅仅涉及到执行数据通讯操作的任务；
2）当一个任务执行数据通讯操作时，通常需要在参与通讯的任务之间建立某种协调机制。例如，在一个任务发送消息时，它必须收到接受任务的确认，以明确当前是可以发送消息的；
3）在消息通讯一节中也已经说明。
6.6 数据依赖性 (Data Dependencies)
定义：
依赖： 当语句的执行顺序影响程序的运行结果时，我们称程序语句之间存在依赖关系。 数据依赖： 数据依赖是由不同任务多次存取相同的内存位置而产生的。数据依赖也是并行程序设计中的关键，因为它是并行化中一个重要的抑制因素。
例子：
循环相关的数据依赖：下面这段代码中，A(J-1) 必须在A(J) 之前被计算出来，因此说A(J) 与 A(J-1) 之间存在数据依赖，所以并行化在这里被抑制。如果任务2中有A(J)，任务1中有A(J-1)，那么要计算出正确的A(J) 则需要：1）分布式内存架构：任务2必须在任务1计算结束之后，从任务1处中获取A(J-1) 的值。2）共享内存架构：任务2在任务1完成对A(J-1) 的更新之后，对A(J-1) 进行读取。
DO J = MYSTART,MYEND
A(J) = A(J-1) * 2.0
END DO
循环无关的数据依赖：在下面的例子中并行化也同样被抑制。Y的值依赖于：1）分布式内存架构： 在任务之间是否需要或者何时需要对X的值的通讯。2）共享内存架构： 哪个任务最后存储X的值。
task 1 task 2
------ ------X = 2 X = 4
. .
. .
Y = X**2 Y = X**3
尽管在并行程序设计中，对所有数据依赖的识别都是重要的，但循环相关的数据依赖尤其重要，因为循环往往是最常见的可并行化部分。
处理方法：
1）分布式内存架构：在同步点传输所需数据；
2）共享式内存结构：在任务之间同步读写操作。
6.7 负载均衡 (Load Balancing)
负载均衡是指在任务之间分配大约相等数量的工作的做法，以便所有任务在所有时间保持繁忙，它也可以被认为是使任务空闲时间最小化。出于性能原因方面的考虑，负载均衡对并行程序很重要。例如如果所有恩物都收到屏障同步点的影响，那么最慢的任务将决定整体性能。
如何实现负载均衡：
平均分配任务量：对于数组/矩阵而言，如果每个任务都执行相同或者类似的工作，那么在任务之间平均分配数据集；2）对于循环迭代而言，如果每个迭代完成的工作量大小类似，则在每个任务中分配相同或者类似的迭代次数；3）如果你的架构是由具有不同性能特征的机器异构组合而成，那么请确保使用某种性能分析工具来简则任何的负载不平衡，并相应调整工作。
采用动态任务分配方法：即使数据在任务之间被平均分配，但是某些特定类型的问题也会导致负载不平衡，如下面三个例子所示。
稀疏矩阵：某些任务会具有真实数据，而大多数任务对应的数据却为0。
自适应网格：某些方格需要被细分，而其它的不需要。
N体模拟：粒子可能会跨任务域迁移，因此某些任务会需要承担更多的工作。
当每个任务的工作量是可变的，或者无法预测的，那么可以采用 调度任务池 (Scheduler-task pool) 方法。每当某个任务完成了它的工作，它就可以从工作队列中领取新的任务。
最终来看，可能需要设计一种在代码中动态发生和处理负载不平衡的算法。
6.8 粒度 (Granularity)
计算通讯比 (computation / Communication Ratio)：
在并行计算中，粒度是对计算与通讯的比例的定性度量。计算周期通常通过同步时间与通讯周期分离。
细粒度并行化 (Fine-grain Parallelism)：
1）在通讯事件之外进行相对较少的计算工作；
2）计算通讯率较低；
3）方便负载均衡；
4）意味着较高的通讯开销以及较少的性能提升机会；
5）如果粒度过细，任务之间的通讯和同步的开销可能需要比计算更长的时间。
粗粒度并行化 (Coarse-grain Parallelism)：
1）在通讯/同步事件之外需要较大量的计算工作；
2）较高的计算/通讯比；
3）意味着较大的性能提升机会；
4）难以进行较好的负载均衡。
最佳选择：
最有效的粒度取决于具体算法及其所运行的硬件环境。在大多数情况下，与通讯/同步相关的开销相对于执行速度很高，因此具有粗粒度的问题是相对有利的。而从另外一方面来讲，细粒度则可以帮助减少由负载不均衡所造成的开销。
6.9 输入输出 (I/O)
坏消息：
1）I/O操作通常被认为是并行化的抑制剂；
2）I/O操作通常比内存操作需要多个数量级的时间；
3）并行I/O系统可能不成熟或者不适用于所有平台；
4）在所有任务均可以看到相同文件空间的环境中，写操作可能导致文件被覆盖；
5）读操作可能受到文件服务器同时处理多个读取请求的能力影响；
6）必须通过网络进行的I/O操作（NFS，非本地）可能导致严重的性能瓶颈，甚至导致文件服务器崩溃。
好消息：
已经具有不少并行文件系统，例如：
GPFS：通用并行文件系统 (General Parallel File System)（IBM），现在也被称为IBM Spectrum Scale。
Lustre：针对Linux的集群（Intel）。
HDFS：Hadoop分布式文件系统（Apache）。
PanFS：Panasas ActiveScale File System for Linux clusters (Panasas, Inc.)更多并行文件系统可以参加这里。
作为MPI-2的一部分，1996年以来MPI的并行I/O编程借口规范已经可用。
注意事项：
1）尽可能减少整体I/O操作；
2）如果你有权访问并行文件系统，请使用它；
3）在大块数据上执行少量写操作往往比在小块数据上进行大量写操作有着更明显的效率提升；
4）较少的文件比许多小文件更好；
5）将I/O操作限制在作业的特定串行部分，然后使用并行通讯将数据分发到并行任务中。例如任务1可以读输入文件，然后将所需数据传送到其它任务。同样，任务2可以再从所有其它任务收到所需数据之后执行写入操作；
6）跨任务的I/O整合——相比于很多任务都执行I/O操作，更好地策略是只让一部分任务执行I/O操作。
6.10 调试 (Debugging)
调试并行代码可能非常困难，特别是随着代码量的扩展。而好消息是有一些优秀的调试器可以提供帮助：
1）Threaded - Pthreads和OpenMP；
2）MPI；
3）GPU/accelerator；
4）Hybrid。
在LC集群上也安装有一些并行调试工具：
1）TotalView (RogueWave Software)；
2）DDT （Allinea）；
3）Inspector（Intel）；
4）Stack Trace Analysis Tool（STAT）（本地开发）。
更多的信息可以参考：LC web pages，TotalView tutorial。
6.11 性能分析和调优 (Performance Analysis and Tuning)
对于调试而言，并行程序的性能分析和调优比串行程序更具挑战性。幸运的是，并行程序性能分析和调优有很多优秀的工具。Livemore计算机用户可以访问这种类似工具，其中大部分都在集群系统上。一些安装在LC系统上的工具包括：
LC's web pages：https://hpc.llnl.gov/software/development-environment-software
TAU: http://www.cs.uoregon.edu/research/tau/docs.php
HPCToolkit: http://hpctoolkit.org/documentation.html
Open|Speedshop: http://www.openspeedshop.org/
Vampir / Vampirtrace: http://vampir.eu/
Valgrind: http://valgrind.org/
PAPI: http://icl.cs.utk.edu/papi/
mpitrace：https://computing.llnl.gov/tutorials/bgq/index.html#mpitrace
mpiP: http://mpip.sourceforge.net/
memP: http://memp.sourceforge.net/
7 并行示例
7.1 数组处理
此示例演示了对二维数组元素的操作：将某个函数作用于二维数组中的每个元素，其中对每个数组元素的操作都是独立于其它数组元素的，并且该问题是计算密集型的。对于串行程序而言，我们依次对每个元素进行操作，其代码类似于：
do j = 1,n
do i = 1,n
a(i,j) = fcn(i,j)
end do
end do
问题：
该问题是否可以被并行化？ 如果对该问题进行分割？需要数据通讯吗？ 有没有数据依赖？ 有没有同步需求？ 是否需要考虑负载均衡？并行方案1：
由于对元素的计算彼此之间是独立的，所以可以有“尴尬并行”的解决方案。
由于数组元素是均匀分布的，所以每个进程可以拥有阵列的一部分（子阵列）。
1）可以选择最佳分配方案以实现高效的内存访问，例如选择步幅为1，或者选择合适的步幅以最大化缓存/内存使用。 2）由于可以使单元跨越子阵列，所以分配方案的选择也取决于编程语言，有关选项可以参见第 6.3 节。由于数组元素的计算是彼此独立的，所以不需要任务之间的通讯和同步。
由于任务之间的工作量是被平均分配的，所以不需要考虑负载均衡。
对数组分割之后，每个任务执行与其拥有的数据相对应的循环部分，其源代码类似于：
请注意只有外部循环变量与串行解决方案不同。
for i (i = mystart; i < myend; i++) {
for j (j = 0; j < n; j++) {
a(i,j) = fcn(i,j);
}
}
一种可能的解决方案：
1）采用单程序多数据 (SPMD) 模型进行实现，每个任务执行相同的程序；
2）主进程对数组进行初始化，将信息发送给子任务，并且接收计算结果；
3）子进程接收到信息之后，执行计算任务，并且将结果发送给主进程；
4）采用Fortran的存储结构，对数组进行块划分；
5）伪代码如下所示。
6）具体的C代码可以参见MPI Program in C：
find out if I am MASTER or WORKER if I am MASTER initialize the array send each WORKER info on part of array it owns send each WORKER its portion of initial array receive from each WORKER results else if I am WORKER receive from MASTER info on part of array I own receive from MASTER my portion of initial array # calculate my portion of array do j = my first column,my last column do i = 1,n a(i,j) = fcn(i,j) end do end do send MASTER results endif
并行方案2：
上一个并行方案展示了静态负载均衡：1）每个任务执行固定量的工作；2）某些很快或者负载较轻的处理器将会拥有空闲时间，而最慢执行的任务最终决定整体性能。
如果所有任务在同一台机器上运行相同量的工作，那么静态负载均衡往往并不是一个主要问题。但是如果你确实有负载均衡方面的问题（某些任务比其它任务运行的快），那么你可以采用“任务池”(pool of tasks)模式。
任务池模式： 里面包含两个进程：
主进程：
1）拥有任务池；2）如果得到请求，给工作进程发送工作任务；3）从工作进程出收集返回结果。
工作进程：
1）从主进程处获取任务；2）执行计算任务；3）向主进程发送结果。
工作进程在运行之前不知道它将处理数组的哪一部分，以及它将执行多少任务。动态负载均衡发生在运行时：运行最快的任务将完成更多的任务。一段可能的源代码如下：
find out if I am MASTER or WORKER if I am MASTER do until no more jobs if request send to WORKER next job else receive results from WORKER end do else if I am WORKER do until no more jobs request job from MASTER receive from MASTER next job calculate array element: a(i,j) = fcn(i,j) send results to MASTER end do endif
讨论：
1）在上述任务池例子中，每个任务计算数组的某一个元素，计算与通讯比率是细粒度的；
2）细粒度的解决方案为了减少任务空闲时间，往往会导致更多的通讯开销；
3）更好地解决方案可能是在每个任务中分配更多的工作，“正确”的工作量依然是依赖于具体问题的。
7.2 圆周率计算
该问题的串行代码大约是这样的：
npoints = 10000circle_count = 0 do j = 1,npoints generate 2 random numbers between 0 and 1 xcoordinate = random1 ycoordinate = random2 if (xcoordinate, ycoordinate) inside circle then circle_count = circle_count + 1end do PI = 4.0*circle_count/npoints
该问题是计算密集型的——大多数时间将花费在对循环的执行。
问题：
该问题是否可以被并行化？ 如何对该问题进行分割？ 任务之间是否需要通讯？ 是否存在数据依赖？ 任务之间是否有同步需求？需 要考虑负载均衡吗？解决方案：
又一个容易被并行化的问题：
1）每个点的计算都是独立的，不存在数据依赖；
2）工作可以被平均分配，不需要考虑负载均衡；
3）任务之间不需要通讯和同步。
下面是并行化之后的伪代码：
npoints = 10000circle_count = 0 p = number of tasksnum = npoints/p find out if I am MASTER or WORKER do j = 1,num generate 2 random numbers between 0 and 1 xcoordinate = random1 ycoordinate = random2 if (xcoordinate, ycoordinate) inside circle then circle_count = circle_count + 1end do if I am MASTER receive from WORKERS their circle_counts compute PI (use MASTER and WORKER calculations) else if I am WORKER send to MASTER circle_count endif
C语言的示例程序可以参考这里：MPI Program in C。
7.3 简单热方程
大多数并行计算问题需要任务之间的通讯，其中一大部分问题需要“相邻”任务之间的通讯。
二维热方程问题描述了在给定初始温度分布以及边界条件的情况下，温度随着时间的变化。有限差分方案可以采用数值方法求解正方形区域内的热扩散方程：
二维数组的元素用来表示正方形区域内的点的温度；
边界处的初始问题是0，中心点的问题最高；
边界处的问题会保持为0；
采用时间步长算法。
每个元素的文图的计算取决于它的邻居的温度：
串行程序的代码可能使这个样子：
do iy = 2, ny - 1 do ix = 2, nx - 1 u2(ix, iy) = u1(ix, iy) + cx * (u1(ix+1,iy) + u1(ix-1,iy) - 2.*u1(ix,iy)) + cy * (u1(ix,iy+1) + u1(ix,iy-1) - 2.*u1(ix,iy)) end doend do
问题：
该问题是否可以被并行化？
如何对该问题进行分割？
任务之间是否需要通讯？
是否存在数据依赖？
任务之间是否需要同步？
是否需要考虑负载均衡？
解决方案：
该问题更具有挑战性。因为存在数据依赖，所以需要任务之间的通讯和同步。整个数组需要被风格成为子数组，并分配给不同任务，每个任务拥有整个数组的一部分。由于任务量是均匀划分的，所以不需要考虑负载均衡。
确定数据依赖：
1）一个任务的 内部元素 和其它任务之间不存在数据依赖；
2）一个任务的 边界元素 则和它的邻居任务之间需要产生数据通讯。
采用单程序多数据模型（SPMD）进行实现：
1）主进程向工作进程发送初始信息，然后等待并收集来自工作进程的计算结果；
2）工作进程在特定的时间步长内计算结果，并与邻居进程之间进行数据交换。
伪代码如下：
find out if I am MASTER or WORKER if I am MASTER initialize array send each WORKER starting info and subarray receive results from each WORKER else if I am WORKER receive from MASTER starting info and subarray # Perform time steps do t = 1, nsteps update time send neighbors my border info receive from neighbors their border info update my portion of solution array end do send MASTER results endif
示例程序可以参加：MPI Program in C。
7.4 一维波动方程
在这个例子中，我们计算经过指定时间量之后，一维波动曲线的振幅。其中的计算会涉及到：
1）y轴上的振幅；
2）x轴上的位置索引i；
3）沿着波动曲线的节点；
4）以离散时间步长更新振幅。
这里需要求解的是如下一维波动方程，其中c是常数。
A(i,t+1) = (2.0 * A(i,t)) - A(i,t-1) + (c * (A(i-1,t) - (2.0 * A(i,t)) + A(i+1,t)))
我们注意到，t时刻的振幅取决于前一刻的时间步长(t, t-1)以及相邻点(i - 1, i + 1)。
问题：
该问题是否可以被并行化？
如何对该问题进行分割？
任务之间是否需要通讯？
人物之间是否存在数据依赖？
任务之间是否需要同步？
是否需要考虑负载均衡？
解决方案：
这是涉及到数据依赖的另外一个例子，其并行方案将会涉及到任务见的通讯和同步。整个振幅阵列被分割并分配给所有的子任务，每个任务拥有总陈列的相等的部分。由于所有点需要相等的工作，所以我们应该均匀地分配节点。我们可以将工作分成多个块，并且允许每个任务拥有大多数连续的数据点。而通讯只需要在数据边界上进行，块大小越大，则所需的通信越少。
采用单程序多数据（SPMD）模型的实现：
1）主进程向工作进程发送初始信息，并且等到各个工作进程返回计算结果；
2）工作进程对特定步长之内的任务进行计算，并且在必要的时候和邻居进程进行数据通讯。
其伪代码如下：
find out number of tasks and task identities #Identify left and right neighborsleft_neighbor = mytaskid - 1right_neighbor = mytaskid +1if mytaskid = first then left_neigbor = lastif mytaskid = last then right_neighbor = first find out if I am MASTER or WORKERif I am MASTER initialize array send each WORKER starting info and subarrayelse if I am WORKER` receive starting info and subarray from MASTERendif #Perform time steps #In this example the master participates in calculationsdo t = 1, nsteps send left endpoint to left neighbor receive left endpoint from right neighbor send right endpoint to right neighbor receive right endpoint from left neighbor #Update points along line do i = 1, npoints newval(i) = (2.0 * values(i)) - oldval(i) + (sqtau * (values(i-1) - (2.0 * values(i)) + values(i+1))) end do end do #Collect results and write to fileif I am MASTER receive results from each WORKER write results to fileelse if I am WORKER send results to MASTERendif
程序示例可以参见：MPI Program in C。
8 参考文献和更多信息
作者：Blaise Barney，Livermore Computing.
在万维网上搜索“parallel programming”或者“parallel computing”将会获得大量信息。
推荐阅读：
”Designing and Building Parallel Programs”. Lan Foster.
http://www.mcs.anl.gov/~itf/dbpp/“
Introduction to Parallel Computing”. Ananth Grama, Anshul Gupta, George Karpis, Vpin Kumar.
http://www-users.cs.umn.edu/~karypis/parbook/“
Overview of Recent Supercomputers”. A.J. van der Steen, Jack Dongarra.
OverviewRecentSupercomputers.2008.pdf
图片/图像由作者以及其它LLNL成员创建，或者从不涉及版权的政府或公领域（）获取，或者经所有者同意从其演示文稿或者网页上获取。
历史：该材料有下面的资源演化而来，而这些资源将不再被维护或者不再可用。
Tutorials located in the Maui High Performance Computing Center's “SP Parallel Programming Workshop”.
Tutorials located at the Cornell Theory Center's “Education and Training” web page.
以上就是并行计算概念及定义全面详解的详细内容，更多关于并行计算的资料请关注我们其它相关文章！
