ＳＭＰ集群上的混合并行計算

1 引言

并行計算機體系結構的一個發展趨勢是SMP（Symmetric Multiprocessor）集群系統。它們是由擁有多個處理器的SMP節點和連接各節點間的快速網絡構成的多級體系結構。理想的并行編程方案可使應用程序設計者能以最有效的方法使用這個混合的硬件結構，獲得理想的性能而不會引起由其導致的任何開銷。

在分布式內存的系統上，使用MPI的消息傳遞已經被廣泛的應用[1-4]，但是，大多數情況下，特別是在大規模節點下，采用純的MPI并行模型并不能取得理想的性能[5]。此外，OpenMP已經成為共享存儲系統編程的工業標準。由于SMP集群同時具有共享存儲和分布存儲兩極存儲結構，因此節點內采用OpenMP進行多線程化、節點間采用消息傳遞的混合并行模式可以更好的利用SMP集群的特性 [6] 。

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

2 MPI和OpenMP并行模型

在并行計算領域，MPI和OpenMP是最為流行的編程模型。

2.1 MPI并行模型

消息傳遞編程模型是使用顯式方式控制并行性的分布存儲模型，MPI是這一模型的事實標準。MPI可移植到分布和共享存儲體系結構上，而且允許靜態任務調度。顯式并行通常提供了一個更好的性能和可移植性。特別適用于粗粒度的并行，使用MPI實現單程序多數據（SPMD）并行模型時，每個進程只能讀寫本地內存中的數據，對遠程數據的訪問則通過進程間顯式的消息傳遞（庫函數調用）來完成的。

MPI包含了多種優化的組通信庫函數，可供編程人員選擇使用最佳的通信模式。但是，MPI并行模型也有其不足之處，比如：細粒度的并行會引發大量的通信；動態負載平衡困難；并行化改進需要大量的修改原有的串行代碼；調試難度大。

2.2 OpenMP并行模型

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

OpenMP的編程相對簡單，充分利用了共享存儲體系結構的特點，避免了消息傳遞的開銷。雖然它也支持粗粒度的并行，但主要還是針對細粒度的循環級并行。OpenMP的另一個特點在于將串行程序轉換為并行程序時無須對代碼作大的改動。其不足之處有只能在共享存儲結構的機器上運行；數據的放置策略不當可能會引發其他問題；并行化的循環粒度過小會增加系統開銷等。

3 混合并行方法

3.1 混合并行的實現方法

為了充分利用SMP集群層次存儲結構的特點，可以考慮將上述兩種編程模型相結合，實現MPI/OpenMP的混合編程模型。該模型同樣具有層次結構:上層的MP I表示節點間的并行；下層的OpenMP表示節點內的多線程并行：首先對問題進行區域分解，將任務劃分成通信不密集的幾個部分，每個部分分配到一個SMP節點上，節點間通過MPI消息傳遞進行通信；然后在每個進程內采用OpenMP編譯制導語句再次分解，并分配到SMP的不同處理器上由多個線程并行執行，節點內通過共享存儲進行通信。圖1描述了SMP集群上MPI/OpenMP混合編程模型的實現機制。

3.2 節點內并行的性能測試

本文首先測試了節點內并行的性能，測試在Intel Xeon Woodcrest 2.6G （雙核）的平臺上進行，結果如圖2和圖3所示。

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

3.3 混合并行的優點

MPI和OpenMP的混合編程模型提供了節點間和節點內的兩級并行機制，綜合了進程間各個區域的粗粒度并行和進程內部循環級的細粒度并行。實踐證明，在很多情況下其執行效率高于純MPI和OpenMP的程序，混合并行模型解決了一些它們無法解決的問題，比如：

（1）負載平衡問題[11]。混合并行模型很好解決了單純MPI程序不容易實現負載平衡的問題，從而提高了并行程序的性能和可擴展性。

（2）通信帶寬和延遲問題[11]。MPI并行程序進程間的通信帶寬和延遲問題可能會嚴重影響程序的執行性能。混合模型的程序將減少通信的次數，并且OpenMP的線程級并行具有較小的延遲。

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

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

4 Napa軟件的并行化測試

4.1 Napa軟件介紹

NAPA軟件是南京航空航天大學自主研發的CFD軟件，可以計算具有復雜氣動造型的三維內外流耦合流場和旋轉流場，該軟件已經經過了大量的算例和實驗數據驗證。

本文前期的工作[13]實現了NAPA軟件的并行化以及串行優化，比較了并行和串行軟件的計算結果，結果表明：對NAPA軟件的并行化改進和優化是成功的，在此基礎上，本文針對NAPA軟件進行了MPI+OpenMP的混合并行改進和并行優化，并在大規模節點上對比了混合并行和純MPI的性能。

4.2 測試平臺介紹

本文的計算平臺節點包括2個Socket（x86平臺， 主頻 2.6 G 雙核）和8G內存，計算節點共32個，千兆交換機，操作系統為Red Hat 9.0，編譯器為Intel Compiler 9.0，消息傳遞庫為Mpich 1.2.7。

4.3 性能評價方法

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

4.4 性能測試

本文采用不同的進程數對平板流動進行了測試，該算例中采用多塊網格結構，本文下面的所有的計算負載和通訊負載都是都是平衡的，圖4給出了四組不同計算規模下的加速比。其中，圖中標出的是一塊網格的網格點數（共128塊），另外，在本測試中，由于迭代步較少，I/O占用會影響統計時間的準確度，因此，下面測試中未計入流場計算結束后的文件輸出。對于純MPI的測試，本文給每個處理核分配一個進程，而MPI+OpenMP混合并行的測試，本文對每個Socket分配一個進程，同時，每個Socket上又分配2個線程。

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

5結束語

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

參考文獻:

[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] 呂曉斌，蘭黔章，朱自強.二維跨音速Euler方程分區并行算法[J].北京航空航天大學學報，2000，26（2）：194-197

[4] 朱國林，李樹民，王開春.維低速NS方程的并行計算[J].空氣動力學學報，2002.

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

[6] 趙永華，遲學斌.基于SMP集群的OpenMP和MPI 混合編程模型及有效實現[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集群的多層次并行編程模型與并行優化技術[J].計算機應用研究，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] 金君，梁德旺，黃國平，雷雨冰.NAPA軟件的并行化研究和效率分析[J].南京航空航天大學學報，2006，38（4）.