焦育威，王 鵬,2，辛 罡

(1.西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,四川 成都 610225；2.廣東省國(guó)產(chǎn)服務(wù)器工程中心,廣東 廣州 510000；3.中國(guó)科學(xué)院大學(xué)，北京 100049；4.中國(guó)科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，四川 成都 610041)

1 引言

近些年大量的啟發(fā)式算法被提出[1]，這些算法在參數(shù)優(yōu)化、控制與決策等問題上都表現(xiàn)出色。多尺度量子諧振子優(yōu)化算法MQHOA(Multi-scale Quantum Harmonic Oscillator Algorithm)是一種量子啟發(fā)式算法，它以Schr?dinger方程為基礎(chǔ)，建立了優(yōu)化問題與量子系統(tǒng)之間的關(guān)系，將優(yōu)化問題轉(zhuǎn)換為求解粒子在約束下的基態(tài)波函數(shù)，且該算法在云計(jì)算、任務(wù)調(diào)度和空間聚類等方向都得到了廣泛的應(yīng)用[2]。

為了提高M(jìn)QHOA的算法性能，近年來學(xué)者對(duì)MQHOA遷移策略和參數(shù)設(shè)置進(jìn)行了研究，文獻(xiàn)[3]分析了能級(jí)穩(wěn)定過程中判據(jù)的變化對(duì)算法性能的影響，表明嚴(yán)格的判據(jù)可提高算法的全局搜索能力，在此基礎(chǔ)上提出了性能更好的版本(MQHOA-AS)。文獻(xiàn)[4,5]通過研究算法的遷移策略對(duì)MQHOA進(jìn)行了改進(jìn)。另一方面有學(xué)者對(duì)MQHOA背后的物理背景進(jìn)行了研究，MQHOA是以波動(dòng)方程在諧振子勢(shì)阱下的波函數(shù)為采樣函數(shù)指導(dǎo)算法迭代過程中的采樣行為，不同的勢(shì)阱下，算法采樣行為具有差異性，針對(duì)的優(yōu)化對(duì)象也不盡相同?；诹孔酉到y(tǒng)中不同的勢(shì)阱，MQHOA開始衍生出不同的版本，如：基于自由粒子的多尺度量子自由粒子優(yōu)化算法MFPOA(Multi-scale Free Particle Optimization Algorithm)，并且相較同類型的優(yōu)化算法，MFPOA在求解近100個(gè)城市節(jié)點(diǎn)數(shù)的TSP問題時(shí)，在求解時(shí)間上具有競(jìng)爭(zhēng)力[6]。

而上述針對(duì)MQHOA的改進(jìn)中，存在一個(gè)共性，處于同一代的種群中，每一個(gè)采樣個(gè)體的約束尺度相同，但不同個(gè)體間的采樣情況具有差異性。尺度的大小決定了當(dāng)前的搜索狀態(tài)，也影響了下一次采樣解的多樣性，對(duì)算法采樣精度和成功率具有較大的影響，采樣情況不同的個(gè)體使用相同的采樣尺度，這一點(diǎn)本身不具有合理性。由此，本文根據(jù)不同的個(gè)體采樣情況差異化其采樣尺度，每一個(gè)體所使用的采樣尺度可以根據(jù)自身采樣情況動(dòng)態(tài)調(diào)節(jié)，不同個(gè)體間的采樣尺度彼此獨(dú)立。

當(dāng)算法所面對(duì)的目標(biāo)函數(shù)結(jié)構(gòu)復(fù)雜或維度較高時(shí)，解空間不可避免地呈指數(shù)級(jí)增加，算法求解所需時(shí)間也隨之增加，算法執(zhí)行效率不可避免地會(huì)降低。此時(shí)傳統(tǒng)的串行計(jì)算模式已經(jīng)不能滿足需求，需要對(duì)算法流程進(jìn)行并行化處理。對(duì)算法并行化，進(jìn)程間的通信對(duì)算法的性能影響較大，MPI并行程序在運(yùn)行過程中，通信等待時(shí)間占整個(gè)算法運(yùn)行時(shí)間的比重較大[7 - 9]，為實(shí)現(xiàn)對(duì)通信開銷的合理折衷，本文提出具有星型拓?fù)渫ㄐ沤Y(jié)構(gòu)的多尺度量子諧振子優(yōu)化算法MQHOA-PS(Multi-scale Quantum Harmonic Oscillator Algorithm Parallelization by Scale)，該算法實(shí)現(xiàn)了采樣尺度間的并行化。

