劉 徐，肖志勇，甘 霖，徐敬蘅，陳宏博

1.江南大學 物聯網工程學院，江蘇 無錫 214122

2.國家超級計算無錫中心，江蘇 無錫 214131

3.清華大學 計算機科學與技術系，北京 100084

1 引言

以超級計算機為代表的高性能計算技術一直以來都是計算機科學研究與應用的重要方向，也是服務于醫(yī)學、軍事、航天等各個領域的計算保障?！吧裢ぬ狻弊鳛槭澜缟系谝慌_峰值性能超過每秒十億億次雙精度浮點計算能力的超級計算機[1]，2016—2017 年4 次成為世界最快超算系統，與“天河2 號”共同實現了我國國產超算在世界超算系統排名上的十連貫。在2019 年5 月最新一期全球超級計算機Top500 中排名第三[2]，也是目前我國最快的超級計算機。“神威·太湖之光”全面采用了國產異構眾核處理器申威26010，全機由40 960 個處理器組成。

申威26010 處理器由主從核結構構成，故部署在“神威·太湖之光”上的應用程序是針對神威架構做的優(yōu)化程序。針對主從核的結構，它有進程級和線程級的并行優(yōu)化，其中主從核內的數據結構和分配對應用程序算法的性能影響較大。使用參數對應用程序數據進行劃分，將數據合理分配在申威26010 處理器主從核上，能充分利用申威異構眾核處理器從而有效提升應用程序性能。通常來說，隨機選取的參數往往無法獲得最優(yōu)性能，而采取遍歷或者人工尋找最優(yōu)參數的方式又耗時太長且開銷過大。此時，采取合適的方法自動獲取最優(yōu)參數，充分利用申威處理器的計算能力就顯得非常重要。

有限差分模板計算用于求解偏微分方程，是科學計算內一個重要分支。它具有易于實現、通用性強等優(yōu)點，被廣泛應用于地震模擬、石油勘探、全球大氣模式數值模擬等多個領域[3-6]。但該算法計算密度高，訪存跨度大，通信和同步開銷大，CPU 利用低，使得算法在實際應用中的性能難以得到保障。因此，提高該算法的可擴展性，減少通信和同步開銷就成為研究人員的重點工作。本文將該算法部署在申威26010 異構眾核處理器上，通過合理分配有限差分模板計算算法數據，充分利用神威處理器強大的計算能力來提升該算法性能。以二維有限差分模板計算算法為例，尋找合理的消息傳遞接口（message passing interface，MPI）規(guī)模參數和從核規(guī)模參數，尋址空間達10 億次方，又由于每運行一次二維有限差分模板計算算法需要近2 分鐘，采用窮舉法需要20 億分鐘，顯然開銷過大，而隨機選擇不需要耗時但往往得不到合適解。故本文采用遺傳算法來解決該NP 問題，在合理時間內尋找合理的參數解。

遺傳算法是根據自然界進化規(guī)律，即適者生存、優(yōu)勝劣汰的繁衍規(guī)律推演出來的一種進化算法。它通過遺傳算子，如交叉算子、變異算子等獲取優(yōu)良基因，在整個搜索空間內尋找產生最優(yōu)染色體[7]。相比于其他進化算法，遺傳算法具有天生并行性，全局尋優(yōu)能力強等特點，對解決大規(guī)模并行機上的組合優(yōu)化問題非常有效[8-9]。雖然現有的基于GPU 的遺傳算法模型在理論上可以適用于異構眾核處理器架構，但是由于并行架構[10]的不同特性、通信復雜度、適應度函數計算復雜以及編譯器優(yōu)化差異的影響[11]，使得優(yōu)化性能和加速比很難得到保證。

基于以上問題，本文面向申威異構眾核處理器，提出一種基于遺傳算法的并行參數自動尋優(yōu)方法。為充分利用申威26010 異構眾核處理器優(yōu)勢，提升有限差分模板計算應用程序的性能，本文采用遺傳算法將有限差分模板計算的數據進行合理分割并部署在申威26010 異構眾核處理器的主從核上。本文工作的主要貢獻有：

