趙瑞祥，鄭 凱，劉 垚，王 肅，劉 艷，沈煥學(xué)，周謙豪

(1.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院，上海 200062； 2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214215；3.華東師范大學(xué) 經(jīng)濟(jì)與管理學(xué)部，上海 200062)(*通信作者電子郵箱kzheng@cs.ecnu.edu.cn)

基于申威眾核處理器的混合并行遺傳算法

趙瑞祥1,2，鄭 凱1,2*，劉 垚1,2，王 肅1,2，劉 艷1,2，沈煥學(xué)1,2，周謙豪3

(1.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院，上海 200062； 2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214215；3.華東師范大學(xué) 經(jīng)濟(jì)與管理學(xué)部，上海 200062)(*通信作者電子郵箱kzheng@cs.ecnu.edu.cn)

傳統(tǒng)遺傳算法求解計(jì)算密集型任務(wù)時(shí)，適應(yīng)度函數(shù)的執(zhí)行時(shí)間增加相當(dāng)快，致使當(dāng)種群規(guī)?；蛘哌M(jìn)化代數(shù)增大時(shí)，算法的收斂速度非常緩慢?；诖?，設(shè)計(jì)了“粗粒度-主從式”混合式并行遺傳算法(HBPGA)，并在目前TOP500上排名第一的超級(jí)計(jì)算機(jī)神威“太湖之光”平臺(tái)上實(shí)現(xiàn)。該算法模型采用兩級(jí)并行架構(gòu)，結(jié)合了MPI和Athread兩種編程模型，與傳統(tǒng)在單核或者一級(jí)并行構(gòu)架的多核集群上實(shí)現(xiàn)的遺傳算法相比，在申威眾核處理器上實(shí)現(xiàn)了二級(jí)并行，并得到了更好的性能和更高的加速比。實(shí)驗(yàn)中，當(dāng)從核數(shù)為16×64時(shí)，最大加速比達(dá)到544，從核加速比超過(guò)31。

混合并行遺傳算法；神威“太湖之光”；眾核；MPI；Athread

0 引言

隨著科技進(jìn)步，計(jì)算密集型任務(wù)需求與日俱增，但許多情況下單純的串行計(jì)算已不能滿足當(dāng)前的要求，單個(gè)芯片的性能提高遇到了瓶頸[1]：越來(lái)越高的集成度，導(dǎo)致高功耗[2]和散熱問(wèn)題難以解決。采用多核或眾核已成為提高處理能力的重要手段，相應(yīng)的程序也需要從串行轉(zhuǎn)向并行。但由于串行程序與并行程序存在巨大的差異，無(wú)法自動(dòng)轉(zhuǎn)換，許多用串行方式實(shí)現(xiàn)的應(yīng)用移植到眾核平臺(tái)運(yùn)行面臨不小的挑戰(zhàn)。

目前關(guān)于并行遺傳算法的研究多數(shù)在多核平臺(tái)實(shí)現(xiàn)[3-5]，并采用消息傳遞接口(Message-Passing-Interface, MPI)編程模型，性能和加速比的提升受到主核數(shù)量的限制，當(dāng)適應(yīng)度函數(shù)的計(jì)算量復(fù)雜時(shí)性能和加速比的提升不明顯。也有關(guān)于在通用并行計(jì)算架構(gòu)[6-9](Compute Unified Device Architecture, CUDA)上基于圖形處理器(Graphics Processing Unit, GPU)的粗粒度并行遺傳算法的實(shí)現(xiàn)報(bào)道[10]。為了與GPU架構(gòu)兼容，在CUDA軟件模型中使用簡(jiǎn)化的單向環(huán)移動(dòng)，提高了遷移速度[11]。但受GPU結(jié)構(gòu)的限制，只適用單指令多數(shù)據(jù)流(Single Instruction Multiple Data, SIMD)類型的數(shù)據(jù)并行，內(nèi)部各處理核之間不允許通信，使其應(yīng)用范圍受到很大局限。曾有學(xué)者試圖利用現(xiàn)場(chǎng)可編程門陣列(Field-Programmable Gate Array, FPGA)來(lái)實(shí)現(xiàn)遺傳算法的并行化，但很難實(shí)現(xiàn)。文獻(xiàn)[12-13]指出，F(xiàn)PGA在硬件架構(gòu)和優(yōu)化時(shí)，靈活性較弱，算法中的許多部分不能很好地映射到硬件。而本文的實(shí)驗(yàn)平臺(tái)采用國(guó)產(chǎn)超算“神威·太湖之光”。該機(jī)是世界上首臺(tái)峰值運(yùn)算性能超過(guò)十億億次量級(jí)的超級(jí)計(jì)算機(jī)，目前在TOP500中排行第一，也是中國(guó)首臺(tái)全部采用國(guó)產(chǎn)處理器構(gòu)建的超級(jí)計(jì)算機(jī)。該機(jī)采用我國(guó)自主研制的“申威 26010”眾核處理器，通過(guò)主核和從核間的并行協(xié)作，可以達(dá)到極高的并行計(jì)算能力。該處理器與GPU相比具有較強(qiáng)的通信和同步能力，與FPGA相比具有較好的靈活性，突出的特點(diǎn)是從核處理能力較強(qiáng)。文獻(xiàn)[14]論證發(fā)現(xiàn)，“申威 26010”上逾98%的理論性能均源自于從核。所以編程時(shí)將串行的、復(fù)雜的、需要內(nèi)存容量大的工作放在擁有較多內(nèi)存的主核上完成，而獨(dú)立的、可以并行執(zhí)行的、計(jì)算密集型的工作放在從核完成，更能體現(xiàn)出該眾核架構(gòu)的優(yōu)勢(shì)。

