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

康 上，錢雪忠，甘 霖

1.江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院 物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無錫 214122

2.國家超級(jí)計(jì)算無錫中心，江蘇 無錫 214131

3.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084

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

由于演化算法具有天然的并行性，許多大規(guī)模優(yōu)化問題的解決思路逐步向并行化靠攏。與此同時(shí)，高性能計(jì)算機(jī)的發(fā)展與普及為算法的并行化提供了強(qiáng)有力的硬件支撐。目前已經(jīng)有很多演化算法在多核處理器架構(gòu)上實(shí)現(xiàn)并行化的探索。

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

本文所使用的“神威·太湖之光”實(shí)驗(yàn)平臺(tái)，是世界上首臺(tái)峰值運(yùn)算性能超過十億億次量級(jí)的超級(jí)計(jì)算機(jī)，機(jī)器全部采用申威26010 國產(chǎn)處理器，申威獨(dú)特的主從核式物理架構(gòu)為實(shí)現(xiàn)二級(jí)并行策略提供了可能?；谏晖姾颂幚砥髌脚_(tái)實(shí)現(xiàn)并行演化算法的研究已經(jīng)有了一些初步的進(jìn)展，趙瑞祥等人提出了“粗粒度-主從式”混合并行遺傳算法[12]。沈煥學(xué)等人實(shí)現(xiàn)了并行非支配排序遺傳算法以解決多目標(biāo)優(yōu)化問題[13]。以上研究?jī)H局限于低維問題，沒有對(duì)大規(guī)模問題的優(yōu)化做進(jìn)一步的討論。

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

（1）針對(duì)申威眾核處理器特殊的架構(gòu)設(shè)計(jì)了進(jìn)程并行+線程并行的二級(jí)并行模型。進(jìn)程級(jí)并行使用消息傳遞接口實(shí)現(xiàn)了基于維度分布原則的CC 模型和基于種群分布原則的池模型；線程級(jí)并行使用64 個(gè)從核加速了個(gè)體適應(yīng)度的計(jì)算過程。

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

（3）為了進(jìn)一步探索SaNSDE 算法使用混合模型后進(jìn)行大規(guī)模擴(kuò)展的性能表現(xiàn)，在CC 模型的基礎(chǔ)上引入池模型。實(shí)現(xiàn)了混合模型下的并行自適應(yīng)鄰域搜索的差分進(jìn)化算法（parallel-hybrid self-adaptive differential evolution with neighborhood search,P-HSaNSDE）。

1 相關(guān)背景知識(shí)

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

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

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

1.2 SaNSDE 算法

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

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

Fig.1 Structure diagram of SW26010 multi-core processor圖1 申威26010眾核處理器結(jié)構(gòu)圖

1.3 合作協(xié)同進(jìn)化模型

CC 模型是一個(gè)維度分布模型，一個(gè)完整的CC模型應(yīng)該包括兩個(gè)流程：?jiǎn)栴}分解和問題優(yōu)化。對(duì)于一個(gè)復(fù)雜的高維問題，CC 先將其劃分為多個(gè)維度較小的子問題，劃分的原則是將具有相關(guān)性的決策變量分為一組，互不相關(guān)的決策變量放在不同的組。然后演化算法分別對(duì)這些子問題求解，最后將子問題的最優(yōu)解進(jìn)行整合就得到了全局最優(yōu)解。

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

Fig.2 Structure of CC圖2 CC 框架的結(jié)構(gòu)

1.4 CCSaNSDE 算法

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

（1）初始化種群，對(duì)每個(gè)個(gè)體進(jìn)行適應(yīng)度評(píng)估，找到當(dāng)前最優(yōu)個(gè)體和最優(yōu)解gbest。

（2）將高維度復(fù)雜問題分解為多個(gè)低維子問題。

（3）按一定順序?qū)γ總€(gè)子問題進(jìn)行優(yōu)化，優(yōu)化完成后更新種群信息。

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

（5）判斷是否達(dá)到最大迭代次數(shù)。若否，轉(zhuǎn)至步驟（3）；若是，輸出gbest。

1.5 池模型

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

Fig.3 Structure of pool model圖3 池模型結(jié)構(gòu)