在華為鯤鵬920處理器上實(shí)現(xiàn)了改進(jìn)后的算法的并行化，并將其與原算法進(jìn)行了對(duì)比分析。選擇華為鯤鵬920的原因在于它是一款國(guó)產(chǎn)的高性能處理器。QHOA提出以來，相關(guān)的研究都是基于Intel或AMD系列處理器的，將MQHOA-PS和MQHOA移植在華為鯤鵬920處理器上實(shí)驗(yàn)，一方面是為了測(cè)試改進(jìn)后算法的性能；另一方面更是為了探究華為鯤鵬920處理器的高性能計(jì)算能力，為以后的國(guó)產(chǎn)處理器研發(fā)和軟件適配提供數(shù)據(jù)參考。

2 標(biāo)準(zhǔn)MQHOA

2.1 MQHOA物理模型

MQHOA受量子力學(xué)中波函數(shù)的物理意義啟發(fā)，通過模擬諧振子運(yùn)動(dòng)，構(gòu)建出算法模型。波函數(shù)可以用于描述量子系統(tǒng)中粒子位置分布概率，具體描述量子系統(tǒng)的方程被稱為Schr?dinger方程，不隨時(shí)間變化的Schr?dinger方程表示如式(1)所示：

(1)

(2)

其中，x0為全局最優(yōu)解。這樣求解目標(biāo)函數(shù)最小值的問題就可以轉(zhuǎn)換為求解諧振子勢(shì)阱下的基態(tài)波函數(shù)問題，此時(shí)的優(yōu)化問題的Schr?dinger方程，如式(3)所示：

(3)

此時(shí)波函數(shù)在基態(tài)的概率密度函數(shù)如式(4)所示：

(4)

從算法的物理模型上看，MQHOA共有3個(gè)迭代過程，分別是能級(jí)穩(wěn)定、能級(jí)下降和采樣尺度下降。在能級(jí)穩(wěn)定的過程中，對(duì)k個(gè)采樣點(diǎn)區(qū)域進(jìn)行固定次數(shù)的采樣，用采樣過程中較優(yōu)的解替換當(dāng)前的解，在高能級(jí)狀態(tài)下搜索解空間，從而定位全局最優(yōu)區(qū)域。當(dāng)能級(jí)達(dá)到暫穩(wěn)態(tài)后，將最差解的位置用k個(gè)采樣位置的均值替換，以此實(shí)現(xiàn)能級(jí)下降。當(dāng)k個(gè)采樣點(diǎn)的標(biāo)準(zhǔn)差小于當(dāng)前采樣尺度時(shí)，算法即達(dá)到基態(tài)，此時(shí)采樣尺度減半，即為采樣尺度下降。算法在更小的采樣尺度下重復(fù)高能級(jí)到低能級(jí)的迭代過程，直到滿足迭代終止條件。MQHOA偽代碼如算法1所示：

算法1MQHOA

輸入：k(種群個(gè)體數(shù))，σmin(最小尺度)，S=[LB,LU](定義域)，σs(采樣尺度)，max_fe(最大迭代次數(shù))。

輸出：最優(yōu)解。

初始化(定義域內(nèi))xi(i=1,2,…,k) 。

步驟2判斷f(x′i)

步驟3計(jì)算標(biāo)準(zhǔn)差σk；

步驟4計(jì)算標(biāo)準(zhǔn)差變化量Δσk=|σk-σ′k|；

步驟5σ′k:σ′k←σk標(biāo)準(zhǔn)差更新；

步驟6判斷Δσk<σs是否滿足，如滿足則轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟1；

步驟7差解替換xworst=xmean；

步驟8判斷σk<σs是否滿足，如滿足則轉(zhuǎn)步驟9，否則轉(zhuǎn)步驟1；

步驟9尺度減半σs=σs/2；

步驟10判斷σs>σmin是否滿足或是否超過最大迭代次數(shù)，二者皆不滿足則轉(zhuǎn)步驟1，否則輸出最優(yōu)解，算法結(jié)束。

上述算法中的步驟9為采樣尺度下降過程，這一過程決定了搜索精度，隨著采樣尺度下降的過程算法也從全局搜索逐步過渡到了局部搜索。從MQHOA算法中可以看出，同一代的所有采樣個(gè)體的采樣尺度相同，這也是傳統(tǒng)MQHOA所存在的缺陷。

2.2 MQHOA缺陷分析

由算法1中的算法流程可知，MQHOA在迭代過程中，采樣點(diǎn)收斂到一定程度后，采樣尺度將進(jìn)行減半操作，在整個(gè)迭代過程中，采樣尺度的變化是單向的，是由大到小的變化，不存在采樣尺度擴(kuò)大行為。隨迭代次數(shù)的增加，采樣尺度遞減到一定程度，算法進(jìn)入局部搜索，此時(shí)不利于陷入局部最優(yōu)解的采樣點(diǎn)跳出當(dāng)前區(qū)域。

