面向申威眾核處理器的并行SaNSDE 算法

康 上，錢雪忠，甘 霖

1.江南大學 人工智能與計算機學院 物聯網技術應用教育部工程研究中心，江蘇 無錫 214122

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

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

演化算法作為經典的啟發式算法，有著易理解、自適應和搜索能力強等優點，從離散的單目標問題到連續的多目標問題，其適用于解決各種復雜的黑盒優化問題。演化算法在解決低維問題上有著優異的表現，然而隨著問題決策變量增加，算法的搜索能力會急劇下降。針對這個問題，現在最為常用的解決方案是將合作協同進化模型（cooperative co-evolution，CC）[1]與演化算法相結合，CC 模型的基本思想是將規模較大的問題分解為多個小規模問題。大量實驗證明這樣的組合取得了很好的效果[2-4]。后來為了提高最優解的質量，Omidvar 等人又提出了基于貢獻的合作協同進化模型[5]及其改進[6-7]。然而遺憾的是，上述研究仍然是處于串行思路下展開的，當面對復雜度高的大規模問題時，算法性能仍然得不到保證。

由于演化算法具有天然的并行性，許多大規模優化問題的解決思路逐步向并行化靠攏。與此同時，高性能計算機的發展與普及為算法的并行化提供了強有力的硬件支撐。目前已經有很多演化算法在多核處理器架構上實現并行化的探索。

Roberge 等人在CUDA（compute unified device architecture）上面實現并行遺傳算法解決無人機路徑規劃問題[8]。Ferrucci 等人在MapReduce 平臺上分別實現了基于主從模型、細胞模型和島嶼模型的并行遺傳算法，并比較了三個模型的性能表現[9]。Cao等人在Spark上實現了并行協同粒子群算法[10]。Abdelhafez等人使用MPI（message passing interface）在多核處理器上實現了基于島嶼模型的分布式遺傳算法[11]。總結以上研究，目前并行遺傳算法大多采用島嶼模型來實現，根據種群分布的原則來劃分任務。然而對于島嶼模型來說，遷移機制會影響算法的性能和尋優能力：遷移頻率和遷移規模過大會增大通信開銷，過小又會降低種群多樣性最終影響解的質量，這無疑增大了島嶼模型的設計難度。另一方面，上述研究也未能對適應度計算過程做出優化。適應度作為判斷個體優劣程度的評價指標，需要在優化過程中對種群中所有個體進行評估，判斷產生的新個體能否進入下一代。問題越復雜，適應度計算量就會越大，例如在資源優化調度、深度學習模型超參數的尋優等問題中，單個個體的適應度評估就要花費很長的時間，在這種情況下程序性能很難得到保證。此外，受硬件平臺的限制，大多數的并行化研究只采用一級并行的策略，未充分挖掘演化算法的并行化潛力。

本文所使用的“神威·太湖之光”實驗平臺，是世界上首臺峰值運算性能超過十億億次量級的超級計算機，機器全部采用申威26010 國產處理器，申威獨特的主從核式物理架構為實現二級并行策略提供了可能。基于申威眾核處理器平臺實現并行演化算法的研究已經有了一些初步的進展，趙瑞祥等人提出了“粗粒度-主從式”混合并行遺傳算法[12]。沈煥學等人實現了并行非支配排序遺傳算法以解決多目標優化問題[13]。以上研究僅局限于低維問題，沒有對大規模問題的優化做進一步的討論。

基于以上問題，本文面向申威異構眾核處理器平臺，以采用二級并行策略的自適應鄰域搜索的差分進化算法（self-adaptive differential evolution algorithm with neighborhood search,SaNSDE）為問題求解過程的優化算法，研究在超級計算機神威·太湖之光上解決大規模優化問題的并行化策略。本文主要工作如下：

（1）針對申威眾核處理器特殊的架構設計了進程并行+線程并行的二級并行模型。進程級并行使用消息傳遞接口實現了基于維度分布原則的CC 模型和基于種群分布原則的池模型；線程級并行使用64 個從核加速了個體適應度的計算過程。

