基于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.)