基于貪心遺傳算法的DIMA軟硬件模塊映射的優化研究

潘云嵩，周崇亮，萬曉冬

(南京航空航天大學 自動化學院，江蘇 南京 211106)

0 引言

航空電子系統是飛行器所有電子系統的總和。其系統大致經歷了分立式、聯合式、綜合模塊化(IMA)3個階段[1]。目前，航空電子正從IMA走向分布式綜合模塊化航空電子系統(DIMA)的發展階段。

DIMA繼承了已應用在B787、A380上的IMA的模塊化概念，制定具有標準統一接口的核心處理器模塊，分別為數據處理模塊(DPM)、信號處理模塊(SPM)、圖像處理模塊(GPM)、網絡支持模塊(NPM)、存儲器模塊(MMM)、電源模塊(PCM)。同時克服了IMA存在的集中式大機柜帶來的可靠性較差、線纜過長、不宜冷卻、故障容易擴散等缺點[2]。核心處理模塊根據需求分布在飛機的各個位置，各個模塊之間通過實時高容錯通信網絡互連。

通過實時高容錯通信網絡連接起來的通用核心處理模塊、傳感器和作動器構成DIMA的硬件物理層[3]。硬件物理層為系統運行提供計算資源、存儲資源、IO資源、能源等。通用核心處理模塊如何分布在飛機上，稱之為硬件模塊映射問題。在DIMA系統中，飛行任務被細分成原子化的子任務模塊，每個子任務只能由一個特定的處理器模塊處理。為在完成一個飛行任務需要多個多種類型的處理器模塊協同合作，即功能應用軟件在多個多種處理器模塊加注和運算，并根據需要驅動傳感器或是作動器完成子任務。飛行任務的子任務模塊如何加載到分布在物理層上的通用處理模塊，稱之為軟件模塊映射問題。

Hamburg Univetsity of Technology的Bj?rnAnnigh?fer從成本的角度出發，提出了基于遺傳算法求解Pareto多目標優化的方案[4-5]。清華大學Chao Zhang從成本和可靠性的角度出發，對多個優化目標賦予不同的權值轉換成基于遺傳算法的單一目標優化問題[6]。上述文獻均未對處理器模塊做細分，把六大類處理器模塊當作同一實體討論，且把子任務模塊和硬件模塊作為一個整體同時進行優化。在航空電子系統運行期間，子任務模塊是動態加注到已經分布在飛機物理層上的通用處理器模塊上，因此把硬件模塊映射和軟件模塊映射分成獨立的兩個階段更適合。本文在采用多種群遺傳算法[7]求解六大類通用處理模塊映射問題的基礎上，采用貪心算法求解軟件映射優化問題。

1 DIMA資源映射問題描述

1.1 硬件模塊映射

DIMA采用模塊化的設計理念。航電功能系統模塊化設計，分出DPM、SPM、GPM、NPM、MMM、PCM六大模塊，每個模塊完成特定的功能。這六大類型模塊要分別安裝到分布在飛機不同位置的機架上，如圖1所示。

1.2 硬件映射數學模型

機架定義為L1,N1,L2,N2,…,Lm,Nm,其中Lm,Nm表示第m個機架具有Nm個安裝槽位供處理器模塊安裝。處理器模塊統一標記為D1,D2,…,DND, 其中ND等于處理器模塊總數量。處理器模塊安裝在機架上，則可以表示為x向量：

X=[X1,Xi,…,XND]

(1)

其中，Xi表示為第i個模塊的安裝向量。

Xi=[xi,L1,…,xi,Lm]

(2)

其中，xi,Lm=1則表示第i個模塊安裝在第Lm機架上。xi,Lm=0，則表示不安裝。

約束條件1：每個模塊只能安裝在一個機架的一個安裝槽位上，一個機架可以安裝多個模塊，即：

AXT≤B

(3)

其中，B為長度為m的一維向量B=[1,1,…,1],A=diag(I,I,…,I),I=[1,1,…,1],長度為ND。

約束條件2：一個機架可以安裝多個模塊，但不能超過機架的總安裝槽位，即：

(4)

其中，1≤j≤m,，Nj表示第j個機架的槽位數量。

硬件映射方案的散熱用向量H表示:

H=[H1,Hi,…,HND]

(5)

其中，Hi表示為第i個模塊的安裝向量。

