基于ＳＭＰ集群的多層次并行編程模型與并行優化技術

摘 要：詳細描述了適用于SMP集群這種多層次并行體系結構的混合并行編程模型MPI/OpenMP，它提供了實現SMP節點間和節點內多層次并行的機制。在此基礎上結合實用的性能評價方法，分別介紹了MPI，OpenMP和單處理器三個層次上的一些常用和有效的并行優化技術，并指出單處理器性能優化是提高并行程序性能一個不容忽視的問題。

關鍵詞：SMP集群；MPI/OpenMP；并行；優化；單處理器性能優化

中圖法分類號：TP393．09 文獻標識碼：A 文章編號：1001-3695(2006)10-0254-03

Hierarchical Parallel Programming Model and Parallelization

and Optimization Techniques Based on SMP Cluster

SHAN Ying，WU Jianping，WANG Zhenghua

(College of Computer Science， National University of Defence Technology， Changsha Hunan 410073， China)

Abstract:This paper describes the hybrid parallel programming model MPI/OpenMP which is suitable for the hierarchical architecture of SMP cluster in detail. It also provides the interand intronode hierarchical parallelism. Then combined with an available performance evaluation method， a number of effective parallelization and optimization techniques on the MPI， OpenMP and singleprocessor three levels are introduced respectively. Meanwhile， we emphasize that performance optimization on singleprocessor is an important issue which cannot be ignored for improving parallel program performance.

Key words:SMP Cluster;MPI/OpenMP;Parallelization;Optimization;Performance Optimization on Singleprocessor

1 引言

高性能計算機（HPC）按其存儲結構可分為共享存儲結構和分布存儲結構兩大類。當前國內外流行的并行計算機體系結構主要有對稱多處理共享存儲并行機（SMP）、分布共享存儲并行機（DSM）、大規模并行機（MPP）和SMP集群等。其中SMP體系結構具有低通信延遲的特點，可采用多線程機制（如Pthreads）和編譯制導（如OpenMP）并行編程，其實現較為簡單，但缺點是可擴展性較差；MPP體系結構基于分布式存儲，具有良好的可擴展性，主要采用消息傳遞機制，實現標準有MPI，PVM等，但其處理器之間的通信開銷大，編程比較困難。目前，以SMP集群（圖1）為代表的層次并行體系結構計算機發展迅速，成為國內外并行機研制的流行趨勢。

這種體系結構的特點是它結合了SMP和MPP的優點，同時具備節點內共享存儲和節點間分布存儲的層次結構，提供了節點內和節點間的兩級并行。此外，單個處理器內部還存在另一級并行性，即指令級并行（InstructionLevel Parallelism，ILP）。單處理器對局部數據進行串行計算的性能直接影響并行程序的執行性能。多層次并行性的存在，客觀上對并行編程模型與并行優化技術的研究提出了更新更高的要求。

2 多層次并行編程模型

2．1 分布式存儲編程模型MPI

MPI（Message Passing Interface）是由學術界、政府和工業協會共同開發的一個消息傳遞編程模型的實現標準，是目前分布式存儲系統上的主流編程模型。它不是一門獨立的編程語言，而是一個庫，提供了與FORTRAN和C/C++語言的綁定。MPI適用于共享和分布式存儲的并行計算環境，用它編寫的程序可以直接在SMP集群上運行。MPI標準于1994年5月正式發布，最新的MPI 2.0版于1997年推出。

MPI具有可移植性好、功能強大、效率高等優點，特別適用于粗粒度的并行，幾乎被所有多線程操作系統（包括UNIX，Windows NT等）支持，是目前超大規模并行計算最可信賴的平臺。使用MPI實現單程序多數據（SPMD）并行模型時，每個進程只能讀/寫本地內存中的數據，對遠程數據的訪問則通過進程間顯式的消息傳遞（庫函數調用）來完成。

MPI包含了多種優化的組通信庫函數，可供編程人員選擇使用最佳的通信模式。在MPI程序中可以實現計算與通信的重疊，提高并行程序的性能。進程間的通信能夠自然地引發同步，從而減少額外的同步開銷。MPI編程模式的明顯優勢在于可由用戶完全控制對數據的劃分和進程的同步，進而優化數據局部性和工作流。但它也有許多不足之處：消息傳遞和全局操作的開銷非常大；細粒度任務會引發大量的通信；動態負載平衡困難；將串行程序轉換為并行程序需要對代碼作大量改動；程序員完成數據和任務的劃分，編程和調試的難度大。