（1）在“神威·太湖之光”上實現消息傳遞接口（MPI）數據規(guī)模參數（TX，TY）和從核規(guī)模參數（NX，NY）自動尋優(yōu)，與編譯器自動分配相比大大提高了工作效率。

（2）面向異構眾核申威26010 處理器，第一次基于遺傳算法實現超大規(guī)模自適應并行參數優(yōu)化。

（3）并行參數（TX，TY，NX，NY） 尋址空間超過10 億次方，使用該方法成功解決了一個在國產異構眾核處理器下多參數尋優(yōu)的NP 問題。在尋址空間內尋找合理參數，并在“神威·太湖之光”平臺下進行有限差分模板計算測試，與編譯系統自動分配結果相比獲得了10.79 倍的加速比，對國產異構多核超級計算機上的并行優(yōu)化具有指導意義。

2 背景和相關工作

2.1 “神威·太湖之光”和SW26010 異構眾核處理器

“神威·太湖之光”是世界領先的超級計算機，全系統峰值運算速度每秒12.54 億億次，持續(xù)運算速度每秒9.3 億億次，性能功耗比每瓦60.5 億次，與其他相同量級計算機相比節(jié)能60%以上[1]?！吧裢ぬ狻笔鞘澜缟鲜着_峰值運算性能超過10 億億次量級超級計算機，也是我國第一臺全部采用國產處理器構建的超級計算機[12]。

“神威·太湖之光”搭載著40 960 個“申威26010”異構眾核處理器。SW26010 基本架構如圖1 所示，每個處理器包含4 個運算核組（computational groups，CG）共260 個計算核心。每個核組包括一個內存控制器（memory controller，MC）和65 個運算核心，即一個8×8 的計算處理單元（central processing elements，CPE）和一個管理處理單元（manage processing element，MPE）[13]。CPE 和MPE 都是完整的64 位RISC（reduced instruction set computing）內核，但它們在計算時處理不同的任務。MPE 支持完整的中斷函數、內存管理和無序問題執(zhí)行，用于管理、任務調度和數據通信；CPE 用于實現超高性能和計算任務。核組內MPI 和CPE 通過主、從核的方式實現并行協作，核組間通過片上網絡（network-on-chip，NOC）進行連接，系統接口用于與片外系統進行連接。

Fig.1 SW26010 multi-core processor structure diagram圖1 申威26010眾核處理器結構圖

SW26010 眾核處理器與其他多核或眾核處理器不同。在內存層次結構上，MPE 采用傳統32 KB L1指令cache，32 KB L1 數據cache 和256 KB L2 指令和數據混合cache，但CPE 僅16 KB L1 指令cache，并用64 KB 的從核局部存儲空間（local data memory，LDM）作為用戶控制快速緩沖。另外，每個CPE 包含控制單元、數據傳輸單元、8 行通信總線、8 列通信總線。8行、8 列的通信總線為8×8 的CPE 間的寄存器通信提供條件，實現CPE 數據共享，減少訪存時間，有效提高帶寬[1，14]。申威異構眾核處理器的架構特點使得從核之間的數據相互隔離，這有利于追求極致性能，但也帶來了更多編程問題?？梢钥闯觯瑧贸绦驍祿姆指顚⒅苯記Q定通信、訪存和計算情況，嚴重影響應用程序的性能[15-16]。

2.2 相關工作

本文研究的重點是針對“神威·太湖之光”平臺上應用程序數據規(guī)模參數進行自動優(yōu)化。本節(jié)討論了前人關于超級計算機并行參數優(yōu)化問題和遺傳算法應用方向的一些相關工作，并提出面向“神威·太湖之光”的遺傳算法參數自動尋優(yōu)方法。

