周雍浩，徐金龍，李 斌，錢(qián) 宏，聶 凱

（1.鄭州大學(xué) 信息工程學(xué)院，鄭州 450001；2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州 450001；3.江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083）

0 概述

編譯器的設(shè)計(jì)與開(kāi)發(fā)是一項(xiàng)復(fù)雜而又艱巨的任務(wù)，其中的編譯優(yōu)化至關(guān)重要。隨著多核處理器設(shè)計(jì)領(lǐng)域技術(shù)的快速發(fā)展，CPU 的基礎(chǔ)運(yùn)算能力不斷提高，但要提升信息系統(tǒng)的應(yīng)用效能，必要的途徑是通過(guò)編譯優(yōu)化技術(shù)來(lái)生成與多核處理器芯片相配套的高效率目標(biāo)代碼。在多核處理器上通過(guò)啟動(dòng)多個(gè)線程來(lái)并行執(zhí)行程序，是充分發(fā)揮多核處理器性能優(yōu)勢(shì)的主要方法。目前，申威高性能多核服務(wù)器上的處理器采用對(duì)稱式共享存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)多線程的主要方法是OpenMP 編程技術(shù)［1］。因此，對(duì)OpenMP程序的編譯優(yōu)化是申威高性能多核服務(wù)器配套的自動(dòng)并行化編譯系統(tǒng)的核心任務(wù)。OpenMP 程序編譯優(yōu)化的主要目標(biāo)是盡量高效地表達(dá)出程序中的并行性，包括翻譯時(shí)刻優(yōu)化、運(yùn)行時(shí)優(yōu)化以及線程級(jí)優(yōu)化等［2-4］。目前，OpenMP 程序編譯優(yōu)化的焦點(diǎn)主要集中在線程級(jí)優(yōu)化［5-6］。

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

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

本文針對(duì)申威高性能處理器上的線程級(jí)并行執(zhí)行模型，提出一種面向神威高性能多核處理器的并行編譯優(yōu)化方法。該方法結(jié)合了fork-join 模型與SPMD 模型的優(yōu)點(diǎn)，OpenMP 程序的串行部分被單線程執(zhí)行，并行部分被合并到一個(gè)大的并行域中從而形成一個(gè)小的SPMD 區(qū)域。在每個(gè)SPMD 區(qū)域中，編譯器可以通過(guò)數(shù)據(jù)依賴分析消除冗余同步，或使用代價(jià)較低的同步來(lái)提高程序的整體性能，以避免fork-join 模型并行效率低及SPMD 模型程序編寫(xiě)復(fù)雜等缺點(diǎn)。

1 OpenMP 程序執(zhí)行模型及問(wèn)題分析

fork-join 模型是OpenMP 編程技術(shù)的標(biāo)準(zhǔn)執(zhí)行模型，也是目前神威平臺(tái)線程級(jí)并行采用的執(zhí)行模型。在起始時(shí)只有一個(gè)主線程執(zhí)行程序語(yǔ)句，當(dāng)遇到OpenMP 編譯制導(dǎo)標(biāo)識(shí)的并行域開(kāi)始時(shí)，主線程派生（fork）出一組子線程共同完成并行域中的計(jì)算任務(wù)，當(dāng)遇到OpenMP 編譯制導(dǎo)標(biāo)識(shí)的并行域結(jié)束時(shí)，所有子線程掛起或者退出執(zhí)行，主線程則繼續(xù)執(zhí)行。與此不同的是，在單程序多數(shù)據(jù)（SPMD）模型中，所有線程執(zhí)行整個(gè)程序，且一直處于活動(dòng)狀態(tài)，串行部分約束為單個(gè)線程執(zhí)行或者多個(gè)線程重復(fù)執(zhí)行。在執(zhí)行程序中并行循環(huán)時(shí)，根據(jù)線程編號(hào)執(zhí)行對(duì)應(yīng)部分的循環(huán)迭代，循環(huán)迭代之間的依賴關(guān)系通過(guò)插入柵障同步語(yǔ)句來(lái)維持。圖1 和圖2 所示為兩種OpenMP 模型的并行執(zhí)行模型。

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

圖2 SPMD 模型Fig.2 SPMD model