由于遺傳算法的種群中每個(gè)個(gè)體之間的數(shù)據(jù)獨(dú)立性強(qiáng)，具有天然的并行性，非常適合于在大規(guī)模并行機(jī)上實(shí)現(xiàn)?；谠撈脚_(tái)，本文將典型的遺傳算法進(jìn)行了二級(jí)并行化設(shè)計(jì)，并結(jié)合兩種編程模型，MPI和Athread(SW26010專用加速線程庫(kù))將其實(shí)現(xiàn)。目前已有的并行遺傳算法一般是實(shí)現(xiàn)一級(jí)并行(MPI模式)，尚未看到有相關(guān)的研究基于申威“26010”眾核處理器實(shí)現(xiàn)遺傳算法的二級(jí)并行。本文的工作在這個(gè)領(lǐng)域是一種新的嘗試。

1 混合式的二級(jí)并行模型的設(shè)計(jì)與實(shí)現(xiàn)

1.1 并行遺傳算法模型介紹

目前遺傳算法的并行模型可分為四種：主從式模型、粗粒度模型、細(xì)粒度模型和混合模型[15]。

曾國(guó)蓀等[16]指出，主從式模型的優(yōu)點(diǎn)是簡(jiǎn)單，且速度和效率優(yōu)于串行遺傳算法，但缺陷是經(jīng)常會(huì)出現(xiàn)主從節(jié)點(diǎn)機(jī)負(fù)載不均衡、通信瓶頸和延遲問(wèn)題。在主從式模型中，選擇、交叉和變異操作由主節(jié)點(diǎn)機(jī)串行執(zhí)行，而適應(yīng)度評(píng)價(jià)由從節(jié)點(diǎn)機(jī)并行執(zhí)行，所以這種模型適合適應(yīng)度函數(shù)復(fù)雜的遺傳算法，對(duì)于適應(yīng)度函數(shù)較簡(jiǎn)單的情況，它將失去并行執(zhí)行的優(yōu)勢(shì)。

粗粒度模型中每經(jīng)過(guò)一定的進(jìn)化代，各個(gè)子群體間將交換若干個(gè)個(gè)體，一方面用來(lái)引入更優(yōu)良的個(gè)體，另一方面豐富種群的多樣性，防止未成熟早收斂現(xiàn)象。對(duì)于粗粒度模型，確定遷移規(guī)模相當(dāng)重要，遷移規(guī)模由遷移率、遷移周期兩個(gè)參數(shù)控制，通常遷移率越大則遷移周期越長(zhǎng)[17]。鄭志軍等[18]通過(guò)實(shí)驗(yàn)證明，大規(guī)模的遷移或遷移周期太短將導(dǎo)致通信開(kāi)銷增多；而遷移規(guī)模太小又容易形成局部最優(yōu)解，影響解的質(zhì)量；遷移周期太長(zhǎng)則會(huì)導(dǎo)致優(yōu)秀個(gè)體不能及時(shí)傳播，反而降低收斂速度。

細(xì)粒度模型具有維持種群多樣性從而抑制早熟現(xiàn)象及能實(shí)現(xiàn)高度并行化等優(yōu)勢(shì)[19]。但由于每個(gè)個(gè)體需要單獨(dú)占用一個(gè)節(jié)點(diǎn)，導(dǎo)致該模型通信開(kāi)銷大，并行機(jī)難以承受，并且研究人員難以找到適用于該模型的并行機(jī)。

混合模型[20-21]是將上述三種模型混合形成的層次模型，一般有三種：粗粒度-細(xì)粒度、粗粒度-粗粒度、粗粒度-主從式。結(jié)合粗粒度模型適合遷移操作的特點(diǎn)和主從式模型適合計(jì)算密集型任務(wù)的優(yōu)勢(shì)，本文采用粗粒度-主從式模型，上層用粗粒度模型，下層用主從式模型。

1.2 混合式的二級(jí)并行模型的設(shè)計(jì)