（2）實現了并行合作協同自適應鄰域搜索的差分進化算法（parallel-cooperative co-evolution self-adaptive differential evolution with neighborhood search,PCCSaNSDE）。研究了算法在解決高維問題上的表現和大規模并行后的性能。

（3）為了進一步探索SaNSDE 算法使用混合模型后進行大規模擴展的性能表現，在CC 模型的基礎上引入池模型。實現了混合模型下的并行自適應鄰域搜索的差分進化算法（parallel-hybrid self-adaptive differential evolution with neighborhood search,P-HSaNSDE）。

1 相關背景知識

1.1 “神威·太湖之光”和申威26010處理器

“神威·太湖之光”是中國第一臺全部采用國產處理器的超級計算機，2016—2017 年曾四次榮登TOP500 超級計算機榜首，在2019 年11 月最新一期全球超級計算機TOP500 中位列第三[14]。

“神威·太湖之光”計算機系統搭載的是申威26010（sunway26010，SW26010）異構眾核處理器。SW26010 基本構架如圖1 所示，一個處理器包含4 個核組（core group，CG）共260 個核心，它們都是64 位的RISC 內核。每個核組包括1 個控制核心（management processing element，MPE）和以8×8 陣列方式排列的64 個計算核心（computing processing element，CPE），即一個主核和64 個從核。在執行運算任務時，MPE 與CPE 的分工是不同的，MPE 主要負責任務的管理和調度；CPE 主要負責執行重復密集的計算。每個SW26010 處理器有32 GB 的內存，單個核組內存為8 GB。每個從核包含64 KB 的片上局部數據空間（local directive memory，LDM），LDM 作為用戶控制快速緩沖。從核訪問主存有兩種方式：gld/gst（global load/store）直接離散訪問和DMA（direct memory access）方式批量訪問，從核之間使用寄存器進行通信。SW26010 特殊的設計方式可以提高整體性能，但是獨特的架構也增大了編程難度，數據的分割會嚴重影響訪存、通信和計算能力[15-16]。因此如何對程序的任務和數據進行劃分，充分發揮從核之間的協作能力和計算效率，是提升性能的關鍵。

1.2 SaNSDE 算法

差分進化（differential evolution，DE）算法于1997年由Storn 和Price 在遺傳算法思想的基礎上提出，模擬遺傳算法中的雜交、變異、復制來設計算子，用于求解多維空間中全局最優解。由于差分進化算法具有結構簡單、易于實現、收斂速度快等優點，被廣泛應用于人工神經網絡、數據挖掘和模式識別等各個領域。DE 有三個主要步驟：（1）變異。使用差分策略實現個體變異，最常見的方法是將兩個不同的個體向量縮放后與待變異個體向量合成。（2）交叉。交換個體間某些向量的信息產生新的個體。（3）選擇。采用優勝劣汰的原則選擇進入下一代的個體。

SaNSDE 算法[17]為DE 算法的改進，相比于DE 算法有兩個改進：（1）變異率F由高斯分布和柯西分布隨機生成，這樣可以產生較大的搜索步長避免結果陷入局部最優解。（2）引入兩種變異策略，在優化過程中根據問題的不同選擇合適的策略，并且可以在優化過程中自適應交叉率CR 的值。

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

1.3 合作協同進化模型

CC 模型是一個維度分布模型，一個完整的CC模型應該包括兩個流程：問題分解和問題優化。對于一個復雜的高維問題，CC 先將其劃分為多個維度較小的子問題，劃分的原則是將具有相關性的決策變量分為一組，互不相關的決策變量放在不同的組。然后演化算法分別對這些子問題求解，最后將子問題的最優解進行整合就得到了全局最優解。

如圖2（a）所示，對于一個D維問題D={x1,x2,…,xD}，CC 將其劃分為M個子問題，按順序進行優化。CC 框架的每個子組在優化過程中是相互獨立的，只需要在優化結束后同步最優解和種群信息，具備天然的并行性，每個子組可以分布在不同的進程上同時進行優化。分布式CC（distribute cooperative coevolution，dCC）與串行CC 在問題分解階段是相同的，區別在于問題優化階段，如圖2（b）所示。

