焦育威，王 鵬,2，辛 罡

(1.西南民族大學計算機科學與技術學院,四川 成都 610225；2.廣東省國產服務器工程中心,廣東 廣州 510000；3.中國科學院大學，北京 100049；4.中國科學院成都計算機應用研究所，四川 成都 610041)

1 引言

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

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

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

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

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

2 標準MQHOA

2.1 MQHOA物理模型

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

(1)

(2)

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

(3)

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

(4)

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

算法1MQHOA

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

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

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

步驟2判斷f(x′i)

步驟3計算標準差σk；

步驟4計算標準差變化量Δσk=|σk-σ′k|；

步驟5σ′k:σ′k←σk標準差更新；

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

步驟7差解替換xworst=xmean；

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

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

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

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

2.2 MQHOA缺陷分析

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

假設目標函數f(x)為雙阱函數，其表達形式如式(5)所示：

(5)

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

(6)

其中,σs為采樣尺度。圖1展示了采樣尺度從0.05擴張到0.1的過程，采樣的采樣尺度擴張后，由式(6)計算可知，該點在下一次迭代過程中跳出局部最優(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 二維雙阱函數采樣尺度擴張示意圖

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

2.3 改進方案

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

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

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

3 MQHOA并行化

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

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

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

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

由于該框架每一個采樣點占據一個進程，因此對進程間通信要求較高，若進程間通信時間會隨進程數量增加而呈數量級增加，則不適合此框架。

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

4 實驗與結果分析

4.1 華為鯤鵬920通信測試

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

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

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

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

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

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

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

4.2 實驗設置與數據

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

實驗環(huán)境為一臺獨立的PC機，處理器為華為鯤鵬920 2249，核數為8，UOS 20操作系統，并行化工具為MPICH 3，在該設備下的實驗不涉及網絡通信。

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

同時將改進后的算法(MQHOA-PS)與原算法(MQHOA)做對照實驗，實驗設置測試函數維度為10，分別測試不同的采樣點(節(jié)點)數量下算法的性能，實驗結果如表3所示，表中算法編號1為MQHOA-PS，編號2為MQHOA。

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

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

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

以表3的數據計算MQHOA-PS在目標函數維度為10時的加速比，結果如表6所示。

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

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

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 函數維度為30，節(jié)點數(采樣點數)為8時MQHOA-PS和MQHOA對7組測試函數重復51次實驗箱體圖

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

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

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

5 結束語

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