近年來，對并行非功能參數進行自動調優(yōu)越來越流行，在典型大搜索空間內在合理時間內尋找高性能參數值具有重要意義[17-20]。Arcuri 和Fraser[21]探討了參數調優(yōu)對算法性能的影響并給出指導原則。Durillo 和Gschwandtner 等人[22]提出一種并行程序的多目標分區(qū)域感知優(yōu)化方法。Wu 和Weimer 等人[23]基于變量的方法自動發(fā)現和探索深層參數。Cosenza和Durillo 等人[24]提出一種基于結構學習的Stencil 自動調優(yōu)方法。Zhou 和He等人[25]提出了一種矢量并行蟻群算法模型解決多核SIMD（single instruction multiple data）并行ACO（ant colony optimization）問題。Khmelev 和Kochetov[26]用遺傳算法解決分割送貨車輛路徑問題。Zavoianu 和Bramerdorfer等人[27]優(yōu)化電機驅動器的性能，有效減少計算時間，降低運行功耗。Singh 等人[28]提出一種用于異構計算機系統中調度工作流應用的方法。Ghosn等人[29]提出了一種基于確定性和隨機性的開放式車間調度并行遺傳算法等。

從以上相關工作可以看出，隨著計算機從單芯片系統發(fā)展到集群系統，遺傳算法也從小規(guī)模串行走向大規(guī)模并行，并被廣泛應用于解決各種超大規(guī)模并行優(yōu)化問題。本文面向國產申威26010 異構眾核處理器，基于遺傳算法完成大規(guī)模多并行參數自動調優(yōu)。該方法對部署在“神威·太湖之光”上應用程序數據進行合理劃分，采用遺傳算法完成大規(guī)模并行參數尋優(yōu)，以期充分利用主核和從核資源，獲取應用程序最高性能。

2.3 本文工作

遺傳算法是通過模擬自然進化法則來解決各種優(yōu)化問題的一種有效算法。它通過隨機初始化一系列種群，以非確定性的方式搜索整個問題空間。對所有問題參數（基因）進行編碼，通過適應度來選擇判斷基因優(yōu)劣，并選擇優(yōu)良基因遺傳給下一代，從而提高種群的平均質量。遺傳算法中每一個后代都通過一定概率發(fā)生反轉、變異，有效避免過早收斂到局部最優(yōu)解。通過選擇和組合優(yōu)良個體的迭代過程產生更好的個體，直到找到最優(yōu)解或者達到停止條件。

結合申威26010 眾核處理器結構特征，將應用程序計算量較大的部分部署在從核上進行加速，部署在從核上的應用程序需要對應用程序進行二級數據分塊，第一級分塊得到MPI 規(guī)模參數（TX，TY），第二級分塊得到從核數據規(guī)模參數（NX，NY）。

本文以二維有限差分模板計算為例，測試和比較模板計算的性能。本文中遺傳算法流程圖如圖2所示，基本操作包括以下部分：

編碼：本文將MPI 數據規(guī)模參數（TX，TY）和從核數據規(guī)模參數（NX，NY）作為“染色體基因”。對基因進行二進制編碼，隨機初始化生成種群。

Fig.2 Flow diagram of algorithm圖2 算法流程圖

選擇：遺傳算法通過適應度函數衡量染色體優(yōu)劣。本文利用CPE 并行計算獲得適應度，通過輪盤賭算法選擇出“優(yōu)良基因”，充分體現了“適者生存、優(yōu)勝劣汰”的自然進化法則。

交叉：自然界通過繼承“父親”和“母親”的優(yōu)良基因獲得“進化”。本文對輪盤賭算法選擇的“優(yōu)良基因”進行單點交叉，獲取下一代基因。

變異：基因突變是產生新個體，跳出局部最優(yōu)的有效方式。本文設定變異概率，從種群中選擇個體，隨機選取變異點進行變異。

運行本文遺傳算法程序，自動修改應用程序的數據分割參數，采用一系列遺傳操作對兩級參數自動尋優(yōu)，尋找合適的數據分塊加速應用程序。

3 神威并行參數自動尋優(yōu)

3.1 染色體編碼和種群初始化

本文提出對參數組合的自動尋優(yōu)方法，使用遺傳算法來解決參數的組合優(yōu)化問題。為更好地解釋本文方法，以二維有限差分模板計算算法為例進行描述和分析。根據SW26010 異構眾核處理器的結構特征可知，應用程序部署在主從核上，主核與從核上數據的分配將嚴重影響到應用程序的性能。本文將單個主核上處理的數據量TX×TY與單個從核上處理的數據量NX×NY作為染色體完成遺傳操作。遺傳算法不能直接處理問題空間內參數組合，將參數集的編碼作為基因輸入，將4 個基因參數（TX，TY，NX，NY）用二進制編碼表示，用染色體形式表示優(yōu)化問題的可行解。