Fig.2 Structure of CC圖2 CC 框架的結構

1.4 CCSaNSDE 算法

CCSaNSDE 算法將SaNSDE 作為CC 模型問題求解階段的優化器，算法具體的執行步驟如下：

（1）初始化種群，對每個個體進行適應度評估，找到當前最優個體和最優解gbest。

（2）將高維度復雜問題分解為多個低維子問題。

（3）按一定順序對每個子問題進行優化，優化完成后更新種群信息。

（4）子問題全都執行完優化操作后重新計算個體適應度，找到當前最優個體和最優解gbest。記在j代中，第i個子種群Si最優個體為。通常，子種群中個體適合度是通過與其他子種群中最優秀的個體相結合來計算的，全局最優值計算方法為:

（5）判斷是否達到最大迭代次數。若否，轉至步驟（3）；若是，輸出gbest。

1.5 池模型

池模型[18]是種群分布模型，池模型將所有個體放入一個共享的數據結構中，處理器可以并發地訪問池中的所有個體。但是每個個體同一時刻只允許有一個處理器對其進行寫操作。如圖3 所示，此處將池設計為一個數組，其中N代表個體數量，數組被劃分為M份，即將種群劃分為M個子種群。多個處理器可以共同處理一個子種群。每個處理器只與池進行交互，彼此之間相互獨立不進行通信。

Fig.3 Structure of pool model圖3 池模型結構

2 SaNSDE 并行算法的設計與實現

申威眾核處理器獨特的主從核式架構為實現算法的高度并行化提供了理想的平臺，然而傳統的并行演化算法難以充分發揮申威的優勢。因此本章針對其物理架構設計了算法的二級并行模型。第一級為進程級并行，即主核間并行；第二級為線程級并行，即從核間并行。主核間并行使用MPI 進行通信，用來進行任務劃分。本文實現了維度分布模型CC和種群分布模型池，從問題維度和種群數量兩方面來分解大規模問題，并且對模型進行了調整使之適用于多核擴展。從核間并行使用申威處理器特有的Athread 線程庫來發揮從核的加速性能，將個體信息分配到64 個從核上，實現個體適應度計算的并行。

2.1 進程級并行

2.1.1 P-CCSaNSDE 算法的設計與實現

由于dCC 并不具備計算資源分配的功能，很難去適應核心數量的變化，為了使CCSaNSDE 算法更加易于進行多核擴展，本文在使用CC 模型的基礎上引入了主從模型。與傳統主從式模型所不同的是從節點不只是執行適應度計算，也會執行優化過程。更確切地說，主節點作為一個管理者主要負責任務分發和管理，優化操作由從節點完成。具體實現步驟如圖4 所示，設置0 號進程為主節點，其余進程為從節點。主節點存有種群信息以及分組結果，優化開始時，主節點將子組依次分配到從節點上，從節點得到子組后使用SaNSDE 算法進行優化，優化完成后將優化結果反饋至主節點。整個優化過程中，從節點之間不進行通信，僅與主節點進行數據交換。各個子組之間的優化同時進行并且相互獨立，這也體現出了P-CCSaNSDE 算法的并行性。

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

當所有子組優化完成后，需要同步種群信息，對于dCC 而言更新種群就意味著要與主節點進行通信交換數據，頻繁通信會花費大量的時間，影響程序性能。為了減少這種損失，本文設置閾值MaxGen，即每個子組需要在相應子節點上優化MaxGen次才與主節點通信更新種群。

在分組數量固定的情況下進行擴展性實驗時，核心數與分組數量不一定相等，考慮到負載均衡的原則，本文對模型結構做出適當調整，當核心數小于分組數量時，子組會被均等分配到每個核心上；當核心數等于分組數量時，子組與核心一一對應；當核心數大于分組數量時，多個核心將處理同一個子組，由主節點選擇其中最優解。

