面向神威高性能多核處理器的并行編譯優化方法

周雍浩，徐金龍，李 斌，錢 宏，聶 凱

（1.鄭州大學 信息工程學院，鄭州 450001；2.數學工程與先進計算國家重點實驗室，鄭州 450001；3.江南計算技術研究所，江蘇 無錫 214083）

0 概述

編譯器的設計與開發是一項復雜而又艱巨的任務，其中的編譯優化至關重要。隨著多核處理器設計領域技術的快速發展，CPU 的基礎運算能力不斷提高，但要提升信息系統的應用效能，必要的途徑是通過編譯優化技術來生成與多核處理器芯片相配套的高效率目標代碼。在多核處理器上通過啟動多個線程來并行執行程序，是充分發揮多核處理器性能優勢的主要方法。目前，申威高性能多核服務器上的處理器采用對稱式共享存儲結構，實現多線程的主要方法是OpenMP 編程技術［1］。因此，對OpenMP程序的編譯優化是申威高性能多核服務器配套的自動并行化編譯系統的核心任務。OpenMP 程序編譯優化的主要目標是盡量高效地表達出程序中的并行性，包括翻譯時刻優化、運行時優化以及線程級優化等［2-4］。目前，OpenMP 程序編譯優化的焦點主要集中在線程級優化［5-6］。

在OpenMP 編程技術中，實現線程級并行主要有兩種模型：標準的fork-join（派生-合并）模型和較為復雜的單程序多數據（Single Program Multi-Data，SPMD）模型［7］。fork-join 模型使用靈活，易于處理程序中的并行域，在程序生成相對簡單且支持增量式開發，但在運行過程中需要多次創建和匯合并行線程，開銷大且運行效率低。SPMD 模型采用多線程協作的執行方式，在程序運行過程中整個線程組僅需一次創建與一次匯合，線程的控制開銷較小且運行效率高，但該模型需要考慮線程之間的數據分配和工作負載，實現比較復雜。目前，神威平臺自動并行編譯系統采用的是fork-join 模型，在程序運行過程中線程的創建和匯合比較頻繁，在并行性的表達上處于一種低效率的狀態。并行域重構技術結合標量分析、依賴關系分析及數據和計算劃分信息等自動并行化技術，盡量合并fork-join 模型中多個單獨的并行域到一個大的并行域中，作為一個小的SPMD 區 域，能夠得到混合fork-join 模型和SPMD 模型的OpenMP 程序。在不增加程序員工作量的前提下，降低線程的控制開銷，提高線程級代碼的并行執行效率。

OpenMP 程序的編程標準嚴格遵守fork-join 模型，每一個并行域在開始執行前必須去共享內存中讀取數據，無論是中小型的SMP 架構還是目前廣為流行的CMP 架構，都無法避免數據劃分和分布的問題［8-9］。因此，fork-join 模型的OpenMP程序不是一個很好的并行編程模型。目前，已有研究人員在不同的平臺上研究利用改進的編程模型優化OpenMP程序。ONODERA 等［10］在GPU 平臺上通過對多重網格預條件共軛梯度（Multigrid Preconditioned Conjugate Gradient，MPCG）等OpenMP 程序的優化研究中指出，OpenMP 程序可以通過合并一些并行域實現更粗粒度的并行，從而提高程序的整體性能［11］。文獻［12-14］在Intel Xeon 處理器上針對jacobi 程序給出了一些具體的OpenMP 程序優化方法，他們通過變量私有化、刪除冗余同步等操作合并OpenMP 程序的并行域來提高程序的運行效率。文獻［15-17］從OpenMP 編譯器優化角度闡述了采用SPMD 模型消除冗余同步，擴大程序并行域，提高可執行程序的性能。ZHU 等［18］在C64 多核模擬器上的測試結果表明，隨著線程數目增加，編譯指示#pragma omp parallel for 和#pragma omp parallel 的代價相當，但是都遠高于#pragma omp for 的代價，兩者相差大約100 倍，證實了并行域合并之后的OpenMP 程序并行代價遠低于未進行合并與擴展的OpenMP 程序。擴大OpenMP 程序中的并行域是一種比較有效的優化方法，但是并沒有給出一種通用的擴大OpenMP 程序并行域的方法。

