基于MPI的弹道仿真的并行计算研究

钟新玉 王 恂 张学军

北京控制与电子技术研究所，北京100038

随着科学技术的飞速发展和所研究问题的规模和复杂性的提高，越来越多的大规模科学工程计算问题对计算机的运行速度提出了非常高的要求。近年来，微处理器的性能不断提高，存储空间日益扩大，高速局域网的逐步发展使得可以利用相对廉价的计算机构建高性能的计算机机群系统。与传统的超级计算机相比，计算机机群系统具有较高的性价比和良好的可扩展性，可以满足不同规模的大型计算问题。

并行计算是解决大型复杂计算问题的主要方法之一，其基本思想是根据一定的规则将一个大的计算问题分解成许多小的子问题，将这些子问题分配调度到高性能计算平台的不同节点上进行计算。将大的问题合理的分解成小问题进行并行计算，可以大大缩短问题的处理时间，提高软硬件资源的利用率。并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用和生物工程等领域，理论研究与应用普及均取得了很大进展［1］。

1 MPI简介

目前，MPI(Message Passing Interface)是一种比较著名的应用于并行环境的消息传递标准，由MPI论坛(MPI Forum)推出，制定该标准的目的是提高并行程序的可移植性和易用性［2］。MPI现已成为产业界广泛支持的并行计算标准，它具有移植性好、功能强大和效率高等优点，而且具有多种不同的免费、高效、实用的版本。MPI从整体上说是一个优秀的、标准的分布式并行计算平台，但其在某些方面还存在不足:MPI没有提供容错的机制，并行应用程序以一个进程组的方式运行时，当进程组中的一个进程或计算机结点失败后，整个并行应用程序都将失败［3］。MPI的实现采用程序体形式，将并行计算和网络通信的细节隔离开来，从而降低了并行编程的复杂性。MPICH是MPI1.2标准的一个完全实现，也是应用范围最广的一种并行及分布式环境。本文采用该环境进行并行计算。

2 提高弹道仿真并行计算效率的方法

某系统软件中需要进行大量的弹道仿真计算，每条弹道仿真中有大量复杂的计算模型和矩阵运算，每条弹道计算时间约为1.5s，若系统软件要进行1000条的弹道计算，总的计算时间约为0.5h，而系统软件需要在1h内完成全部功能计算，且弹道仿真的计算时间占系统总运行时间的比重很小，这大大超过了系统软件的运行时间，无法满足系统性能要求。因此，需要缩短弹道计算时间，而并行计算是当前提高计算效率的有效方式之一，可以解决总体计算时间过长的不足，大大缩短系统计算的时间，提高软硬件资源的利用率。

并行计算的任务是减少程序运行时间。如何在最短的时间内完成计算，提高运行效率，可以从以下几个方面考虑［4］:

1)减少通信量。并行计算进程之间肯定存在数据通信。要去掉不必要的数据通信，尽量减少数据通信量和通信时间;

2)减少通信次数。每一次数据通信都要根据相应的协议对数据进行打包等操作，会消耗额外CPU时间;

3)利用通信与计算的重叠提高运行效率。MPI提供了非阻塞的通信方式，进程在通信没有完成时可以继续进行计算。正确的使用通信与计算的重叠能提高算法的整体运行效率;

4)采用性能相同的计算机构建计算机机群。采用相同计算机的目的是使各节点的性能一致，同时简化系统的管理，方便并行编程时计算任务的分割，提高计算速度。

3 弹道仿真并行性分析

并行计算分为时间并行和空间并行，主要研究的是空间上的并行问题［5-6］，所采用的高性能并行体系主要有5类:并行向量处理机(PVP)、对称多处理共享存储并行机(SMP)、大规模并行处理机(MPP)、工作站机群(COW)和分布式共享存储处理机(DSM)。COW与巨型机和MPP系统等高性能并行体系相比，具有高性价比，可扩展性好，结构灵活等特点，与以往的并行系统的不同主要表现在它的异质性和非独占性，即组成系统的工作站的计算能力各不相同，并且每个工作站上可能有其他用户计算在执行［7］。

为了在多个处理器节点上合理地进行任务调度以提高计算效率，设计出合理的并行方案，需先对弹道仿真计算模型的可并行性进行分析。每条弹道仿真计算都有相同的输入数据和数据类型相同的输出数据，仿真计算之间的数据交互量很少，仿真计算可以独立的运行。仿真计算结束之后，将计算结果发送给数据交互中心，数据交互中心负责分发初始数据给各个弹道计算，并接收弹道仿真计算的结果。因此，弹道仿真并行计算结构示意图如图1所示。