fork-join 編程模型的OpenMP 程序是對(duì)相應(yīng)的循環(huán)進(jìn)行并行化，實(shí)現(xiàn)簡(jiǎn)單且易于增量式開(kāi)發(fā)，缺點(diǎn)是多個(gè)線程組的啟動(dòng)和同步代價(jià)很高，尤其在嵌套循環(huán)中容易出現(xiàn)嵌套并行的情況，在嵌套并行時(shí)線程組頻繁地創(chuàng)建和注銷，極大地增加了操作系統(tǒng)對(duì)線程組管理和控制的開(kāi)銷，嚴(yán)重影響程序的整體運(yùn)行效率。程序中跨循環(huán)的優(yōu)化無(wú)法實(shí)施，Cache 利用率低，并行性能受串行部分占比限制，因此，程序的整體運(yùn)行效率不高。與此相比，SPMD 模型的OpenMP 程序?qū)⒉⑿醒h(huán)合并到一個(gè)大的并行域中，減少了多個(gè)線程組創(chuàng)建和匯合的開(kāi)銷，同時(shí)編譯器可以通過(guò)分析消除冗余同步，進(jìn)行更充分的數(shù)據(jù)劃分，高效提升Cache 利用率。但是，SPMD 模型的OpenMP 程序并行域更大，程序中變量數(shù)據(jù)屬性的分析變得非常復(fù)雜，在循環(huán)優(yōu)化時(shí)數(shù)據(jù)的依賴分析和并行線程之間的同步優(yōu)化具有較大的難度，因此，SPMD 模型的OpenMP 程序不容易實(shí)現(xiàn)。本文提出的并行域重構(gòu)技術(shù)將OpenMP 程序中運(yùn)行效率低的fork-join 執(zhí)行模型轉(zhuǎn)換成運(yùn)行效率高的SPMD 執(zhí)行模型來(lái)提高程序的整體性能。

圖3 所示為并行域重構(gòu)技術(shù)后OpenMP 程序的執(zhí)行模型。

圖3 并行域重構(gòu)模型Fig.3 Parallel region reconstruction model

2 并行域重構(gòu)技術(shù)

并行域重構(gòu)技術(shù)包括并行域合并和并行域擴(kuò)展，下面分別使用程序?qū)嵗龑?duì)這兩種技術(shù)進(jìn)行說(shuō)明，并給出并行域重構(gòu)技術(shù)的實(shí)現(xiàn)方法。

2.1 并行域合并

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

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

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

為了確保并行域合并不修改原程序語(yǔ)義，這里需要保證各個(gè)子線程獲取數(shù)據(jù)的更新順序和執(zhí)行順序擁有相同的一致性。后者能通過(guò)OpenMP 中的柵障同步操作來(lái)實(shí)現(xiàn)，前者可以通過(guò)OpenMP 的制導(dǎo)指令flush 操作來(lái)保證可見(jiàn)數(shù)據(jù)的一致性。此外，相鄰并行域的合并還需要解決2 個(gè)問(wèn)題：合并過(guò)程中遇到的變量數(shù)據(jù)屬性沖突和合并過(guò)程中程序串行語(yǔ)句的處理。

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

代碼清單3 展示了一個(gè)并行區(qū)域合并遇到的數(shù)據(jù)屬性的沖突示例。并行域1 中聲明k為共享變量，并行域2 中聲明k為私有變量。并行域1 和并行域2無(wú)法進(jìn)行合并，因?yàn)樽兞縦在并行域合并時(shí)存在數(shù)據(jù)屬性沖突問(wèn)題。針對(duì)該問(wèn)題，本文采用標(biāo)準(zhǔn)OpenMP 編譯制導(dǎo)語(yǔ)句 private、firstprivate 和lastprivate 修改共享變量的數(shù)據(jù)屬性，然后再次嘗試合并。例如，在編譯代碼清單3 示例程序過(guò)程中通過(guò)對(duì)變量k的定值-引用鏈分析發(fā)現(xiàn)，共享變量k在并行域1 中引用，而定值卻在并行域1 先前的程序段中。因此，在并行域1 對(duì)變量k進(jìn)行私有化處理，則需要使k先前的定值在并行域1 內(nèi)部可見(jiàn)，需要在引用前將這個(gè)定值引入到并行域1 中，這可以通過(guò)OpenMP 提供的firstprivate 子句實(shí)現(xiàn)，如代碼清單4所示。

代碼清單3變量數(shù)據(jù)屬性沖突示例

代碼清單4變量數(shù)據(jù)屬性修改示例

修改變量k的數(shù)據(jù)屬性后，進(jìn)一步可實(shí)現(xiàn)并行域1和并行域2 的合并。代碼清單5 展示了修改變量k的數(shù)據(jù)屬性后并行域1 和并行域2 的合并。