以往并行遺傳算法，實(shí)現(xiàn)的一般是一級(jí)并行(MPI模式)，存在通信延遲、負(fù)載不均衡、核的數(shù)量少、同步困難等問(wèn)題，加速比較低，不能充分發(fā)揮出并行算法的優(yōu)勢(shì)。考慮到“申威 26010”眾核處理器的物理結(jié)構(gòu)和“粗粒度-主從式”混合并行遺傳算法邏輯結(jié)構(gòu)相似，本文設(shè)計(jì)和實(shí)現(xiàn)了混合式的二級(jí)并行的遺傳算法，可以充分利用申威眾核架構(gòu)實(shí)現(xiàn)遺傳算法的高度并行。

如圖1[14]所示，一個(gè)處理器節(jié)點(diǎn)擁有4個(gè)核組(Core Group, CG)，每一個(gè)核組由一個(gè)主核(Management Processing Element, MPE)和64個(gè)按照8×8的Mesh拓?fù)浣Y(jié)構(gòu)構(gòu)成的從核(Computing Processing Element, CPE)組成，且核組間由片上內(nèi)部網(wǎng)絡(luò)互聯(lián)，并支持低延遲的寄存器級(jí)數(shù)據(jù)通信。圖2中p1、p2、p3、p4分別代表4個(gè)子種群，每一個(gè)子種群就是一個(gè)島，各島之間按粗粒度模型并行進(jìn)化，每一子種群又按分配的從核數(shù)量分成n組，除最后一組外，其他各組包含同等數(shù)量的個(gè)體，組數(shù)n不超過(guò)N(N為每個(gè)核組內(nèi)的從核數(shù)，當(dāng)前為64)。組內(nèi)的個(gè)體按主從式模型并行進(jìn)化，初始化、選擇、交叉、變異在主核中運(yùn)行，適應(yīng)度計(jì)算在從核中進(jìn)行。通過(guò)將遺傳算法中的各子種群映射到核組的主核上，將子種群內(nèi)的各組映射到該核組的從核上，核組間采用粗粒度模式并行，核組內(nèi)采用主從式模式并行，實(shí)現(xiàn)了種群間和種群內(nèi)的兩級(jí)并行，提高了算法的收斂速度和求解質(zhì)量。

圖1 “申威 26010”眾核處理器架構(gòu)

圖2 混合并行遺傳算法結(jié)構(gòu)

如圖3所示，為本文采用的主從加速并行的并行模型。主從加速并行方法是“太湖之光”計(jì)算機(jī)系統(tǒng)支持的兩級(jí)并行方法，從核根據(jù)實(shí)際應(yīng)用課題的核心計(jì)算內(nèi)容進(jìn)行眾核加速，而主核完成同步、通信、I/O和串行代碼的計(jì)算。本文的核心計(jì)算內(nèi)容為適應(yīng)度函數(shù)計(jì)算。為完成適應(yīng)度函數(shù)的眾核計(jì)算，首先初始線程庫(kù)和創(chuàng)建線程組，啟動(dòng)核組中的所有可用資源。然后將種群內(nèi)個(gè)體信息通過(guò)Athread加載到對(duì)應(yīng)從核上，此時(shí)主核處于等待狀態(tài)，從核進(jìn)行眾核加速計(jì)算，計(jì)算完成后通過(guò)Athread將個(gè)體信息寫回主核。最后主核在確認(rèn)線程組所有從核都完成任務(wù)后，停止從核流水線，關(guān)閉從核組，完成本次眾核加速計(jì)算任務(wù)。

圖3 主從加速并行示意圖

1.3 混合式的二級(jí)并行模型的實(shí)現(xiàn)

就并行編程來(lái)說(shuō)，本文結(jié)合了消息傳遞和共享內(nèi)存兩種編程模型，即MPI和Athread的混合編程。MPI一般用于主核間的通信。而節(jié)點(diǎn)內(nèi)部的工作可通過(guò)“申威 26010”加速線程庫(kù)(Athread庫(kù))完成，它是針對(duì)主從加速編程模型所設(shè)計(jì)的程序加速庫(kù)，其目的是為了用戶能夠方便、快捷地對(duì)核組內(nèi)的線程進(jìn)行控制和調(diào)度，從而更好地發(fā)揮核組內(nèi)多運(yùn)算核心的加速性能[22-23]。該混合編程模型分為兩層：上層為粗粒度模型中島間的并行，即每一個(gè)島對(duì)應(yīng)一個(gè)進(jìn)程；下層為島內(nèi)部的并行，采用主/從式模型，主核上的進(jìn)程啟動(dòng)多個(gè)從核上的線程并行執(zhí)行，每一個(gè)從核運(yùn)行一個(gè)線程，從而實(shí)現(xiàn)了進(jìn)程和線程的兩級(jí)并行。