本文針對申威高性能處理器上的線程級并行執行模型，提出一種面向神威高性能多核處理器的并行編譯優化方法。該方法結合了fork-join 模型與SPMD 模型的優點，OpenMP 程序的串行部分被單線程執行，并行部分被合并到一個大的并行域中從而形成一個小的SPMD 區域。在每個SPMD 區域中，編譯器可以通過數據依賴分析消除冗余同步，或使用代價較低的同步來提高程序的整體性能，以避免fork-join 模型并行效率低及SPMD 模型程序編寫復雜等缺點。

1 OpenMP 程序執行模型及問題分析

fork-join 模型是OpenMP 編程技術的標準執行模型，也是目前神威平臺線程級并行采用的執行模型。在起始時只有一個主線程執行程序語句，當遇到OpenMP 編譯制導標識的并行域開始時，主線程派生（fork）出一組子線程共同完成并行域中的計算任務，當遇到OpenMP 編譯制導標識的并行域結束時，所有子線程掛起或者退出執行，主線程則繼續執行。與此不同的是，在單程序多數據（SPMD）模型中，所有線程執行整個程序，且一直處于活動狀態，串行部分約束為單個線程執行或者多個線程重復執行。在執行程序中并行循環時，根據線程編號執行對應部分的循環迭代，循環迭代之間的依賴關系通過插入柵障同步語句來維持。圖1 和圖2 所示為兩種OpenMP 模型的并行執行模型。

圖1 fork-join 模型Fig.1 fork-join model

圖2 SPMD 模型Fig.2 SPMD model

fork-join 編程模型的OpenMP 程序是對相應的循環進行并行化，實現簡單且易于增量式開發，缺點是多個線程組的啟動和同步代價很高，尤其在嵌套循環中容易出現嵌套并行的情況，在嵌套并行時線程組頻繁地創建和注銷，極大地增加了操作系統對線程組管理和控制的開銷，嚴重影響程序的整體運行效率。程序中跨循環的優化無法實施，Cache 利用率低，并行性能受串行部分占比限制，因此，程序的整體運行效率不高。與此相比，SPMD 模型的OpenMP 程序將并行循環合并到一個大的并行域中，減少了多個線程組創建和匯合的開銷，同時編譯器可以通過分析消除冗余同步，進行更充分的數據劃分，高效提升Cache 利用率。但是，SPMD 模型的OpenMP 程序并行域更大，程序中變量數據屬性的分析變得非常復雜，在循環優化時數據的依賴分析和并行線程之間的同步優化具有較大的難度，因此，SPMD 模型的OpenMP 程序不容易實現。本文提出的并行域重構技術將OpenMP 程序中運行效率低的fork-join 執行模型轉換成運行效率高的SPMD 執行模型來提高程序的整體性能。

圖3 所示為并行域重構技術后OpenMP 程序的執行模型。

圖3 并行域重構模型Fig.3 Parallel region reconstruction model

2 并行域重構技術

并行域重構技術包括并行域合并和并行域擴展，下面分別使用程序實例對這兩種技術進行說明，并給出并行域重構技術的實現方法。

2.1 并行域合并

并行域的合并是指在兩個相鄰的單獨并行域之間插入一個柵障同步（如果兩個并行域存在數據依賴性），然后把這兩個并行域直接合并為一個大的并行域，作為一個小的SPMD 區域。代碼清單1 和代碼清單2 展示了一個相鄰并行域合并的代碼示例。需要說明的是，在神威平臺的自動并行化編譯器中，parallel、for、sections 和single 構造的最后都有一個隱式的柵障同步。

代碼清單1相鄰并行域代碼合并前的形式

代碼清單2相鄰并行域代碼合并后的形式