代碼清單5數(shù)據(jù)屬性修改后的并行域合并

對(duì)變量進(jìn)行私有化處理會(huì)屏蔽掉變量原來(lái)的定值，無(wú)論是并行域內(nèi)部的定值-引用關(guān)系，還是并行域結(jié)構(gòu)上下程序之間的定值-引用關(guān)系都有可能被修改，已經(jīng)有學(xué)者對(duì)這一問(wèn)題進(jìn)行了深入的研究［19-21］。為滿足共享變量私有化之前所有的定值-引用關(guān)系，本文設(shè)進(jìn)行私有化處理的共享變量在并行域中沒(méi)有定值。本文在這一前提下確定能否對(duì)一個(gè)并行域中的變量實(shí)行私有化處理，只有滿足共享變量在并行域中沒(méi)有被定值，才能確定并行域合并過(guò)程中不存在變量屬性沖突，然后嘗試私有化處理，進(jìn)一步實(shí)現(xiàn)并行域合并。

2）串行語(yǔ)句處理。如果兩個(gè)相鄰的并行域之間存在若干條串行語(yǔ)句，那么并行域合并操作無(wú)法直接實(shí)施。此時(shí)，可以通過(guò)約束執(zhí)行來(lái)使得串行語(yǔ)句包含在并行域中，再實(shí)施并行域的合并，這可以通過(guò)OpenMP 制導(dǎo)語(yǔ)句master 或者single 來(lái)實(shí)現(xiàn)。

代碼清單6 和代碼清單7 展示了一個(gè)合并過(guò)程中串行語(yǔ)句處理的程序示例。串行語(yǔ)句通過(guò)OpenMP 制導(dǎo)子句single 和master 約束執(zhí)行，實(shí)現(xiàn)與并行域的合并，進(jìn)一步合并更多的并行域。但是，這樣的做法也增加了同步操作，帶來(lái)新的額外開(kāi)銷，但優(yōu)點(diǎn)是串行域的代碼可以用來(lái)作為并行域中新的工作負(fù)載，還可以根據(jù)串行域代碼的特點(diǎn)進(jìn)一步轉(zhuǎn)化為section 類型的并行任務(wù)，從而提供更多的負(fù)載均衡選擇方案。

代碼清單6并行域合并過(guò)程中串行語(yǔ)句處理前的形式

代碼清單7并行域合并過(guò)程中串行語(yǔ)句處理后的形式

2.2 并行域擴(kuò)張

并行域擴(kuò)張主要有循環(huán)并行域擴(kuò)張、控制流并行域擴(kuò)張和跨越函數(shù)邊界的并行域擴(kuò)張3 種情況。

1）循環(huán)并行域擴(kuò)張。如果一個(gè)循環(huán)中的所有語(yǔ)句都被包含在一個(gè)并行域中，則該并行域可以被擴(kuò)張到該循環(huán)之外。這是一種較為高效的并行域優(yōu)化模型，如果一個(gè)并行域擴(kuò)張到N次迭代的循環(huán)之外，則并行域的創(chuàng)建和匯合次數(shù)將減少N-1 次。例如，代碼清單8 和代碼清單9 展示了一個(gè)簡(jiǎn)單的循環(huán)結(jié)構(gòu)并行區(qū)域擴(kuò)展，j 循環(huán)對(duì)應(yīng)的并行域可以擴(kuò)展到i循環(huán)之外。在并行域擴(kuò)展之前，并行域創(chuàng)建和匯合100 次，而擴(kuò)展之后并行域創(chuàng)建和匯合僅1 次，減少了99 次。

代碼清單8循環(huán)結(jié)構(gòu)并行域擴(kuò)張前的代碼形式

代碼清單9循環(huán)結(jié)構(gòu)并行域擴(kuò)張后的代碼形式

2）控制流并行域擴(kuò)展。當(dāng)并行域出現(xiàn)在選擇結(jié)構(gòu)的分支中時(shí)，可以將整個(gè)選擇結(jié)構(gòu)包含在一個(gè)大的并行域中。例如，代碼清單10 中的if-then-else 結(jié)構(gòu)，采用并行域擴(kuò)張的方法能將它變?yōu)橐粋€(gè)大的并行域，擴(kuò)張后的并行結(jié)構(gòu)如代碼清單11 所示。這里需要注意的是，如果選擇結(jié)構(gòu)中含有串行分支，則必須對(duì)串行的分支進(jìn)行保護(hù)或者進(jìn)行計(jì)算私有化處理。

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

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

