1 引言

并行計(jì)算機(jī)體系結(jié)構(gòu)的一個(gè)發(fā)展趨勢(shì)是SMP（Symmetric Multiprocessor）集群系統(tǒng)。它們是由擁有多個(gè)處理器的SMP節(jié)點(diǎn)和連接各節(jié)點(diǎn)間的快速網(wǎng)絡(luò)構(gòu)成的多級(jí)體系結(jié)構(gòu)。理想的并行編程方案可使應(yīng)用程序設(shè)計(jì)者能以最有效的方法使用這個(gè)混合的硬件結(jié)構(gòu)，獲得理想的性能而不會(huì)引起由其導(dǎo)致的任何開銷。

在分布式內(nèi)存的系統(tǒng)上，使用MPI的消息傳遞已經(jīng)被廣泛的應(yīng)用[1-4]，但是，大多數(shù)情況下，特別是在大規(guī)模節(jié)點(diǎn)下，采用純的MPI并行模型并不能取得理想的性能[5]。此外，OpenMP已經(jīng)成為共享存儲(chǔ)系統(tǒng)編程的工業(yè)標(biāo)準(zhǔn)。由于SMP集群同時(shí)具有共享存儲(chǔ)和分布存儲(chǔ)兩極存儲(chǔ)結(jié)構(gòu)，因此節(jié)點(diǎn)內(nèi)采用OpenMP進(jìn)行多線程化、節(jié)點(diǎn)間采用消息傳遞的混合并行模式可以更好的利用SMP集群的特性 [6] 。

近幾年來，多極混合并行計(jì)算已經(jīng)被應(yīng)用于許多應(yīng)用中[7]，并且取得了較大的成功[8-10]，本文首先介紹了OpenMP和MPI并行模型和混合并行方法，以Napa軟件為例，進(jìn)行了MPI+OpenMP混合并行改進(jìn)，最后在大規(guī)模節(jié)點(diǎn)上對(duì)比了混合并行和純MPI的性能。

2 MPI和OpenMP并行模型

在并行計(jì)算領(lǐng)域，MPI和OpenMP是最為流行的編程模型。

2.1 MPI并行模型

消息傳遞編程模型是使用顯式方式控制并行性的分布存儲(chǔ)模型，MPI是這一模型的事實(shí)標(biāo)準(zhǔn)。MPI可移植到分布和共享存儲(chǔ)體系結(jié)構(gòu)上，而且允許靜態(tài)任務(wù)調(diào)度。顯式并行通常提供了一個(gè)更好的性能和可移植性。特別適用于粗粒度的并行，使用MPI實(shí)現(xiàn)單程序多數(shù)據(jù)（SPMD）并行模型時(shí)，每個(gè)進(jìn)程只能讀寫本地內(nèi)存中的數(shù)據(jù)，對(duì)遠(yuǎn)程數(shù)據(jù)的訪問則通過進(jìn)程間顯式的消息傳遞（庫函數(shù)調(diào)用）來完成的。

MPI包含了多種優(yōu)化的組通信庫函數(shù)，可供編程人員選擇使用最佳的通信模式。但是，MPI并行模型也有其不足之處，比如：細(xì)粒度的并行會(huì)引發(fā)大量的通信；動(dòng)態(tài)負(fù)載平衡困難；并行化改進(jìn)需要大量的修改原有的串行代碼；調(diào)試難度大。

2.2 OpenMP并行模型

OpenMP使用Fork-Join的并行執(zhí)行模式。開始時(shí)由一個(gè)主線程執(zhí)行程序，該線程一直串行地執(zhí)行，直到遇到第一個(gè)并行化制導(dǎo)語句后才開始并行執(zhí)行。過程如下: ①Fork：主線程創(chuàng)建一隊(duì)線程并行執(zhí)行并行域中的代碼；②Join：當(dāng)各線程執(zhí)行完畢后被同步或中斷，最后又只有主線程在執(zhí)行。

