开发Linux下的并行程序

性能并行计算所处理的问题具有程序规模庞大、编写困难、计算量大、运行时间长，以及数据量巨大等特点，因此选择一个好的并行计算平台和并行编程工具非常重要。Linux是一个非常优秀的操作系统，其上的MPI和PVM是目前最流行的并行编程语言。本文将介绍如何借助Linux来构建并行计算系统，以及如何在Linux平台下开发MPI和PVM并行程序。

并行计算环境
并行计算是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台独立计算机构成的集群。

并行计算基于一个简单的想法：n台计算机应该能够提供n倍的计算能力，不论当前计算机的速度如何，都可以期望被求解的问题将在1/n的时间内完成。显然这只是一个理想的情况，因为被求解的问题在通常情况下都不可能被分解为完全独立的各个部分，而是需要进行必要的数据交换和同步。尽管如此，并行计算仍然可以使整个计算机系统的性能得到实质性的改进，而改进的程度取决于欲求解问题自身的并行程度。

并行计算的优点是具有巨大的数值计算和数据处理能力，能够被广泛地应用于国民经济、国防建设和科技发展中具有深远影响的重大课题，如石油勘探、地震预测和预报、气候模拟和大范围天气预报、新型武器设计、核武器系统的研究模拟、航空航天飞行器、卫星图像处理、天体和地球科学、实时电影动画系统及虚拟现实系统等等。

目前，并行计算已经成为计算机科学研究和应用中的热点，各种并行计算系统层出不穷，其中发展最快的当数基于Linux平台的并行计算环境。使用Linux来构建并行计算平台具有许多优点：

◆ 廉价　Linux最大的优势就是价格，通常只需少量的软、硬件投资就可以拥有一个PC工作站或服务器。相比之下，Linux对硬件的要求比Windows要低得多，即使是普通用户也可以利用Linux来构建一个高性能的并行计算环境，从而替代以往开销昂贵的大型计算机。

◆ 开放　自由和开放是Linux最吸引人的特点，同时也为提高并行系统的性能提供了更加广阔的空间。开发者可以很容易地深入到系统的核心，从而使在操作系统一级提高性能成为可能。

◆ 高效　在相同软硬件配置情况下，Linux与其他操作系统相比具有更高的效率，尤其是网络性能和稳定性，而这些正是衡量并行计算平台优劣的关键所在。

并行编程模型
为了简化并行程序的设计，需要采用合适的并行编程模型。目前两种最重要的并行编程模型是数据并行和消息传递。数据并行编程模型的编程级别较高，编程相对简单，但只适用于解决数据并行问题；消息传递编程模型的编程级别较低，编程相对复杂，但却有着更加广泛的应用范围。

数据并行指的是将相同的操作同时作用于不同的数据，从而提高问题求解速度。数据并行很早就被应用于向量计算机。长期的实践表明数据并行可以高效地解决大部分科学与工程计算问题。数据并行模型是一种较高层次上的并行计算模型，它提供给程序员一个全局的地址空间。通常这类模型所采用的语言本身就提供有并行执行的语义，因而程序员只需要简单地指明执行什么样的并行操作和并行操作的对象，就实现了数据并行的编程。例如，对于矩阵运算，要使矩阵B和矩阵C中的对应元素相加后赋给矩阵A，则通过语句：

A = B + C

这样就能够完成相应的功能。正因如此，数据并行的表达是相当简单和简洁的，它不需要程序员关心并行系统是如何对该操作进行并行处理的。

数据并行模型虽然可以解决许多科学与工程计算问题，但对于非数值计算类问题，如果仍通过数据并行的方式来进行，则难以取得较高的效率。目前，数据并行模型面临的主要问题是如何实现高效的编译。只有具备了高效的编译器后，数据并行程序才可以在共享内存和分布式内存的并行计算机上取得高效率，才可能提高并行程序设计的效率和可移植性，从而进一步推广数据并行程序设计技术。

