一種構(gòu)件調(diào)度策略生成新方法

海軍裝備部裝備項目管理中心 林麗娜 胡子穎

本文給出一種基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成算法，將構(gòu)件動態(tài)部署和調(diào)度策略的生成描述成新的裝箱問題。實驗表明，本文給出的基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成算法，能夠較好地解決大規(guī)模構(gòu)件的動態(tài)部署問題。

現(xiàn)有信息系統(tǒng)軟件服務構(gòu)件的部署和調(diào)度，通常采用兩種簡化的策略：基于預案的方法、人工調(diào)度方法。而對于抽象問題而言，構(gòu)件部署問題屬于典型的裝箱問題，是復雜的組合最優(yōu)化問題。從計算復雜性來講，裝箱問題是一個NP完全問題，難以精確求解，當下的解決方案是近似算法，包括FF,NF,FFD,BFD算法。

基于預案的調(diào)度方法，是事先人為制定好構(gòu)件與CPU計算單元的對應關(guān)系，制定構(gòu)件缺省加載配置表。基于預案的調(diào)度方法缺點在于，對于大型復雜系統(tǒng)軟件，完全人工制定預案的方式工作量大，預案效果難以得到保證。完全人工調(diào)度的方法則存在效率低和難以給出最優(yōu)方案的問題。

本文所給出的基于圖約束裝箱算法BPPR的構(gòu)件調(diào)度策略生成方法，以嵌入式信息處理設(shè)備中的CPU為頂點，以CPU計算資源為頂點權(quán)重，以單個CPU上RapidIO高速數(shù)據(jù)傳輸通道數(shù)量限制頂點的最大度約束，以不同CPU之間構(gòu)件的通信鏈路為邊，形成一張圖。因此，該類構(gòu)件部署的問題即轉(zhuǎn)化為一個最優(yōu)圖的求解問題，要求滿足構(gòu)件運行資源和數(shù)據(jù)傳輸需求的同時，使得占用的CPU數(shù)目最小，需要建立的高速數(shù)據(jù)鏈路數(shù)量最少。

1 圖約束裝箱問題BPPR的形式化表達

結(jié)合嵌入式信息處理設(shè)備中的構(gòu)件調(diào)度問題，將BPPR裝箱問題可描述如下：

采用RapidIO高速總線的嵌入式多CPU單元的信息處理裝備中，給定一組容量為W的箱子（CPU）B={b1,b2,...,bm}，和n個物品（構(gòu)件）的序列L={a1,a2,...,an}，物品ai的體積（如：CPU、內(nèi)存占用率）為wi（wi ≤ W），要求將這些物品裝進若干箱子中，使得每個箱子中裝載的物品總體積不大于W，并使所用的箱子數(shù)目最小。

在通過求解裝箱問題來生成構(gòu)件部署策略時，除了滿足經(jīng)典裝箱問題所需要考慮的箱子容量和物品體積條件外，還需要滿足硬件環(huán)境中CPU的通信鏈路數(shù)量限制。因此，需要建立裝箱過程的圖約束條件。

給定一組待部署的構(gòu)件，建立構(gòu)件間通信關(guān)系的對稱鄰接矩陣A：

其中，aij表示構(gòu)件i與構(gòu)件j之間存在數(shù)據(jù)收發(fā)關(guān)系，如果它們被部署到不同的CPU之上，則需要在兩個CPU之間建立一條RapidIO通信鏈路。后面可通過鄰接矩陣A，對構(gòu)件進行輔助搜索。

當構(gòu)件部署到CPU單元后，以CPU為頂點，CPU之間的RapidIO通信鏈路為邊，便得到一張m個頂點的無向圖G=(B, E)。要求圖的所有頂點的“度”不大于數(shù)值c(c∈N*)，即每個CPU所建立的RapidIO通道數(shù)目不大于c。

基于以上符號約定，將BPPR裝箱問題用線性規(guī)劃的方式描述如下：

其中，dk表示第k個CPU（頂點）的度，變量x，y是兩個二叉決策模型，其含義分別是：

可見，BPPR裝箱問題是一個雙目標優(yōu)化問題，目標函數(shù)(1)是為了使所使用的CPU數(shù)量收斂到最小，目標函數(shù)(2)的目標是使所需要創(chuàng)建的RapidIO通道數(shù)量最小。約束公式(3)保證了單個構(gòu)件被且僅被分配到一個CPU上。約束公式(4)保證了CPU資源能夠滿足其加載的所有構(gòu)件的計算資源需求。約束公式(6)確保不會超過單個CPU的RapidIO通道限制。本文給出的BPPR模型為一維裝箱問題，實際上可以根據(jù)需要擴展到高維度裝箱問題，其原理相同。

2 BPPR裝箱問題求解

本文給出的BPPR裝箱問題求解方法，其特點是一種變權(quán)綜合目標函數(shù)求解算法，該算法包括兩個階段的計算，用以求解復雜的BPPR多目標優(yōu)化問題。算法結(jié)合了廣度優(yōu)先搜索技術(shù)以及可變權(quán)重的排序算法，稱為VWSOF（Variable Weight Synthesizing Objective Function）算法。

本文所設(shè)計的VWSOF算法將問題的求解分解為兩個階段。第一階段，排序。通過可變組合系數(shù)法，依據(jù)物品的權(quán)重對構(gòu)件進行降序排序；第二階段，改進的FFD搜索算法，對給定的構(gòu)件序列，從降序序列中取出第一個未裝箱的物品，并采用廣度優(yōu)先搜索算法從隊列中依次取出未分配物品，求解其最優(yōu)裝箱策略。循環(huán)迭代上述兩個階段的計算過程，直到滿足收斂條件或達到預先設(shè)定的迭代次數(shù)。