假設(shè)目標(biāo)函數(shù)f(x)為雙阱函數(shù)，其表達(dá)形式如式(5)所示：

(5)

其中，V0、a和δ為控制雙阱函數(shù)結(jié)構(gòu)的參數(shù)，V0用于調(diào)節(jié)勢(shì)壘的高度，a和δ分別控制極小值間的水平距離和高度差，在x=±a附近雙阱函數(shù)取得極值。當(dāng)V0=4.0，a=2.0，δ=0.3時(shí)，雙阱函數(shù)f(x)的二維圖像如圖1所示，此時(shí)目標(biāo)函數(shù)在x1=2.0附近存在一個(gè)局部最優(yōu)解。通過文獻(xiàn)[4]中的采樣函數(shù)可計(jì)算圖1中采樣點(diǎn)x1=2.0時(shí)跳出局部最優(yōu)的概率p為：

(6)

其中,σs為采樣尺度。圖1展示了采樣尺度從0.05擴(kuò)張到0.1的過程，采樣的采樣尺度擴(kuò)張后，由式(6)計(jì)算可知，該點(diǎn)在下一次迭代過程中跳出局部最優(yōu)解的概率也隨之增加，即p(x1,σs=0.1)>p(x1,σs=0.05)。

Figure 1 Schematic diagram of sampling scale expansion of two-dimensional double-well function圖1 二維雙阱函數(shù)采樣尺度擴(kuò)張示意圖

因此，整個(gè)種群采用同一采樣尺度搜索是不合理的，不利于“陷入”局部最優(yōu)的采樣點(diǎn)跳出當(dāng)前區(qū)域。

2.3 改進(jìn)方案

基于不同的采樣點(diǎn)在迭代過程中的采樣情況不同，可以根據(jù)采樣點(diǎn)自身差異性進(jìn)行采樣尺度自適應(yīng)調(diào)節(jié)，該調(diào)節(jié)策略為雙向調(diào)節(jié)。與原采樣尺度縮減不同，采樣點(diǎn)可根據(jù)采樣情況擴(kuò)大自身采樣尺度，當(dāng)采樣情況差時(shí)，自身采樣尺度以某一系數(shù)進(jìn)行擴(kuò)張?zhí)幚?，因此在迭代過程中，除采樣尺度初始值相同外，經(jīng)過迭代，所有采樣點(diǎn)的采樣尺度都不盡相同，且相互保持獨(dú)立。采樣尺度調(diào)節(jié)流程如圖2所示，圖2中l(wèi)為采樣尺度擴(kuò)張系數(shù)。此時(shí)每一個(gè)采樣點(diǎn)xi都具有獨(dú)立的采樣尺度σ(xi)，采樣情況不好的個(gè)體，經(jīng)過迭代其自身采樣尺度將增大，這樣更加有利于跳出局部最優(yōu)解。

該方案對(duì)采樣尺度的合理性擴(kuò)張可以提高算法跳出局部最優(yōu)的概率，提高尋優(yōu)成功率，但增加采樣尺度擴(kuò)張步驟無疑會(huì)提高算法時(shí)間復(fù)雜度，為了保證算法在尋優(yōu)成功率和時(shí)間上都具有競(jìng)爭(zhēng)力，該方案的并行化十分重要。與此同時(shí)，該方案具備良好的并行特性，采樣點(diǎn)間采樣尺度的擴(kuò)張過程無需與其他節(jié)點(diǎn)交換信息，迭代過程中具有獨(dú)立性，因此可將每一個(gè)采樣點(diǎn)的擴(kuò)張過程并行化，即如圖2所示的迭代過程可分配到不同的節(jié)點(diǎn)上運(yùn)算，而采樣尺度的縮減過程需要對(duì)全局采樣點(diǎn)的采樣尺度進(jìn)行評(píng)估，對(duì)此過程設(shè)置一個(gè)獨(dú)立的節(jié)點(diǎn)進(jìn)行相應(yīng)計(jì)算。

Figure 2 Flow chart of sampling scale expansion 圖2 采樣度擴(kuò)張流程圖

3 MQHOA并行化