2.1.2 P-HSaNSDE 算法的設計與實現

為了避免單一模型造成粒度過粗或者過細的問題，本文在CC 框架的基礎上又引入了池模型。探索使用混合模型下進行大規模擴展的性能。整個程序分為兩層：在第一層dCC 模型將高維問題劃分為低維子組，屬于維度分布模型；第二層為池模型，將每個子組進一步分解為子種群，屬于種群分布模型。對于一個D維問題首先使用分組策略劃分為M個子組{S1,S2,…,SM}。在這里將每一個子組Si看作一個種群，每個種群與分配到的處理器共同組成一個池模型，若種群S1分配到兩個進程P1和P2，則將S1分為兩個子種群,每個進程分配到一個子種群。第二個種群S2分配到三個進程，則將其劃分為三部分與三個進程一一對應。考慮到當單個進程內個體數量過小時，會降低種群多樣性，影響算法的搜索能力，本文引入了Jia 等人在文中提到的種群平衡性策略[19]。種群數量與處理器的數量相關聯，當處理器增加時，種群數也會增加；當處理器減少時，種群數也會相應減少。種群數量|Si|和進程數|Pi|的關系如下:

這樣可以保證每個處理器都有相同數量的個體，不會由于進程數增加造成個體數量降低。引入池模型的算法進行大規模擴展時，會先根據種群一致性原則擴充種群，當優化結束后，采用精英主義的原則，保留子種群中較優的個體。

2.2 線程級并行

以上模型分別從維度和種群方面劃分任務并均等分配到不同處理器上，減少了單個處理器的計算壓力。考慮到每個處理器在執行優化操作時需要進行適應度評估，比較優化前后的效果決定種群是否進入下一代。復雜的大規模問題往往會在適應度計算時花費大量的時間，對這部分進行優化也是提升程序性能的關鍵。針對此問題，本文使用申威眾核處理器特有的Athread 線程庫，將種群內個體的適應度評估交給從核陣列進行加速。

從核訪存方式有兩種：一是通過寄存器直接訪存；二是寄存器LDM 訪存。由于申威26010 處理器主從核之間沒有共享緩存，寄存器直接訪存時間開銷巨大[20]，本文采用DMA 方式將數據拷貝至LDM 之后再進行訪存，通過這種方法提高訪存速度。

主核偽代碼如算法1 所示。由于Athread 是共享內存編程模型，主從核都要定義共享變量，函數開始時要先初始化線程庫，然后啟動線程組進行計算并等待計算完成，最后當程序結束后要將線程回收。

算法1主核偽代碼

從核偽代碼如算法2 所示。首先發起DMA 將主存中的數據發送至從核的LDM，計算完成后發起DMA 將結果發送回主核。

算法2從核偽代碼

3 實驗與分析

3.1 適應度函數及實驗參數

為了測試P-CCSaNSDE 和P-HSaNSDE 兩個算法在申威眾核處理器上大規模擴展的效果，本文以優化結果和加速比兩個指標評價算法的性能。適應度函數采用以下4 個標準測試函數，為了模擬大規模問題，將n設置為1 024。

4 個標準測試函數的理論最小值為0，優化結果越接近0，說明算法的優化效果更好。種群中個體數量NP 為64，迭代的終止條件為單進程上適應度評估次數達到2×106次，設置MaxGen為50，即每個進程優化50 次后再進行通信交換數據。實驗結果都是獨立運行25 次后取平均值。

3.2 收斂結果