TX、TY作為MPI 數據規(guī)模參數，本文中取值為0 到1 023 內的整數值，故選擇9 位二進制串，即000000000 到111111111 進行編碼；基因NX、NY是從核數據規(guī)格參數取值，本文取值為0 到127 內整數，選擇用6 位二進制串，即000000 到111111 進行編碼表示。將4 個參數編碼為一個30 位的基因串，即染色體用于表示個體所有參數組合解。

本文采用隨機方法產生初始種群。把二進制編碼解碼為十進制數，二進制編碼解碼位實數的映射公式如下：

其中，M表示由二進制編碼對應的十進制數值，xi位對應基因變量的二進制表示，bi和ai表示對應基因變量二進制的上下限，l為二進制基因串長度，本文取值為30。另外，受神威系統結構影響，基因NY取值必須為8的整數倍，基因TY取值必須為8×NY的整數倍。

3.2 適應度函數

適應度函數是用來評判基因優(yōu)劣的標準，個體適應度高低決定了是否將其基因遺傳給下一代。本文在申威國產處理器上測試二維有限差分模板計算性能，計算性能作為適應度反饋給遺傳函數，性能高則適應度高，遺傳給下一代的概率就更大。

二維有限差分模板計算是一種基于偏微分方程的數值離散方法，被廣泛應用于解決地震波模擬、石油勘探等各種非線性問題，本文中有限差分的具體計算形式如圖3 所示，每個中心單元的取值由上下左右8 個單元的取值所確定。

Fig.3 2D finite difference Stencil calculation diagram圖3 二維有限差分模板計算示意圖

另外，本文還對有限差分的單元進行矢量化，并加載到4 個SIMD 寄存器，同時對4 個SIMD 寄存器進行處理，即可以同時計算4 個單元，具體計算形式如圖4 所示。

Fig.4 Parallel computation of 4 SIMD registers圖4 4 個SIMD 寄存器并行計算示意圖

3.3 并行模塊

本文采用主從動態(tài)并行方式進行異構并行編程，即通過MPI+Athread 的方式使用主核和從核，主核主要負責任務分配，從核進行并行計算和寫回計算結果。每個主核（MPE）上可運行一個MPI 進程，Athread 是神威系統特有的線程庫，用來控制從核陣列。該方式適合從核計算時間不固定的情況，采用兩級主從并行方式進行大規(guī)模并行計算，第一級是進程級別的主從并行，第二級是異構眾核處理器核組內部的主從并行。

主核部分偽代碼如算法1 所示，MPI 實現多個主核之間的并行，Athread 提供封裝函數庫和API 接口，Athread 從核并行程序中主核進程內容包括相應頭文件、共享變量定義、從核口函數類型聲明、初始化從核軟件環(huán)境、啟動線程、回收線程、終止從核環(huán)境。

算法1主核偽代碼

從核進程內包括相應頭文件、共享變量定義、從核局存變量聲明、從核線程綁定、發(fā)起DMA（direct memory access）讀數據、完成計算、發(fā)起DMA 寫回數據。具體從核部分偽代碼如算法2 所示。

算法2從核偽代碼

3.4 選擇和繁衍

本文使用輪盤賭算法進行選擇操作，保留更優(yōu)良的染色體作為雙親染色體為下一代提供基因。選擇的過程是達爾文優(yōu)勝劣汰、適者生存自然進化規(guī)律的體現。經輪盤賭選擇得到的雙親染色體通過交叉算子將優(yōu)良基因遺傳給下一代，但只進行交叉操作容易導致過早收斂進入局部最優(yōu)，故本文還通過變異的方法跳出局部最優(yōu)尋找其他更優(yōu)解。

輪盤賭算法的基本思想是根據適應度函數值來評判個體被選擇的概率，適應度越高，被選擇的概率越大。首先，計算種群適應度，求得每個染色體被選擇的概率：

其中，f（xi）為適應度函數值，n為個體總數，求取每個染色體的累積概率：