為了確保并行域合并不修改原程序語義，這里需要保證各個子線程獲取數據的更新順序和執行順序擁有相同的一致性。后者能通過OpenMP 中的柵障同步操作來實現，前者可以通過OpenMP 的制導指令flush 操作來保證可見數據的一致性。此外，相鄰并行域的合并還需要解決2 個問題：合并過程中遇到的變量數據屬性沖突和合并過程中程序串行語句的處理。

1）變量數據屬性沖突處理。在多線程程序中，變量屬性包括共享和私有兩種。共享變量在并行域中只有一個副本，并行域中的所有線程均可對其進行讀、寫等修改操作，且這種修改對并行域中的所有線程都是可見的。與此不同的是，并行域中的所有線程都擁有私有變量的一個副本，線程內部私有變量的修改并不影響其他線程內部私有變量的值。實際的并行域合并操作經常遇到變量的數據屬性沖突問題，因此，對變量數據屬性的沖突是需要解決的重要問題之一。

代碼清單3 展示了一個并行區域合并遇到的數據屬性的沖突示例。并行域1 中聲明k為共享變量，并行域2 中聲明k為私有變量。并行域1 和并行域2無法進行合并，因為變量k在并行域合并時存在數據屬性沖突問題。針對該問題，本文采用標準OpenMP 編譯制導語句 private、firstprivate 和lastprivate 修改共享變量的數據屬性，然后再次嘗試合并。例如，在編譯代碼清單3 示例程序過程中通過對變量k的定值-引用鏈分析發現，共享變量k在并行域1 中引用，而定值卻在并行域1 先前的程序段中。因此，在并行域1 對變量k進行私有化處理，則需要使k先前的定值在并行域1 內部可見，需要在引用前將這個定值引入到并行域1 中，這可以通過OpenMP 提供的firstprivate 子句實現，如代碼清單4所示。

代碼清單3變量數據屬性沖突示例

代碼清單4變量數據屬性修改示例

修改變量k的數據屬性后，進一步可實現并行域1和并行域2 的合并。代碼清單5 展示了修改變量k的數據屬性后并行域1 和并行域2 的合并。

代碼清單5數據屬性修改后的并行域合并

對變量進行私有化處理會屏蔽掉變量原來的定值，無論是并行域內部的定值-引用關系，還是并行域結構上下程序之間的定值-引用關系都有可能被修改，已經有學者對這一問題進行了深入的研究［19-21］。為滿足共享變量私有化之前所有的定值-引用關系，本文設進行私有化處理的共享變量在并行域中沒有定值。本文在這一前提下確定能否對一個并行域中的變量實行私有化處理，只有滿足共享變量在并行域中沒有被定值，才能確定并行域合并過程中不存在變量屬性沖突，然后嘗試私有化處理，進一步實現并行域合并。

2）串行語句處理。如果兩個相鄰的并行域之間存在若干條串行語句，那么并行域合并操作無法直接實施。此時，可以通過約束執行來使得串行語句包含在并行域中，再實施并行域的合并，這可以通過OpenMP 制導語句master 或者single 來實現。

代碼清單6 和代碼清單7 展示了一個合并過程中串行語句處理的程序示例。串行語句通過OpenMP 制導子句single 和master 約束執行，實現與并行域的合并，進一步合并更多的并行域。但是，這樣的做法也增加了同步操作，帶來新的額外開銷，但優點是串行域的代碼可以用來作為并行域中新的工作負載，還可以根據串行域代碼的特點進一步轉化為section 類型的并行任務，從而提供更多的負載均衡選擇方案。

代碼清單6并行域合并過程中串行語句處理前的形式

代碼清單7并行域合并過程中串行語句處理后的形式

2.2 并行域擴張

并行域擴張主要有循環并行域擴張、控制流并行域擴張和跨越函數邊界的并行域擴張3 種情況。

