于堯，趙忠文，郭皇皇

（裝備學(xué)院復(fù)雜電子系統(tǒng)仿真實驗室，北京101416）

為了充分挖掘并行仿真潛力，實現(xiàn)負(fù)載優(yōu)化是提升并行仿真效率的關(guān)鍵問題。一般解決方式分為動態(tài)負(fù)載平衡和靜態(tài)負(fù)載平衡兩種算法，動態(tài)負(fù)載平衡[1-8]是一種通用的平衡方法，但這種方法本身存在通信開銷較大的問題，因此在特定的應(yīng)用領(lǐng)域，靜態(tài)負(fù)載平衡設(shè)計一般比動態(tài)均衡算法更有效。在靜態(tài)負(fù)載平衡技術(shù)中，文獻(xiàn)[9]提出規(guī)則分塊算法和不規(guī)則分塊算法相結(jié)合的方法，從圖論的角度討論了靜態(tài)負(fù)載平衡問題，文獻(xiàn)[10-16]提出了基于蟻群算法的調(diào)度策略，提高了并行計算性能；文獻(xiàn)[17]提出基于最大-最小蟻群算法的模糊分類設(shè)計方法，實現(xiàn)了精確性與解釋性的折衷。但相關(guān)文獻(xiàn)對于仿真中存在的通信負(fù)載平衡問題研究相對較少，因此本文針對并行仿真通信負(fù)載的優(yōu)化問題進(jìn)行研究。

由于模型間的復(fù)雜交互，使通信負(fù)載和計算負(fù)載的測試及優(yōu)化變得繁瑣及困難，本文將狀態(tài)通信問題轉(zhuǎn)化為模型間的交互作用，將模型的計算負(fù)載轉(zhuǎn)化為模型復(fù)雜度問題，通過蟻群算法將交互頻繁的仿真模型聚合到相同的處理器上，以減少處理器間模型消息傳遞的通信開銷，采用遺傳算法快速搜索優(yōu)勢，以此彌補(bǔ)蟻群算法初期信息素匱乏導(dǎo)致算法收斂速度慢的缺陷。充分發(fā)揮多核處理器優(yōu)勢，還需滿足不同處理器總模型復(fù)雜度均衡，從交互作用及模型復(fù)雜度兩個方面實現(xiàn)負(fù)載優(yōu)化。

1　負(fù)載優(yōu)化問題的簡化

仿真模型如何映射到多核處理器將會對仿真效率有很大的影響，由于同一個處理器上模型的通信開銷將遠(yuǎn)小于不同處理器的通信開銷，因此應(yīng)當(dāng)將交互頻繁的仿真模型指派到同一個處理器上，以減少通信負(fù)載，為充分發(fā)揮多核處理器計算能力，每個處理器應(yīng)根據(jù)自身處理能力以及模型的計算量進(jìn)行適度映射。

由于模型間的狀態(tài)通信以及模型計算量在整個動態(tài)仿真中是變化的而且難以準(zhǔn)確測量或描述，因此可將該問題簡化，將模型的通信問題轉(zhuǎn)化為模型交互作用問題，將模型的計算負(fù)載轉(zhuǎn)化為模型復(fù)雜度問題。模型的交互作用體現(xiàn)在傳遞消息上，傳遞消息的越頻繁，交互作用就越大，兩個模型間的通信越就緊密，因此將交互作用頻繁的模型聚合在同一個處理器上，將會減少通信開銷，模型的交互作用可根據(jù)模型的交互結(jié)構(gòu)進(jìn)行靜態(tài)分析計算。模型復(fù)雜度反映的是模型的計算量，模型設(shè)計的越復(fù)雜，可以認(rèn)為模型的計算量越大，模型復(fù)雜度可采用群決策法進(jìn)行分析計算，然后根據(jù)層次分析法可計算出各模型復(fù)雜程度的權(quán)重，該權(quán)重值即作為模型復(fù)雜度。但實際中模型的計算量不僅和模型的復(fù)雜度有關(guān)，還與模型在仿真中執(zhí)行的頻率有關(guān)，因此可通過交互作用進(jìn)行補(bǔ)償，即交互作用越大計算量越大。最后將交互作用頻繁的模型聚合在一起，映射到同一個處理器上以減少通信開銷，為充分發(fā)揮多核處理器性能，應(yīng)保證每個處理器聚合后的模型復(fù)雜度相差較小。