2．2 共享存儲編程模型OpenMP

目前廣泛使用的共享存儲編程模型有直接使用線程API的Thread（如Pthreads）和基于編譯制導的OpenMP。綜合編程模型的評價標準——計算性能和易用性考慮，OpenMP優于Thread。原因之一是像Pthreads這樣的API被認為是低層原語，需要考慮復雜線程間的同步和互斥；OpenMP命令提供對并發、同步以及數據處理的支持，但不需要顯式設置互斥鎖、條件變量、數據范圍以及初始化。

OpenMP是共享存儲系統編程的工業標準，由OpenMP Architecture Review Board于1997年推出，現已發展到2.0版。它不是一門獨立的語言，而是對基本語言（如FORTRAN，C/C++）的擴展。其目標是為SMP系統提供可移植、可擴展的開發接口。OpenMP規范了一系列的編譯制導、運行庫和環境變量來說明共享存儲結構的并行機制。編譯制導是對程序設計語言的擴展，進一步提供對并行區域、工作共享、同步構造的支持，并且支持數據的共享和私有化。運行庫和環境變量使得用戶可以調整并行程序的執行環境。OpenMP實現的是線程級的并行，線程間通信通過讀/寫共享變量實現。

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

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

2．3 混合編程模型MPI/OpenMP

2．3．1 混合編程模型的實現

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

2．3．2 混合編程模型的優點

MPI與OpenMP的混合編程模型提供了節點間和節點內的兩級并行機制，其貢獻在于結合了進程級的粗粒度并行（如域分解）和循環級的細粒度并行。混合模型的方法適合于具有內在多級結構的大型應用程序。實踐證明，在很多情況下其執行效率高于純MPI和OpenMP程序，解決了一些它們無法解決的問題，主要有：

（1）負載平衡問題。在MPI并行程序中可能出現負載不平衡的問題，使程序的性能受損。而在混合編程模型中，OpenMP能夠很好地解決該問題，彌補了MPI的不足，從而提高并行程序的性能。

（2）MPI進程數受限的問題。一些應用問題存在所需進程數與處理機數目不匹配的問題。若前者太小，則不能充分發揮機器的效率；太大，又無法執行。使用混合編程模型，首先執行MPI分解策略，啟動理想數目的進程，再用OpenMP進一步分解子任務，則可以使所有處理機得到高效利用。

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

（4）細粒度并行問題。OpenMP適合解決細粒度問題，但粒度太小也會增加系統的開銷。當應用問題需要增大并行的粒度時，混合編程模型是個很好的選擇。

2．3．3 混合編程模型需要注意的一些問題

（1）模型要求MPI必須是線程安全的。

（2）要避免在OpenMP并行區域內調用MPI_Init()和MPI的通信函數，后者只能出現在CRITICAL，MASTER或SINGLE結構中，并且應當謹慎使用SINGLE結構。

（3）從可移植性考慮，混合編程時應在每個進程中使用omp_set_num_threads(n)函數定義線程的數目，而不是通過設置環境變量omp_num_threads實現。

（4）不同MPI進程內的線程可以進行點對點的通信，但是必須要注意正確的發送和接收。因為MPI進程內的多線程共享同樣的MPI通信符， 所以不同MPI進程內的線程進行通信時，應該使用顯式的消息標志。

（5）在使用接收的數據前要確保接收操作完成；在發送數據前要確保計算完成；在發送數據完成前不能修改數據。

（6）當每個MPI進程生成不同數目的線程， 即OMP_DYNAMIC為真時， 如果在OpenMP的并行區域內進行MPI的廣播和收集操作， 可能會產生意想不到的問題， 一定要慎用。

上述三種并行編程模型各有各的適用范圍。究竟哪種編程模型最優，則取決于具體的問題、集群的硬件組成、網絡和可用軟件等多種因素。

3 多層次并行與優化技術

如前面所述，SMP集群的體系結構具有多層次的并行性，因此開發基于SMP集群的高效并行程序需要從上到下依次對每個層次的并行性進行充分挖掘。在下面的章節中我們分別介紹各個層次的一些并行與優化技術。

3．1 一種實用的性能評價方法

加速比SP和效率EP是并行程序常用的性能評價標準。設MPI并行程序包含P個進程，TS和TP分別是執行串行程序和并行程序的墻鐘時間，則SP和EP的定義分別為

SP=TS/TP

EP=SP/P