進(jìn)程并行的實(shí)現(xiàn)：將遺傳算法的求解任務(wù)分解為若干個(gè)相對(duì)獨(dú)立的子任務(wù)，為每一個(gè)子任務(wù)分配一個(gè)主核，即一個(gè)進(jìn)程。子任務(wù)間的通信，使用MPI模型實(shí)現(xiàn)。進(jìn)程間可以同步執(zhí)行，也可以異步執(zhí)行。文獻(xiàn)[24]表明，異步執(zhí)行由于達(dá)到執(zhí)行條件時(shí)不需要獲取其他進(jìn)程狀態(tài)就可以執(zhí)行，減少了等待時(shí)間，所以比同步速度更快。

線程并行的實(shí)現(xiàn)：將上一步分解完成的子任務(wù)繼續(xù)分解為二級(jí)子任務(wù)，每一個(gè)二級(jí)子任務(wù)對(duì)應(yīng)核組的一個(gè)從核，即一個(gè)線程。因?yàn)楹私M內(nèi)的若干線程共享內(nèi)存，所以節(jié)點(diǎn)內(nèi)使用共享存儲(chǔ)的Athread實(shí)現(xiàn)并行編程。

本文采用混合并行編程模型的目的是充分利用申威眾核系統(tǒng)的硬件資源，保證負(fù)載均衡，降低通信代價(jià)，從而提高并行程序的性能。若采用單一的MPI并行編程，實(shí)際只利用了主核的性能，核組內(nèi)的從核沒(méi)有能夠發(fā)揮作用，浪費(fèi)了寶貴的計(jì)算資源。采用混合并行編程模型后，由于進(jìn)程內(nèi)包含若干線程，各線程通過(guò)利用從核資源，使進(jìn)程執(zhí)行時(shí)間縮短，進(jìn)程間通信延遲也相應(yīng)降低，高效實(shí)現(xiàn)了進(jìn)程和線程的兩級(jí)并行，算法的性能得到較大的提升。

2 混合并行遺傳算法描述及實(shí)現(xiàn)

2.1 混合并行遺傳算法描述及流程

混合并行遺傳算法流程如圖4所示。

圖4 混合并行遺傳算法流程

主要步驟如下。

1)初始化操作。程序通過(guò)調(diào)用MPI_Comm_size()函數(shù)獲得總進(jìn)程數(shù)，并設(shè)定第0號(hào)進(jìn)程為主進(jìn)程，其他進(jìn)程為從進(jìn)程。主進(jìn)程調(diào)用MPI_Bcast()將染色體上下限參數(shù)以廣播的方式發(fā)送給其他進(jìn)程。從進(jìn)程收到參數(shù)后，獨(dú)立并行地在相應(yīng)主核內(nèi)初始化種群。

2)適應(yīng)度計(jì)算操作。從進(jìn)程在主核內(nèi)串行執(zhí)行交叉、變異等操作，而后通過(guò)對(duì)應(yīng)線程完成適應(yīng)度計(jì)算。首先從核調(diào)用Athread_get()函數(shù)，從主核內(nèi)獲取種群內(nèi)個(gè)體信息，然后在從核內(nèi)并行執(zhí)行個(gè)體適應(yīng)度計(jì)算，最后從核調(diào)用Athread_put()函數(shù)，將計(jì)算好的個(gè)體信息返回主核。

3)遷移操作。當(dāng)遺傳算法中每代的個(gè)體適應(yīng)度值計(jì)算完成后，通過(guò)輪盤賭策略選出將要遷移的若干個(gè)體(本文為3個(gè))，進(jìn)程通過(guò)調(diào)用MPI_Isend()函數(shù)，將選中的若干個(gè)體遷移到其他進(jìn)程，而后通過(guò)MPI_Recv()函數(shù)接收來(lái)自其他進(jìn)程的遷移個(gè)體，并隨機(jī)替換本種群中適應(yīng)值小的若干個(gè)體。

4)歸約操作。若當(dāng)前進(jìn)化代數(shù)達(dá)到最大進(jìn)化數(shù)，則跳出循環(huán)，停止執(zhí)行以上操作，進(jìn)入最后的歸約操作。進(jìn)程調(diào)用MPI_Reduce()函數(shù)，在各子種群中選出最優(yōu)個(gè)體作為最后結(jié)果。

混合并行遺傳算法模型可以從兩個(gè)方面實(shí)現(xiàn)，一是并行編程模型實(shí)現(xiàn)，二是混合并行遺傳算法實(shí)現(xiàn)。

2.2 混合并行遺傳算法實(shí)現(xiàn)