在串行模式下，MQHOA的能級(jí)穩(wěn)定過程中k個(gè)采樣點(diǎn)需要進(jìn)行k次采樣運(yùn)算，當(dāng)某一采樣點(diǎn)在進(jìn)程上運(yùn)算時(shí)，剩下的k-1個(gè)采樣點(diǎn)需要排隊(duì)等待，這一過程浪費(fèi)了大量的時(shí)間，如果將采樣過程分配給不同的進(jìn)程可以有效降低算法運(yùn)行時(shí)間。文獻(xiàn)[10] 雖提出了分別具有3種不同并行粒度的MQHOA-P算法，但同一代的采樣點(diǎn)依舊使用相同的采樣尺度，采樣尺度的大小只取決于采樣尺度減半過程，沒有尺度自適應(yīng)過程，面對(duì)復(fù)雜函數(shù)或高維函數(shù)，解的多樣性只能以增加采樣點(diǎn)數(shù)量的方式得到保障，且實(shí)驗(yàn)求解最優(yōu)區(qū)域的精度和成功率在文中并未說明，全文意在表達(dá)MQHOA并行化的可行性，并沒有提出具有高精度和高成功率的MQHOA并行化框架。本節(jié)具體闡述基于采樣尺度自適應(yīng)的MQHOA并行化框架，這一框架在保持較高尋優(yōu)精度的同時(shí)具有高成功率，它的核心在于采樣尺度的自適應(yīng)處理策略對(duì)解多樣性的提高。

采樣尺度的自適應(yīng)過程在從節(jié)點(diǎn)上進(jìn)行，這一過程同時(shí)受到主節(jié)點(diǎn)的調(diào)控，主從節(jié)點(diǎn)間對(duì)采樣尺度的相互調(diào)控過程涉及進(jìn)程間通信操作，通信時(shí)間如果過多，將對(duì)算法的性能造成負(fù)面影響，因此設(shè)計(jì)一種“多計(jì)算，少通信”的并行模式非常重要，這一點(diǎn)也是MPI所利用的“以計(jì)算換通信”的原則。MQHOA采樣過程中有k個(gè)采樣點(diǎn)，首先將采樣點(diǎn)分配到k個(gè)進(jìn)程中，每一個(gè)采樣點(diǎn)占據(jù)獨(dú)立的節(jié)點(diǎn)，采樣點(diǎn)自身所占據(jù)的節(jié)點(diǎn)負(fù)責(zé)采樣操作和尺度擴(kuò)張操作；然后，設(shè)置一個(gè)主節(jié)點(diǎn)，用于計(jì)算k個(gè)采樣點(diǎn)的標(biāo)準(zhǔn)差，用于處理能級(jí)穩(wěn)定過程中的替換操作和采樣尺度下降操作，主節(jié)點(diǎn)主要用于判斷算法是否滿足進(jìn)入下一過程的條件，以及能級(jí)下降和采樣尺度下降操作。

并行后的MQHOA-PS流程如圖3所示，主節(jié)點(diǎn)完成初始化后，將采樣尺度信息和采樣點(diǎn)信息傳遞到從節(jié)點(diǎn)，從節(jié)點(diǎn)獨(dú)立進(jìn)行m次采樣操作，期間采樣尺度依據(jù)采樣情況動(dòng)態(tài)擴(kuò)張，當(dāng)m次采樣完成后，將數(shù)據(jù)發(fā)送到主節(jié)點(diǎn)，此時(shí)主節(jié)點(diǎn)通過返回的采樣信息計(jì)算種群標(biāo)準(zhǔn)差σk，并判斷是否進(jìn)入下一過程，以及通過返回的信息判斷全局采樣情況，是否對(duì)整體尺度進(jìn)行減半操作，判斷算法是否滿足終止條件，同時(shí)輸出最優(yōu)解。

通過圖3可知，每一個(gè)采樣點(diǎn)占據(jù)一個(gè)獨(dú)立的節(jié)點(diǎn)，每一個(gè)采樣點(diǎn)的采樣尺度依據(jù)自身采樣情況在從節(jié)點(diǎn)上以系數(shù)l線性擴(kuò)張，根據(jù)總體收斂情況在主節(jié)點(diǎn)上進(jìn)行采樣尺度減半的操作。從信息利用的角度看，MQHOA-PS框架是利用k個(gè)采樣點(diǎn)的適應(yīng)度值判斷當(dāng)前采樣尺度是否擴(kuò)張，k個(gè)采樣點(diǎn)的適應(yīng)度方差用于判斷當(dāng)前采樣尺度是否下降，以此實(shí)現(xiàn)k個(gè)采樣點(diǎn)的采樣尺度自適應(yīng)過程，避免了算法在迭代過程中采用相同的采樣尺度，不利于跳出局部最優(yōu)的缺陷。

由于該框架每一個(gè)采樣點(diǎn)占據(jù)一個(gè)進(jìn)程，因此對(duì)進(jìn)程間通信要求較高，若進(jìn)程間通信時(shí)間會(huì)隨進(jìn)程數(shù)量增加而呈數(shù)量級(jí)增加，則不適合此框架。

