基于MPI的彈道仿真的并行計算研究

鐘新玉 王 恂 張學(xué)軍

北京控制與電子技術(shù)研究所，北京100038

隨著科學(xué)技術(shù)的飛速發(fā)展和所研究問題的規(guī)模和復(fù)雜性的提高，越來越多的大規(guī)模科學(xué)工程計算問題對計算機(jī)的運(yùn)行速度提出了非常高的要求。近年來，微處理器的性能不斷提高，存儲空間日益擴(kuò)大，高速局域網(wǎng)的逐步發(fā)展使得可以利用相對廉價的計算機(jī)構(gòu)建高性能的計算機(jī)機(jī)群系統(tǒng)。與傳統(tǒng)的超級計算機(jī)相比，計算機(jī)機(jī)群系統(tǒng)具有較高的性價比和良好的可擴(kuò)展性，可以滿足不同規(guī)模的大型計算問題。

并行計算是解決大型復(fù)雜計算問題的主要方法之一，其基本思想是根據(jù)一定的規(guī)則將一個大的計算問題分解成許多小的子問題，將這些子問題分配調(diào)度到高性能計算平臺的不同節(jié)點(diǎn)上進(jìn)行計算。將大的問題合理的分解成小問題進(jìn)行并行計算，可以大大縮短問題的處理時間，提高軟硬件資源的利用率。并行計算的應(yīng)用已遍布天氣預(yù)報、石油勘探、航空航天、核能利用和生物工程等領(lǐng)域，理論研究與應(yīng)用普及均取得了很大進(jìn)展［1］。

1 MPI簡介

目前，MPI(Message Passing Interface)是一種比較著名的應(yīng)用于并行環(huán)境的消息傳遞標(biāo)準(zhǔn)，由MPI論壇(MPI Forum)推出，制定該標(biāo)準(zhǔn)的目的是提高并行程序的可移植性和易用性［2］。MPI現(xiàn)已成為產(chǎn)業(yè)界廣泛支持的并行計算標(biāo)準(zhǔn)，它具有移植性好、功能強(qiáng)大和效率高等優(yōu)點(diǎn)，而且具有多種不同的免費(fèi)、高效、實(shí)用的版本。MPI從整體上說是一個優(yōu)秀的、標(biāo)準(zhǔn)的分布式并行計算平臺，但其在某些方面還存在不足:MPI沒有提供容錯的機(jī)制，并行應(yīng)用程序以一個進(jìn)程組的方式運(yùn)行時，當(dāng)進(jìn)程組中的一個進(jìn)程或計算機(jī)結(jié)點(diǎn)失敗后，整個并行應(yīng)用程序都將失?。?］。MPI的實(shí)現(xiàn)采用程序體形式，將并行計算和網(wǎng)絡(luò)通信的細(xì)節(jié)隔離開來，從而降低了并行編程的復(fù)雜性。MPICH是MPI1.2標(biāo)準(zhǔn)的一個完全實(shí)現(xiàn)，也是應(yīng)用范圍最廣的一種并行及分布式環(huán)境。本文采用該環(huán)境進(jìn)行并行計算。

2 提高彈道仿真并行計算效率的方法

某系統(tǒng)軟件中需要進(jìn)行大量的彈道仿真計算，每條彈道仿真中有大量復(fù)雜的計算模型和矩陣運(yùn)算，每條彈道計算時間約為1.5s，若系統(tǒng)軟件要進(jìn)行1000條的彈道計算，總的計算時間約為0.5h，而系統(tǒng)軟件需要在1h內(nèi)完成全部功能計算，且彈道仿真的計算時間占系統(tǒng)總運(yùn)行時間的比重很小，這大大超過了系統(tǒng)軟件的運(yùn)行時間，無法滿足系統(tǒng)性能要求。因此，需要縮短彈道計算時間，而并行計算是當(dāng)前提高計算效率的有效方式之一，可以解決總體計算時間過長的不足，大大縮短系統(tǒng)計算的時間，提高軟硬件資源的利用率。

并行計算的任務(wù)是減少程序運(yùn)行時間。如何在最短的時間內(nèi)完成計算，提高運(yùn)行效率，可以從以下幾個方面考慮［4］:

1)減少通信量。并行計算進(jìn)程之間肯定存在數(shù)據(jù)通信。要去掉不必要的數(shù)據(jù)通信，盡量減少數(shù)據(jù)通信量和通信時間;

2)減少通信次數(shù)。每一次數(shù)據(jù)通信都要根據(jù)相應(yīng)的協(xié)議對數(shù)據(jù)進(jìn)行打包等操作，會消耗額外CPU時間;