本節以采用島嶼模型的P-SaNSDE 算法為基準進行結果對比。算法在測試函數F1、F2、F3 和F4 上的收斂結果如表1 所示。隨著核心數量增加，兩個并行算法的優化結果都有較為明顯的提升。相對于PSaNSDE 算法，采用CC 模型的P-CCSaNSDE 算法收斂結果變化的趨勢更顯著，最優解的質量更高，在F1函數上效果差異最大。需要特別指出的是，當處理核心數小于分組數量時，解的質量并沒有很明顯的提升，但是當處理核心數大于分組數量時，優化效果有了大幅度的提升。這說明當多個核心處理一個子組時，優化過程中會增加產生優質解的可能性，從而提高最終解的質量，這也是大規模并行的優勢所在。通過觀察實驗數據，P-SaNSDE 算法，從1 核擴展到1 024 核之后，優化結果雖有提升，但是并沒有很大的突破。這說明CC 模型相較于需要考慮遷移策略的島嶼模型，更易于進行大規模擴展。

Table 1 Fitness of P-SaNSDE and P-CCSaNSDE on benchmark functions表1 P-SaNSDE 和P-CCSaNSDE 算法在測試函數上的適應度

圖5 為采用dCC+Pool 混合模型的P-HSaNSDE算法在4 個測試函數上優化結果隨核數增加的變化情況。隨著核心數量增加，與P-CCSaNSDE 算法相比，P-HSaNSDE 在F2 和F3 函數的收斂效果有了進一步的提升，在F1 和F4 函數上則略有下降。這說明針對特定問題，使用合適的混合模型可以提高最優解的質量。

Fig.5 Fitness of 4 benchmark functions圖5 4 個測試函數的適應度

3.3 加速比

CC 模型與混合模型雖然實現方法不同，但是大規模擴展后單個核心內所處理的種群大小是相同的，因此性能是相同的。本節僅以P-CCSaNSDE 算法為例，討論算法二級并行后的性能表現。如圖6 所示，隨著核心數量增加，算法的性能有很大的提升：當核數為1 時，算法是串行執行的，唯一的進程需要處理所有的子組，此時程序的運行時間最長；隨后核心數量每增加一倍，單核心處理的子組數量就減少50%，運行時間也隨之減少50%。當核數增加至32 時，每個進程只處理一個子組，此時程序運行時間最低，達到最大加速比，在4個標準測試函數上分別為134.29、186.05、239.01 和189.80。

在隨后的大規模擴展的實驗中，核數從32 提升到1 024，算法性能逐漸下降，這是由于核數增加會導致進程間通信耗時增大，最終影響性能。然而從表2可知，當核數最高擴展到1 024 時，算法仍然有很高的加速比，運行時間遠遠低于串行版本。經過大規模擴展后的算法，不僅在優化結果方面有較大優勢，而且也有極高的性能表現。

Table 2 Speedup表2 加速比

3.4 相關工作對比

從優化結果來看，使用CC 模型和混合模型的算法在4 個測試函數上的最優解質量都要遠遠高于PSaNSDE，并且隨著擴展規模增大，這種差異就愈加明顯。兩個算法在4 個測試函數上的收斂結果各有優劣。P-CCSaNSDE 在F1 和F4 函數上收斂效果較好，而P-HSaNSDE 在F2 和F3 函數上收斂效果更優。

從算法運行時間上來看，采用二級并行后的算法有著十分優異的性能表現，即使進行大規模擴展后算法運行時間仍然遠遠低于串行版本。與傳統僅使用一級并行的算法相比，使用Athread 加速適應度計算后，算法獲得了更好的加速效果。

Fig.6 Speedup of 4 benchmark functions圖6 4 個測試函數的加速比

4 結束語

本文以“神威·太湖之光”為實驗平臺，通過研究和分析申威異構眾核處理器特殊的架構，對演化算法求解大規模優化問題從進程級和線程級兩方面進行了高度并行化實現。在模型選擇上，分別使用了CC 模型和CC+Pool 的混合模型，并對其進行了大規模的擴展。為了充分發揮SW26010 處理器的性能，使用從核對適應度計算部分進行了加速。實驗表明，在高維測試函數上，多核擴展后的P-CCSaNSDE和P-HSaNSDE 算法表現出了很強的搜索能力，相較于P-SaNSDE 算法，收斂結果有很明顯的提升，并且二級并行后的算法具有很高的加速比，在4 個測試函數上最高達到了239.01。