Figure 3 Flow chart of MQHOA-PS圖3 MQHOA-PS流程圖

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

4.1 華為鯤鵬920通信測(cè)試

并行過程伴隨著通信過程，通信時(shí)間如果太長(zhǎng)，反而會(huì)導(dǎo)致算法效率降低，實(shí)驗(yàn)前對(duì)CPU進(jìn)行通信測(cè)試可預(yù)估通信在算法迭代中的時(shí)間比重，初步判斷實(shí)驗(yàn)可行性。MPI通信大致可分為2種：一種涉及物理機(jī)間的通信，進(jìn)程1和進(jìn)程2處于不同的物理機(jī)上，兩者間的通信除內(nèi)存讀寫外還包括網(wǎng)絡(luò)傳輸時(shí)間；另一種是同一機(jī)器內(nèi)的點(diǎn)對(duì)點(diǎn)通信，這一過程不涉及網(wǎng)絡(luò)傳輸，是通過操作系統(tǒng)進(jìn)程間通信機(jī)制實(shí)現(xiàn)的。點(diǎn)對(duì)點(diǎn)通信可分為4大類[11]：(1)基于NIC(Network Interface Card)環(huán)路；(2)基于用戶態(tài)共享內(nèi)存；(3)基于核心態(tài)共享內(nèi)存；(4)基于I/OAT(I/O Acceleration Technology)。目前MPI支持軟件采用的點(diǎn)對(duì)點(diǎn)通信方式主要是基于用戶態(tài)共享內(nèi)存實(shí)現(xiàn)的，但上述不論哪種通信方式都涉及數(shù)據(jù)拷貝過程。

由于CPU間的通信受不同的服務(wù)器體系架構(gòu)和物理機(jī)間的連接方式影響，本節(jié)對(duì)不同物理機(jī)上的進(jìn)程間通信不做討論，只對(duì)華為鯤鵬920做點(diǎn)對(duì)點(diǎn)通信測(cè)試[12]，這一測(cè)試可從側(cè)面反映華為鯤鵬920的讀寫能力，可預(yù)估華為鯤鵬920支持算法并行化的最大程度。

實(shí)驗(yàn)平臺(tái)選用的是搭載華為鯤鵬920八核處理器的PC機(jī)，操作系統(tǒng)為UOS 20，華為鯤鵬920基于ARM架構(gòu)，采用RISC精簡(jiǎn)指令集。利用MPI的消息傳遞功能實(shí)現(xiàn)不同進(jìn)程間的點(diǎn)對(duì)點(diǎn)通信，然后記錄通信時(shí)間，對(duì)處理器的通信能力進(jìn)行初步評(píng)估，看是否滿足MQHOA-PS并行框架的通信需求。本實(shí)驗(yàn)在單機(jī)上進(jìn)行，只測(cè)試處于同一物理機(jī)的核間通信，不涉及網(wǎng)絡(luò)傳輸，測(cè)試的傳輸數(shù)據(jù)包為雙精度浮點(diǎn)型數(shù)組，通過MPI_Send和MPI_Recv函數(shù)實(shí)現(xiàn)數(shù)據(jù)包在2個(gè)進(jìn)程間的傳輸，每組實(shí)驗(yàn)重復(fù)11次，將11次重復(fù)實(shí)驗(yàn)所花費(fèi)時(shí)間的平均值繪制成圖4。

Figure 4 Relationship between the size and time of sending and receiving packets 圖4 發(fā)送和接收數(shù)據(jù)包的大小與時(shí)間的關(guān)系

為了探究節(jié)點(diǎn)數(shù)量對(duì)傳輸時(shí)間的影響，分別設(shè)置大小為1 MB、2 MB、3 MB的數(shù)據(jù)包，節(jié)點(diǎn)數(shù)量為k，實(shí)驗(yàn)記錄主節(jié)點(diǎn)接收由k-1個(gè)從節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的時(shí)間，實(shí)驗(yàn)重復(fù)11次，重復(fù)實(shí)驗(yàn)的平均值繪制成圖5。

Figure 5 Relationship between node number and time when transmitting packets of different sizes圖5 傳輸不同大小數(shù)據(jù)包時(shí)節(jié)點(diǎn)數(shù)量與時(shí)間的關(guān)系