3)利用通信與計算的重疊提高運(yùn)行效率。MPI提供了非阻塞的通信方式，進(jìn)程在通信沒有完成時可以繼續(xù)進(jìn)行計算。正確的使用通信與計算的重疊能提高算法的整體運(yùn)行效率;

4)采用性能相同的計算機(jī)構(gòu)建計算機(jī)機(jī)群。采用相同計算機(jī)的目的是使各節(jié)點(diǎn)的性能一致，同時簡化系統(tǒng)的管理，方便并行編程時計算任務(wù)的分割，提高計算速度。

3 彈道仿真并行性分析

并行計算分為時間并行和空間并行，主要研究的是空間上的并行問題［5-6］，所采用的高性能并行體系主要有5類:并行向量處理機(jī)(PVP)、對稱多處理共享存儲并行機(jī)(SMP)、大規(guī)模并行處理機(jī)(MPP)、工作站機(jī)群(COW)和分布式共享存儲處理機(jī)(DSM)。COW與巨型機(jī)和MPP系統(tǒng)等高性能并行體系相比，具有高性價比，可擴(kuò)展性好，結(jié)構(gòu)靈活等特點(diǎn)，與以往的并行系統(tǒng)的不同主要表現(xiàn)在它的異質(zhì)性和非獨(dú)占性，即組成系統(tǒng)的工作站的計算能力各不相同，并且每個工作站上可能有其他用戶計算在執(zhí)行［7］。

為了在多個處理器節(jié)點(diǎn)上合理地進(jìn)行任務(wù)調(diào)度以提高計算效率，設(shè)計出合理的并行方案，需先對彈道仿真計算模型的可并行性進(jìn)行分析。每條彈道仿真計算都有相同的輸入數(shù)據(jù)和數(shù)據(jù)類型相同的輸出數(shù)據(jù)，仿真計算之間的數(shù)據(jù)交互量很少，仿真計算可以獨(dú)立的運(yùn)行。仿真計算結(jié)束之后，將計算結(jié)果發(fā)送給數(shù)據(jù)交互中心，數(shù)據(jù)交互中心負(fù)責(zé)分發(fā)初始數(shù)據(jù)給各個彈道計算，并接收彈道仿真計算的結(jié)果。因此，彈道仿真并行計算結(jié)構(gòu)示意圖如圖1所示。

上述過程中，每個彈道仿真計算是獨(dú)立進(jìn)行的，所以多條彈道仿真計算可以實(shí)行并行化。為了讓多個任務(wù)能夠自動地進(jìn)行計算，減少進(jìn)程間的通信量，采用了任務(wù)并行的方案。系統(tǒng)軟件和彈道并行計算運(yùn)行在不同的計算機(jī)上，因此采取主從式的并行計算模式，即由一個主進(jìn)程先讀入彈道仿真計算的初始數(shù)據(jù)，并將其分發(fā)到各個子進(jìn)程，根據(jù)一定的算法將N條彈道計算分配到各子進(jìn)程，再由各個子進(jìn)程負(fù)責(zé)相應(yīng)彈道仿真計算，最后由數(shù)據(jù)交互中心匯總仿真結(jié)果數(shù)據(jù)。這樣通過有效的任務(wù)分解和任務(wù)并行來提高運(yùn)算速度。彈道仿真的并行計算流程如圖2所示。

圖1 彈道仿真的并行計算結(jié)構(gòu)示意圖

圖2 彈道仿真的并行計算流程圖

4 并行計算設(shè)計與實(shí)現(xiàn)

并行算法設(shè)計中最常用的是PCAM方法，即劃分、通信、組合和映射。劃分是將一個大問題平均劃分成若干小問題，并讓其在各個處理器上同時執(zhí)行;通信是在分析執(zhí)行過程中，協(xié)調(diào)和交換數(shù)據(jù)與任務(wù);組合則是將較小的問題組合到一起，以提高性能和減少任務(wù)開銷;映射則是將任務(wù)分配到每個處理器上。并行算法不僅要考慮問題本身，而且還要考慮所使用的并行模型，網(wǎng)絡(luò)連接等［8］。

為提高并行計算的效率，按照PCAM法，根據(jù)彈道編號按區(qū)劃分計算任務(wù)，并把任務(wù)映射到各個處理器。軟件采用主從式的計算模式，主進(jìn)程負(fù)責(zé)分發(fā)初始數(shù)據(jù)和匯總計算結(jié)果，子進(jìn)程負(fù)責(zé)彈道計算。為減少通信開銷，只有主進(jìn)程和子進(jìn)程之間進(jìn)行通信和數(shù)據(jù)交換。并行計算采用基于MPI消息傳遞的并行編程模型實(shí)現(xiàn)。為保證通信的可靠性和數(shù)據(jù)的有效性，點(diǎn)對點(diǎn)通信采取阻塞發(fā)送和接收機(jī)制。各個并行執(zhí)行的部分之間通過消息傳遞來交換信息、協(xié)調(diào)同步和控制執(zhí)行。

