文/鄭磊

1 引言

分區(qū)向模塊的分配問題是IMA航電總體配置必須要涉及的問題，在分配過程中需要綜合考慮模塊調(diào)度和通信延遲等限制條件。若將分區(qū)看作是周期運行的任務(wù)，那么分區(qū)向模塊的分配就類似于多處理器任務(wù)分配問題。O.Kermia[2]與J.Korst[3]等人針對無占先限制的周期任務(wù)向多處理器分配的問題提出了快速啟發(fā)式算法；T.Davidovic[4]等人針對在多處理器上非周期任務(wù)調(diào)度問題引入了MILP公式；S.Thanikesavan[5][6][7]探討了基于MILP公式的的多處理器周期任務(wù)調(diào)度問題。針對IMA分區(qū)分配問題，P.Bieber[8][9]等人從安全性和可靠性需求角度研究了應(yīng)用向模塊分配的問題；Ahmad[10]等人針對這一問題，通過將所有的約束條件線性化利用了MILP方法，在使用圖論進行一步初始化簡化變量數(shù)量后對該方程進行解析求解。由于問題本身變量數(shù)量的龐大，問題解算時間隨著分區(qū)數(shù)量和模塊數(shù)量的增多而增加，因此必須采用必要的簡化方法減少分區(qū)分配問題的解算時間，使用圖形理論進行問題簡化是非常有效的方法。

本文使用圖形理論對分區(qū)分配問題進行進一步簡化，提出分區(qū)合并算法達到減少算法解算時間的目的。

2 分區(qū)分配模型

以M表示Nm個IMA模塊的集合，即M={m1,m2,…,mNm,}，P為Np個分區(qū)的集合，即M={p1,p2,…,pNp,}。設(shè)各個IMA模塊具有同一性，即任意分區(qū)pj∈P可以在任意模塊mk∈M上運行，分區(qū)的執(zhí)行時間并不依賴于任一模塊。任意模塊mk∈M具有兩個基本屬性，分別為總可用存儲空間Rk和最大分區(qū)數(shù)Nk。由于模塊的同一性，設(shè)模塊間的通信延遲為一定值，則分區(qū)間的通信延遲主要由分區(qū)通信本身決定。分區(qū)間的通信延遲受模塊影響部分可用一延遲矩陣Δ來表示：

其中δi,j代表代表分區(qū)pi和pj分配到不同模塊后的通信延遲受模塊影響部分。

任一分區(qū)pj∈P具有如下屬性：

（1）ΕjP,分區(qū)pj的執(zhí)行時間；

（2）TjP，分區(qū)pj的運行周期，顯然有ΕjP≤ TjP；

（3）rj，分區(qū)需求的存儲空間。

以tj（1）表示分區(qū)pj的第一次執(zhí)行的開始時刻，那么由于分區(qū)運行的嚴格的周期性，它的第k次運行的開始時刻tj(k)則為：

出于某些安全性考慮，可能出現(xiàn)某兩個分區(qū)不可以分配到一個模塊中的情況。以 表示這樣的分區(qū)組(pi,pj)∈P2的集合，其中分區(qū)pi和pj不可以分配到同一模塊。

系統(tǒng)中的各個分區(qū)在運行時會進行各種形式的通信，在行為上表現(xiàn)為接收和發(fā)送數(shù)據(jù)。以Λ表示系統(tǒng)中所有NΛ個通信路徑向量的集合，即其中λir表示第i個通信路徑向量，它由該路徑所經(jīng)過的所有r個分區(qū)序列組成，若通信路徑λir先后經(jīng)過分區(qū) pj,pk…pl，有 λir=(j,k,…,l)。 以 L(λir)表示 通信路徑λir端到端的通信延遲。

定義一個包含二進制變量ai,j的矩陣A來表示分區(qū)向模塊的分配。

在分區(qū)向模塊分配過程中一個正確的分區(qū)分配必須滿足如下三種限制條件：