圖4的橫軸為數(shù)據(jù)包的大小，縱軸為發(fā)送和接收對(duì)應(yīng)大小數(shù)據(jù)包的時(shí)間，實(shí)驗(yàn)結(jié)果顯示,發(fā)送和接收0.97 MB內(nèi)的雙精度浮點(diǎn)型數(shù)據(jù)包所用時(shí)間數(shù)量級(jí)為10-4s。MQHOA-PS以初始化30個(gè)采樣點(diǎn)為例，在函數(shù)維度為100的情況下，每一次迭代單一節(jié)點(diǎn)傳輸?shù)淖畲髷?shù)據(jù)量約為24 KB，此時(shí)表中的傳輸時(shí)間的數(shù)量級(jí)為10-4s。圖5中傳輸同樣大小的數(shù)據(jù)包，消耗的時(shí)間隨節(jié)點(diǎn)數(shù)線性增長(zhǎng)，在工程設(shè)計(jì)中，可根據(jù)最大時(shí)間限制合理設(shè)置算法并行化程度；同時(shí)說明華為鯤鵬920可較好地支持MQHOA-PS并行化，不會(huì)因?yàn)楣?jié)點(diǎn)數(shù)增加而發(fā)生時(shí)間“爆炸”現(xiàn)象，華為鯤鵬920進(jìn)程間的通信滿足MQHOA-PS并行化框架對(duì)通信消耗的需求，且具備大規(guī)模運(yùn)算能力。

4.2 實(shí)驗(yàn)設(shè)置與數(shù)據(jù)

為了驗(yàn)證MQHOA-PS的有效性，本文以MQHOA為對(duì)照組設(shè)計(jì)實(shí)驗(yàn)，實(shí)驗(yàn)選擇7組標(biāo)準(zhǔn)測(cè)試函數(shù)，維度為2,10,15的實(shí)驗(yàn)組，實(shí)驗(yàn)重復(fù)10次，維度為30的實(shí)驗(yàn)組，實(shí)驗(yàn)重復(fù)51次,測(cè)試函數(shù)信息如表1所示，包含3個(gè)多峰函數(shù)(f1～f3)和4個(gè)單峰函數(shù)(f4～f7)，MQHOA-PS與MQHOA在實(shí)驗(yàn)中的迭代上限設(shè)置為n*10000,n為測(cè)試函數(shù)的維度。

實(shí)驗(yàn)環(huán)境為一臺(tái)獨(dú)立的PC機(jī)，處理器為華為鯤鵬920 2249，核數(shù)為8，UOS 20操作系統(tǒng)，并行化工具為MPICH 3，在該設(shè)備下的實(shí)驗(yàn)不涉及網(wǎng)絡(luò)通信。

首先對(duì)MQHOA-PS在2維和15維條件下實(shí)驗(yàn)，其中尺度擴(kuò)張系數(shù)l設(shè)置為1.2，節(jié)點(diǎn)數(shù)分別設(shè)置為3,5,8，實(shí)驗(yàn)數(shù)據(jù)如表2所示，其中Fbest表示重復(fù)實(shí)驗(yàn)中的解最小值，Mean為重復(fù)實(shí)驗(yàn)的解均值，Time為重復(fù)實(shí)驗(yàn)所消耗的平均時(shí)間，Sr為尋優(yōu)成功率，d代表函數(shù)維度，當(dāng)解小于1×10-5時(shí)判定成功，精度為1×10-14，當(dāng)解小于1×10-14時(shí)，輸出為0。

同時(shí)將改進(jìn)后的算法(MQHOA-PS)與原算法(MQHOA)做對(duì)照實(shí)驗(yàn)，實(shí)驗(yàn)設(shè)置測(cè)試函數(shù)維度為10，分別測(cè)試不同的采樣點(diǎn)(節(jié)點(diǎn))數(shù)量下算法的性能，實(shí)驗(yàn)結(jié)果如表3所示，表中算法編號(hào)1為MQHOA-PS，編號(hào)2為MQHOA。

為了探究MQHOA-PS針對(duì)高維函數(shù)的尋優(yōu)能力，實(shí)驗(yàn)設(shè)置節(jié)點(diǎn)數(shù)為8，重復(fù)實(shí)驗(yàn)51次，遵循實(shí)驗(yàn)對(duì)照原則，MQHOA的采樣點(diǎn)數(shù)量設(shè)置為8，2組算法對(duì)照實(shí)驗(yàn)的迭代上限為3×105，51次重復(fù)實(shí)驗(yàn)結(jié)果如表4所示，51次重復(fù)實(shí)驗(yàn)所得的測(cè)試函數(shù)值如圖6所示。圖6的縱軸為函數(shù)值。