1）循環并行域擴張。如果一個循環中的所有語句都被包含在一個并行域中，則該并行域可以被擴張到該循環之外。這是一種較為高效的并行域優化模型，如果一個并行域擴張到N次迭代的循環之外，則并行域的創建和匯合次數將減少N-1 次。例如，代碼清單8 和代碼清單9 展示了一個簡單的循環結構并行區域擴展，j 循環對應的并行域可以擴展到i循環之外。在并行域擴展之前，并行域創建和匯合100 次，而擴展之后并行域創建和匯合僅1 次，減少了99 次。

代碼清單8循環結構并行域擴張前的代碼形式

代碼清單9循環結構并行域擴張后的代碼形式

2）控制流并行域擴展。當并行域出現在選擇結構的分支中時，可以將整個選擇結構包含在一個大的并行域中。例如，代碼清單10 中的if-then-else 結構，采用并行域擴張的方法能將它變為一個大的并行域，擴張后的并行結構如代碼清單11 所示。這里需要注意的是，如果選擇結構中含有串行分支，則必須對串行的分支進行保護或者進行計算私有化處理。

代碼清單10控制流并行域擴張前的代碼形式

代碼清單11控制流并行域擴張后的代碼形式

3）跨越函數邊界的并行域擴展。并行域擴展僅能在函數內部進行通常是不夠的。函數體通過并行域合并，能夠將函數體內部的全部語句包含在并行域中。跨越函數體邊界的并行域擴展是指將特定函數體內部的并行域擴展到整個函數的外部（即調用點處），進一步獲得更多的并行域合并機會。

代碼清單12 和代碼清單13 展示了一個跨越函數邊界的并行域擴張示例。跨越函數邊界的并行域擴張擴大了并行域的范圍，從而有可能進一步改善程序的結構，增加并行計算的粒度。但是，跨越函數邊界的并行域擴展會徹底改變線程的堆棧結構，而且這種做法隱含著對函數體內局部變量的數據屬性私有化處理。為了保證并行域擴展不修改原程序語義，必須經過定義使用鏈保證函數體內局部變量私有化處理的合法性，此外，還需要對數據屬性的制導進行優化以消除不必要的重復私有化。

代碼清單12跨越函數體邊界并行域擴張前的代碼形式

代碼清單13跨越函數體邊界并行域擴張后的代碼形式

跨越函數邊界的擴展是基于編譯器過程間分析的結果，前提是至少能訪問被調用函數的調用點和函數體。其原因是并行域擴張預示著對被調函數體的修改，被調函數體的修改對所有調用者都是可見的，因此，能夠通過找到這個函數在整個程序中的所有調用點插入制導子句來完成這一擴展。如果被調函數為外部函數，過程間分析無法明確被調函數的全部調用點，又或者不能確保對被調函數進行跨函數邊界的擴展使所有的調用點都受益，本文的做法是對被調函數同時生成兩個版本，即復制被調函數的函數體，對復制的函數體進行跨越函數邊界的并行域擴展，或保存被調函數的原函數體，因此可以不必修改被調函數的全部調用點，也不必依賴整體過程間分析結果。

2.3 并行域重構技術的算法實現

在并行域合并和并行域擴展的基礎上，本文選擇自底向上的遞歸調用算法構造SPMD 并行域。在開始時把OpenMP 程序中的每個并行循環視為小的SPMD 并行域，然后從循環的最內層開始，對相同循環層的并行循環嘗試進行并行域合并，如果相同循環層的全部程序語句都包含在同一個并行域內，則向外循環層進行并行域擴展，直至遭遇不能合并的程序語句。并行域重構把多個并行域以及并行域之間的串行代碼合并到一個SPMD 區域中，同時將循環體、控制流以及函數體中的并行域進行擴展，整個OpenMP 程序被包含在一個大的SPMD 并行域中，整個程序結構如代碼清單14 所示。

代碼清單14并行域重構后的代碼框架

3 實驗評估

本文的工作來源于神威平臺自動并行化編譯系統優化項目，并行域重構技術已集成在該系統的原型中。

3.1 實驗環境、測試集及測試內容

實驗環境、測試集及測試內容如下：