（1）調(diào)度限制：分配到同一個模塊中的分區(qū)不能有執(zhí)行時間上的重疊。

（2）資源限制：分配到同一個模塊的所有分區(qū)所需求的存儲空間之和要小于模塊的總可用存儲空間；分區(qū)數(shù)量之和要小于模塊可載有的最大分區(qū)數(shù)；一個分區(qū)只能被分配到一個模塊中；滿足(pi,pj)∈ε的兩個分區(qū)不能分配到同一模塊中。

（3）通信延遲限制：每一個通信路徑端到端的延遲L(λir)要小于最大可允許的延遲上限 Lmax(λir)。在給定分區(qū)集合向多模塊分配的問題中，就是要尋找一個方法使得該方法產(chǎn)生的結(jié)果能夠滿足上述所有的限制條件。

2.1 分區(qū)分配中的調(diào)度限制

由式（2）可得分區(qū)pj第k次運行的時間區(qū)間為Ik(tj(1) )=[tj(k),tj(k)+ΕjP]。限制條件：分配到同一個模塊中的任意兩個分區(qū)pi和pj不能有執(zhí)行時間上的重疊就可以表述為

圖1：模塊間通信延遲

圖2：同一模塊內(nèi)分區(qū)的調(diào)度延遲

Korst在文獻[3]中提出的兩個周期任務(wù)執(zhí)行時間不發(fā)生重疊的充分必要條件可以應(yīng)用于分區(qū)調(diào)度范疇中：

其中，gi,j為分區(qū)周期TiP與TjP的最大公約數(shù)。

分區(qū)對處理器的總占用率Uim不能大于1，若模塊mi分區(qū)數(shù)為ni，有：

其中UiP=ΕjP/TjP為分區(qū)pj的處理器占用率。

2.2 分區(qū)分配中的資源限制

分配到同一個模塊的所有分區(qū)所需求的存儲空間之和Rjm要小于模塊的總可用存儲空間可表示為：

分配到同一模塊上的分區(qū)數(shù)量之和要小于模塊可載有的最大分區(qū)數(shù)可表示為：

一個分區(qū)只能被分配到一個模塊中可表示為：

滿足(pi,pj)∈ε的兩個分區(qū)不能分配到同一模塊中可表示為：

2.3 分區(qū)分配中的通信延遲限制

在分區(qū)分配過程中，對任意通信路徑λir∈Λ，端到端的延遲 L(λir)要小于最大可允許的延遲上限。端到端的通信延遲為整條通信鏈路中的分區(qū)的執(zhí)行時間與分區(qū)間通信延遲之和，可用下式表示：

3 使用分區(qū)邏輯合并簡化模型

由式（5）可獲得在分區(qū)調(diào)度限制下不可分配在同一模塊上的分區(qū)組的集合，并使之與滿足 (pi,pj)∈ε的集合合并為集合 Ε，(pi,pj)∈Ε則為所有不可分配在同一模塊上的分區(qū)組的集合。

由式（11）和（12）可得任意通信路徑延遲的最大值為：

其中 L'(λir)和 Lmax'(λir)分別為只考慮分區(qū)分配造成的最大延遲和該延遲的上限值。若 L'(λir)>Lmax'(λir)，則該通信路徑中至少有兩個分區(qū)必須分配到同一模塊上，對于通信路徑最多可以有r-1個這樣的分區(qū)組合。

采用圖型理論進行模型簡化可以在極大限度上減少變量的數(shù)量。在分區(qū)分配問題中可采用如圖3所示分區(qū)關(guān)系圖G[10]：

在圖3中，每一個節(jié)點代表一個分區(qū)，兩個分區(qū)間的連線表明這兩個分區(qū)可以分配到同一個模塊上，反之沒有連線的兩個分區(qū)則不能分配到同一模塊上，即滿足(pi,pj)∈Ε。