本文采用“粗粒度-主從式”混合并行遺傳算法模型。模型包括上下兩層，上層由粗粒度并行遺傳算法模型構(gòu)成，該層將整個(gè)種群劃分為若干子種群，每一個(gè)子種群稱作一個(gè)島，對(duì)應(yīng)一個(gè)核組的主核。島與島之間獨(dú)立并行的執(zhí)行遺傳操作，當(dāng)經(jīng)過(guò)固定的進(jìn)化代數(shù)，種群之間通過(guò)某種遷移策略進(jìn)行島之間的個(gè)體遷移，以交換種群信息，使種群內(nèi)優(yōu)良個(gè)體得以保留，種群多樣性得以保持。下層由主從式并行遺傳算法模型構(gòu)成，島內(nèi)的遺傳操作包括遷移、變異、交叉、適應(yīng)度計(jì)算等，除了適應(yīng)度計(jì)算，其他操作都由在主核上運(yùn)行的進(jìn)程串行執(zhí)行，而進(jìn)程內(nèi)啟動(dòng)的若干線程按主從式模型在從核上進(jìn)行適應(yīng)度計(jì)算。

3 算法測(cè)試與結(jié)果分析

本文的測(cè)試函數(shù)為標(biāo)準(zhǔn)測(cè)試函數(shù)[25-26]:

通過(guò)求函數(shù)的最小值測(cè)試遺傳算法的性能。由于測(cè)試函數(shù)計(jì)算量小，執(zhí)行時(shí)間短，不能充分體現(xiàn)出超算中從核的高性能。文獻(xiàn)[27]指出，可以在適應(yīng)度函數(shù)的計(jì)算語(yǔ)句中加入一個(gè)掛起語(yǔ)句，可以根據(jù)問(wèn)題的規(guī)模，設(shè)置將系統(tǒng)掛起的時(shí)間，模擬等時(shí)間的計(jì)算量，以分析遺傳算法針對(duì)不同規(guī)模問(wèn)題的求解性能。本文也采用在適應(yīng)度函數(shù)內(nèi)加入掛起語(yǔ)句來(lái)增加計(jì)算量以模擬大規(guī)模問(wèn)題的求解。

本實(shí)驗(yàn)的運(yùn)算平臺(tái)為無(wú)錫超算中心的神威“太湖之光”超級(jí)計(jì)算機(jī)，其硬件配置如表1[28]所示。遺傳算法具體參數(shù)如下：雜交概率為0.8，變異概率為0.15，遷移個(gè)體為3。

為驗(yàn)證所設(shè)計(jì)HBPGA算法的性能，同時(shí)也為了測(cè)試申威眾核處理器中從核的性能，實(shí)驗(yàn)采用4個(gè)評(píng)價(jià)指標(biāo)：執(zhí)行時(shí)間、從核加速比、加速比和求解精度。Rastrigin函數(shù)的測(cè)試結(jié)果反映在圖5、圖6和表3中，Hansen函數(shù)和Rosenbrock函數(shù)的測(cè)試結(jié)果反映在圖7和圖8中。

表1 神威“太湖之光”主要參數(shù)

圖5的種群大小為198，使用主核數(shù)為6，每個(gè)主核配11個(gè)從核，橫坐標(biāo)是進(jìn)化代數(shù)，縱坐標(biāo)是執(zhí)行時(shí)間。圖中MPI代表僅使用MPI通信，hybrid表示同時(shí)使用了MPI和Athread，即本文的HBPGA算法。由圖5所示，HBPGA的執(zhí)行時(shí)間和執(zhí)行時(shí)間的增長(zhǎng)速度遠(yuǎn)小于純MPI，執(zhí)行速率最多提高了12.7倍。

圖5 兩類算法基于Rastrigin函數(shù)的執(zhí)行時(shí)間

一般并行算法性能的提升使用加速比指標(biāo)，但本文的算法使用了大量從核處理器，需要有新的衡量指標(biāo)即從核加速比來(lái)衡量從核的性能。從核加速比定義如下：固定的并行問(wèn)題w，獲取僅使用主核運(yùn)行的情況下的并行運(yùn)行時(shí)間Tg以及獲取主核和從核共同進(jìn)行處理情況下的運(yùn)行時(shí)間為Tc，得到從核加速比S=Tg/Tc。獲取串行執(zhí)行時(shí)間Ts，得到加速比H=Ts/Tc。

表2的種群大小107 520，最大執(zhí)行代數(shù)20，每個(gè)主核配64個(gè)從核。已測(cè)得串行執(zhí)行時(shí)間為13 683.185 6 s。通過(guò)變化主核數(shù)得到表3。由表3可知，HBPGA隨著主核的增加，從核加速比不斷增加，當(dāng)主核數(shù)為16時(shí)(從核數(shù)為16×64)，加速比達(dá)到544.38，從核加速比為31.85。

表2 從核加速比與主核數(shù)的關(guān)系(固定從核數(shù))

為考察主核固定情況下從核增加對(duì)性能的影響，將主核數(shù)固定為10，逐步增加從核數(shù)，得到圖6。圖6中種群大小6 000，最大執(zhí)行代數(shù)20。圖中顯示，隨著從核數(shù)的增加，HBPGA的從核加速比隨之增加。當(dāng)從核數(shù)達(dá)到60時(shí)，從核加速比達(dá)到最大值24.74。