4.1 任務(wù)劃分

并行計算的基本思想是將原任務(wù)分解成若干子任務(wù)，并將子任務(wù)分配到處理器上，由多個進(jìn)程并行執(zhí)行。通過對彈道仿真的并行性分析，對彈道仿真的計算可以分區(qū)進(jìn)行。分區(qū)計算的目的是分解彈道仿真計算任務(wù)，即將計算任務(wù)劃分為若干子域，機(jī)群的每個處理器負(fù)責(zé)處理其中的某一個子域，因此劃分的區(qū)域個數(shù)與實(shí)際應(yīng)用中處理器的個數(shù)相關(guān)。彈道并行計算平臺采用同構(gòu)計算服務(wù)器，每臺計算服務(wù)器的計算性能相同，分配給各個計算服務(wù)器的計算任務(wù)量相當(dāng)，最大限度地減少服務(wù)器之間的數(shù)據(jù)轉(zhuǎn)移，以達(dá)到各處理器負(fù)載平衡。

4.2 數(shù)據(jù)通信

每條彈道仿真計算都有相同的輸入數(shù)據(jù)和數(shù)據(jù)類型相同的輸出數(shù)據(jù)，計算之間的數(shù)據(jù)交互量很少，可以獨(dú)立運(yùn)行。彈道仿真計算采用主從式計算模式，數(shù)據(jù)交互中心(主進(jìn)程)負(fù)責(zé)分發(fā)初始數(shù)據(jù)，并匯總計算結(jié)果;從進(jìn)程接收主進(jìn)程發(fā)送的初始化數(shù)據(jù)，并進(jìn)行彈道仿真計算，待彈道仿真計算結(jié)束之后，將計算結(jié)果發(fā)送給數(shù)據(jù)交互中心(主進(jìn)程)。只有主從進(jìn)程之間進(jìn)行通信，從進(jìn)程之間無需進(jìn)行數(shù)據(jù)交互。點(diǎn)對點(diǎn)通信采取阻塞發(fā)送和接收機(jī)制，可以保證通信的可靠性和數(shù)據(jù)的有效性。

4.3 任務(wù)組合與映射

任務(wù)組合可以提高性能和減少任務(wù)開銷，映射是為了將任務(wù)分配到各個處理器。任務(wù)組合與映射的具體實(shí)現(xiàn)方案如下:所有彈道仿真計算數(shù)量為Total，處理器總數(shù)量為size。

首先，每個處理器至少可以分配的彈道仿真計算任務(wù)量為AverageTaskNumber，則

這些剩余的彈道仿真任務(wù)量LeftTaskNumber將分配到處理器，規(guī)定編號小的處理器分得更多的計算任務(wù)，這樣就可以得到編號為rank(0≤rank≤size-1)的處理器分配的彈道任務(wù)的數(shù)量TaskNumPerProcess，則

5 性能分析

評價并行計算性能需要引入2個參數(shù):加速比Sp和并行效率Fp［4］。計算如下式

式中，p為節(jié)點(diǎn)個數(shù);Tp為在p個節(jié)點(diǎn)上并行計算彈道的時間;Ts為單機(jī)運(yùn)算耗時;Sp為加速比，是衡量并行計算速度的參數(shù);Fp是衡量并行計算效率的參數(shù)，表示并行計算對計算機(jī)資源的利用率。

本文的測試環(huán)境為4臺刀片服務(wù)器組成的機(jī)群系統(tǒng)。刀片服務(wù)器的操作系統(tǒng)為:Windows Server 2008 HPC Edition;CPU為Intel(R)Xeon(R)CPU X5650，頻率為2.67GHZ，核數(shù)為12;內(nèi)存容量為24GB。系統(tǒng)軟件運(yùn)行的環(huán)境為:操作系統(tǒng)是Windows XP SP3，CPU 是 Intel(R)Xeon(R)CPU X5690，頻率為 3.47GHZ，核數(shù)為6;內(nèi)存容量為4GB。彈道并行計算程序由C語言編寫，并行計算環(huán)境為MPICH2-1.4.1p1。表1中的計算時間是5次不同CPU核數(shù)并行計算的時間均值。

1000條彈道串行與并行計算的性能比較如表1所示。不同節(jié)點(diǎn)的加速比和并行計算效率分別見圖3和圖4。

表1 串行計算與并行計算的性能比較

圖3 不同數(shù)量CPU核數(shù)的加速比比較