再設Ci，Di分別是第i個進程的CPU執行時間和空閑時間，CT=Ci，DT=Di分別表示所有進程的CPU執行時間和空閑時間總和，參考文獻［4］對EP進一步分解，有

EP=TSTP×P=TSCT+DT=TSCT×CTCT+DT=TSCT×CTTP×P

定義數值效率NEP=TS/CT，它反映應用程序的CPU執行時間在并行計算前后的變化；并行效率PEP=CT/(TP×P)，反映應用程序并行執行時的CPU平均空閑程度。顯然，效率EP等于數值效率NEP=TS/CT與并行效率PEP=CT/(TP×P)的乘積。因此，優化一個并行化應用程序的效率可以分別考察其數值效率和并行效率：①如果數值效率遠小于1，說明增加的冗余計算過多，或者出現Cache沖突現象，需要改進數值算法或并行后的單處理器性能；②如果并行效率遠小于1，則說明存在提高算法并行度和負載平衡能力、優化通信結構、減少通信次數與通信量、重疊計算與通信的必要性；③不能因為效率接近1而忽視對數值效率和并行效率各自的考察和優化。

3．2 MPI并行與優化技術

（1）數據劃分。數據劃分的目的是實現數據并行，它決定了負載平衡情況和通信開銷的大小。數據劃分要使得程序的并行性盡可能地得到開發， 而通信開銷最小且負載平衡， 同時數據劃分要提高操作的局部性。對并行程序進行優化時， 首先要對數據劃分進行分析， 看它是否達到最優。

（2）任務劃分。首先針對具體問題確定合適的劃分點，必要時通過數據/控制相關性轉換與消除以支持劃分；然后實現應用問題并行性到計算平臺并行性的映射，結合數據分布優化技術，減少遠程I/O和消息傳遞。

（3）通信量和通信開銷最小化。編程時將多個單獨的消息合并成一個大消息一次傳遞， 并且集中可以集中的通信，從而減少消息傳遞的啟動次數和時間。另外，盡量采用系統提供的廣播、移位等功能。

（4）動態負載平衡方法。對于負載動態變化的計算問題，采用動態負載平衡的策略可以取得理想的效果。同時需要在負載平衡的系統開銷與負載不平衡所導致的性能損失之間進行折中。

（5）計算與通信的重疊。如果應用程序的并行效率較低，而負載比較平衡，可以考慮采用計算與通信重疊的技術來提高程序的性能，其基本原則是：盡量提前處理和發送其他進程需要的數據，推后接收暫時沒有用到的來自其他進程的數據，如MPI提供的非阻塞發送函數MPI_Isend()和非阻塞接收函數MPI_Irecv()就可以有效地用于Jacobi迭代程序中的計算和通信重疊。

3．3 OpenMP并行與優化技術

SMP節點內的OpenMP并行化一般針對循環級的細粒度并行化，這主要是因為：①絕大多數程序的主要計算量集中在循環中，對循環并行化把握住了問題的關鍵；②細粒度并行化的性能較好，并且工作量小，程序員幾乎不用關心其他并行化的細節， 而只要在循環計算外使用OpenMP編譯制導指令即可。

OpenMP并行化的循環選取是個很重要的問題，可以遵循以下幾點原則：

(1)盡量選擇計算時間占全局計算時間比例大的循環進行并行化，因為對循環的并行化同時也帶來進程和線程反復切換調度的開銷， 這對于計算量不大的循環來說是不值得的。

(2)可能有一些循環因為存在數據相關性而無法并行化。如果這是個計算量很小的循環，可能對程序的性能影響不大；但如果這個循環的計算量很大，不對它并行化可能使程序性能損失很多時， 則可以考慮進行循環變換，使其能夠并行化， 從而優化這樣的循環計算。

此外，線程數目的選擇也是OpenMP并行化要關心的問題之一，我們用參考文獻［5］的兩個例子進行說明。①顯式Laplace方程組求解問題在曙光3000上的測試表明，最佳的求解線程數應是SMP節點內的處理器數目：若線程數目過小，則機器的整體效率得不到充分發揮；過大，又會出現競爭總線帶寬的問題，使程序的性能降低。當集群總的線程數保持不變時，隨著節點數的增加，加速比有一定的下降。②用MPI/OpenMP混合模型實現的NAS CG基準測試程序在曙光3000上的測試表明，當節點數目固定時，隨著線程數增加，加速比增加緩慢。這主要是因為CG屬于內存需求密集型的問題，節點內線程數目的增加引起訪存沖突，這時宜通過使用多節點來緩解競爭。與此相關的問題還有待進一步研究。