在消息传递模型中，各个并行执行的任务之间通过传递消息来交换信息、协调步伐、控制执行。消息传递一般是基于分布式内存的，但同样也适应于共享内存的并行计算机。消息传递模型为程序员提供了更加灵活的控制手段和表达形式，一些用数据并行模型很难表达的并行算法，采用消息传递模型则可以很容易地实现。机动灵活和控制手段的多样化，是消息传递模型能提供很高执行效率的重要原因。

消息传递模型为程序员提供了尽可能大的灵活性，但同时也将各个并行任务之间复杂的信息交换及协调控制交给了程序员，从而在一定程度上加重了程序员的负担。尽管如此，消息传递模型的基本通信模式仍然是简单和清楚的，目前大量并行程序采用的都是消息传递并行编程模型。

并行编程语言
由于消息传递并行编程模型的广泛应用，目前已经出现了许多基于该模型的并行编程语言，其中最流行的是PVM（Parallel Virtual Machine）和MPI（Message Process Interface）。第一个将工作站集群作为并行计算平台并被广泛接受的并行编程语言是PVM。它由美国的Oak Ridge国家实验室、Tennessean大学、Emorg大学、CMU大学等联合开发而成，能够将异构的Unix计算机通过异构网络连接成一个“虚拟”的并行计算系统，为其上运行的应用程序提供分布式并行计算环境。

PVM是一种基于局域网的并行计算环境。它通过将多个异构的计算机有机地组织起来，形成一个易于管理、易于编程、并且具有很好的可扩展性的并行计算环境。目前PVM支持C和Fortran语言。程序员首先参照消息传递模型编写好并行程序，然后将编译后的程序以任务为单位在网络中特定类型的计算机上运行。PVM能够在虚拟机中自动加载任务并运行，并且还提供了任务间相互通信和同步的手段。由于所有的计算任务都被分配到合适的计算节点上，多个节点并行运算，从而实现了任务一级的并行。

PVM为利用现有计算资源进行并行程序的开发与研究提供了一种有效的解决方案。由于PVM免费、开放和易于使用的特性，使得它成为一个被广泛接受的并行程序开发环境，目前几乎所有的并行计算系统都支持PVM。

MPI是为开发基于消息传递模型的并行程序而制定的工业标准，其目的是为了提高并行程序的可移植性和易用性。参与MPI标准制定的人员来自欧美40多个组织，大部分主要的并行计算机制造商、大学研究所、政府实验室、工业组织等都投入到MPI标准化工作。有了统一的并行编程语言标准，并行计算环境下的应用软件及软件工具就都能够实现透明的移植，各个厂商就可以依据标准提供独具特色和优势的软件实现和软件支持，从而提高了并行处理的能力。

MPI是一种基于消息传递模型的并行编程接口，目前已经发展成为消息传递模型的代表和事实上的工业标准，而不是一门具体的语言。迄今为止，所有的并行计算机制造商都提供对MPI的支持，因而从理论上说任何一个正确的MPI程序可以不加修改地在所有并行计算机上运行。

MPI只是一个并行编程语言标准，要编写基于MPI的并行程序，还必须借助某一MPI具体实现。MPICH是Linux平台下最重要的一种MPI实现，是一个与MPI规范同步发展的版本。每当MPI标准推出新的版本时，MPICH就会有相应的实现版本。LAM（Local Area Multicomputer）是Linux平台下另一免费的MPI实现。它由Ohio州立大学开发，主要用于异构的网格计算并行系统。

MPICH的安装和配置
MPICH是MPI的一种具体实现。下面以1.2.4版本为例，介绍如何在Linux上安装和配置MPICH，此处采用的操作系统为Red Hat 7.3。

1.下载MPICH软件包

根据需要及机器配置的不同，可从http://www.mcs.anl.gov/mpi/mpich/download.html下载相应的MPICH软件包。此处采用的软件包是mpich-1.2.4.tar.gz。

$ tar xzvf mpich-1.2.4.tar.gz
$ cd mpich-1.2.4
 
$ ./configure --prefix=/usr/local
$ make

4.测试编译的正确性

$ cd examples/basic/
$ make cpi
$ ../../bin/mpirun -np 4 cpi

若该程序能正确运行，则表明整个MPI软件包的编译是正确的。注意，若在运行测试程序时出现“Permission denied.”的错误信息，可以试着以其它用户或重新登录后再运行该测试程序。

