基于MPI的彈道仿真的并行計(jì)算研究

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

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

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

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

1 MPI簡(jiǎn)介

目前，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è)界廣泛支持的并行計(jì)算標(biāo)準(zhǔn)，它具有移植性好、功能強(qiáng)大和效率高等優(yōu)點(diǎn)，而且具有多種不同的免費(fèi)、高效、實(shí)用的版本。MPI從整體上說(shuō)是一個(gè)優(yōu)秀的、標(biāo)準(zhǔn)的分布式并行計(jì)算平臺(tái)，但其在某些方面還存在不足:MPI沒(méi)有提供容錯(cuò)的機(jī)制，并行應(yīng)用程序以一個(gè)進(jìn)程組的方式運(yùn)行時(shí)，當(dāng)進(jìn)程組中的一個(gè)進(jìn)程或計(jì)算機(jī)結(jié)點(diǎn)失敗后，整個(gè)并行應(yīng)用程序都將失敗［3］。MPI的實(shí)現(xiàn)采用程序體形式，將并行計(jì)算和網(wǎng)絡(luò)通信的細(xì)節(jié)隔離開(kāi)來(lái)，從而降低了并行編程的復(fù)雜性。MPICH是MPI1.2標(biāo)準(zhǔn)的一個(gè)完全實(shí)現(xiàn)，也是應(yīng)用范圍最廣的一種并行及分布式環(huán)境。本文采用該環(huán)境進(jìn)行并行計(jì)算。

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

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

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

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

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

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

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

3 彈道仿真并行性分析

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

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

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

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

圖2 彈道仿真的并行計(jì)算流程圖

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

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

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

4.1 任務(wù)劃分

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

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

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

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

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

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

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

5 性能分析

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

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

本文的測(cè)試環(huán)境為4臺(tái)刀片服務(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。彈道并行計(jì)算程序由C語(yǔ)言編寫(xiě)，并行計(jì)算環(huán)境為MPICH2-1.4.1p1。表1中的計(jì)算時(shí)間是5次不同CPU核數(shù)并行計(jì)算的時(shí)間均值。

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

表1 串行計(jì)算與并行計(jì)算的性能比較

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

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

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

6 結(jié)論

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

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

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

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

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

［3］ 王萃寒，趙展，許小剛，等.分布式并行計(jì)算環(huán)境:MPI［J］.計(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并行計(jì)算在圖像處理方面的應(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ì)算綜論［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ì)算機(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］ 計(jì)永昶，丁衛(wèi)群，陳國(guó)良，等.一種實(shí)用的并行計(jì)算模型［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(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.)