并行计算与MPI研究
周文荣
摘 要：并行计算作为现代科学计算的一种重要方法，常用于解决复杂和计算量大的问题。MPI程序包含了并行计算的思想，文章对并行计算与MPI进行了研究，了解了MPI程序思想，对并行计算意义较大。
关键词：并行计算；MPI；并行算法
1 并行计算简介
并行计算与串行计算的区别在于，串行计算只在单个CPU上进行求解，而并行计算则是同一个时间段内在多个CPU上求解；从硬件角度上来讲，串行计算就是在普通计算机上求解，并行计算则是于并行计算机上求解。需要并行计算求解的问题须能分成很多并行子问题[1]。
在20世纪50年代之后，日益提升的计算速度逐渐成为互联网、娱乐游戏、科学计算领域的决定因素。例如画面优美反应灵敏的电脑游戏、精确及时的引擎搜索、清晰明了的医学成像等方方面面都离不开计算性能的提升。中国的现代生活很多都在和计算产生着关联，例如在生物医药方面，医学专家可以利用计算分析的相关知识通过患者的基因找到不会对人体产生损伤的替代药物，通过提高计算性能来提高分析蛋白质结构的能力；在能源方面，快速的计算能力能在太阳能电池、风力发电机和蓄电池方面帮助开发人员进行更加准确的建模，得到更加高效清洁的能源信息。在新闻报刊上经常提到的高性能计算其实和并行计算意思相同，这样表述的原因是高性能计算和超级计算都用到并行计算。
并行计算的特点主要表现在：（1）并行计算由相对独立的模块独立分开管理控制；（2）在并行计算中会存在多个模块同时异步进行，该并行能有效降低运行耗费的时间；（3）所有的模块与模块之间存在一定的交互；（4）并行计算可能由于并发和交互导致错误发生[2-3]。
并行计算采用的并行方法主要包括：（1）资源共享，是指用软件方法实现资源在某段时间内可以同时访问；（2） 资源重复，是指通过重复设置和利用硬件和软件资源，以此来提高计算机系统的性能；（3）时间重叠，例如不同的进程在时间上相同资源的使用相互错开或者轮流重复利用某硬件资源，来提升速度。并行遗传算法是并行计算的一个分支应用，将会大大减少得到最优解所需要的时间。
本文既然涉及并行计算，肯定也会涉及并行体系。并行体系的主要特点为：（1）并行性，多流水、超标量是提升CPU并行性能的重中之重。在新型并行体系中，根据并行的程度分级；（2）可扩展性，是指增加资源时，性能和功能得到提升。认识可扩展性应该认识到成本伸缩的比例应该小于线性比例。
早期的微处理器的计算性能以平均每年50%的速度提升。后来受到摩尔定律的限制，微处理性能提升速度渐渐变慢，在进入21世纪之后，主流的微处理器制造商已决定通过并行处理来快速提升微处理器的计算性能，以求进一步提升计算能力。由此可见并行计算对现代科学计算至关重要。
2 系统分类
并行计算在专门的平台上完成，完成整个并行过程的平台一般称为并行计算机。串行计算机主要包含3个方面：处理器、内存及数据通道。并行计算机主要含有3个大类：共享存储的多处理机、分布式存储的多处理机和集群[4]。
自20世纪70年代起，并行的硬件平台就处于高速发展阶段，各种硬件平台相继出现，向量机、单指令多数据流系统和多指令多数据流系统等相继面世。随着时间的脚步慢慢向前迈进，向量机和单指令多数据流系统慢慢被淘汰，而多指令多数据流系统越来越受到大家的推崇。
3 并行算法
3.1 同步并行
主要是因為不同的进程完成速度不同，在使用同步命令之后，速度快的进程需要等速度慢的进程结束之后再与速度慢的进程同时进行下一步。
3.2 异步并行
主要是由于并行计算的独立性产生的，进程之间相互独立，也没有执行同步命令，各个进程可以按照各自的节奏有序地进行。
3.3 数值并行
主要是因为现实生活中很多模型是用数学模型表示的，而这些数学模型大部分能用数值来计算。
3.4 非数值并行
主要是指除去数值计算之外的计算，例如关系计算、逻辑计算等。
并行算法的主要特点是：（1）并行算法与计算机的结构有很大的关系，针对同一问题，当所使用的并行计算机的结构不同时，最后所使用的算法不同；（2）并行算法比较复杂，并行算法和任务分配、数据分配、数据结构等有着较多联系，而数据的分配、任务的分配和数据的结构都比较复杂，只要有一种不同就可能会导致算法的并行效果完全不同。
4 MPI并行程序设计
消息传递接口（Multi Point Interface，MPI）是一种基于并行计算的模型。MPI标准公布之后，很多MPI实现相继出现，例如使用LAM和MPICH实现MPI变得越发流行[5]。
由俄亥俄州的州立大学超级计算中心开发的LAM可以免费实现MPI。LAM在异构网络集群环境下，向使用者提供MPI实现所需要的编程界面以及实现过程中所需要的调试环境。LAM是免费的、开放的、开源的，且具有不错的扩展特点，能动态扩充虚拟机与进程组。
MPICH是具有可移植性的MPI实现，由美国密西根州立大学和美国国家实验室在制定MPI标准的过程中联合开发，MPICH出现的主要目的是为MPI提供一个具有高的可移植性和高效率的接口。
MPI的目标是实现较高的移植性和较高的通信效率。MPI在发展的过程中有效地结合了实用性，并巧妙利用了之前开发的消息传递系统中消息通信的知识，成功地变成一种通用的标准。
MPI是一种集合，此集合包含了很多不同的函数库，这些函数可以被C或FORTRAN调用。可以将MPI理解为具有可移植性和扩展性的消息传递模型。这样的消息传递模型同时也是并行计算的标准。MPI代表的是一种规范，所以很多产商都对它予以肯定。
1997年形成的MPI-2包含有大概200多个函数，其中最基本的是6个函数。只要使用这6个基本函数，就代表一个完整的MPI程序。
MPI的主要优点为高效的通信性、便捷的实用性、较高的移植性和准确的定义等。
MPI的目的是指MPI标准的目的。MPI标准的目的为：（1）通信效率的提高；（2）由于它的可移植性，它必须能在异构的环境下实现；（3）MPI需要在不同的进程之间传递消息，所以MPI需要具有消息传递接口；（4）MPI的接口必须可以用C语言或者FORTRAN语言调用；（5）因为MPI具有可扩展性，所以MPI的接口需要可以进行延伸；（6）设计出的接口一定为安全有效的；（7）设计接口的语言必须是独立的。这样的接口能够在多平台上实现，能够被直接调用。
MPI不仅可以在PC/Windows系统下的并行机上实现，而且也可以在Linux系统下的并行机上实现。一个用C或者FORTRAN开发的MPI程序不仅可以在一个PC机上实现，也可以在并行机上实现，同时可以在集群上实现，不管此平台是哪家公司制造的，不管是哪种操作系统，只要保持原样进行移植就能成功编译。
5 MPI基本函数
MPI中包含6个基本函数，这些基本函数如下[5]：
5.1 MPI初始化函数
MPI初始化函数的原型是int MPI_Init（int *argc， char **argv）。MPI_Init是MPI的程序中使用的第一個MPI函数，该函数会对MPI程序和MPI的环境进行初始化。
5.2 MPI结束函数
MPI结束函数的函数原型是：int MPI_Finalize（void）。当MPI程序需要结束时就会调用结束函数MPI_Finalize。结束函数位于涉及MPI代码的最后面，是MPI代码执行过程中所用到的最后一个函数。
5.3 MPI获取当前进程编号的函数
MPI获取当前进程编号的函数模型如下：MPI_COMM_rank（MPI_COMM comm， int *rank）。第一个参数comm表示进程处于的唯一通信域；第二个参数表示在这个通信域中的进程所代表的编号。MPI获取当前编号函数的目的是求出此进程在该通信域中的编号，然后将这个编号赋给第二个参数rank。
5.4 MPI获取通信域中所包含的进程数目的函数
MPI得到位于通信域中的进程的数目的函数模型为int MPI_Comm_size（MPI_Comm comm， int *size）。MPI获取通信域中所包含的进程的个数的函数的模型中第一个参数comm表示的是通信域，后面一个参数size代表comm中的含有进程个数。此函数返回一个通信域中的进程总体的数目给size。只要是位于此通信域里面的进程都可以用此函数来获取这个通信域包含有几个进程。
5.5 发送消息函数
发送消息函数的函数原型为：int MPI_Send（void *buf， int count， MPI_Datatype datatype， int deat， int tag， MPI_Comm comm）。
buf —所发送的数据的首地址
Count—所发送的数据的个数
Datatype—所发送的数据的数据类型
dest—需要发送到的目标进程的编号
Tag—所发送的消息的标志
Comm—通信域
5.6 接收消息函数
接收消息函数的函数模型为：int MPI_Recv（void *buf， int count， MPI_Datatype datatype， int source， int tag， MPI_Comm comm， MPI_Status *status）。
Buf—所接收的数据的首地址
Count—所接收的数据的个数
Datatype—所接收的数据的类型
Source—所接收的数据的来源进程编号
Tag—所接收的消息的编号
Comm—通信域
Status—接收数据的时候返回的状态
6 MPI并行模式
MPI程序在编写过程中分为两种不同模式：对等模式和主从模式。
6.1 对等模式
在这种模式中，进程与进程之间地位平等，能相互联系。对等体现在不同进程地位相同，MPI代码功能类似上，唯一的不同体现为不同的进程所处理的处理对象和数据不同[6-7]。在消息模型中存在4个对等结点时，对等节点之间的通信模式如图1所示。
在对等模式中，各个对等节点相互通信，并将结果和控制信息进行传递。其中有一个对等点的任务是将任务进行分配，在完成之后又在此节点上进行结果汇总。
6.2 主从模式
在主从模式中，不同的节点功能和地位不同[8]。在主从模式中会存在1个主进程和1个或多个从进程，主进程与从进程之间的关系如图2所示。
在主从模式中，主进程主要进行控制，从进程主要进行计算。主进程的任务是对所有进程进行初始化，将计算任务分到从进程；从进程根据主进程的要求完成计算任务，并将最后取得的结果返回到主进程。
[参考文献]
[1]陈国良.并行计算：结构·算法·编程[M].北京：高等教育出版社，1999.
[2]DARRIBA D，TABOADA GL，DOALLO R，et al. Model Test 2：more models，new heuristics and parallel computing[J].Nature Methods，2012（8）：772-772.
[3]GOLUB GH，ORTEGA JM. Scientific computing：an introduction with parallel computing[M]. Amsterdam： Elsevier，2014.
[4]ROBERGE V，TARBOUCHI M， LABONT? G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].Industrial Informatics，2013（1）：132-141.
[5]STEVENS B，GIORGETTA M，ESCH M，et al. Atmospheric component of the MPI-M earth system model：ECHAM6[J].Journal of Advances in Modeling Earth Systems，2013（2）：146-172.
[6]GUNARATHNE T，ZHANG B，WU TL，et al. Scalable parallel computing on clouds using twister4Azure iterative mapreduce[J].Future Generation Computer Systems，2013（4）：1035-1048.
[7]CHANDY KM，TAYLOR S. An introduction to parallel programming[J].Jones and Bartlet，1992（4）：361-370.
[8]CANTPAZ E. A survey of parallel genetic algorithms[J].Calculateurs Paralleles Reseaux Et Systems Repartis，1998（4）：429-449.
Abstract： As an important method of modern scientific computing， parallel computing is often used to solve the complex and large amount of computational problems. The MPI program contains the idea of parallel computing. In this paper， the parallel computing and MPI are studied， and the idea of MPI is find out， which is of great significance to parallel computing.
Key words： parallel computing； MPI； parallel algorithm