5.安装MPICH软件包

如果测试程序能够正确运行，则表明整个编译过程是正确的，此时就可以通过以下命令的执行来安装MPICH软件 $ cd ../../
$ su -c “make install”

6.权限设置

为了能够在多个不同的机器上运行MPI程序，首先需要其它机器对启动MPI程序的机器放权，即允许启动MPI程序的机器访问其它机器。权限的设置主要有两种方法，一种是在其它所有机器的/etc/hosts.equiv文件中加入启动MPI程序的机器名。例如要在node1这台机器上启动MPI进程，而计算过程中要用到node2和node3两台计算机，则需要在node2和node3机器的/etc/hosts.equiv文件中加入如下一行：

node1

这样就使得node2和node3都允许node1通过rlogin、rsh等命令进行访问。为了使一台机器能够同时运行多个 node1

如果/etc/hosts.equiv文件不存在，则需要先创建该文件。

设置权限的另外一种方法是通过.rhosts文件来实现。具体的做法是对MPI程序运行过程中要用到的所有计算机，在运行该程序账户的Home目录下创建一个.rhosts文件，并在该文件中标明允许哪些机器的哪些账户进行访问。

例如，在node1、node2和node3机器上都有gary这一账号，若要允许node1机器上的gary账号能够分别对nod node1 gary
 
为了简便起见，最好在每个机器上都建立相同的账户名，使得MPI程序能够在相同的账户下运行。以上的配置都是基于R系列命令的（包括rlogin、rsh、rexec等），这种配置对于一般应用来说已经足够了。但如果并行计算环境要求有相当高的安全性，则应该考虑用SSH来代替R系列命令，具体的做法请参考MPICH的相关文档。

7.主机设置

要使MPI程序启动后能够在多个主机上并行执行，还必须对可用的主机进行设置，相应的配置文件为/usr/local/share/machines.LINUX。编辑该文件，在每一行写上可用的机器名。例如，只要在该文件中添加以下几行：

node1
node2
node3
 
就可以有3台计算机供MPI使用。

至此，MPICH在一台机器上的安装和配置过程就基本结束。将相同的步骤应用于并行计算环境中其它的计算机后，就可以构造出一个基于MPICH的并行计算平台。

PVM的安装和配置
PVM免费、开放的特性使得它成为一个被广泛接受的并行程序开发环境。它可以安装到Linux、Unix和Windows等多种操作系统上。以下以3.4.4版本为例，介绍如何在Linux平台上安装和配置PVM。

1.下载PVM软件包

根据需要及机器配置的不同，可以从http://www.netlib.org/pvm3/index.html下载相应的PVM软件包。此处采用的软件包是pvm3.4.4.tgz。

$ cp pvm3.4.4.tgz /usr/local/src/
$ cd /usr/local/src/
$ tar xzvf pvm3.4.4.tgz
 
3.设置环境变量

PVM在启动和运行的过程中需要用到环境变量PVM_ROOT和PVM_ARCH。每个要用到PVM的用户都需要设置这两个环境变量。环境变量PVM_ROOT的值为PVM软件包展开后根目录所在的位置，此处应该设为“/usr/local/src/pvm3”。环境变量PVM_ARCH的值标明了主机所对应的体系结构，对于运行Linux操作系统的主机来说，该值即为“LINUX”。

若使用的是bash，则为主机上所有用户添加这两个环境变量的方法是在/etc/bashrc文件中添加如下两行脚本：

export PVM_ROOT=/usr/local/src/pvm3
export PVM_ARCH=LINUX

若使用的是csh，则应该在/etc/csh.cshrc文件中添加如下两行脚本：

setenv PVM_ROOT /usr/local/src/pvm3
setenv PVM_ARCH LINUX

$ source /etc/bashrc

4.编译PVM软件包

当设置的环境变量生效后，执行下面的命令来编译整个软件包：

$ cd /usr/local/src/pvm3
$ make
 
5.建立符号连接

如果编译过程一切正常，则在/usr/local/src/pvm3/lib目录下生成可执行脚本pvm。为了今后使用方便，可以为其建立相应的符号连接：

