一、为什么要并行计算？
计算机界有一个著名的定律叫摩尔定律，是由Intel创始人之一戈登摩尔所提出的。他说，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍。然而，晶体管的数量增加，功耗和产生的热量也随之大幅增加。当散热能力近乎达到极限时，通过增加单个CPU的性能来换取更高的运算性能已不可取。考虑到物理极限的约束和设计更复杂的架构所产生的高额成本等因素，开始朝向多核的方向发展。
二、如何实现并行计算？
将一个计算任务分配到多个节点上去计算，通常有两种方式。一个是任务并行，一个数据并行。顾名思义，任务并行就是每个节点执行不同的任务，而数据并行就是每个节点存储不同的数据。因为本系列教程的重点是MPI，因此从程序这一划分粒度来分类，可分为SPMD（单程序多数据）和MPMD（多程序多数据并行）。
SPMD即为多个计算集群都运行同一个程序，然而他们各自的存储是独立的。比如进程0和进程1分别有一个数组A，这两个数组可以分别为[0,2,3]和[1,2,3]。当执行一个程序，要求计算A=A+1时，进程0和进程1会同时用各自的数组A去执行相同的程序，得到的结果分别为[1,3,4]和[2,3,4]。所以，在这种情况下，如果想对某一进程执行特殊于其他进程的操作，可以加一个if(process_id==0)的语句，从而让进程1不进入该if语句中去。MPMD则相当于各自进程执行各自的程序。SPMD和MPMD的表达能力是相同的，只是针对不同的问题编写难易而已。MPI是可以写SPMD和MPMD的并行程序的。之所以这么设计，是由并行计算机的体系结构所决定的，因此有必要简单描述一下计算机的运作方式。
当前的计算机采用冯诺依曼体系结构，CPU执行的指令和参与计算所用到的数据都存储于内存（该内存指的是存储设备，不单指内存条）当中，而CPU会按照程序顺序执行。众所周知，内存是线性存储的。即假一个内存有256个存储空间，则这256个存储空间的地址会依次对应于0-255。因此，将CPU设计成多个核心时，需要解决存储问题。
在设计并行计算机时，最直接的方式就是多个计算单元共享一个内存，即如下图所示。共享内存的编程在数据交换和访问上有较大的优势，程序编写起来更加简单。但在扩展性上有较大的瓶颈。另一种方式为分布式内存，即每个计算单元有单独的内存，计算单元之间的数据访问通过互联网络去传输。这一架构在可移植性和扩展上会强很多，但消息的传递会成为程序设计中的难点。将这两点结合，即是分布式共享内存并行计算机的架构，也是当今最常用的体系结构。之后的MPI编程中，将会涉及很多消息通信，之后的学习会加深对此的理解。
三、改写一个串行程序
前半部分讲了基本理论，接下来通过分析一个串行程序和一个并行程序，来讲解MPI是如何实现上述理论过程的。
我们不妨举一个简单的例子，假设A是一个2×4的矩阵，想对矩阵A进行求和。如果是串行程序，那么需要写两层循环。
1
2
3
4
5
6
7
8
int sum=0;
for(int i=0;i<2;i++)
{
for(int j=0;j<4;j++)
{
sum=sum+A[i][j];
}
}
如果我们想使用2个进程去做并行计算，这两个进程分别做第一行和第二行的求和，然后再将这两个数去求和。MPI_SEND和MPI_RECV这两个函数分别为发送和接收，具体的将在之后一章讲解。
本代码只是用于讲解MPI如何实现数据通信，真正的并行程序是不会这么写的，在之后的章节会介绍对等模式和主从模式。在用MPI进行计算时，消息通信的时间成本是比较大的，所以通常会采用重复计算来避免不必要的通信，使总运行时间变短。在具体优化代码时，是需要分析通信时间和计算时间，使其达到一个最优平衡。不过，下面这个程序可以看出MPI程序的基本写法和几个基本操作。
初学者可能会受到串行程序的思维惯性。为了便于理解，可以把下面这个程序理解成是在两个独立的进程上运行，不仅计算独立，存储也独立。而这俩cpu的标识要通过myid这个变量来获取。存储独立代表着这两个变量A只有变量名相同，存储的数据内容地址是不同的。从下面代码可以看出，两个进程分别对不同的数组A和变量s在执行相同的代码。为了让两个进程做不同的操作，就需要加上if语句，当myid是0的时候自然就不会执行else if语句里的内容了，反之同理。在两个进程分别做完各自的操作之后，需要一个进程把数据发送给另一个进程，这样才能将结果汇总起来。进程与进程之间在实际上是平等关系。但是可以在逻辑上，规定比如进程0是主进程，涉及到分发和接受时赋予进程0以特殊的逻辑地位，这就是后面要讲的并行程序的主从模式。除此之外还有对等模式，后文会专题去讲。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);//得到的变量myid即为当前的进程号
//假设要求和的矩阵为A={[1,1,1,1],[2,2,2,2]}
if(myid==0)
{
memset(A,1,sizeof(int)); //将数组A全赋值为1
}
else if (myid==1)
{
memset(A,2,sizeof(int)); //将数组A全赋值为2
}
//以上部分是将数组的两行分别存储到进程0和进程1上
for(int i=0;i<4;i++)
{
s=s+A[i];
}
if(myid==1)
{
MPI_Send(s,1,MPI_INT,0,99,MPI_COMM_WORLD);
//将求和结果s发送到进程0
}
if(myid==0)
{
MPI_Recv(s1,1,MPI_INT,1,99,MPI_COMM_WORLD,&status);
//用s1这个变量来存储从进程1发送来的求和结果
s=s+s1;
}
printf("%d",&s);
MPI_Finalize();
参考资料
1.都志辉. 高性能计算并行编程技术:MPI并行程序设计[M]. 清华大学出版社, 2001.