3）跨越函數(shù)邊界的并行域擴(kuò)展。并行域擴(kuò)展僅能在函數(shù)內(nèi)部進(jìn)行通常是不夠的。函數(shù)體通過(guò)并行域合并，能夠?qū)⒑瘮?shù)體內(nèi)部的全部語(yǔ)句包含在并行域中?？缭胶瘮?shù)體邊界的并行域擴(kuò)展是指將特定函數(shù)體內(nèi)部的并行域擴(kuò)展到整個(gè)函數(shù)的外部（即調(diào)用點(diǎn)處），進(jìn)一步獲得更多的并行域合并機(jī)會(huì)。

代碼清單12 和代碼清單13 展示了一個(gè)跨越函數(shù)邊界的并行域擴(kuò)張示例?？缭胶瘮?shù)邊界的并行域擴(kuò)張擴(kuò)大了并行域的范圍，從而有可能進(jìn)一步改善程序的結(jié)構(gòu)，增加并行計(jì)算的粒度。但是，跨越函數(shù)邊界的并行域擴(kuò)展會(huì)徹底改變線程的堆棧結(jié)構(gòu)，而且這種做法隱含著對(duì)函數(shù)體內(nèi)局部變量的數(shù)據(jù)屬性私有化處理。為了保證并行域擴(kuò)展不修改原程序語(yǔ)義，必須經(jīng)過(guò)定義使用鏈保證函數(shù)體內(nèi)局部變量私有化處理的合法性，此外，還需要對(duì)數(shù)據(jù)屬性的制導(dǎo)進(jìn)行優(yōu)化以消除不必要的重復(fù)私有化。

代碼清單12跨越函數(shù)體邊界并行域擴(kuò)張前的代碼形式

代碼清單13跨越函數(shù)體邊界并行域擴(kuò)張后的代碼形式

跨越函數(shù)邊界的擴(kuò)展是基于編譯器過(guò)程間分析的結(jié)果，前提是至少能訪問(wèn)被調(diào)用函數(shù)的調(diào)用點(diǎn)和函數(shù)體。其原因是并行域擴(kuò)張預(yù)示著對(duì)被調(diào)函數(shù)體的修改，被調(diào)函數(shù)體的修改對(duì)所有調(diào)用者都是可見(jiàn)的，因此，能夠通過(guò)找到這個(gè)函數(shù)在整個(gè)程序中的所有調(diào)用點(diǎn)插入制導(dǎo)子句來(lái)完成這一擴(kuò)展。如果被調(diào)函數(shù)為外部函數(shù)，過(guò)程間分析無(wú)法明確被調(diào)函數(shù)的全部調(diào)用點(diǎn)，又或者不能確保對(duì)被調(diào)函數(shù)進(jìn)行跨函數(shù)邊界的擴(kuò)展使所有的調(diào)用點(diǎn)都受益，本文的做法是對(duì)被調(diào)函數(shù)同時(shí)生成兩個(gè)版本，即復(fù)制被調(diào)函數(shù)的函數(shù)體，對(duì)復(fù)制的函數(shù)體進(jìn)行跨越函數(shù)邊界的并行域擴(kuò)展，或保存被調(diào)函數(shù)的原函數(shù)體，因此可以不必修改被調(diào)函數(shù)的全部調(diào)用點(diǎn)，也不必依賴整體過(guò)程間分析結(jié)果。

2.3 并行域重構(gòu)技術(shù)的算法實(shí)現(xiàn)

在并行域合并和并行域擴(kuò)展的基礎(chǔ)上，本文選擇自底向上的遞歸調(diào)用算法構(gòu)造SPMD 并行域。在開(kāi)始時(shí)把OpenMP 程序中的每個(gè)并行循環(huán)視為小的SPMD 并行域，然后從循環(huán)的最內(nèi)層開(kāi)始，對(duì)相同循環(huán)層的并行循環(huán)嘗試進(jìn)行并行域合并，如果相同循環(huán)層的全部程序語(yǔ)句都包含在同一個(gè)并行域內(nèi)，則向外循環(huán)層進(jìn)行并行域擴(kuò)展，直至遭遇不能合并的程序語(yǔ)句。并行域重構(gòu)把多個(gè)并行域以及并行域之間的串行代碼合并到一個(gè)SPMD 區(qū)域中，同時(shí)將循環(huán)體、控制流以及函數(shù)體中的并行域進(jìn)行擴(kuò)展，整個(gè)OpenMP 程序被包含在一個(gè)大的SPMD 并行域中，整個(gè)程序結(jié)構(gòu)如代碼清單14 所示。