1）實驗環境。實驗環境為新一代神威高性能多核服務器SW1621。SW1621 服務器的處理器為共享內存架構的申威1621 處理器，搭載神威自動并行化編譯系統、中標麒麟操作系統以及神威計算機存儲管理系統等。詳細的配置信息如表1 所示。

表1 實驗環境Table1 Experimental environment

2）測試集。選擇面向高端服務器上OpenMP 程序性能測試的NPB3.3-OMP Benchmarks 和SPEC OMP2012 Benchmarks。

NAS 并行基準測試集（NAS Parallel Benchmark，NPB）是由美國航空航天局開發的一套計算流體力學應用程序的集合，已經成為公認的測試大規模并行機和超級計算機性能的標準程序集。NPB3.x-OMP 為NPB 測試集中程序的OpenMP 并行版本，被廣泛認為是檢測并行計算機上的OpenMP 程序的性能標準。表2 所示為NPB3.3 測試集中每個應用程序的規模與功能。NPB 測試集中每個基準測試程序有7 類計算規模，分別為S、W、A、B、C、D、E。其中A 類規模最小，S 類是樣例程序，B 類規模通常用于測試高性能服務器。因此，本文選擇B 類規模進行測試。

表2 NPB3.3 Benchmarks 應用程序規模和功能Table 2 Application size and functionality in NPB3.3 Benchmarks

標準性能評估組織（Standard Performance Evaluation Corporation，SPEC）是一個全球性的第三方非營利性組織，致力于建立、維護和認證一套應用于評測計算機系統性能的標準化基準套件。SPEC 歷經多年的開發積累和沉淀，已經成為全球眾多用戶廣泛認可的標準測試程序。SPEC OMP2012 專注于測試計算機系統中OpenMP 程序性能，強調OpenMP 并行編譯器支持和庫支持。表3 所示為SPEC OMP 測試集中每個應用程序描述。數據輸入規模從小到大分別test、train 和ref，本文選擇ref 規模進行測試來驗證本文方法的準確性。

表3 SPEC OMP2012 Benchmarks 應用程序規模和功能Table 3 Application size and functionality in SPEC OMP2012 Benchmarks

3）測試內容為并行域重構技術對自動并行化編譯系統的性能提升效果。在神威1621 服務器上，分別使用原自動并行化編譯系統和集成了并行域重構技術的自動并行化編譯系統，編譯運行NPB3.3-OMP Benchmarks 和SPEC OMP2012 Benchmarks 中的應用程序，檢查編譯和運行結果，對比運行時間，計算運行效率提升。運行效率提升的計算公式為：

其中：T1為原自動并行化編譯系統生成的目標碼運行時間；T2為集成了并行域重構技術的自動并行化編譯系統生成的目標碼運行時間；E為運行效率提升，當E＞0 時，說明本文方法對自動并行化編譯系統的運行效率有提升，當E≤0 時，說明本文方法對自動并行化編譯系統的運行效率沒有提升或者降低。

3.2 實驗結果與分析

神威1621 高性能服務CPU 集成了16 顆Core3A處理器，為了檢測并行域重構技術在充分發揮多核處理器體系結構優勢下的運行效率提升效果，本文選擇了16 線程的運行時間作為參考依據。NPB3.3-OMP Benchmarks 的測試結果靜態統計和運行效率提升如表4 和圖4 所示，SPEC OMP2012 Benchmarks的測試結果靜態統計和運行效率提升如表5 和圖5所示，其中，√表示編譯通過且運行結果正確。

圖5 SPEC OMP2012 Benchmarks 運行效率Fig.5 Running efficiency of SPEC OMP2012 Benchmarks

表4 NPB3.3-OMP Benchmarks 測試結果Table 4 Test results for NPB3.3-OMP Benchmarks

表5 SPEC OMP2012 Benchmarks 測試結果Table 5 Test results for SPEC OMP2012 Benchmarks

圖4 NPB3.3-OMP Benchmarks 運行效率Fig.4 Running efficiency of NPB3.3-OMP Benchmarks