上述过程中，每个弹道仿真计算是独立进行的，所以多条弹道仿真计算可以实行并行化。为了让多个任务能够自动地进行计算，减少进程间的通信量，采用了任务并行的方案。系统软件和弹道并行计算运行在不同的计算机上，因此采取主从式的并行计算模式，即由一个主进程先读入弹道仿真计算的初始数据，并将其分发到各个子进程，根据一定的算法将N条弹道计算分配到各子进程，再由各个子进程负责相应弹道仿真计算，最后由数据交互中心汇总仿真结果数据。这样通过有效的任务分解和任务并行来提高运算速度。弹道仿真的并行计算流程如图2所示。

图1 弹道仿真的并行计算结构示意图

图2 弹道仿真的并行计算流程图

4 并行计算设计与实现

并行算法设计中最常用的是PCAM方法，即划分、通信、组合和映射。划分是将一个大问题平均划分成若干小问题，并让其在各个处理器上同时执行;通信是在分析执行过程中，协调和交换数据与任务;组合则是将较小的问题组合到一起，以提高性能和减少任务开销;映射则是将任务分配到每个处理器上。并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等［8］。

为提高并行计算的效率，按照PCAM法，根据弹道编号按区划分计算任务，并把任务映射到各个处理器。软件采用主从式的计算模式，主进程负责分发初始数据和汇总计算结果，子进程负责弹道计算。为减少通信开销，只有主进程和子进程之间进行通信和数据交换。并行计算采用基于MPI消息传递的并行编程模型实现。为保证通信的可靠性和数据的有效性，点对点通信采取阻塞发送和接收机制。各个并行执行的部分之间通过消息传递来交换信息、协调同步和控制执行。

4.1 任务划分

并行计算的基本思想是将原任务分解成若干子任务，并将子任务分配到处理器上，由多个进程并行执行。通过对弹道仿真的并行性分析，对弹道仿真的计算可以分区进行。分区计算的目的是分解弹道仿真计算任务，即将计算任务划分为若干子域，机群的每个处理器负责处理其中的某一个子域，因此划分的区域个数与实际应用中处理器的个数相关。弹道并行计算平台采用同构计算服务器，每台计算服务器的计算性能相同，分配给各个计算服务器的计算任务量相当，最大限度地减少服务器之间的数据转移，以达到各处理器负载平衡。

4.2 数据通信

每条弹道仿真计算都有相同的输入数据和数据类型相同的输出数据，计算之间的数据交互量很少，可以独立运行。弹道仿真计算采用主从式计算模式，数据交互中心(主进程)负责分发初始数据，并汇总计算结果;从进程接收主进程发送的初始化数据，并进行弹道仿真计算，待弹道仿真计算结束之后，将计算结果发送给数据交互中心(主进程)。只有主从进程之间进行通信，从进程之间无需进行数据交互。点对点通信采取阻塞发送和接收机制，可以保证通信的可靠性和数据的有效性。

4.3 任务组合与映射

任务组合可以提高性能和减少任务开销，映射是为了将任务分配到各个处理器。任务组合与映射的具体实现方案如下:所有弹道仿真计算数量为Total，处理器总数量为size。

首先，每个处理器至少可以分配的弹道仿真计算任务量为AverageTaskNumber，则

这些剩余的弹道仿真任务量LeftTaskNumber将分配到处理器，规定编号小的处理器分得更多的计算任务，这样就可以得到编号为rank(0≤rank≤size-1)的处理器分配的弹道任务的数量TaskNumPerProcess，则

5 性能分析

评价并行计算性能需要引入2个参数:加速比Sp和并行效率Fp［4］。计算如下式

式中，p为节点个数;Tp为在p个节点上并行计算弹道的时间;Ts为单机运算耗时;Sp为加速比，是衡量并行计算速度的参数;Fp是衡量并行计算效率的参数，表示并行计算对计算机资源的利用率。

本文的测试环境为4台刀片服务器组成的机群系统。刀片服务器的操作系统为:Windows Server 2008 HPC Edition;CPU为Intel(R)Xeon(R)CPU X5650，频率为2.67GHZ，核数为12;内存容量为24GB。系统软件运行的环境为:操作系统是Windows XP SP3，CPU 是 Intel(R)Xeon(R)CPU X5690，频率为 3.47GHZ，核数为6;内存容量为4GB。弹道并行计算程序由C语言编写，并行计算环境为MPICH2-1.4.1p1。表1中的计算时间是5次不同CPU核数并行计算的时间均值。

1000条弹道串行与并行计算的性能比较如表1所示。不同节点的加速比和并行计算效率分别见图3和图4。