3．4 單處理器的性能優化

在對大型應用程序進行性能優化后，一些學者發出了這樣的感慨：獲得良好的并行可擴展性并不困難，而獲得高的單處理器性能更具有挑戰性。單處理器性能的發揮直接影響到系統整體性能的發揮，但人們通常認為那只是編譯器研究的任務。而實際上，因為并行機的存儲結構十分復雜，優化單處理器執行串行程序的性能影響非常明顯，用戶的編程風格在很大程度上影響著處理器和編譯器對ILP的開發利用程度。目前的一個趨勢是高性能微處理器的飛速發展，單個處理器內部集成了大量的硬件資源，使用多種高級的動態執行策略，對應用中蘊涵的ILP具有越來越大的需求。

在單處理器性能優化的研究中，可以采取以下的技術路線：首先使用基于處理器內硬件計數器的程序性能Profiling工具，獲取微體系結構級別的性能信息，分析程序性能的瓶頸及其原因；然后針對具體的問題，結合面向Cache的性能優化和面向指令級流水線并行的優化，消除細粒度控制/數據相關性，優化數據布局和訪存順序以提高Cache命中率，重組計算序列以增大可用的ILP。行之有效的一些優化方法包括：①循環交換，即按程序數組元素在內存中的存儲順序對嵌套循環的次序進行交換，以提高數據的空間局部性；②循環展開，高效地使用通用寄存器，減少了循環的轉移開銷和訪存次數，有利于發現指令間存在的并行性；③用乘法運算替換除法運算，使用數學公式減少對內部函數的調用；④對某些運算使用已有的快速算法；⑤分塊計算，將計算區域劃分成適合Cache大小的多個子區域，并按區組織計算，提高Cache命中率。實踐證明，單處理器性能優化能夠有效地提高并行程序的整體性能，如對矩陣乘問題的優化可使其在某些并行機上的性能提高十倍。

4 結束語

目前，SMP集群的多層次并行體系結構計算機已成為主流的高性能計算平臺。本文介紹的MPI/OpenMP多層次并行編程模型充分發揮了這種多層次體系結構的特點，用戶在編程時結合使用MPI，OpenMP和單處理器等多層次并行與優化技術，可使得一些應用問題的并行程序性能超過單純的MPI或OpenMP并行程序，且具有良好的可移植性。總的來說，目前的多層次并行研究大多是應用開發再加上比較測試，理論分析方面的工作較少。在數據分布方面，較多地考慮各個節點間的數據分割，而較少考慮單個節點內部數據優化放置策略以減少或消除偽共享；在性能測試和評價方面，單獨討論個別應用性能情況的較多，而針對同類應用問題分析其特征共性及其優化規律的較少。要想獲得較高的并行性能，單處理器的性能優化也不容忽視。如何實現從應用并行性到機器并行性的自然映射，獲得良好的性能可擴展性，充分發揮計算平臺的性能潛力，還有很多問題尚待解決。

參考文獻：

［1］MPI:A MessagePassing Interface Standard.Message Passing Interface Forum［EB/OL］.http://www.mpiforum.org/，1995．

［2］OpenMP C/C++ Application Program Interface version 2.0［EB/OL］.http://www.openmp.org/，200211．

［3］Gabriele Jost， Haoqiang Jin. Comparing the OpenMP， MPI， and Hybrid Programming Paradigms on an SMP Cluster［R］.NAS Technical Report NAS03019，2003.

［4］莫則堯，等.應用程序并行與優化關鍵技術研究［C］. 第六屆全國并行計算學術會議論文集.長沙：國防科技大學出版社，2000.192-200.

［5］陳勇，陳國良，等.SMP機群混合編程模型研究［J］. 小型微型計算機系統，2004，25(10):17631767.

［6］劉杰，等.并行程序的優化與性能評價［J］. 計算機工程與科學，2000，22(5):67-70.

［7］車永剛.科學計算程序性能分析與優化關鍵技術研究［D］. 工學博士學位論文.長沙：國防科技大學，2004.

作者簡介：

單瑩(1982-)，女，江蘇連云港人，碩士研究生，主要研究方向為并行與分布處理；吳建平(1974-)，男，湖南人，助理研究員，博士，主要研究方向為并行算法；王正華(1962-)，男，湖南人，教授，博導，主要研究方向為并行算法與系統結構。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文