代碼清單14并行域重構(gòu)后的代碼框架

3 實(shí)驗(yàn)評(píng)估

本文的工作來(lái)源于神威平臺(tái)自動(dòng)并行化編譯系統(tǒng)優(yōu)化項(xiàng)目，并行域重構(gòu)技術(shù)已集成在該系統(tǒng)的原型中。

3.1 實(shí)驗(yàn)環(huán)境、測(cè)試集及測(cè)試內(nèi)容

實(shí)驗(yàn)環(huán)境、測(cè)試集及測(cè)試內(nèi)容如下：

1）實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)環(huán)境為新一代神威高性能多核服務(wù)器SW1621。SW1621 服務(wù)器的處理器為共享內(nèi)存架構(gòu)的申威1621 處理器，搭載神威自動(dòng)并行化編譯系統(tǒng)、中標(biāo)麒麟操作系統(tǒng)以及神威計(jì)算機(jī)存儲(chǔ)管理系統(tǒng)等。詳細(xì)的配置信息如表1 所示。

表1 實(shí)驗(yàn)環(huán)境Table1 Experimental environment

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

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

表2 NPB3.3 Benchmarks 應(yīng)用程序規(guī)模和功能Table 2 Application size and functionality in NPB3.3 Benchmarks

標(biāo)準(zhǔn)性能評(píng)估組織（Standard Performance Evaluation Corporation，SPEC）是一個(gè)全球性的第三方非營(yíng)利性組織，致力于建立、維護(hù)和認(rèn)證一套應(yīng)用于評(píng)測(cè)計(jì)算機(jī)系統(tǒng)性能的標(biāo)準(zhǔn)化基準(zhǔn)套件。SPEC 歷經(jīng)多年的開(kāi)發(fā)積累和沉淀，已經(jīng)成為全球眾多用戶廣泛認(rèn)可的標(biāo)準(zhǔn)測(cè)試程序。SPEC OMP2012 專注于測(cè)試計(jì)算機(jī)系統(tǒng)中OpenMP 程序性能，強(qiáng)調(diào)OpenMP 并行編譯器支持和庫(kù)支持。表3 所示為SPEC OMP 測(cè)試集中每個(gè)應(yīng)用程序描述。數(shù)據(jù)輸入規(guī)模從小到大分別test、train 和ref，本文選擇ref 規(guī)模進(jìn)行測(cè)試來(lái)驗(yàn)證本文方法的準(zhǔn)確性。

表3 SPEC OMP2012 Benchmarks 應(yīng)用程序規(guī)模和功能Table 3 Application size and functionality in SPEC OMP2012 Benchmarks

3）測(cè)試內(nèi)容為并行域重構(gòu)技術(shù)對(duì)自動(dòng)并行化編譯系統(tǒng)的性能提升效果。在神威1621 服務(wù)器上，分別使用原自動(dòng)并行化編譯系統(tǒng)和集成了并行域重構(gòu)技術(shù)的自動(dòng)并行化編譯系統(tǒng)，編譯運(yùn)行NPB3.3-OMP Benchmarks 和SPEC OMP2012 Benchmarks 中的應(yīng)用程序，檢查編譯和運(yùn)行結(jié)果，對(duì)比運(yùn)行時(shí)間，計(jì)算運(yùn)行效率提升。運(yùn)行效率提升的計(jì)算公式為：

其中：T1為原自動(dòng)并行化編譯系統(tǒng)生成的目標(biāo)碼運(yùn)行時(shí)間；T2為集成了并行域重構(gòu)技術(shù)的自動(dòng)并行化編譯系統(tǒng)生成的目標(biāo)碼運(yùn)行時(shí)間；E為運(yùn)行效率提升，當(dāng)E＞0 時(shí)，說(shuō)明本文方法對(duì)自動(dòng)并行化編譯系統(tǒng)的運(yùn)行效率有提升，當(dāng)E≤0 時(shí)，說(shuō)明本文方法對(duì)自動(dòng)并行化編譯系統(tǒng)的運(yùn)行效率沒(méi)有提升或者降低。

3.2 實(shí)驗(yàn)結(jié)果與分析