$ su -c “ln -s /usr/local/src/pvm3/lib/pvm \
> /usr/local/bin/pvm”

6.权限设置

PVM的权限设置与MPICH相同，既可以直接修改/etc/hosts.equiv文件，也可以修改每个账号Home目录下的.rhosts文件。例如，若要在node1机器上启动PVM进程，而计算过程中还需要用到node2和node3两台计算机，则 node1

这样使得node1能够通过rlogin、rsh等命令访问node2和node3。

7.主机设置

大部分Linux发行版，都在/etc/hosts文件中将主机名作为本机回送地址的别名添加到127.0.0.1一行中，以 127.0.0.1      node1 localhost
 
127.0.0.1      localhost

至此，PVM在一台机器上的安装和配置过程就基本结束了。将相同的步骤应用于并行计算环境中其它的计算机后，就能够构造出一个基于PVM的并行计算平台了。
基于MPICH的并行程序设计
下面用一个简单的例子，给出在Linux平台上开发MPI并行程序的一个基本框架，以便对基于MPICH的并行程序有一个感性认识。基于MPICH的并行程序可以用C或者Fortran开发，此处给出的例子是用C语言编写的。

/*====================*
 * mpi_hello.c - Demo program of MPICH. *
 *====================*/

#include <stdio.h>
#include “mpi.h”

int main(int argc, char **argv)
{
  int myrank, nprocs, namelen;
  char processor_name[MPI_MAX
_PROCESSOR_NAME];

  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_
WORLD, &nprocs);
  MPI_Comm_rank(MPI_COMM
_WORLD, &myrank);
 MPI_Get_processor_name(processor_name, &namelen);

  printf(“Hello World!  I’m rank %d of %d on %s\n”, myrank,
    nprocs, processor_name);
  
  MPI_Finalize();
  return 0;
}
 
为了保证编译的正确性，程序的首部必须包含MPI的头文件mpi.h。该文件给出了MPI所有调用接口的说明，并对所有用到的常量进行了定义。MPI_MAX_PROCESSOR_NAME就是该文件中定义的一个常量，是某一MPI具体实现（此处即为MPICH）中允许的主机名的最大长度。

在调用任何MPI函数之前，必须先调用MPI_Init()进行相应的初始化工作。当所有MPI函数调用都完成之后，还必须调用MPI_Finalize()进行相应的清理工作。命令行参数通过MPI_Init()函数传递给MPI，以便为各个并行执行的程序建立起正确的运行环境。

接下去的几个MPI函数用来获得并行计算环境的一些基本信息。上面的示例程序只是简单地输出了这些信息，但通常情况下这些信息将被用来进行问题的自动分解，或者用于建立各并行机间的通信。MPI_Comm_size()函数可以得到参与并行计算的进程个数；MPI_Comm_rank()函数可以得到当前正在运行的进程的标识；而MPI_Get_processor_name()函数则能够获得当前进程所在主机的名称。

基于MPI的并行程序可能有很多种编译方法，大多数MPI实现都提供了一个易于使用的脚本来完成编译，这些脚本能够为编译器设置合适的参数，帮助编译器找到MPI头文件所在的目录，并能够连接上所需的库文件，从而保证编译过程的正确性。MPICH和LAM都提供了一个名为mpicc的脚本来完成并行程序的编译。例如，要编译上述的示例程序，只需执行下面的命令即可：

$ mpicc -o mpi_hello mpi_hello.c
 
在并行环境中的多台计算机上同时执行该程序，要将编译好的程序复制到不同的机器上，并且可执行程序必须放 $ mpirun -np 6 mpi_hello

在MPICH中，mpirun是MPI程序的启动脚本，它简化了并行进程的启动过程，尽可能屏蔽了底层的实现细节，从而为用户提供了一个通用的MPI并行机。在用mpirun命令执行并行程序时，参数-np指明了需要并行运行的进程个数。mpirun首先在本地结点上启动一个进程，然后根据/usr/local/share/machines.LINUX文件中所列出的主机，为每个主机启动一个进程。若进程数比可用的并行节点数多，则多余的进程将重新按照上述规则进行 Hello World!  I′m rank 0 of 6 on node1
Hello World!  I′m rank 1 of 6 on node2
Hello World!  I′m rank 5 of 6 on node3
Hello World!  I′m rank 3 of 6 on node1
Hello World!  I′m rank 2 of 6 on node2
Hello World!  I′m rank 4 of 6 on node3