為衡量本文提出的HBPGA算法對(duì)解的質(zhì)量的影響，采用Rastrigin函數(shù)進(jìn)行了測(cè)試。測(cè)試中，種群大小設(shè)為198，執(zhí)行30次實(shí)驗(yàn)，都能收斂，平均收斂代數(shù)為11.9，優(yōu)于串行算法的收斂代數(shù)(同等參數(shù)約為15)。實(shí)驗(yàn)還使用Hansen函數(shù)和Rosenbrock函數(shù)在同等進(jìn)化代數(shù)下對(duì)算法的執(zhí)行時(shí)間進(jìn)行了測(cè)試(圖7和圖8)，結(jié)果表明，與一級(jí)并行的MPI模型的算法相比，HBPGA算法在申威眾核處理器下明顯具有更短的執(zhí)行時(shí)間。

圖6 從核加速比與從核的關(guān)系(固定主核數(shù))

圖7 兩類算法基于Hansen函數(shù)的執(zhí)行時(shí)間

圖8 兩類算法基于Rosenbrock函數(shù)的執(zhí)行時(shí)間

4 結(jié)語(yǔ)

本文通過(guò)分析申威眾核的物理拓?fù)浜筒⑿羞z傳算法邏輯結(jié)構(gòu)，并結(jié)合兩者的特點(diǎn)，設(shè)計(jì)出基于申威眾核的“粗粒度-主從式”混合并行遺傳算法，并進(jìn)行了性能的比較和分析。該算法模型在眾核架構(gòu)上具有一定的通用性，可以通過(guò)替換不同的適應(yīng)度函數(shù)解決不同的問(wèn)題，應(yīng)用于不同場(chǎng)景。利用MPI和Athread兩種并行編程工具，使所設(shè)計(jì)的算法在申威眾核處理器上實(shí)現(xiàn)進(jìn)程級(jí)和線程級(jí)的兩級(jí)并行。最后，對(duì)混合并行遺傳算法進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)表明，不論與傳統(tǒng)串行遺傳算法還是單純采用MPI的并行遺傳算法比較，本文提出的基于申威眾核處理器的混合并行遺傳算法在求解速度和收斂代數(shù)方面都有明顯提高。

本文針對(duì)申威眾核處理器和并行遺傳算法進(jìn)行了研究，還有很多后續(xù)的工作有待開(kāi)展，如，對(duì)申威眾核架構(gòu)更深層次的研究和分析，對(duì)本文提出的混合并行遺傳算法進(jìn)一步性能優(yōu)化，以及將算法應(yīng)用于車輛導(dǎo)航、物流配送等組合優(yōu)化問(wèn)題等。

References)

[1] ESMAEILZADEH H, BLEM E, AMANT R S, et al. Dark silicon and the end of multicore scaling [C]// Proceeding of the 38th Annual International Symposium on Computer Architecture. New York: ACM, 2011: 365-376.

[2] 鄭方,張昆,鄔貴明,等.面向高性能計(jì)算的眾核處理器結(jié)構(gòu)級(jí)高能效技術(shù)[J].計(jì)算機(jī)學(xué)報(bào),2014,37(10):2176-2186.(ZHENG F, ZHANG K, WU G M, et al. Architecture techniques of many-core processor for energy-efficient in high performance computing [J]. Chinese Journal of Computers, 2014, 37(10): 2176-2186.)

[3] ZHENG L, LU Y, GUO M, et al. Architecture-based design and optimization of genetic algorithms on multi- and many-core systems [J]. Future Generation Computer Systems, 2014, 38(3): 75-91.

[4] UMBARKAR A J, JOSHI M S, HONG W C. Multithreaded Parallel Dual Population Genetic Algorithm (MPDPGA) for unconstrained function optimizations on multi-core system [J]. Applied Mathematics and Computation, 2014, 243: 936-949.

[5] 丁孟為.遺傳算法在多核系統(tǒng)上的性能分析和優(yōu)化[D].上海：上海交通大學(xué),2012.(DING M W. Performance analysis and optimization of genetic algorithms on multi-core systems [D]. Shanghai: Shanghai Jiao Tong University, 2012.)

[6] NVIDIA Corporation. NVIDIA’s next generation CUDA compute architecture: FERMI [EB/OL]. [2016- 09- 15]. http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf.

[7] LIU X, SMELYANSKIY M, CHOW E, et al. Efficient sparse matrix-vector multiplication on x86-based many-core processors [C]// Proceedings of the 27th International ACM Conference on International Conference on Supercomputing. New York: ACM, 2013: 273-282.

[8] SAINI S, JIN H, JESPERSEN D, et al. An early performance evaluation of many integrated core architecture based SGI rackable computing system [C]// Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2013: Article No. 94.

[9] 巨濤,朱正東,董小社.異構(gòu)眾核系統(tǒng)及其編程模型與性能優(yōu)化技術(shù)研究綜述[J].電子學(xué)報(bào),2015,43(1):111-119.(JU T , ZHU Z D, DONG X S. The feature, programming model and performance optimization strategy of heterogeneous many-core system: a review [J]. Acta Electronica Sinica, 2015, 43(1): 111-119.)