圖4 不同數(shù)量CPU核數(shù)的并行計算效率比較

從表1，圖3和4可以看出，CPU核數(shù)為24時，1000條彈道并行計算時間約為1min，即可滿足系統(tǒng)性能的要求，并且加速比和并行計算效率分別為23.127，96.36%，獲得了較高的加速比和計算效率，這充分說明基于MPI的彈道并行計算方案是可行的。同時實(shí)驗數(shù)據(jù)說明隨著CPU核數(shù)的增加，加速比增大趨勢變緩，并行計算效率逐步降低，這是因為在彈道計算任務(wù)規(guī)模不變的情況下，隨著CPU核數(shù)的增加，進(jìn)程之間的通信開銷逐漸增大，導(dǎo)致計算效率下降，加速比增大變緩。

6 結(jié)論

1)基于MPI的消息傳遞機(jī)制實(shí)現(xiàn)了1000條彈道仿真的并行計算。采用主從式的計算模式，主進(jìn)程廣播彈道仿真的初始化數(shù)據(jù)，收集并行計算結(jié)果;從進(jìn)程收到廣播數(shù)據(jù)后，開始彈道計算，待計算結(jié)束后，將計算結(jié)果發(fā)送給主進(jìn)程。主、從進(jìn)程各司其職，僅在主進(jìn)程和從進(jìn)程之間通信，減少了進(jìn)程之間的通信開銷，大大提高了彈道仿真的計算效率。

2)試驗數(shù)據(jù)結(jié)果表明，用傳統(tǒng)的串行計算1000條彈道仿真時間約為1502s，而采用并行計算方式，在CPU核數(shù)為48時，計算時間約為33s，計算時間約為串行計算時間的1/45;將基本MPI的并行計算技術(shù)應(yīng)用到彈道仿真計算中，是一次成功的嘗試，大大縮短了彈道仿真計算的時間，系統(tǒng)性能明顯提升。

3)文中的彈道仿真并行計算是任務(wù)間的并行，并行粒度不高;并行計算硬件平臺是同構(gòu)機(jī)群系統(tǒng)，機(jī)群中的每臺服務(wù)器運(yùn)行的進(jìn)程個數(shù)由配置文件指定，并行計算過程中沒有考慮服務(wù)器之間的負(fù)載均衡問題，可能存在負(fù)載均衡不理想的情況;點(diǎn)對點(diǎn)通信采用阻塞機(jī)制，通信與計算的重疊度不高。因此，未來的工作是研究彈道仿真計算的并行算法，任務(wù)內(nèi)部并行計算，進(jìn)一步提高并行的粒度;尋找方案，解決服務(wù)器之間的負(fù)載均衡問題;在保證數(shù)據(jù)的有效性下，可以嘗試使用非阻塞機(jī)制，通信和計算重疊進(jìn)行，進(jìn)一步縮短計算時間，提高計算效率;嘗試將并行計算技術(shù)應(yīng)用到其他工程領(lǐng)域中。

［1］ 格蘭瑪.并行計算導(dǎo)論第二版［M］.張武，譯.北京:中國機(jī)械出版社，2005.Grama A.Introduction to Parallel Computing［M］.2nded.Zhang Wu，transl.Beijing:China Machine Press，2005.

［2］ 都志輝.高性能計算并行編程技術(shù)—并行程序設(shè)計［M］.北京:清華大學(xué)出版社，2001.(Du Zhihui.High Performance Computing Technology-Parallel Program Design［M］.Beijing:Tsinghua University press，2001.)

［3］ 王萃寒，趙展，許小剛，等.分布式并行計算環(huán)境:MPI［J］.計算機(jī)科學(xué)，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］ 呂捷，張?zhí)煨颍瑥埍劂y.MPI并行計算在圖像處理方面的應(yīng)用［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，F(xiàn)oster I，F(xiàn)ox G.并行計算綜論［J］.摩根考夫曼，2005:40-68.(Dongarra J，F(xiàn)oster I，F(xiàn)ox G，et al.Sourcebook of Parallel Computing ［J］.Morgan Kaufmann，2005:40-68.)

［6］ Hwang Kai，Brist F A.計算機(jī)體系結(jié)構(gòu)和并行處理方法［J］.紐約:麥格勞-希爾，1984:13-21.(Hwang Kai，Brist F A.Computer Architecture and Parallel Processing［J］.New York:MaGraw-Hill，1984:13-21.)

［7］ 計永昶，丁衛(wèi)群，陳國良，等.一種實(shí)用的并行計算模型［J］.計算機(jī)學(xué)報，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］ 姚麗萍，王遠(yuǎn)飛.基于MPI的大氣污染擴(kuò)散模型的并行計算研究［J］.計算機(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.)