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

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

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

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

1 MPI簡介

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

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

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

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

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

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

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

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

3 彈道仿真并行性分析

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

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

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

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

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

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

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

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

4.1 任務(wù)劃分

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

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

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

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

任務(wù)組合可以提高性能和減少任務(wù)開銷，映射是為了將任務(wù)分配到各個處理器。任務(wù)組合與映射的具體實現(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é)點個數(shù);Tp為在p個節(jié)點上并行計算彈道的時間;Ts為單機運算耗時;Sp為加速比，是衡量并行計算速度的參數(shù);Fp是衡量并行計算效率的參數(shù)，表示并行計算對計算機資源的利用率。

本文的測試環(huán)境為4臺刀片服務(wù)器組成的機群系統(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)軟件運行的環(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é)點的加速比和并行計算效率分別見圖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ù)據(jù)說明隨著CPU核數(shù)的增加，加速比增大趨勢變緩，并行計算效率逐步降低，這是因為在彈道計算任務(wù)規(guī)模不變的情況下，隨著CPU核數(shù)的增加，進程之間的通信開銷逐漸增大，導(dǎo)致計算效率下降，加速比增大變緩。

6 結(jié)論

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

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

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

［1］ 格蘭瑪.并行計算導(dǎo)論第二版［M］.張武，譯.北京:中國機械出版社，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］.計算機科學(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í)煨?，張必銀.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.計算機體系結(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)群，陳國良，等.一種實用的并行計算模型［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］ 姚麗萍，王遠飛.基于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.)