類似于最大無關(guān)組（MIS）[11]的概念，在該圖中可以找到這樣一個集合B，該集合包含的所有分區(qū)彼此互相不能分配到同一模塊上，如在該圖中有(p1,p3,p6)∈B。在分區(qū)路徑λir延遲 L'(λir)>Lmax'(λir)的約束下，可以找到r-1個必須分配到同一模塊的分區(qū)組合，并將pi,pj兩個分區(qū)合并成一個節(jié)點pi,j進行考慮，在合并的同時，新節(jié)點要繼承原先節(jié)點與其他節(jié)點互斥關(guān)系。設(shè)集合Dg為以pi,j為元素的集合，即pi,j∈Dg。在圖3中，虛線表示一條通信路徑λ14，它先后經(jīng)過分區(qū)p1,p5,p6,p7，若有Lmax'則(p5,p6)或(p6,p7)必須分配在一個模塊中，將(p5,p6)節(jié)點合并后的關(guān)系圖Gg'為圖4，(p6,p7)的合并與之同理。

4 分區(qū)分配方法流程

整個分區(qū)分配算法包含如下幾步：

（1）由式（5）解算出所有滿足(pi,pj)∈Ε的分區(qū)組合，并作出分區(qū)間關(guān)系圖G。

（2）由式（15）和（16）對每一條通信路徑進行分析，求解出所有pi,j∈Dg，并在關(guān)系圖G中合并相關(guān)的pi和pj獲得關(guān)系圖Gg'。若總共有Nλ條通信路徑，則關(guān)系圖Gg'的最大數(shù)量NG為

（4）將Bg所包含的分區(qū)分配到每一個模塊中（一個模塊最多分配一個分區(qū)或合并后的分區(qū)對）。設(shè)必須分配到模塊mk中的分區(qū)組成的集合為若有pi∈Bg必分配到模塊mk中，則有

（6）對所有Nm個模塊作運算其 中 l=1,2,…,Nm，且l≠k獲得只能分配到模塊mk的分區(qū)，并將同時滿足式（6～8）條件的分區(qū)分配到模塊mk。

（7）重復(fù)5）和6），直到無法獲得只能分配到一個模塊中的分區(qū)。這樣就可以獲得對應(yīng)于每個Gg'的兩種數(shù)據(jù)：其一為必須分配到各個模塊的分區(qū)集合其二為可分配到兩個以上模塊的分區(qū)集合和每個分區(qū) pi∈Pg'可以分配的模塊的集合Mpig。集合Pg'所含分區(qū)只須滿足式（6～8）的限制條件就可以分配到各個模塊。

（8）在集合Mpig中，找出當前模塊處理器占用率最小的模塊mk，將集合Pg'中處理器占用率UjP最大的模塊分配到mk中，分配的同時要滿足式（7）和（8）的約束條件。

引入Np維矩陣C=[ci,j]表示分區(qū)之間的關(guān)系，若分區(qū)pi,pj可以分配到同一模塊上，則ci,j=1，反之 ci,j=0，ci,j=cj,i，若 i=j規(guī)定 ci,j=0。分區(qū)間的合并可以通過矩陣元素間的邏輯運算來表示，算法如下：若分區(qū)pj和pk(j

若分區(qū)關(guān)系如圖3，分區(qū)合并情況如圖4則有

該算法的流程如圖5。

由此，即可獲得對應(yīng)于每個Gg'的和。

5 結(jié)語

從算法解算過程可以看出，整個解算過程所需的邏輯運算次數(shù)較少，通過引入矩陣元素間的邏輯運算，使算法便于編程實現(xiàn)，并通過引入分區(qū)合并機制減少了運算次數(shù)，是一個可行的分區(qū)分配問題解決方案。

圖3：分區(qū)關(guān)系圖

圖4：合并后的分區(qū)關(guān)系圖

圖5：分區(qū)分配算法流程