1.1　交互作用的計算

靜態(tài)分析方法是圍繞仿真任務(wù)進(jìn)行靜態(tài)分析的一種方法，所謂靜態(tài)指的是仿真運行前進(jìn)行的處理器映射，在運行的過程中不作調(diào)整，直到運行結(jié)束為止。通過仿真任務(wù)在處理器上的合理映射，以達(dá)到仿真系統(tǒng)的綜合性能最優(yōu)。

為了讓交互頻繁的模型映射到相同的處理器，我們可將模塊間的交互作用轉(zhuǎn)化為關(guān)系距離的概念，交互作用越大，兩者的關(guān)系距離則越小，按照關(guān)系距離對模型進(jìn)行聚合，交互作用轉(zhuǎn)化為距離公式如式（2）所示，其中dijnew表示關(guān)系距離。

1.2　模型復(fù)雜度的計算

群決策也稱為多人決策，它是將不同知識結(jié)構(gòu)及不同經(jīng)驗的決策者集中在一起，彌補(bǔ)個人知識及經(jīng)驗的不足的科學(xué)決策方法。在一個群決策過程中，大多要求各個決策者給出因素的評價分值或是比較的結(jié)果等。對于模型的復(fù)雜度的確定可根據(jù)模型的相互觸發(fā)關(guān)系、模型的內(nèi)部設(shè)計結(jié)構(gòu)、以及模型程序設(shè)計結(jié)構(gòu)進(jìn)行比較分析，形成決策者對各模型復(fù)雜程度的判斷矩陣。其模型復(fù)雜度比較的評語集應(yīng)如表1所示。

表1　模型i對模型j復(fù)雜度的評語集

2　基于改進(jìn)蟻群算法的處理器映射

為了讓交互頻繁的模型映射到相同的處理器上，我們首先需要對模型進(jìn)行排序，排序的原則就是保證兩兩模型間的交互作用盡可能大，即模型間總的交互作用最大。我們將模塊間的交互作用轉(zhuǎn)化為關(guān)聯(lián)距離的概念，交互作用越大，兩者的關(guān)聯(lián)距離則越小，從而將每個處理器交互作用最大問題轉(zhuǎn)化為關(guān)聯(lián)距離最短問題。對于這類問題概率搜索算法有其獨特的優(yōu)勢，但也有其明顯的缺陷，因此本節(jié)首先利用遺傳算法全局搜索的優(yōu)勢對蟻群算法的初始信息素值進(jìn)行修正，解決了蟻群算法前期由于初始信息素過低而引起的全局搜索收斂慢的問題，再利用蟻群算法的反饋機(jī)制尋找模型排序的最優(yōu)解。為了充分發(fā)揮多核處理器的并行能力，需要將閉合排序按照關(guān)聯(lián)距離的大小進(jìn)行切割聚類，從而保證每個組的交互作用盡可能的大，同時需要根據(jù)每個模型復(fù)雜度及每個處理器的能力進(jìn)行計算負(fù)載平衡，從而讓每個處理器能夠充分發(fā)揮其計算能力。

2.1　改進(jìn)的蟻群算法設(shè)計

1）遺傳算法編碼對模型的關(guān)聯(lián)距離進(jìn)行二進(jìn)制編碼，生成距離矩陣D，起始點到目標(biāo)結(jié)束點的路徑序列作為一條染色體的編碼，每個染色體都代表了一個完整模型交互作用距離的路徑。

2）適應(yīng)度函數(shù)設(shè)定染色體g的適應(yīng)度函數(shù)如式（4）所示，其中的Dkikj表示第i個模型到第j個模型的距離。

3）選擇操作采用輪盤賭選擇方法，從舊群體按概率選擇到新群體當(dāng)中。

4）交叉操作兩條染色體隨機(jī)選擇一個公共點作為交叉點，從起始點到交叉點的節(jié)點順序保持不變，將交叉點與目標(biāo)節(jié)點間的順序相互交換。

5）變異操作一條染色體中任選兩個點進(jìn)行位置互換。

6）遺傳算法結(jié)束在遺傳算法的迭代過程中同時統(tǒng)計進(jìn)化率，公式為

設(shè)遺傳算法迭代次數(shù)為N，若連續(xù)三次進(jìn)化率都小于最小進(jìn)化率時，則停止遺傳算法迭代過程，進(jìn)入蟻群算法。