2 SaNSDE 并行算法的設(shè)計(jì)與實(shí)現(xiàn)

申威眾核處理器獨(dú)特的主從核式架構(gòu)為實(shí)現(xiàn)算法的高度并行化提供了理想的平臺(tái)，然而傳統(tǒng)的并行演化算法難以充分發(fā)揮申威的優(yōu)勢(shì)。因此本章針對(duì)其物理架構(gòu)設(shè)計(jì)了算法的二級(jí)并行模型。第一級(jí)為進(jìn)程級(jí)并行，即主核間并行；第二級(jí)為線程級(jí)并行，即從核間并行。主核間并行使用MPI 進(jìn)行通信，用來進(jìn)行任務(wù)劃分。本文實(shí)現(xiàn)了維度分布模型CC和種群分布模型池，從問題維度和種群數(shù)量?jī)煞矫鎭矸纸獯笠?guī)模問題，并且對(duì)模型進(jìn)行了調(diào)整使之適用于多核擴(kuò)展。從核間并行使用申威處理器特有的Athread 線程庫來發(fā)揮從核的加速性能，將個(gè)體信息分配到64 個(gè)從核上，實(shí)現(xiàn)個(gè)體適應(yīng)度計(jì)算的并行。

2.1 進(jìn)程級(jí)并行

2.1.1 P-CCSaNSDE 算法的設(shè)計(jì)與實(shí)現(xiàn)

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

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

當(dāng)所有子組優(yōu)化完成后，需要同步種群信息，對(duì)于dCC 而言更新種群就意味著要與主節(jié)點(diǎn)進(jìn)行通信交換數(shù)據(jù)，頻繁通信會(huì)花費(fèi)大量的時(shí)間，影響程序性能。為了減少這種損失，本文設(shè)置閾值MaxGen，即每個(gè)子組需要在相應(yīng)子節(jié)點(diǎn)上優(yōu)化MaxGen次才與主節(jié)點(diǎn)通信更新種群。

在分組數(shù)量固定的情況下進(jìn)行擴(kuò)展性實(shí)驗(yàn)時(shí)，核心數(shù)與分組數(shù)量不一定相等，考慮到負(fù)載均衡的原則，本文對(duì)模型結(jié)構(gòu)做出適當(dāng)調(diào)整，當(dāng)核心數(shù)小于分組數(shù)量時(shí)，子組會(huì)被均等分配到每個(gè)核心上；當(dāng)核心數(shù)等于分組數(shù)量時(shí)，子組與核心一一對(duì)應(yīng)；當(dāng)核心數(shù)大于分組數(shù)量時(shí)，多個(gè)核心將處理同一個(gè)子組，由主節(jié)點(diǎn)選擇其中最優(yōu)解。

2.1.2 P-HSaNSDE 算法的設(shè)計(jì)與實(shí)現(xiàn)

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

這樣可以保證每個(gè)處理器都有相同數(shù)量的個(gè)體，不會(huì)由于進(jìn)程數(shù)增加造成個(gè)體數(shù)量降低。引入池模型的算法進(jìn)行大規(guī)模擴(kuò)展時(shí)，會(huì)先根據(jù)種群一致性原則擴(kuò)充種群，當(dāng)優(yōu)化結(jié)束后，采用精英主義的原則，保留子種群中較優(yōu)的個(gè)體。

2.2 線程級(jí)并行

以上模型分別從維度和種群方面劃分任務(wù)并均等分配到不同處理器上，減少了單個(gè)處理器的計(jì)算壓力?？紤]到每個(gè)處理器在執(zhí)行優(yōu)化操作時(shí)需要進(jìn)行適應(yīng)度評(píng)估，比較優(yōu)化前后的效果決定種群是否進(jìn)入下一代。復(fù)雜的大規(guī)模問題往往會(huì)在適應(yīng)度計(jì)算時(shí)花費(fèi)大量的時(shí)間，對(duì)這部分進(jìn)行優(yōu)化也是提升程序性能的關(guān)鍵。針對(duì)此問題，本文使用申威眾核處理器特有的Athread 線程庫，將種群內(nèi)個(gè)體的適應(yīng)度評(píng)估交給從核陣列進(jìn)行加速。

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