此時，生成0 到1 內的隨機數r，并判斷r在累積概率內的所在區(qū)間，得到相應染色體。按照以上規(guī)則，采用輪盤賭算法選取在當前適應度函數下更可能存活的個體，在本文中即選擇出性能更高的染色體。被選中的染色體成為雙親進行交叉操作，將優(yōu)良基因遺傳給下一代。

3.4.1 交叉算子

交叉操作是遺傳算法中最主要的遺傳操作，通過組合雙親染色體的優(yōu)良基因特性得到新的下一代個體，體現了信息交換和優(yōu)勝劣汰的思想。本文采用了單點交叉法，如圖5 所示，在輪盤賭算法選出的雙親染色體中隨機選擇交叉點，兩條染色體交叉位之后的基因進行位置交換產生新的兩條染色體，重復此操作直到達到一個種群的個體數。具體算法實現的偽代碼如下：

算法3交叉算子偽代碼

Fig.5 Crossover operator圖5 交叉算子

3.4.2 變異算子

變異操作是解決遺傳算法陷入局部最優(yōu)的有效方法，通常有根據概率隨機選擇染色體或固定染色體兩種變異方式。本文采用了前一種方式，以1%的概率進行變異操作。從種群中隨機選擇一個染色體，對選中的染色體隨機選擇一個變異點進行變異。算法如下：

算法4變異算子偽代碼

4 性能結果與分析

4.1 二維有限差分模板計算測試

本例測試在申威26010 國產異構眾核處理器下進行，為簡單化測試模型，測試函數采取為邊界值等于2 的二維有限差分模板計算模型。使用64 個從核進行并行計算，采用遺傳算法自動分配MPI 規(guī)格參數（TX，TY）和從核規(guī)格參數（NX，NY）。通過比較執(zhí)行時間、性能、加速比3 個評價指標，評價基于遺傳算法自動選取的最優(yōu)并行參數對于面向“神威·太湖之光”的二維有限差分模板計算算法性能的影響。受“神威·太湖之光”平臺限制，遺傳算法部分使用Python 實現，性能并行計算適應度函數部分使用C 語言實現。

本例實驗中遺傳算法內的控制參數選用固定值，交叉率為80%，變異率為2%，種群大小為50，迭代次數選取50 次。圖6 展示了在該條件下隨迭代次數增加，性能提升情況。MPI 參數取值為TX=243，TY=1 156，從核規(guī)格參數取值為NX=44，NY=72 時，性能趨于穩(wěn)定值，達到最高性能13.744 306 GFlop/s。

為提供真實的性能分析，本文通過Roofline模型[9]來分析程序的性能上界，該方法在特定平臺上尋找特定應用程序性能上界。二維有限差分模板計算量為11 Flop，SW26010 每個核組的測量帶寬近似為26 GB/s[20]，故在SW26010 單核心組上的二維有限差分模板計算算法的性能上界近似為：

Fig.6 Graph of performance changes with increase of genetic iterations圖6 遺傳代數增加性能變化圖

但上述性能上界的計算包括一些在實際二維有限差分模板計算程序中不可能實現的強假設。首先，二維有限差分數據存在冗余讀?。黄浯?，二維有限差分模板計算數據不對齊使得數據訪問帶寬不能達到上限；最后，onchip 操作將阻塞主存訪問。故在實際情況下，難以達到性能上界的80%[30]。本文最高性能達到性能上界的77%，效果較好。

為考察從核并行和SIMD 并行計算對性能影響，通過表1 展示了編譯系統自動分配的運行時間，使用10 次隨機選取參數中運行時間最少的與使用遺傳算法得到的并行參數實現64 個從核運行和加入SIMD的運行時間對比。從表1 看出，編譯系統自動分配將導致數據的分散化，運行時間為0.569 065 s，之后3組實驗數據都以此為基礎計算對應的加速比。隨機選擇參數難以得到最優(yōu)分配參數，10 次隨機選擇參數中最小的運行時間為0.160 922 s，達到3.53 倍加速比。使用本文遺傳算法自動尋優(yōu)最優(yōu)并行參數運行時間為0.075 774 s，加速比可達7.51，明顯高于隨機分配值。此外，本文使用遺傳算法得到的最優(yōu)并行參數進一步加入了SIMD 處理，運行時間為0.052 724 s，加速比為10.79。