7）遺傳算法對蟻群算法信息素的修正選擇遺傳算法結(jié)果的適應(yīng)值最高的前10%條路徑V，作為蟻群算法的初始路徑，由于遺傳算法沒有信息素值，所以定義τF=k?F（g）為遺傳算法產(chǎn)生的信息素值，k為常數(shù)，當(dāng)有多條路徑經(jīng)過仿真模型位置時，τa需要進(jìn)行疊加。因此，蟻群算法的信息素初值為τs=τa+τF，τa為常數(shù)。

8）目標(biāo)點轉(zhuǎn)移概率采用輪盤賭原理的路徑選擇策略，見式（6），式（6）中的為t時刻螞蟻k從模型i轉(zhuǎn)移到模型j的概率。其中ηij（t）為啟發(fā)函數(shù)，表示螞蟻從模型i轉(zhuǎn)移到模型j的期望程度；allowk（k=1，2，…，m）為螞蟻k待訪問模型的集合；α為信息素重要程度因子，簡稱信息素因子，其值越大，表明信息素強(qiáng)度影響越大；β為啟發(fā)函數(shù)重要程度因子，簡稱啟發(fā)函數(shù)因子，其值越大，表明啟發(fā)函數(shù)影響越大。

9）信息度更新規(guī)則螞蟻在行走的同時，信息素的強(qiáng)度也在揮發(fā)而逐漸消失。式（7）中的ρ（0<ρ<1）表示信息素的揮發(fā)程度，信息素濃度為

其中式（8）中的Q為信息素常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；Lk為第k只螞蟻經(jīng)過路徑的總長度，并記錄最短路徑時模型的連接順序。

2.2　模型聚類與處理器的映射

改進(jìn)的蟻群算法按照總交互作用最大，其意義是兩兩模型間的交互作用也將越大，從而得到各模型連接的一個封閉的關(guān)聯(lián)環(huán)，關(guān)聯(lián)環(huán)上每個點代表了一個仿真模型，每個邊代表仿真模型間的關(guān)聯(lián)距離，整個關(guān)聯(lián)環(huán)點的順序體現(xiàn)了在總關(guān)聯(lián)距離最小時，仿真模型的連接順序，如圖1（a）所示。

如果僅考慮通信的切換開銷最小，將所有的模型映射到同一個處理器上，顯然通信的切換開銷將是最小的，但是多核處理器的性能顯然沒有發(fā)揮出來，因此還需要先將關(guān)聯(lián)環(huán)進(jìn)行適當(dāng)?shù)膭澐?，將交互頻繁的模型聚類，然后將每段的模型映射到相應(yīng)的處理器上，從而充分發(fā)揮多核處理器的并行計算優(yōu)勢。

圖1　蟻群算法的關(guān)聯(lián)環(huán)示意圖

1）關(guān)聯(lián)環(huán)切割

關(guān)聯(lián)環(huán)的分割的過程實際是將交互頻繁的模型聚類的過程，根據(jù)關(guān)聯(lián)距離的大小進(jìn)行切割的，其中關(guān)聯(lián)距離為無窮大的必須進(jìn)行切割，這部分表示模型之間沒有任何交互作用，通常是模型是區(qū)域隔離的，例如某個地面雷達(dá)站只會定位其探測范圍內(nèi)的飛機(jī)的位置，而距離其較遠(yuǎn)未知的飛機(jī)與該雷達(dá)如果沒有任何交互，因此他們的關(guān)聯(lián)距離才會為無窮大，因此先進(jìn)行切割。然后依次按照關(guān)聯(lián)距離的由大到小將關(guān)聯(lián)環(huán)進(jìn)行切割，如圖1（b）所示，直到發(fā)生斷開邊的模型存在緊密的交互作用后停止切分（設(shè)置關(guān)聯(lián)距離小于某一閾值即停止），我們可認(rèn)為剩余連接的模型都是交互頻繁的。

2）處理器的映射

切割后的n組模型需要再一次重組到m個處理器上，為了充分發(fā)揮處理器的計算能力，處理器的映射應(yīng)該考慮計算負(fù)載平衡，其目的在于讓所有處理器盡量在相同的時間根據(jù)各自的處理能力完成各自相應(yīng)的任務(wù)量。在此我們忽略并行仿真中每個處理器等待其他處理器的消息的時間，僅考慮處理器的效率因素，分配給處理器相應(yīng)的任務(wù)量，即處理效率即比為任務(wù)量分配比，可按照式（9）計算每個處理器應(yīng)分配的任務(wù)量，其中P代表處理器的計算能力，C代表聚合后的各段模型總復(fù)雜度，右下標(biāo)數(shù)字代表處理器標(biāo)號。

