海军装备部装备项目管理中心 林丽娜 胡子颖

本文给出一种基于图约束装箱算法的构件调度策略生成算法，将构件动态部署和调度策略的生成描述成新的装箱问题。实验表明，本文给出的基于图约束装箱算法的构件调度策略生成算法，能够较好地解决大规模构件的动态部署问题。

现有信息系统软件服务构件的部署和调度，通常采用两种简化的策略：基于预案的方法、人工调度方法。而对于抽象问题而言，构件部署问题属于典型的装箱问题，是复杂的组合最优化问题。从计算复杂性来讲，装箱问题是一个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装箱算法相结合的两个计算阶段，并给出基于熵权法的多指标装箱方案对比方法。

与现有构件调度策略相比，本文给出的构件调度策略生成算法既保证了构件调度策略计算的高效性和准确性，同时保证了适当的灵活性和扩展性，可以推广到其他类似设备的构件调度问题的解决。