神威1621 高性能服務(wù)CPU 集成了16 顆Core3A處理器，為了檢測(cè)并行域重構(gòu)技術(shù)在充分發(fā)揮多核處理器體系結(jié)構(gòu)優(yōu)勢(shì)下的運(yùn)行效率提升效果，本文選擇了16 線程的運(yùn)行時(shí)間作為參考依據(jù)。NPB3.3-OMP Benchmarks 的測(cè)試結(jié)果靜態(tài)統(tǒng)計(jì)和運(yùn)行效率提升如表4 和圖4 所示，SPEC OMP2012 Benchmarks的測(cè)試結(jié)果靜態(tài)統(tǒng)計(jì)和運(yùn)行效率提升如表5 和圖5所示，其中，√表示編譯通過(guò)且運(yùn)行結(jié)果正確。

圖5 SPEC OMP2012 Benchmarks 運(yùn)行效率Fig.5 Running efficiency of SPEC OMP2012 Benchmarks

表4 NPB3.3-OMP Benchmarks 測(cè)試結(jié)果Table 4 Test results for NPB3.3-OMP Benchmarks

表5 SPEC OMP2012 Benchmarks 測(cè)試結(jié)果Table 5 Test results for SPEC OMP2012 Benchmarks

圖4 NPB3.3-OMP Benchmarks 運(yùn)行效率Fig.4 Running efficiency of NPB3.3-OMP Benchmarks

由表4 和表5 可知，集成了并行域重構(gòu)技術(shù)的自動(dòng)并行化編譯系統(tǒng)編譯通過(guò)了全部NPB3.3-OMP Benchmarks 和SPEC OMP2012 Benchmarks 中的基準(zhǔn)程序，且運(yùn)行結(jié)果全部正確。分析其原因是由于并行域重構(gòu)技術(shù)主要集中在中間優(yōu)化過(guò)程，采用的是保守型的做法，對(duì)后端機(jī)器描述文件和系統(tǒng)的基礎(chǔ)庫(kù)影響比較少，因此不影響整個(gè)編譯系統(tǒng)的正確性。

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

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

實(shí)驗(yàn)結(jié)果顯示，NPB3.3-OMP 的整體運(yùn)行效率提升效果優(yōu)于SPEC OMP2012，其原因是SPEC OMP2012 的程序規(guī)模較大，復(fù)雜程度相對(duì)較高，包含了更多難以分析的函數(shù)調(diào)用，數(shù)據(jù)變量的屬性存在較多復(fù)雜的讀寫(xiě)操作，編譯器層面無(wú)法進(jìn)行有效的并行域合并。例如350 和362 雖然合并了大量的并行域，但是在幾個(gè)熱點(diǎn)函數(shù)核心循環(huán)段中的函數(shù)調(diào)用關(guān)系比較復(fù)雜，或者私有變量存在太多比較復(fù)雜的操作導(dǎo)致無(wú)法進(jìn)行合并，因此沒(méi)有取得明顯的運(yùn)行效率提升。

4 結(jié)束語(yǔ)

為提升神威高性能多核服務(wù)器自動(dòng)并行化編譯系統(tǒng)生成的OpenMP 程序的執(zhí)行效率，本文提出一種并行域重構(gòu)技術(shù)。該技術(shù)通過(guò)并行域合并和并行域擴(kuò)展來(lái)擴(kuò)大OpenMP 程序中的并行域范圍，減少OpenMP 程序的并行域數(shù)目，降低線程組頻繁創(chuàng)建和合并等控制開(kāi)銷，并將標(biāo)準(zhǔn)的fork-join 執(zhí)行模型轉(zhuǎn)換成高效的SPMD 執(zhí)行模型。為測(cè)試并行域重構(gòu)技術(shù)性能的提升效果，本文通過(guò)NPB3.3-OMP 和SPEC OMP2012 測(cè)試集在新一代神威高性能多核服務(wù)器SW1621 上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，并行域重構(gòu)技術(shù)不影響自動(dòng)并行化編譯系統(tǒng)的正確性，且運(yùn)行效率明顯提升。后續(xù)將在并行域重構(gòu)技術(shù)的基礎(chǔ)上結(jié)合數(shù)據(jù)依賴分析及數(shù)據(jù)劃分等技術(shù)，消除并行域中的冗余同步操作，進(jìn)一步提升神威平臺(tái)OpenMP 程序的并行執(zhí)行效率。