OpenMP的編程相對(duì)簡(jiǎn)單，充分利用了共享存儲(chǔ)體系結(jié)構(gòu)的特點(diǎn)，避免了消息傳遞的開銷。雖然它也支持粗粒度的并行，但主要還是針對(duì)細(xì)粒度的循環(huán)級(jí)并行。OpenMP的另一個(gè)特點(diǎn)在于將串行程序轉(zhuǎn)換為并行程序時(shí)無須對(duì)代碼作大的改動(dòng)。其不足之處有只能在共享存儲(chǔ)結(jié)構(gòu)的機(jī)器上運(yùn)行；數(shù)據(jù)的放置策略不當(dāng)可能會(huì)引發(fā)其他問題；并行化的循環(huán)粒度過小會(huì)增加系統(tǒng)開銷等。

3 混合并行方法

3.1 混合并行的實(shí)現(xiàn)方法

為了充分利用SMP集群層次存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，可以考慮將上述兩種編程模型相結(jié)合，實(shí)現(xiàn)MPI/OpenMP的混合編程模型。該模型同樣具有層次結(jié)構(gòu):上層的MP I表示節(jié)點(diǎn)間的并行；下層的OpenMP表示節(jié)點(diǎn)內(nèi)的多線程并行：首先對(duì)問題進(jìn)行區(qū)域分解，將任務(wù)劃分成通信不密集的幾個(gè)部分，每個(gè)部分分配到一個(gè)SMP節(jié)點(diǎn)上，節(jié)點(diǎn)間通過MPI消息傳遞進(jìn)行通信；然后在每個(gè)進(jìn)程內(nèi)采用OpenMP編譯制導(dǎo)語句再次分解，并分配到SMP的不同處理器上由多個(gè)線程并行執(zhí)行，節(jié)點(diǎn)內(nèi)通過共享存儲(chǔ)進(jìn)行通信。圖1描述了SMP集群上MPI/OpenMP混合編程模型的實(shí)現(xiàn)機(jī)制。

3.2 節(jié)點(diǎn)內(nèi)并行的性能測(cè)試

本文首先測(cè)試了節(jié)點(diǎn)內(nèi)并行的性能，測(cè)試在Intel Xeon Woodcrest 2.6G （雙核）的平臺(tái)上進(jìn)行，結(jié)果如圖2和圖3所示。

其中，Share Socket表示Socket中不同處理核之間的消息傳遞，而Different Socket表示不同Socket之間的消息傳遞?？梢奡hare Socket間的通信性能明顯好于不同Socket 間的通信性能。

3.3 混合并行的優(yōu)點(diǎn)

MPI和OpenMP的混合編程模型提供了節(jié)點(diǎn)間和節(jié)點(diǎn)內(nèi)的兩級(jí)并行機(jī)制，綜合了進(jìn)程間各個(gè)區(qū)域的粗粒度并行和進(jìn)程內(nèi)部循環(huán)級(jí)的細(xì)粒度并行。實(shí)踐證明，在很多情況下其執(zhí)行效率高于純MPI和OpenMP的程序，混合并行模型解決了一些它們無法解決的問題，比如：

（1）負(fù)載平衡問題[11]?；旌喜⑿心Ｐ秃芎媒鉀Q了單純MPI程序不容易實(shí)現(xiàn)負(fù)載平衡的問題，從而提高了并行程序的性能和可擴(kuò)展性。

（2）通信帶寬和延遲問題[11]。MPI并行程序進(jìn)程間的通信帶寬和延遲問題可能會(huì)嚴(yán)重影響程序的執(zhí)行性能。混合模型的程序?qū)p少通信的次數(shù)，并且OpenMP的線程級(jí)并行具有較小的延遲。

（3）通信與計(jì)算的重疊[12]。大多數(shù)MPI實(shí)現(xiàn)都是使用單線程實(shí)現(xiàn)的。這種單線程的實(shí)現(xiàn)可以避免同步和上下文切換的開銷，但是它不能將通信和計(jì)算分開，因此，對(duì)于多處理系統(tǒng)上，單個(gè)的MPI進(jìn)程不能同時(shí)進(jìn)行通信和計(jì)算。MPI+OpenMP混合模型可以選擇主線程或指定一個(gè)線程進(jìn)行通信，而其他線程執(zhí)行計(jì)算，從而實(shí)現(xiàn)了通信與計(jì)算的重疊。

