一種構件調度策略生成新方法

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

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

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

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

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

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

結合嵌入式信息處理設備中的構件調度問題，將BPPR裝箱問題可描述如下：

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

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

給定一組待部署的構件，建立構件間通信關系的對稱鄰接矩陣A：

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

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

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

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

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

2 BPPR裝箱問題求解

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

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

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

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

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

第三步：根據最新的物品權重，對物品進行降序排列。

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

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

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

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

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

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

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

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

（3）計算第j個指標的熵權：

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

3 實驗驗證

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

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

表1 本文VWSOF算法核心流程

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

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

（1）將基于RapidIO高速數據總線的嵌入式設備下構件的調度問題抽象為一種全新的基于圖約束的裝箱問題BPPR，是一種多目標函數優化問題，并給出問題的形式化表示。

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

與現有構件調度策略相比，本文給出的構件調度策略生成算法既保證了構件調度策略計算的高效性和準確性，同時保證了適當的靈活性和擴展性，可以推廣到其他類似設備的構件調度問題的解決。