Hi=[Hi,L1,…,Hi,Lm]

(6)

其中，Hi,Lm≠0則表示第i模塊安裝在第lm機架上且散熱量為Hi,Lm≠0，Hi,Lm=0，則表示此槽位沒有模塊。

約束條件3：機架上安裝的處理器模塊總散熱量不能超過機架的最大冷卻能力，即：

AHT≤C

(7)

其中，C為長度為m的一維向量C=[C1,…Cm]，Cm為機架的最大冷卻能力，A=diag(I,I,…,I),I=[1,1,…,1],長度為ND。

在航電系統運行期間，處理器模塊會與外圍設備(傳感器或是作動器)產生交互，機架到外圍設備的距離用矩陣L表示：

(8)

其中，lqp表示q機架到第p個外圍設備的距離，lqp=lpq，則所有安裝在機架里的處理器到外圍設備的距離用Dis表示，即：

(9)

(10)

1.3 軟件模塊映射問題

DIMA分成3個層次結構，分別為功能層、任務層、處理器模塊層。系統功能被分成多個子任務。這些子任務是原子化，即一個子任務只能分配給一個處理器模塊處理。但一個處理器模塊可以處理多個來自不同系統功能的子任務。軟件模塊映射問題就是系統所有的子任務如何加注到模塊上，如圖2所示。

圖2 軟件映射示意圖

系統任務用F表示，原子任務用T表示，式(11)表示第i個系統功能可分成m個子任務。式(12)表示整個DIMA共有N個系統功能。

FI=(Ti,1,Ti,2,…,Ti,m)

(11)

F=(F1,F2,…,FN)

(12)

處理器模塊用M表示，MT表示該模塊能處理T類型的任務。

軟件映射問題就是給出功能Fi，依據怎樣的規則在DIMA模塊層中找出能完成該功能所需的處理器模塊集合Mset={MT1,…,MTm}。

2 問題優化求解

2.1 硬件映射的優化

上文已對硬件映射做了數學描述，建立如式(13)所示的數學模型，即求Dis最小值：

(13)

St.AXT≤B

AHT≤C

該模型是帶3個約束條件的單一目標優化問題。優化的目標為處理器模塊到外圍設備的距離Dis最短。Dis在DIMA系統中是個很關鍵的指標，直接關系到通信效率、線纜費用等方面。本文采用帶有修復因子的多種群遺傳算法求解該硬件映射的最優解。

染色體采用自然數編碼形式[8]?？偣灿衜個模塊需要安裝，記為(1，2，3，…，m)。所有的機架共有n個安裝槽位，編號為(1，2，3，…，n)。染色體編碼形式如圖3所示，其中標記為“0”表示此槽位不安裝任何模塊。采用自然數編碼形式能保證滿足式(3)和式(4)的約束條件。

圖3 染色體編碼形式

隨機產生染色體交叉位置k，然后交換1～k的染色體體位，并記下兩條1～k染色體體位的對應關系。依照1～k對應關系，交換k～n兩條染色體體位。

隨機產生2個染色體的突變位置，然后交換這2個位置的編碼，完成染色體的突變。

修復策略：對生成的每一代染色體，計算其對應機架上所有模塊產生的散熱量，如果超過了機架的冷卻能力，隨機把該機架上的模塊放入具有剩余冷卻能力最大的機架內，直至滿足式(7)對機架冷卻能力的約束條件。

多種群遺傳算法在常規的標準遺傳算法(SGA)的基礎上引入多個種群。每個種群配置不同的交叉概率pc和突變概率pm，這樣能擴大算法的搜索范圍。每個種群通過移民算法，把最優的個體引入其他種群，實現多個種群的協同進化。其算法框架如圖4所示。

圖4 多種群算法流程圖

對硬件映射問題的求解，需要的數據有機架的數量、每個機架的槽位、每個機架與外圍設備的距離和處理器模塊的散熱量，限于篇幅就不列出了。如圖5和圖6所示，采用多種群算法求解硬件映射問題約進化到80代時收斂。

圖5 每一代種群進化結果

圖6 每一代精英個體適應度

對精英個體的染色體通過解碼就得到該問題的最優解，如表1所示。表1中表示150個硬件處理模塊在3個機架上的映射，自然數是硬件處理模塊的編號，0值表示該機架該位置不安裝任何處理器模塊。限于篇幅，未能列出全部數據。