由于上述實(shí)驗(yàn)在搭載華為鯤鵬920的PC上完成，PC所搭載的處理器核數(shù)為8，算法的并行規(guī)模受核數(shù)制約，因此將MQHOA-PS提交到由AMD構(gòu)建的超算中心進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)提交作業(yè)的隊(duì)列節(jié)點(diǎn)配置為：AMD EPYC 7452，單節(jié)點(diǎn)(這里的節(jié)點(diǎn)指物理機(jī)，與算法并行化節(jié)點(diǎn)不同) 64 核，主頻2.35 GHz，256 GB內(nèi)存，節(jié)點(diǎn)間采用InfiniBand網(wǎng)絡(luò)互連。實(shí)驗(yàn)設(shè)置的維度為30，節(jié)點(diǎn)(采樣點(diǎn))數(shù)分別為8,30，每組實(shí)驗(yàn)重復(fù)11次，重復(fù)實(shí)驗(yàn)的結(jié)果如表5所示。

Table 1 Names and expressions of seven test functions

Table 2 Optimization results of MQHOA-PS on 7 test functions with 2 and 15 dimensions

Table 3 Optimization results of MQHOA-PS and MQHOA on 7 test functions with 10 dimensions

4.3 結(jié)果分析

將相同的作業(yè)在單個(gè)處理器上運(yùn)行消耗的時(shí)間定義為T1，由N個(gè)核并行處理消耗的時(shí)間定義為TN，加速比SN被定義為T1與TN的比值(SN=T1/TN)，可以用來衡量并行模式的有效性，若運(yùn)行時(shí)間與核數(shù)成反比，則該并行框架為理想狀態(tài)[13]。

以表3的數(shù)據(jù)計(jì)算MQHOA-PS在目標(biāo)函數(shù)維度為10時(shí)的加速比，結(jié)果如表6所示。

通過表6可以明顯看到，伴隨計(jì)算節(jié)點(diǎn)的增加，算法的加速比開始下降，這是因?yàn)橹鞴?jié)點(diǎn)每經(jīng)過一次循環(huán)，需要向k-1個(gè)從節(jié)點(diǎn)發(fā)送和接收一次數(shù)據(jù)，節(jié)點(diǎn)數(shù)的增加導(dǎo)致執(zhí)行通信操作的次數(shù)更加頻繁，主節(jié)點(diǎn)接收數(shù)據(jù)的大小與從節(jié)點(diǎn)數(shù)量成正比，從節(jié)點(diǎn)數(shù)量越多，越會(huì)增加主節(jié)點(diǎn)在每一次迭代過程中的I/O操作時(shí)間，因此對(duì)于MQHOA-PS而言，將節(jié)點(diǎn)數(shù)量控制在一定值內(nèi)可以有效提高算法效率。

節(jié)點(diǎn)數(shù)量增加相應(yīng)地采樣點(diǎn)數(shù)也會(huì)隨之增加，由表2可見，f4和f7的求解成功率會(huì)隨節(jié)點(diǎn)數(shù)(采樣點(diǎn))的增加而上升，原因在于增加采樣點(diǎn)可以增加解的多樣性，有利于種群跳出局部最優(yōu)，這主要是由函數(shù)自身特征決定的。表2和表5中部分函數(shù)伴隨節(jié)點(diǎn)數(shù)的增加，求解精度反而下降，如表5中測(cè)試函數(shù)f2在8個(gè)節(jié)點(diǎn)的情況下，最優(yōu)解精度達(dá)到10-12，而節(jié)點(diǎn)數(shù)為30時(shí)，最優(yōu)解精度為102，已經(jīng)無法找到最優(yōu)解位置。導(dǎo)致這一現(xiàn)象的關(guān)鍵點(diǎn)在于實(shí)驗(yàn)是有迭代上限的，在有限的迭代次數(shù)內(nèi)，增加節(jié)點(diǎn)數(shù)，勢(shì)必導(dǎo)致通信操作次數(shù)增加，采樣操作次數(shù)占總迭代次數(shù)比重下降，以計(jì)算換通信而節(jié)約時(shí)間的方法無疑會(huì)犧牲求解精度，算法并行化程度過高反而會(huì)降低算法性能(求解精度與求解時(shí)間)。由表5可見，當(dāng)節(jié)點(diǎn)數(shù)從8增加到30后，算法的求解時(shí)間明顯增加，漲幅在2個(gè)數(shù)量級(jí)。這是因?yàn)楣?jié)點(diǎn)的增加導(dǎo)致通信操作更加頻繁，由于AMD超算隊(duì)列涉及網(wǎng)絡(luò)延遲，因此在編程過程中應(yīng)根據(jù)函數(shù)特征有針對(duì)性地設(shè)置節(jié)點(diǎn)數(shù)，以減少通信次數(shù)占迭代上限的比重。