由表4 和表5 可知，集成了并行域重構技術的自動并行化編譯系統編譯通過了全部NPB3.3-OMP Benchmarks 和SPEC OMP2012 Benchmarks 中的基準程序，且運行結果全部正確。分析其原因是由于并行域重構技術主要集中在中間優化過程，采用的是保守型的做法，對后端機器描述文件和系統的基礎庫影響比較少，因此不影響整個編譯系統的正確性。

圖4 結果顯示，在NPB3.3-OMP Benchmarks 中運行效率提升比較明顯的是BT、FT、SP、UA、IS、MG、LU，整體運行效率提升10.77%。BT、SP 和UA這3 個基準程序的核心循環段都存在函數調用，尤其是BT 和SP 核心段非常相似，都是分別對塊三對角系統的X、Y和Z方向求解，核心循環段中函數調用為3 個求解器（xsolve，ysolve，zsolve）。原自動并行化編譯器分別對3 個求解器（xsolve，ysolve，zsolve）的循環添加“！$OMP PARALLEL DO”制導語句，并行域重構技術通過函數體擴展將“！$OMP PARALLEL DO”制導語句擴展到整個循環體之外，擴大了整個并行區域，減少了線程組頻繁創建的開銷，取得了10%以上的運行效率提升。在IS、MG 和LU 核心循環段相對集中，并行的循環段之間存在一條或多條串行語句，原自動并行化系統分別針對這些循環段并行處理，添加并行編譯指示，沒有將相鄰的并行循環段做合并處理，并行域重構技術通過修改部分屬性沖突的變量（例如，LU 中的i、j+e、k等）合并了部分相鄰的循環段，因此也取得了一定的加速比提升。

圖5 結果顯示，在SPEC OMP2012 Benchmarks中性能提升較明顯的是367、370、376、360、372，整體運行效率提升7.94%。367 的核心為拉普拉斯卷積函數中的計算循環段，這些計算循環段之間存在部分賦值語句，或存在加、乘賦的串行執行語句，并行域重構技術先將這些語句限制為單線程執行，然后再與其他相鄰的并行域進行合并。該課題成功合并的并行域比較多，數據連續性得到改善，因此運行效率提升明顯。370、376、360、372 這4 道課題熱點函數本身含有的循環段并不多，這些課題的共同特點是核心循環段中存在較多的嵌套并行循環層，并行域重構技術通過循環并行域擴展將并行域外提，減少了嵌套循環內部并行域頻繁創建和合并的開銷，提高了運行效率。雖然362 課題成功合并了較多的并行循環，但是核心循環段中始終存在兩個無法合并的規約變量沖突，因此取得運行效率提升并不明顯。

實驗結果顯示，NPB3.3-OMP 的整體運行效率提升效果優于SPEC OMP2012，其原因是SPEC OMP2012 的程序規模較大，復雜程度相對較高，包含了更多難以分析的函數調用，數據變量的屬性存在較多復雜的讀寫操作，編譯器層面無法進行有效的并行域合并。例如350 和362 雖然合并了大量的并行域，但是在幾個熱點函數核心循環段中的函數調用關系比較復雜，或者私有變量存在太多比較復雜的操作導致無法進行合并，因此沒有取得明顯的運行效率提升。

4 結束語

為提升神威高性能多核服務器自動并行化編譯系統生成的OpenMP 程序的執行效率，本文提出一種并行域重構技術。該技術通過并行域合并和并行域擴展來擴大OpenMP 程序中的并行域范圍，減少OpenMP 程序的并行域數目，降低線程組頻繁創建和合并等控制開銷，并將標準的fork-join 執行模型轉換成高效的SPMD 執行模型。為測試并行域重構技術性能的提升效果，本文通過NPB3.3-OMP 和SPEC OMP2012 測試集在新一代神威高性能多核服務器SW1621 上進行實驗，結果表明，并行域重構技術不影響自動并行化編譯系統的正確性，且運行效率明顯提升。后續將在并行域重構技術的基礎上結合數據依賴分析及數據劃分等技術，消除并行域中的冗余同步操作，進一步提升神威平臺OpenMP 程序的并行執行效率。