然后根據(jù)式（10）檢驗每個處理器的計算負(fù)載是否平衡，其中α為允許的誤差范圍，其中i為處理器標(biāo)號，其取值范圍為1，2…m。

3　實驗驗證及分析

實驗算例采用的是某個導(dǎo)彈突防仿真，對敵方分布的5個目標(biāo)群分別使用128/256/314/512/640枚導(dǎo)彈進(jìn)行目標(biāo)群轟炸，每個目標(biāo)群含有一套雷達(dá)干擾設(shè)備，導(dǎo)彈分配到5個目標(biāo)群數(shù)量比為26:26:26:25:25，采用上述方法將仿真模型映射到多核處理器進(jìn)行并行仿真。

1）模型間交互作用及模型復(fù)雜度

將該仿真分成5個子任務(wù)，D1R1、D2R2、…、D5R5，其中D代表導(dǎo)彈，R代表雷達(dá)設(shè)備，導(dǎo)彈具有移動模型，雷達(dá)具有決策模型、干擾模型和移動模型，模型的t、p、s以及模型間的交互作用計算如表2所示，未說明模型間交互作用記為0；通過群決策法可得4個模型復(fù)雜度分別為0.53、0.11、0.08、0.29。

表2　模型間的交互作用

2）蟻群算法的聚類

按照式（2）將交互作用轉(zhuǎn)化為關(guān)系距離，按照式（4）-（8）的蟻群算法將模型進(jìn)行排序，然后根據(jù)關(guān)聯(lián)距離的大小將模型聚類，停止切分的的關(guān)聯(lián)距離閾值設(shè)置為R1-R5的模型間交互作用的最小值。利用MATLAB實現(xiàn)改進(jìn)的蟻群算法的模型聚類的過程，其實驗參數(shù)設(shè)定如表3所示。

表3　實驗參數(shù)設(shè)定

MATLAB的仿真結(jié)果如圖2所示，其中1-5分別代表D1-D5的移動模型，6-8、9-11、12-14、15-17、18-20分別代表R1-R5的3個模型。比較傳統(tǒng)蟻群算法和改進(jìn)的蟻群算法，5次實驗的平均運行時間分別由20.40 s提高到11.88 s，驗證了算法改進(jìn)的有效性。

圖2　模型交互作用的聚合圖

3）處理器的映射

以128個導(dǎo)彈的處理器分配為例，根據(jù)每個處理器的模型復(fù)雜度平衡原則將模型映射到處理器上。映射到四核和八核處理器上，結(jié)果如表4和表5所示。

表4　四核處理器的模型映射關(guān)系

表5　八核處理器的模型映射關(guān)系

4）仿真實驗驗

基于ROSS仿真引擎對上述模型進(jìn)行實現(xiàn)，將模型分別映射到處理器為四、八核的處理器上進(jìn)行運行，并與串行仿真進(jìn)行比較，比較結(jié)果如圖3所示，經(jīng)比較發(fā)現(xiàn)并行仿真中，四核處理器仿真效率比串行提高63.0%，八核處理器仿真效率比串行提高73.6%，均能夠較好的發(fā)揮并行仿真的能力，說明了該方法能夠通過模型合理映射到處理器上實現(xiàn)負(fù)載的優(yōu)化，能夠比較充分發(fā)揮多核處理器的性能，驗證了該方法的有效性。

圖3　并行仿真與串行仿真的效率對比

4　結(jié)束語

本文將仿真模型通信負(fù)載及計算負(fù)載問題簡化為模型交互作用及模型復(fù)雜度問題，利用改進(jìn)的蟻群算法將模型按照交互作用進(jìn)行排序和聚類，并根據(jù)模型復(fù)雜度以及處理器的能力將模型映射到處理器上，該方法能夠減少仿真中的通信開銷，并能充分發(fā)揮仿真的并行程度，在導(dǎo)彈突防的仿真中得到了很好的效果，證明了該方法在并行仿真的負(fù)載優(yōu)化的有效性。