（4）解決少數(shù)應(yīng)用進(jìn)程數(shù)受限的問題。通過混合并行可以更好的利用所有的處理器/核都能得到高效率的應(yīng)用。

4 Napa軟件的并行化測(cè)試

4.1 Napa軟件介紹

NAPA軟件是南京航空航天大學(xué)自主研發(fā)的CFD軟件，可以計(jì)算具有復(fù)雜氣動(dòng)造型的三維內(nèi)外流耦合流場(chǎng)和旋轉(zhuǎn)流場(chǎng)，該軟件已經(jīng)經(jīng)過了大量的算例和實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證。

本文前期的工作[13]實(shí)現(xiàn)了NAPA軟件的并行化以及串行優(yōu)化，比較了并行和串行軟件的計(jì)算結(jié)果，結(jié)果表明：對(duì)NAPA軟件的并行化改進(jìn)和優(yōu)化是成功的，在此基礎(chǔ)上，本文針對(duì)NAPA軟件進(jìn)行了MPI+OpenMP的混合并行改進(jìn)和并行優(yōu)化，并在大規(guī)模節(jié)點(diǎn)上對(duì)比了混合并行和純MPI的性能。

4.2 測(cè)試平臺(tái)介紹

本文的計(jì)算平臺(tái)節(jié)點(diǎn)包括2個(gè)Socket（x86平臺(tái)， 主頻 2.6 G 雙核）和8G內(nèi)存，計(jì)算節(jié)點(diǎn)共32個(gè)，千兆交換機(jī)，操作系統(tǒng)為Red Hat 9.0，編譯器為Intel Compiler 9.0，消息傳遞庫為Mpich 1.2.7。

4.3 性能評(píng)價(jià)方法

并行計(jì)算中，我們把并行程序分成兩部分：即串行部分和并行部分，如果用Ts表示串行部分串行執(zhí)行所需的時(shí)間，Tcomp表示并行部分串行執(zhí)行所需的時(shí)間，Tcomm表示P個(gè)進(jìn)程并行計(jì)算中通訊部分占用的時(shí)間，使用P個(gè)進(jìn)程執(zhí)行的時(shí)間為Tp，那么單進(jìn)程串行執(zhí)行的時(shí)間為：T1=Ts+Tcomp ，P個(gè)進(jìn)程并行執(zhí)行的加速比（Speedup）、并行效率（Efficiency）、通信占用比（η_comm）分別是：

4.4 性能測(cè)試

本文采用不同的進(jìn)程數(shù)對(duì)平板流動(dòng)進(jìn)行了測(cè)試，該算例中采用多塊網(wǎng)格結(jié)構(gòu)，本文下面的所有的計(jì)算負(fù)載和通訊負(fù)載都是都是平衡的，圖4給出了四組不同計(jì)算規(guī)模下的加速比。其中，圖中標(biāo)出的是一塊網(wǎng)格的網(wǎng)格點(diǎn)數(shù)（共128塊），另外，在本測(cè)試中，由于迭代步較少，I/O占用會(huì)影響統(tǒng)計(jì)時(shí)間的準(zhǔn)確度，因此，下面測(cè)試中未計(jì)入流場(chǎng)計(jì)算結(jié)束后的文件輸出。對(duì)于純MPI的測(cè)試，本文給每個(gè)處理核分配一個(gè)進(jìn)程，而MPI+OpenMP混合并行的測(cè)試，本文對(duì)每個(gè)Socket分配一個(gè)進(jìn)程，同時(shí)，每個(gè)Socket上又分配2個(gè)線程。