Table 4 Optimization results of MQHOA-PS and MQHOA on 7 test functions with 30 dimensions and 8 nodes

Figure 6 Boxplot MQHOA-PS and MQHOA for 7 test functions with 30 dimensions and 8 nodes for 51 times repeat experiments圖6 函數(shù)維度為30，節(jié)點(diǎn)數(shù)(采樣點(diǎn)數(shù))為8時(shí)MQHOA-PS和MQHOA對(duì)7組測(cè)試函數(shù)重復(fù)51次實(shí)驗(yàn)箱體圖

Table 5 Optimization results of MQHOA-PS on 7 test functions with 30 dimensions and different node numbers on AMD processors

Table 6 Acceleration ratio of test functions with 10 dimensions

通過表4和圖6可知，當(dāng)采樣點(diǎn)數(shù)量相同時(shí)，MQHOA-PS的求解成功率和消耗時(shí)間明顯優(yōu)于MQHOA的，且MQHOA-PS的解分布情況更加穩(wěn)定，解的精確性和穩(wěn)定性要優(yōu)于MQHOA，MQHOA-PS的求解時(shí)間與MQHOA求解時(shí)間相比，平均具有2個(gè)數(shù)量級(jí)的優(yōu)勢(shì)。其中MQHOA采樣點(diǎn)數(shù)為8時(shí)，對(duì)測(cè)試函數(shù)f6求解成功率為0，通過參考文獻(xiàn)[3]中的表1可知，MQHOA在30維時(shí)對(duì)測(cè)試函數(shù)f6的求解最優(yōu)值為7.03E-09，此時(shí)采樣點(diǎn)數(shù)量為20，而MQHOA-PS通過8個(gè)采樣點(diǎn)求解的最優(yōu)值為2.15E-12，求解精度遠(yuǎn)優(yōu)于MQHOA，說明MQHOA-PS的采樣尺度自適應(yīng)策略有效增大了解的多樣性，用較少的采樣點(diǎn)即可達(dá)到較高的尋優(yōu)精度。針對(duì)測(cè)試函數(shù)f2,MQHOA的求解成功率為0，且文獻(xiàn)[4,5]中根據(jù)不同的遷移策略改進(jìn)的MQHOA系列算法(CM-MQHOA和TS-MQHOA)在30維時(shí)對(duì)測(cè)試函數(shù)f2的求解成功率為0，而MQHOA-PS在8個(gè)采樣點(diǎn)的情況下，可將求解成功率提高到0.58。這說明針對(duì)結(jié)構(gòu)類似于f2的多峰函數(shù)，增加解的多樣性可提高尋優(yōu)成功率，也再一次驗(yàn)證了采樣尺度自適應(yīng)策略的有效性。

結(jié)合表3和表4可見，并行化后的算法MQHOA-PS在8個(gè)節(jié)點(diǎn)內(nèi)，求解同樣的函數(shù)，所需要的時(shí)間都遠(yuǎn)小于MQHOA的，這表明了本文并行方案的有效性，在15維以內(nèi)，除f4外的測(cè)試函數(shù)中，MQHOA-PS在8個(gè)節(jié)點(diǎn)內(nèi)的求解成功率都要優(yōu)于同一條件下的MQHOA。

總體而言，MQHOA-PS在保證成功率和精度的前提下整體性能要優(yōu)于MQHOA的，一方面是采樣尺度間相互獨(dú)立，增加解了的多樣性，不易陷入局部最優(yōu)，提高了尋優(yōu)精度；另一方面基于采樣尺度的并行化框架有效地對(duì)算法進(jìn)行了“加速”，實(shí)驗(yàn)結(jié)果也表明了本文并行框架的有效性。

5 結(jié)束語

本文提出采樣個(gè)體間使用獨(dú)立尺度采樣的策略，對(duì)MQHOA算法進(jìn)行改進(jìn)，提高了算法跳出局部最優(yōu)解的能力，同時(shí)對(duì)這一策略設(shè)計(jì)了并行化框架，提出基于尺度并行化的MQHOA-PS，通過實(shí)驗(yàn)表明了這一并行化框架的有效性和合理性。將MQHOA算法和MQHOA-PS移植到華為鯤鵬920和AMD EPYC 7452處理器上進(jìn)行測(cè)試實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果體現(xiàn)了華為鯤鵬920處理器點(diǎn)對(duì)點(diǎn)通信能力和計(jì)算能力，可以較好地支持算法并行化，同時(shí)展現(xiàn)了基于鯤鵬處理器開發(fā)有高性能計(jì)算需求應(yīng)用的可行性。