Table 1 Comparison of running time and acceleration ratio表1 運行時間、加速比對比表

4.2 三維逆時偏移成像算法測試

為進一步證明本文方法正確性與實用性，對三維逆時偏移成像算法進行測試與分析。地震成像是石油工業(yè)中尋找儲蓄層位置的基本工具，通過生成地形圖像探究地質結構。地震建模中首先產生聲波并記錄距離震源一定距離處地表的響應；然后對記錄數據采用某種算法進一步重建傳播介質的性質[3]。描述地震波傳播要非常精確的復雜波方程。逆時偏移成像算法（reverse time migration，RTM）利用雙程波生成地形圖像，在高陡構造、鹽下成像中呈現顯著優(yōu)勢，是目前地震建模中最常用的偏移算法之一[4-5]。圖7 為本文RTM 算法流程圖。從流程圖中可知RTM算法的主要原理是邊界值為2和邊界值為4的三維有限差分模板計算。具體計算方式如圖8 所示。

本文在“神威·太湖”上實現RTM 算法并對該算法進行分析，由于在計算過程中僅有一個方向的數據連續(xù)存儲在內存中，這種非均勻內存訪問導致非常大的時間開銷。本文提出使用遺傳算法對影響RTM 算法性能嚴重的三維從核規(guī)格參數進行自動尋優(yōu)，充分利用硬件資源以減少時間開銷。

本例中，將三維從核規(guī)格參數組合的二進制碼作為染色體。受申威異構眾核處理器架構和RTM 算法條件限制，三維參數NX、NY、NZ的取值變化范圍分別為[1，500]、[1，1 000]和[1，1 000]內的整數，其中NX必須為4 的倍數，并且NX、NY、NZ的乘積不超過3×107。采用RTM 算法運行時間的倒數作為適應度函數，即當算法運行時間越短，對應染色體適應度越高。本例中遺傳算法迭代次數為30 次，其他控制參數均與二維有限差分模板計算算法相同。

圖9 展示了使用本文方法當迭代次數增加時RTM 算法的優(yōu)化結果。從圖中可以看出，隨迭代次數增加，算法性能有效提高，并在第21 次迭代時取得最優(yōu)效果，然后保持穩(wěn)定值。

表2 展示了系統自動分配參數、10 次隨機選擇取參數中運行時間最少的與采用本文自動尋優(yōu)方法得到的參數三種情況下三維逆時偏移成像算法運行時間與加速比，加速比以編譯系統自動分配的數據為基礎進行計算比較。從表中可以看出，與系統自動分配參數相比，采用本文方法自動尋優(yōu)得到的最優(yōu)參數使三維逆時偏移成像算法達到了6.31倍加速比。

Fig.7 Flow chart of RTM algorithm圖7 RTM 算法流程圖

Fig.8 3D finite difference Tencil calculation diagram圖8 三維有限差分模板計算示意圖

Fig.9 Change in inverse of RTM running time as the number of iterations increases圖9 隨迭代次數增加RTM 運行時間倒數變化圖

Table 2 Comparison of running time and acceleration ratio of RTM algorithm表2 RTM 運行時間與加速比對比表

5 結論

本文對“神威·太湖之光”深層架構進行研究和分析，對國產申威異構眾核處理器上的并行參數進行研究，首次提出了面向神威國產處理器的并行參數自動尋優(yōu)方法。該方法基于遺傳算法實現了并行參數自動尋優(yōu)，通過犧牲一定時間在10 億次尋址空間中尋找較優(yōu)的參數，在時間和性能中尋找平衡，有效解決了一個申威眾核異構處理器上數據規(guī)模參數分配的NP 問題。自動獲取的并行參數對MPI 數據規(guī)模和從核數據規(guī)模進行合理劃分，在“神威·太湖之光”上進行二維有限差分模板計算算法測試和三維逆時偏移成像算法測試，與編譯系統自動分配參數相比最高分別達到了10.79 倍和6.31 倍的加速比。對于有限差分模板計算、逆時偏移成像等算法在異構多核超級計算機上的并行優(yōu)化具有指導意義。