圖中可以看到，當(dāng)處理核總數(shù)較少的時(shí)候，與MPI+OpenMP 混合并行模型相比，由于MPI的并行粒度相對(duì)較大，因此性能明顯占優(yōu)，進(jìn)程數(shù)小于32的時(shí)候，除了Grid 97*13*25 之外，其余的并行效率都超過了95%，前者性能較低是由于單進(jìn)程上的計(jì)算量相對(duì)其他的計(jì)算較小，因此通信占用就比較大，因此效率較低。隨著處理核的增加，MPI并行模式的通信量也增加，圖4中可以看到，當(dāng)通信量達(dá)到一定規(guī)模之后，不管是Share Socket還是Different Socket的通信帶寬都大大減小，因此在128個(gè)處理核的測(cè)試中，MPI并行模式下的并行效率也明顯降低，相對(duì)來說，而混合并行模型由于減少了通信的進(jìn)程數(shù)，從而減少了計(jì)算中的通信占用比，因此性能較好。

5結(jié)束語

OpenMP+MPI這種混合并行模型相比單純的MPI消息傳遞更能充分利用SMP集群系統(tǒng)，在某些情況下可以改善性能。本文首先對(duì)兩種不同情況下的節(jié)點(diǎn)內(nèi)的通訊進(jìn)行了測(cè)試，表明基于Share Socket的通信性能較好，然后采用MPI+OpenMP混合并行模型對(duì)NAPA軟件進(jìn)行了改進(jìn)和測(cè)試，結(jié)果表明，就NAPA軟件本身而言，采用MPI并行模型在小規(guī)模節(jié)點(diǎn)情況下性能較好，而采用混合并行模型在多節(jié)點(diǎn)情況下可以大大減少通信，從而獲得更好的性能。

參考文獻(xiàn):

[1] Dimitri J. Mavriplis， Michael J. Aftosmis， Marsha Berger， High Resolution Aerospace Applications using the NASA Columbia Supercomputer， 2005

[2] Charles D H.Two-dimensional aerodynamic characteristics of the NACA0012 airfoil in the langley 8-foot transonic pressure tunnel[R].NASA TM-81927，1981

[3] 呂曉斌，蘭黔章，朱自強(qiáng).二維跨音速Euler方程分區(qū)并行算法[J].北京航空航天大學(xué)學(xué)報(bào)，2000，26（2）：194-197

[4] 朱國(guó)林，李樹民，王開春.維低速NS方程的并行計(jì)算[J].空氣動(dòng)力學(xué)學(xué)報(bào)，2002.

[5] 馮云，周淑秋天.MPI+OpenMP混合并行編程模型應(yīng)用研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2006，(2).

[6] 趙永華，遲學(xué)斌.基于SMP集群的OpenMP和MPI 混合編程模型及有效實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2005，22（10）.

[7] D S Henty. Performance of Hybrid message Passing and Shared Memory Parallels for Dircrete Element Modeling[J]， In Proceedings of the ACM/IEEE conference on Supercomputing， Dalas， Texas， United States， 2000:10.

[8] R Rabenseifner， G Wellein. Communication and Optimization Aspects of Parallel programming Models on Hybrid Architecture. International Journal of High Performance Computing Applications， 2003， 17(1).

[9] F Cappello， D Etiemble. MPI Versus MPI+OpenMP on IBM SP for the NAS Benchmarks. In Proceedings of 2000 ACM/IEEE Conference on Supercomputing， Dallas， Texas， USA， IEEE Computer Society Press， 2000

[10] G Krawezik， F Cappello. Performance Comparison of MPI and Three OpenMP Programming Style on Shared Memory Multiprocessors. In ACM SPAA， San Diego， USA， Jun. 2003

[11] 單瑩，吳建平，王正華.基于SMP集群的多層次并行編程模型與并行優(yōu)化技術(shù)[J].計(jì)算機(jī)應(yīng)用研究，2006.

[12] USFMPI：A Multi-threaded Implementation of MPI for Linux Clusters[C] In Proceedings of the 15thInternational Conference on Parallel and Distributed Computing and Systems， Marina del Rey， CA 2003.[J] Scientific Programming， Vol. 9， No 2-3，2001.

[13] 金君，梁德旺，黃國(guó)平，雷雨冰.NAPA軟件的并行化研究和效率分析[J].南京航空航天大學(xué)學(xué)報(bào)，2006，38（4）.