主核偽代碼如算法1 所示。由于Athread 是共享內(nèi)存編程模型，主從核都要定義共享變量，函數(shù)開始時(shí)要先初始化線程庫，然后啟動(dòng)線程組進(jìn)行計(jì)算并等待計(jì)算完成，最后當(dāng)程序結(jié)束后要將線程回收。

算法1主核偽代碼

從核偽代碼如算法2 所示。首先發(fā)起DMA 將主存中的數(shù)據(jù)發(fā)送至從核的LDM，計(jì)算完成后發(fā)起DMA 將結(jié)果發(fā)送回主核。

算法2從核偽代碼

3 實(shí)驗(yàn)與分析

3.1 適應(yīng)度函數(shù)及實(shí)驗(yàn)參數(shù)

為了測(cè)試P-CCSaNSDE 和P-HSaNSDE 兩個(gè)算法在申威眾核處理器上大規(guī)模擴(kuò)展的效果，本文以優(yōu)化結(jié)果和加速比兩個(gè)指標(biāo)評(píng)價(jià)算法的性能。適應(yīng)度函數(shù)采用以下4 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，為了模擬大規(guī)模問題，將n設(shè)置為1 024。

4 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的理論最小值為0，優(yōu)化結(jié)果越接近0，說明算法的優(yōu)化效果更好。種群中個(gè)體數(shù)量NP 為64，迭代的終止條件為單進(jìn)程上適應(yīng)度評(píng)估次數(shù)達(dá)到2×106次，設(shè)置MaxGen為50，即每個(gè)進(jìn)程優(yōu)化50 次后再進(jìn)行通信交換數(shù)據(jù)。實(shí)驗(yàn)結(jié)果都是獨(dú)立運(yùn)行25 次后取平均值。

3.2 收斂結(jié)果

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

Table 1 Fitness of P-SaNSDE and P-CCSaNSDE on benchmark functions表1 P-SaNSDE 和P-CCSaNSDE 算法在測(cè)試函數(shù)上的適應(yīng)度

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

Fig.5 Fitness of 4 benchmark functions圖5 4 個(gè)測(cè)試函數(shù)的適應(yīng)度

3.3 加速比

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

在隨后的大規(guī)模擴(kuò)展的實(shí)驗(yàn)中，核數(shù)從32 提升到1 024，算法性能逐漸下降，這是由于核數(shù)增加會(huì)導(dǎo)致進(jìn)程間通信耗時(shí)增大，最終影響性能。然而從表2可知，當(dāng)核數(shù)最高擴(kuò)展到1 024 時(shí)，算法仍然有很高的加速比，運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)低于串行版本。經(jīng)過大規(guī)模擴(kuò)展后的算法，不僅在優(yōu)化結(jié)果方面有較大優(yōu)勢(shì)，而且也有極高的性能表現(xiàn)。

Table 2 Speedup表2 加速比

3.4 相關(guān)工作對(duì)比

從優(yōu)化結(jié)果來看，使用CC 模型和混合模型的算法在4 個(gè)測(cè)試函數(shù)上的最優(yōu)解質(zhì)量都要遠(yuǎn)遠(yuǎn)高于PSaNSDE，并且隨著擴(kuò)展規(guī)模增大，這種差異就愈加明顯。兩個(gè)算法在4 個(gè)測(cè)試函數(shù)上的收斂結(jié)果各有優(yōu)劣。P-CCSaNSDE 在F1 和F4 函數(shù)上收斂效果較好，而P-HSaNSDE 在F2 和F3 函數(shù)上收斂效果更優(yōu)。

從算法運(yùn)行時(shí)間上來看，采用二級(jí)并行后的算法有著十分優(yōu)異的性能表現(xiàn)，即使進(jìn)行大規(guī)模擴(kuò)展后算法運(yùn)行時(shí)間仍然遠(yuǎn)遠(yuǎn)低于串行版本。與傳統(tǒng)僅使用一級(jí)并行的算法相比，使用Athread 加速適應(yīng)度計(jì)算后，算法獲得了更好的加速效果。

Fig.6 Speedup of 4 benchmark functions圖6 4 個(gè)測(cè)試函數(shù)的加速比

4 結(jié)束語

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