VWSOF也是一種近似算法，算法為迭代求解過程，通過Niter次迭代后，得到一個近似最優(yōu)的裝箱策略，最后從若干有效解中選出最優(yōu)的一個。VWSOF算法的主要流程如下：

第一步：參數(shù)初始化。根據(jù)BPPR裝箱問題的描述，初始化箱子和物品的參數(shù)，以及約束圖的相關(guān)參數(shù)。

第二步：采用可變組合系數(shù)法，為所有物品計算權(quán)重。變權(quán)目標函數(shù)定義如下：

第三步：根據(jù)最新的物品權(quán)重，對物品進行降序排列。

第四步：選擇一個待裝箱的物品。從排序好的物品序列中第一個尚未被裝箱的物品開始，以鄰接矩陣A給出的物品間的連接關(guān)系為路徑，采用深度搜索算法BFS（Breadth First Search）搜索出下一個待裝箱的物品。

第五步：采用經(jīng)典FFD算法對物品進行裝箱。在對物品進行裝箱求解時，出判斷物品總體積是否超過箱子容積外，還需要同時滿足公式(3)、(4)、(5)、(6)的約束條件。

第六步：重復執(zhí)行步驟（四）、步驟（五），知道所有物品裝箱完成，并將裝箱結(jié)果記錄到。若裝箱過程中有物品無法找到能夠滿足所有裝箱和圖約束條件的箱子來裝載，則返回步驟（二）。

第七步：重復執(zhí)行步驟（二）到步驟（六）的過程，直到達到迭代次數(shù)。

第八步：選擇近似最優(yōu)的裝箱策略。本文所設(shè)計的VWSOF算法對于多目標函數(shù)最優(yōu)化問題最佳方案的判定方法是（算法1中的步驟6），根據(jù)ListOfSolution中各備選方案所對應的無向圖G= (B,E)的頂點數(shù)量m和邊的數(shù)量兩個評價指標進行對比。具體方法是，采用熵權(quán)法根據(jù)每個方案si的兩個指標mi和邊的數(shù)量的值對指標進行賦權(quán)，進而實現(xiàn)對比。對于待評價ListOfSolution中的u個裝箱方案，和v= 2個評價指標，形成原始數(shù)據(jù)矩陣R= (rij)u×v：

其中，rij表示第j個指標下第i個待評價方案的評價值。則，本文的基于熵權(quán)法的最佳方案的判定方法具體實現(xiàn)步驟如下：

（1）計算第j個指標下第i個項目的指標值的比重pij：

（2）計算第j個指標的熵值ej：

（3）計算第j個指標的熵權(quán)：

至此，得到兩個評價指標的綜合權(quán)數(shù)，對每個方案si進行加權(quán)評價，選出箱子和通道資源消耗最小的一組裝箱方案為問題的最佳方案。

3 實驗驗證

對VWSOF算法進行實驗驗證，設(shè)置主要的圖約束條件如下：

其中，頂點最大入度為4，頂點最大出度為8，單個箱子的最大容量為1，單個物品權(quán)重取值為 (0,0.6]之間的隨機數(shù)。動態(tài)生成一定數(shù)量的物品，分別采用BFD和VWSOF算法進行裝箱，得到實驗結(jié)果如表1所示。

表1 本文VWSOF算法核心流程

如表1所示，傳統(tǒng)BFD算法由于在裝箱過程中只根據(jù)物品重量和箱子容量進行裝箱，因此很難滿足圖的邊約束條件。而本文VWSOF算法，通常可以計算出滿足圖約束條件的裝箱解。由于VWSOF算法相比BFD算法多計算了邊約束條件，因此所使用的箱子數(shù)量通常比后者多。另外，本文VWSOF算法在某些情況下也無法得到滿足約束條件的裝箱解，但是隨著迭代次數(shù)的增大，得到解的概率增大。

本文給出一種基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成方法，滿足基于RapidIO高速總線的嵌入式信息處理設(shè)備下，對于大量具有復雜信息交互關(guān)系的服務構(gòu)件的快速部署策略生成，并能夠充分滿足設(shè)備計算資源、RapidIO高速數(shù)據(jù)總線資源的合理利用與分配。論文貢獻主要在于：

（1）將基于RapidIO高速數(shù)據(jù)總線的嵌入式設(shè)備下構(gòu)件的調(diào)度問題抽象為一種全新的基于圖約束的裝箱問題BPPR，是一種多目標函數(shù)優(yōu)化問題，并給出問題的形式化表示。

（2）給出所設(shè)計的BPPR問題的近似求解方法，一種變權(quán)綜合目標函數(shù)求解算法，將復雜的多目標函數(shù)最優(yōu)化問題分解為可變權(quán)重排序和基于廣度搜索BFS和FFD裝箱算法相結(jié)合的兩個計算階段，并給出基于熵權(quán)法的多指標裝箱方案對比方法。

與現(xiàn)有構(gòu)件調(diào)度策略相比，本文給出的構(gòu)件調(diào)度策略生成算法既保證了構(gòu)件調(diào)度策略計算的高效性和準確性，同時保證了適當?shù)撵`活性和擴展性，可以推廣到其他類似設(shè)備的構(gòu)件調(diào)度問題的解決。