表1 串行计算与并行计算的性能比较

图3 不同数量CPU核数的加速比比较

图4 不同数量CPU核数的并行计算效率比较

从表1，图3和4可以看出，CPU核数为24时，1000条弹道并行计算时间约为1min，即可满足系统性能的要求，并且加速比和并行计算效率分别为23.127，96.36%，获得了较高的加速比和计算效率，这充分说明基于MPI的弹道并行计算方案是可行的。同时实验数据说明随着CPU核数的增加，加速比增大趋势变缓，并行计算效率逐步降低，这是因为在弹道计算任务规模不变的情况下，随着CPU核数的增加，进程之间的通信开销逐渐增大，导致计算效率下降，加速比增大变缓。

6 结论

1)基于MPI的消息传递机制实现了1000条弹道仿真的并行计算。采用主从式的计算模式，主进程广播弹道仿真的初始化数据，收集并行计算结果;从进程收到广播数据后，开始弹道计算，待计算结束后，将计算结果发送给主进程。主、从进程各司其职，仅在主进程和从进程之间通信，减少了进程之间的通信开销，大大提高了弹道仿真的计算效率。

2)试验数据结果表明，用传统的串行计算1000条弹道仿真时间约为1502s，而采用并行计算方式，在CPU核数为48时，计算时间约为33s，计算时间约为串行计算时间的1/45;将基本MPI的并行计算技术应用到弹道仿真计算中，是一次成功的尝试，大大缩短了弹道仿真计算的时间，系统性能明显提升。

3)文中的弹道仿真并行计算是任务间的并行，并行粒度不高;并行计算硬件平台是同构机群系统，机群中的每台服务器运行的进程个数由配置文件指定，并行计算过程中没有考虑服务器之间的负载均衡问题，可能存在负载均衡不理想的情况;点对点通信采用阻塞机制，通信与计算的重叠度不高。因此，未来的工作是研究弹道仿真计算的并行算法，任务内部并行计算，进一步提高并行的粒度;寻找方案，解决服务器之间的负载均衡问题;在保证数据的有效性下，可以尝试使用非阻塞机制，通信和计算重叠进行，进一步缩短计算时间，提高计算效率;尝试将并行计算技术应用到其他工程领域中。

［1］ 格兰玛.并行计算导论第二版［M］.张武，译.北京:中国机械出版社，2005.Grama A.Introduction to Parallel Computing［M］.2nded.Zhang Wu，transl.Beijing:China Machine Press，2005.

［2］ 都志辉.高性能计算并行编程技术—并行程序设计［M］.北京:清华大学出版社，2001.(Du Zhihui.High Performance Computing Technology-Parallel Program Design［M］.Beijing:Tsinghua University press，2001.)

［3］ 王萃寒，赵展，许小刚，等.分布式并行计算环境:MPI［J］.计算机科学，2003，30(1):25-26.(Wang Cuihan，Zhao Zhan，Xu Xiaogang，et al.The Distributed Parallel Computing Environment:MPI［J］.Computer Science，2003，30(1):25-26.)

［4］ 吕捷，张天序，张必银.MPI并行计算在图像处理方面的应用［J］.红外与激光工程，2004，33(5):496-499.(Lv Jie，Zhang Tianxu，Zhang Biyin.MPI Parallel Computing in the Application of Image Processing ［J］.Infrared and Laser Engineering，2004，33(5):496-499.)

［5］ Dongarra J，Foster I，Fox G.并行计算综论［J］.摩根考夫曼，2005:40-68.(Dongarra J，Foster I，Fox G，et al.Sourcebook of Parallel Computing ［J］.Morgan Kaufmann，2005:40-68.)

［6］ Hwang Kai，Brist F A.计算机体系结构和并行处理方法［J］.纽约:麦格劳-希尔，1984:13-21.(Hwang Kai，Brist F A.Computer Architecture and Parallel Processing［J］.New York:MaGraw-Hill，1984:13-21.)

［7］ 计永昶，丁卫群，陈国良，等.一种实用的并行计算模型［J］.计算机学报，2001，24(4):437-441.(Ji Yongchang，Ding Weiqun，Chen Guoliang，et al.A Practical Parallel Computing Model［J］.Journal of Computer，2001，24(4):437-441.)

［8］ 姚丽萍，王远飞.基于MPI的大气污染扩散模型的并行计算研究［J］.计算机工程，2005，31(22):54-57.(Yao Liping，Wang Yuanfei.Parallel Computing Research of Air Pollution Diffusion Model Based on MPI［J］.Computer Engineering，2005，31(22):54-57.)