[10] POSPICHAL P, JAROS J, SCHWARZ J. Parallel genetic algorithm on the CUDA architecture [C]// Proceedings of the 2010 European Conference on the Applications of Evolutionary Computation, LNCS 6024. Berlin: Springer, 2010: 442-451.

[11] XUE Y, QIAN Z, WEI G, et al. An efficient Network-on-Chip (NoC) based multicore platform for hierarchical parallel genetic algorithms [C]// Proceedings of the 8th IEEE/ACM International Symposium on Networks-On-Chip. Piscataway, NJ: IEEE, 2014:17-24.

[12] GUO L, THOMAS D B, GUO C, et al. Automated framework for FPGA-based parallel genetic algorithms [C]// Proceedings of the 2014 24th International Conference on Field Programmable Logic and Applications. Piscataway, NJ: IEEE, 2014: 1-7.

[13] GUO L, GUO C, THOMAS D B, et al. Pipelined genetic propagation [C]// Proceedings of the 2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines. Washington, DC: IEEE Computer Society, 2015: 103-110.

[14] 王一超,林新華,蔡林金,等.太湖之光上基于神威OpenACC 的GTC-P 移植與優(yōu)化研究[EB/OL]. [2017- 05- 01]. http://max.book118.com/html/2017/0623/117447540.shtm.(WANG Y C, LIN X H, CAI L J, et al. Porting and optimizing GTC-P on TaihuLight supercomputer with Sunway OpenACC [EB/OL]. [2017- 05- 01]. http://max.book118.com/html/2017/0623/117447540.shtm.)

[15] 郭彤城,慕春棣.并行遺傳算法的新進(jìn)展[J].系統(tǒng)工程理論與實(shí)踐,2002,22(2):15-23.(GUO T C, MU C D. The parallel drifts of genetic algorithms [J]. Systems Engineering—Theory & Practice, 2002, 22(2): 15-23.)

[16] 曾國(guó)蓀,丁春玲.并行遺傳算法分析[J].計(jì)算機(jī)工程,2001,27(9):53-55.(ZENG G S, DING C L. An analysis on parallel genetic algorithm [J]. Computer Engineering, 2001, 27(9): 53-55.)

[17] 李想,魏加華,傅旭東.粗粒度并行遺傳算法在水庫(kù)調(diào)度問(wèn)題中的應(yīng)用[J].水力發(fā)電學(xué)報(bào),2012,31(4):28-33.(LI X, WEI J H, FU X D. Application of coarse-grained genetic algorithm to reservoir operation [J]. Journal of Hydroelectric Engineering, 2012, 31(4): 28-33.)

[18] 鄭志軍,鄭守淇.粗粒度并行遺傳算法性能分析[J].小型微型計(jì)算機(jī)系統(tǒng),2006,27(6):1002-1006.(ZHENG Z J, ZHENG S Q. Performance analysis of coarse-grained parallel genetic algorithms [J]. Journal of Chinese Computer Systems, 2006, 27(6): 1002-1006.)

[19] BACH F R, JORDAN M I. Learning spectral clustering [J]. Advances in Neural Information Processing Systems, 2004, 16(2): 2006.

[20] XUE S, GUO S, BAI D. The analysis and research of parallel genetic algorithm [C]// Proceedings of the 2008 4th International Conference on Wireless Communications, Networking and Mobile Computing. Piscataway, NJ: IEEE, 2008: 1-4.

[21] CHENG C H, FU A W, ZHANG Y. Entropy-based subspace clustering for mining numerical data [C]// Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 1999: 84-93.

[22] 國(guó)家超級(jí)計(jì)算無(wú)錫中心.“神威·太湖之光”系統(tǒng)快速使用指南[EB/OL]. [2016- 09- 15]. http://www.nsccwx.cn/ceshi.php?id=13.(National Supercomputing Center in Wuxi. Guide of “Sunway TaihuLight” [EB/OL]. [2016- 09- 15]. http://www.nsccwx.cn/ceshi.php?id=13.)

[23] 國(guó)家超級(jí)計(jì)算無(wú)錫中心.“神威·太湖之光”編譯系統(tǒng)用戶手冊(cè) [EB/OL]. [2016- 09- 15].http://www.nsccwx.cn/ceshi.php?id=12.(National Supercomputing Center in Wuxi. User’s manual of “Sunway Taihu-Light” computer compilation system [EB/OL]. [2016- 09- 15]. http://www.nsccwx.cn/ceshi.php?id=12.)

[24] ZHENG L, LU Y, GUO M, et al. Architecture-based design and optimization of genetic algorithms on multi-and many-core systems [J]. Future Generation Computer Systems, 2014, 38(3): 75-91.