基于PVM的并行程序设计
在用PVM进行并行程序设计时，程序员首先要将被求解的问题分解成独立的程序，然后用C或者Fortran实现每个程序，最后再通过PVM提供的虚拟机在整个并行计算环境中运行。下面用一个简单的例子，给出在Linux平台上开发PVM并行程序的一个基本框架。

/*===================*
 * pvm_hello.c - Demo
program of PVM.*
 *==================*/

#include <stdio.h>
#include “pvm3.h”

int main(int argc, char** argv)
{
  int i, mytid, dtid, info, nhost, narch;
  struct pvmhostinfo* hostp;

mytid = pvm_mytid();
dtid = pvm_tidtohost(mytid);
info = pvm_config(&nhost, &narch, &hostp);

for (i = 0; i < nhost && hostp[i].hi_tid != dtid; i++)
    ;
printf(“Hello World! My task id is t%x on %s with %d hosts.\n”,
mytid, hostp[i].hi_name, nhost);

pvm_exit();
return 0;
}

上述示例程序给出了启动和终止一个PVM程序的基本步骤：首先在程序首部包含PVM的头文件pvm.h。然后调用pvm_mytid()函数获得当前运行进程的任务标识符，调用pvm_tidtohost()函数获得与任务标识符对应的主机标识符。若想获得当前进程所在虚拟机的相关信息(如主机总数和平台种类等)，则可以通过调用函数pvm_config()来实现。最后，当所有的PVM函数都执行完后，调用pvm_exit()函数来结束整个并行计算过程。

PVM没有提供一个单独的脚本来完成编译过程，要编译上述示例程序，需要手工执行以下命令：

$ gcc -o pvm_hello -I/usr/local/src/pvm3/include/ \
> -L/usr/local/src/pvm3/lib/LINUX/ pvm_hello.c -lpvm3

同MPICH一样，用PVM编写的程序要想能够在多台主机上并行运行，首先要将编译好的可执行文件复制到不同的机器上。PVM要求用户运行的可执行文件都应该位于Home目录下的pvm3/bin/LINUX下。例如，要想在node1上以gary账户启动上述示例程序，同时要求node2和node3能够并行执行该程序，则应先将可执行文件pvm_hello复制到node1、node2和node3机器上的/home/gary/pvm3/bin/LINUX目录下，然后在node1上执行如下命令：

$ cd ~/pvm3/bin/LINUX
$ pvm
pvm> add node2 node3
pvm> spawn -6 -> pvm_hello
pvm> halt

PVM专门提供了一个Shell来对并行执行的任务进行管理和调度。上述程序中add命令用来添加一个新的并行节点机；spawn命令用来启动一个并行程序，参数“-6”指明了并行执行的进程个数，参数“->”指示将输出信息显示在屏幕上；halt命令则用来终止整个并行计算虚拟机。

上述示例程序的一次执行结果如下所示：

[1:t40002] Hello World! My task id is t40002 on node1 with 3 hosts.
[1:t40002] EOF
[1:t40003] Hello World! My task id is t40003 on node1 with 3 hosts.
[1:t40003] EOF
[1:tc0002] Hello World! My task id is tc0002 on node3 with 3 hosts.
[1:t80001] Hello World! My task id is t80001 on node2 with 3 hosts.
[1:t80001] EOF
[1:tc0001] Hello World! My task id is tc0001 on node3 with 3 hosts.
[1:tc0001] EOF
[1:tc0002] EOF
[1:t80002] Hello World! My task id is t80002 on node2 with 3 hosts.
[1:t80002] EOF
[1] finished
 
并行计算使用多台计算机或者具有多个处理器的计算机来求解问题，从而为求解大规模复杂问题提供了可能。作为一个优秀的操作系统，Linux特别适合用来组建并行计算平台。