表1 硬件模塊映射結果

2.2 軟件模塊映射優化

求解軟件映射問題時確定如下3個優化目標：

1) 要能保證完成系統功能。

2) 子任務加注到處理器模塊盡可能靠近外圍設備。處理器靠近外圍設備就地處理，避免了數據在通信網絡上的遠程傳輸。

3) 協同合作完成系統功能的多個多種類型的處理器模塊在空間上盡可能接近。處理器模塊聚集度高，將直接縮短處理器模塊之間數據的傳輸距離，這就能提高DIMA通信效率和可靠性。

其中x，y為模塊在飛機平面上的空間位置坐標。

本文采用基于優先級的貪心算法[9]解決軟件映射問題。首先依據任務緊迫性、運算數據大小等因素事先排出子任務的優先級，然后采用貪心的策略遍歷所有可行解依次找到滿足上述3個優化目標的解。其算法過程如下：

a) 遍歷所有的核心處理模塊，沒有剩余運算能力的核心處理模塊排除在搜索范圍之外。

b) 依據子任務的優先級，從高到低逐個選擇處理器模塊，依據以下2個優先級準則：

1) 若子任務需要用到某種外圍設備，則采用遍歷方式尋找離該外圍最近的模塊。

3) 模塊m加入集群，更新集群中心。

c) 如果還有子任務沒有分配，則繼續步驟a)和步驟b)，否則結束遍歷。

在硬件映射完成的基礎上，采用貪心策略依次滿足軟件模塊映射的3個優化目標，最終必定能找到一個近似最優的軟件模塊映射問題解，即求得子任務加載到通用處理器模塊的方案。限于篇幅，未能列出優化軟件模塊映射問題的輸入數據，軟件模塊映射優化結果，見表2所示。表2表示4個具有不同優先級的子任務軟件模塊被加注到4個硬件模塊之上。

表2 軟件模塊映射結果

3 結語

分布式綜合化模塊化航空電子系統(DIMA)是在聯合式航空電子系統和綜合化模塊化航空電子系統的基礎上發展起來面向未來的下一代航空電子系統。從國內外公開發表的文獻來看，DIMA的資料還不是很多，知識點非常零散。本文采用多種群遺傳算法解決DIMA硬件映射問題，實驗結果顯示是有效果的。對軟件映射問題，本文提出了基于優先級貪心算法。其實質是用貪心算法找到合適的映射方案，以期滿足盡可能縮短數據在處理器模塊之間、處理器模塊與傳感器作動器之間的傳輸距離3個優化目標。

[1] 徐科華, 陳謀, 徐揚,等. 民用飛機機載電子系統分布式體系架構研究[J]. 工程設計學報, 2012, 19(6):494-498.

[2] 朱聞淵, 尹家偉, 蔣祺明. 新型航空電子系統總線互連技術發展綜述[J]. 計算機工程, 2011(s1):398-402.

[3] Wolfig R, Jakovljevic M. Distributed IMA and DO-297: Architectural, communication and certification attributes [C] //Digital Avionics Systems Conference, IEEE/AIAA 27th. IEEE, 2008(1): 4-10.

[4] Annighofer B, Thielecke F. Multi-objective mapping optimization for distributed Integrated Modular Avionics[J]. Digital Avionics Systems Conference, 2012,6B2:1-13.

[5] B. Annigh?fer, Thielecke F. A systems architecting framework for optimal distributed integrated modular avionics architectures[J]. CEAS Aeronautical Journal, 2015, 6(3):1-12.

[6] Zhang C, Xiao J. Modeling and optimization in Distributed Integrated Modular Avionics[J]. Digital Avionics Systems Conference, 2013:1-20.

[7] 劉鵬程, 李新利. 基于多種群遺傳算法的含分布式電源的配電網故障區段定位算法[J]. 電力系統保護與控制, 2016, 44(2):36-41.

[8] 鄒琳, 夏巨諶, 胡國安. 基于實數編碼的多種群并行遺傳算法研究[J]. 小型微型計算機系統, 2004, 25(6):982-986.

[9] 代文強, 李曉榮, 馮毅. 最大和搜索結果多樣性問題及其貪婪算法分析[J]. 系統工程理論與實踐, 2016(3):706-711.