[25] 胡玉蘭,潘福成,梁英,等.基于種群規(guī)?？勺兊拇至６炔⑿羞z傳算法[J].小型微型計(jì)算機(jī)系統(tǒng),2003,24(3):534-536.(HU Y L, PAN F C, LIANG Y, et al. Parallel genetic algorithm based on population size mutable coarse-grained [J]. Journal of Chinese Computer Systems, 2003, 24(3): 534-536.)

[26] TSOULOS I G, TZALLAS A, TSALIKAKIS D. PDoublePop: an implementation of parallel genetic algorithm for function optimization [J]. Computer Physics Communications, 2016, 209: 183-189.

[27] 凌實(shí),劉曉平.基于MPI的主從式并行遺傳算法研究與實(shí)現(xiàn)[EB/OL].[2016- 12- 11]. http://xueshu.baidu.com/s?wd=paperuri%3A%2890fc2666352b25fdeaecbd242355ca7c%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fwww.doc88.com%2Fp-0406863398613.html&ie=utf-8&sc_us=5462928728543012625.(LIN S, LIU X P. The study and implementation of master-slave parallel genetic algorithm based on MPI [EB/OL]. [2016- 12- 11]. http://xueshu.baidu.com/s?wd=paperuri%3A%2890fc2666352b25fdeaecbd242355ca7c%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fwww.doc88.com%2Fp-0406863398613.html&ie=utf-8&sc_us=5462928728543012625.)

[28] FU H H, LIAO J F, YANG J Z, et al. The Sunway TaihuLight supercomputer: system and applications [J]. Science China Information Sciences, 2016, 59(7): 072001.

HybridparallelgeneticalgorithmbasedonSunwaymany-coreprocessors

ZHAO Ruixiang1,2, ZHENG Kai1,2*, LIU Yao1,2, WANG Su1,2, LIU Yan1,2, SHENG Huanxue1,2, ZHOU Qianhao3

(1.CollegeofComputerScienceandSoftwareEngineering,EastChinaNormalUniversity,Shanghai200062,China;2.StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,WuxiJiangsu214215,China;3.FacultyofEconomicsandManagement,EastChinaNormalUniversity,Shanghai200062,China)

When the traditional genetic algorithm is used to solve the computation-intensive task, the execution time of the fitness function increases rapidly, and the convergence rate of the algorithm is very low when the population size or generation increases. A “coarse-grained combined with master-slave” HyBrid Parallel Genetic Algorithm (HBPGA) was designed and implemented on Sunway “TaihuLight” supercomputer which is ranked first in the latest TOP500 list. Two-level parallel architecture was used and two different programming models, MPI and Athread were combined. Compared with the traditional genetic algorithm implemented on single-core or multi-core cluster with single-level parallel architecture, the algorithm using two-level parallel architecture was implemented on the Sunway many-core processors, better performance and higher speedup ratio were achieved. In the experiment, when using 16×64 CPEs (Computing Processing Elements), the maximum speedup can reach 544, and the CPE speedup ratio is more than 31.

hybrid parallel genetic algorithm; Sunway “TaihuLight”; many-core; MPI; Athread

2017- 04- 10;

2017- 07- 11。

數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目(2016A05)。

趙瑞祥(1990—),男,吉林扶余人,碩士研究生,主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)、云計(jì)算; 鄭凱(1968—),男,浙江寧波人,副教授,博士,主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)、云計(jì)算; 劉垚(1981—),男,安徽靈璧人,高級(jí)工程師,碩士,主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)、高性能計(jì)算; 王肅(1980—),女,河南許昌人,講師,博士,主要研究方向：智能優(yōu)化、信息系統(tǒng); 劉艷(1976—),女,吉林通化人,助理研究員,博士,主要研究方向：智能優(yōu)化、信息系統(tǒng); 沈煥學(xué)(1992—),男,安徽安慶人,碩士研究生,主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò); 周謙豪(1997—),男,上海人,主要研究方向：高性能計(jì)算。

1001- 9081(2017)09- 2518- 06

10.11772/j.issn.1001- 9081.2017.09.2518

TP311.52; TP338.6

A

This work is partially supported by the Open Fund Project of the State Key Laboratory of Mathematical Engineering and Advanced Computing (2016A05).

ZHAORuixiang, born in 1990, M. S. candidate. His research interests include computer network, cloud computing.

ZHENGKai, born in 1968, Ph. D., associate professor. His research interests include computer network, cloud computing.

LIUYao, born in 1981, M. S., senior engineer. His research interests include computer network, high performance computing.

WANGShu, born in 1980, Ph. D., lecturer. Her research interests include intelligent optimization, information system.

LIUYan, borin in 1976, Ph. D., assistant research fellow. Her research interests include intelligent optimization, information system.

SHENHuanxue, born in 1992, M. S. candidate. His research interests include computer network.

ZHOUQianhao, born in 1997. His research interests include high performance computing.