信息处理单元测试系统并行测试技术研究

周 强，王钰萌，王廷凯

(北京航空航天大学 自动化科学与电气工程学院，北京 100191)

0 引言

信息处理单元是飞控系统的重要组成部分，其主要由计算机板、译码板、遥测板以及总线信号板等部分组成。为了满足质量控制标准，所需验证的测试项目众多，同时每个测试项也需要经过长达数百次的重复测试。常规的测试系统通常采用串行测试的方式，整个测试流程需要的时间较长，测试效率较低。因此，并行测试技术是未来的发展方向。

对于并行测试技术，业内已有部分研究。20世纪80年代，并行处理技术在工业测试领域里开始使用，并逐渐发展成为一种新兴的测试技术——并行测试[1]。并行测试技术将测试流程中的任务重新规划，使占用资源不冲突的任务同时执行，这样能节省大量的测试时间[2]。所以，并行测试技术具有测试速率高、资源利用充分的特点，相较于串行测试，有着巨大优势。目前，美国NI公司在将并行测试技术应用于自动化测试领域最为成功，其开发的智能化测试系统软件平台，将整个测试流程分解为多个子任务，并利用任务调度算法优化求解最优策略[3]。平台中的用户界面简单易使用，用户仅需在人机交互界面中输入待测的测试项和所需时间，测试软件就能快速地生成相应的调度序列，然后将测试调度策略反馈给用户并执行。

根据信息处理单元测试系统实际的测试流程和所需资源的使用情况，将并行测试技术引入到系统中，重新对相互独立的测试任务进行并行化分析。提出改进的自适应遗传算法，即IAGA算法，基于IAGA算法进行并行测试任务调度算法的设计，并搭建了算法的仿真实验环境，联合本测试系统的任务调度模型得出实验结果并进行详细分析，接着与其他算法进行对比，验证IAGA算法的可行性和优越性，并以算法为核心实现了系统中的并行测试模块。

1 信息处理单元测试系统总体设计

信息处理单元测试系统是一套以PXIe总线工控计算机为核心的自动测试系统，其具体实现的测试功能包括：①与载机通信测试(1553B、ARINC429)、②一次性指令测试、③遥测功能测试、④RS422总线通道测试、⑤加速度/角速度脉冲测试[4]。

按照“自顶向下”模块化的设计原则信息处理单元测试系统由测控系统、供电单元、接口单元组成，如图1所示。

1.1 测试系统软件实现

信息处理单元测试系统软件基于Windows 7操作系统，在VS2010平台下采用C++语言和MFC框架进行开发。综合测试软件主要由单项任务测试、板卡自检、并行测试模块、自动测试四个部分组成，综合测试软件界面如图2所示。

图2 综合软件界面图

综合测试软件采用单文档视图结构，利用界面分割技术，实现模块化测试界面的设计，系统的所有测试功能均嵌入在测试界面中，由用户进行选择和配置。板卡影响着测控系统的质量与性能，在用户使用时进行板卡测试十分必要。并且，在自动测试之前，应先设置并行测试模块，不同的状态会有不同的配置选，根据测试的具体情况来输入相应单项测试任务的时间，从而生成并行执行任务序列。

1.2 并行测试模块的实现方案

并行测试模块是信息处理单元测试系统中的关键部分，对系统的测试效率有着重要的影响[5-6]。

图3为并行测试模块实现的流程，本文首先对整个系统的测试流程进行分析：飞控产品由飞控计算机部件、译码控制部件、惯测接口部件、总线接口部件四个部分组成，并深入研究这四个部分所涉及的测试任务之间的关系。接下来根据任务所占用的资源情况和任务之间的时序要求建立并行测试的任务调度模型，以得到任务资源矩阵、任务之间的时序约束矩阵等。然后利用改进的自适应遗传算法求解任务调度模型，得到所有可能的并行序列，并通过全局搜索找出最优并行序列，最后将算法嵌入到测试软件中以提供给用户使用。

图3 并行测试实现流程图

2 并行测试模块的任务调度模型搭建

2.1 任务调度数学描述

并行测试任务调度问题可以描述为：

测试流程中的任务的集合为S={s1，s2，s3，…，sm}，测试所需的仪器资源集合为W={w1，w2，w3，…，wn}，任务相应的占用时长为T={t1，t2，t3，…，tm}；

令任务资源矩阵为SW，假如任务Sj需要其中的资源Wi，则SW(j，i)=1；否则SW(j，i)=0；

令资源相关矩阵为TW，WA是任务SA的资源集合，WB是任务SB的资源集合，若WA∩WB=≠Ø，则称资源集合WA和资源集合WB相关，TW(A，B)=1，相当于任务SA与任务SB所需的资源相冲突，不能同时测试；否则，称之为资源不相关，TW(A，B)=0；

令时序约束矩阵为TS，假如任务SA的优先级(执行顺序)高于任务SB，SA>SB，则TS(A，B)=1；否则，TS(A，B)=0；

总而言之，并行测试任务调度的数学模型可以概括为：求解任务调度序列矩阵TP，找出总测试时长最短的TP，以获得最优的测试效率[7-8]。相当的函数可以表示为TF=min{sum_time(TP)}，其中sum_time(TP)表示任务调度序列矩阵TP执行完成时所需的总时长，此函数的约束条件为：

1)若sj>si，则N(TP，sj)>N(TP，si)；

2)若N(TP，sj)=N(TP，si)，则Wj∩Wi=Ø。

约束条件表达式中：N(TP，sk)表示任务sk在任务调度序列矩阵TP中的步骤号，1)句表示任务优先级高的测试任务先测试，2)句表示若两个测试任务的步骤号相同，则这两个测试任务没有资源冲突。

2.2 测试流程分析及模型建立

信息处理单元测试系统中的并行测试模块主要由测试任务集、仪器资源以及软件系统三个方面组成。并行测试模块的实现，需要将复杂的测试流程分解为满足时序约束的测试任务集，将被测产品所需的测试通过功能拆分的方式分解为若干项测试任务。信息处理单元测试系统共有15项测试任务，依次编号为s1～s15。根据测试系统的实际测试情况，记录飞控组件中每个测试任务所占用的板卡资源，接着分别记录每个测试任务在常温条件下单独测试时所需要的平均时间。

表1 常温条件下测试任务所占用的板卡资源与测试时间表

根据并行测试的任务调度模型可知，资源任务集矩阵为：

根据测试流程中每个测试任务的具体情况可得，每个部分的测试没有必要的时序顺序，但部分内部的测试任务之间有一些时序要求，具体任务之间的时序约束如下：

1)在测试开始前，应首先进行自检测试，即s1优先于s2、s3、s4、s5、s6、s7、s8、s9、s10、s11、s12、s13、s14、s15；

2)在对译码控制部件的测试中，s3优先于s4；

3)在对惯测接口部件的测试中，s8优先于s9、s10；

4)在对总线接口部件的测试中，s11优先于s12、s13、s14、s15。

那么根据任务调度模型可得时序约束矩阵为：

TS15×15=

资源任务矩阵表示每项测试任务所占用的资源数量，时序约束矩阵表示所有测试任务之间的执行先后顺序。因此，两个矩阵中包含某些任务可同时执行的所有信息，通过这些信息可以得出可行的并行序列以实现并行测试。首先，通过资源任务矩阵，提取所有可并行执行的任务集，然后，通过时序约束矩阵将不符合时序约束的任务集进行矫正，具体解决策略采用智能优化算法。

3 任务调度算法设计与并行实现

3.1 遗传算法改进

基本遗传算法收敛速度慢、局部搜索能力差以及容易陷入局部最优解，显然，在解决并行测试任务调度的问题时，需要对其进行改进[9-10]。因此本文提出一种改进的自适应遗传算法，即IAGA算法，包含排序分组以及改进的自适应变化的思想，以提高算法的收敛速度，增强算法跳出局部最优的能力[11]。

3.1.1 选择算子的改进

本文采用排序分组(sort-grouped model)选择方式[12]，基本思想是：根据种群中个体适应度值从大到小进行排序，然后将已排序的个体分为三组，通过比例再进行选择，具体实现过程如下：

1)根据个体适应度的大小，对个体进行降序排列。

2)将排序过的种群，按照比例分为：高适应度个体集合(占比1/8)、中适应度个体集合(占比6/8)，低适应度个体集合(占比1/8)。

3)将低适应度个体集合直接淘汰，不参与选择，高适应度个体集合按照之前的比例复制两份，中适应度个体集不变。

4)最后将新产生的种群直接全部选择，进入到下一代的遗传进化过程中。

采用这种排序分组的方式，可以将适应度过低的个体直接淘汰，不参与以后的进化过程，从而提升算法的收敛速度，并且通过选择多数适应度中等的个体继续进化，以保留种群的多样性，从而增加找到全局最优解的可能性。

3.1.2 变异算子的改进

对于传统遗传算法来说，变异的概率在进化的过程中是保持不变的，是一个小于1的常数值。这种通过变异产生的子代随机性强，会较早的出现“早熟”现象，陷入局部最优的“陷阱”，使得算法失去效力；在进化末期，高度“成熟”的个体依然很可能变异，这会降低算法的收敛的速度，使得进化变得漫无目的[13]。

本文采用一种在进化过程中变异概率跟随个体动态变化的方法，其基本思想是：当个体的适应度大于种群平均适应度时，应尽可能保存当前个体，相应地变异概率应变地很小；反之，个体的适应度越小，为了产生更好的子代，变异概率应变地越大[14-15]。

3.2 算法设计及具体流程

3.2.1 基本数学模型设计

将改进的自适应遗传算法应用于信息处理单元测试系统的并行测试模块中，需要设计一系列可供算法调用的数学模型，包括染色体编码、生成的执行序列矩阵与适应度函数，具体设计如下所示。

1)编码的定义：

将染色体设定为并行测试任务调度扩展矩阵，如公式所示，行号表示板卡资源序号，列号表示测试顺序，每一行代表着占用相应资源的任务集执行顺序，每一列代表着可同时执行的任务集。

(1)

其中：Chromn×k(ri，j)表示占用ri号板卡资源的任务号srij在第j步执行测试。如果任务集S中的某个任务当前被选中，则srij=sj(sj∈S)，否则，srij=0。

2)种群的生成：

首先，从任务集S中随机挑选一个任务，通过任务资源矩阵SW确定该任务所需的资源，再将所需资源对应的任务序号放置在染色体中。然后重复之前的步骤，继续选择未被占用资源的任务，直到该步骤执行的任务数量达到饱和，最后继续执行下一步骤的任务选择，直到所有的任务都被选择，具体流程如图4所示。

图4 生成并行序列流程图

图5 IAGA算法流程图

求取并行序列的算法伪代码如下：

whileS不为空

k←1;

forj←1 ton//循环找到第k步可并执行的序列

ifS不为空//随机选择剩余资源不冲突的任务 例如s1,s1占用资源w1,w4

Chrom(1,k)←1;

Chrom(4,k)←1;

delete(s1,S);//从任务集S中删除任务s1

k←k+1;//当第k步任务集达到饱和,继续下一步

3)适应度函数设计：

在遗传算法中，适应度函数的设计十分关键，它直接影响着算法的收敛速度以及算法找到全局最优解的能力。在并行测试领域，如何提升资源利用率和减少测试时间是算法研究的重点问题。因此，并行测试任务调度问题实质上是测试任务与测试资源之间的分配问题，本质上是一个NP-hard问题，是多目标组合优化问题。显然，减少总测试时间是第一优化目标，在测试时间最优时，提高资源利用率则是第二优化目标。除此之外，由于产生初始种群时，没有考虑到任务之间的时序性，以至于随机产生的个体有可能是无效解，所以在优化前两个因素之前，保证解的有效性是第一要务。因此，在设计适应度函数时应考虑时序、时间、资源这三方面因素，具体内容如下。

1)错误因子：

错误因子(Error Factor)体现着并行序列中时序的错乱程度，其表达如下：

(2)

2)速度比：

速度比(speed ratio)定义为串行测试的总时间与并行序列所需的总测试时间之比，速度比越大，所需测试时间越少。其数学表达式如下：

(3)

3)并行率：

(4)

式中，m表示总任务数，step表示总步数，其含义是在并行测试的过程中每步执行的任务总数的权重之和与所有任务的权重之比。

综上所述，结合以上三个因素的多目标适应度函数应设计为：

(5)

式中，σ表示时序权重系数，λ表示时间权重系数，这两个参数的大小取决于三个因子对并行测试的重要程度，通过实验分析可知，在进化的前期，E>10，S<2，故当σ取0.4，取0.5时，算法的效果比较好。

3.2.2 算法具体流程

基于改进的改进遗传算法求解并行测试任务调度的算法流程如下：

1)设定该算法的初始参数，包括算法最大的迭代次数、种群数量、交叉概率、变异的最大概率以及最小概率。

2)首先根据种群生成算法初始化种群，初始代数设定为1。

3)根据多目标适应度函数计算种群中每个个体的适应度大小。

4)基于排序分组的思想，从种群中选出目标个体作为下一代进化过程中的父代。

5)按照设定的交叉概率对被选择的父代个体进行交叉操作。

6)按照设定的变异的最大和最小概率计算出每个子代的变异概率，进行变异操作，并基于禁忌搜索的思想，选择产生的个体。

7)如果迭代次数大于设定值，终止操作；否则，迭代次数自增1，跳转到步骤3)，继续进行遗传操作。

8)算法结束，选择种群中的最优个体，也就是最优的任务调度序列。

4 算法仿真实验结果与分析

4.1 实验参数设定

选取本系统中的任务调度模型进行算法仿真验证。

4.1.1 仿真环境配置

仿真实验环境如表2所示。

表2 算法仿真环境配置

4.1.2 参数设置

经过大量的实验分析，算法的各个参数以表3的值时，算法的效果比较好，找到最优解的能力也比较强。

表3 算法初始参数设置

4.2 仿真结果及分析

4.2.1 适应度函数收敛曲线

图6代表函数的总体适应度与时间变化在迭代的过程中的变化情况。

横轴表示迭代次数，左侧纵轴表示种群总体的平均适应度值，以常数为单位；右侧纵轴表示在每一代种群中所有个体对应的任务调度矩阵所需的平均测试时间，以秒为单位。图中共有两条曲线，实线代表种群在迭代过程中适应度的变化，虚线代表种群在迭代过程中测试时间的变化。由图可知，适应度越高，时间越短，适应度与时间几乎同时变化，两者均在第15代开始不再变化，此时适应度的值为0.838，测试时间为79 s。由公式(4)可知，时间因素在适应度函数的权重占比非常高，除错误因子外，是第二重要的影响因素，图中的曲线变化正印证了这一点。

图7为函数的总体适应度与并行率变化在迭代的过程中的变化情况。

图7 适应度与并行率变化曲线

横轴表示迭代次数，左侧纵轴表示种群总体的平均适应度值，以常数为单位；右侧纵轴表示在每一代种群中所有个体对应的任务调度矩阵的并行率，以秒为单位。图中共有两条曲线，实线代表种群在迭代过程中适应度的变化，虚线代表种群在迭代过程中并行率的变化。由图可知，适应度的变化与并行率的变化并不同步，并行率高的时候，适应度并不一定高，当两者不再变化时，适应度为0.838，而并行率为0.088 8，并不是最高，可见两者的变化相关性较低。由公式(5)可知，并行率在适应度函数的权重占比是最小的，在同时满足错误因子和速度比的优化下，并行率才可能会变高。一定的并行率，即使不是最高，也依然符合优化思路，图中曲线正证明了这一点。

4.2.2 全局最优解的验证

为了验证最优解是否是全局最优，采用TaskScheduler-T 算法[16]。TaskScheduler-T 算法的基本思想是：随机生成可行的并行测试任务调度，然后枚举所有解得到最优解，它每次都能找到最优解，但相当费时[17]。

图8为在样本量为3 000的情况下采用TaskScheduler-T 算法所生成的调度序列对应时间曲线。

图8 3 000次随机生成的样本的测试时间曲线

所有样本中的测试时间集中在85～115秒之间，最大值为118秒，最小值为79秒。可见，在足够多的调度序列中，也未能找到比本论文中采用改进的自适应遗传算法所得到的更好的解。对于TaskScheduler-T 算法来说，只要样本量足够大，随机搜索的空间也就越大，也就能找出所有可行的解，故本算法所求取的解为全局最优解。

4.2.3 实验结果分析

(6)

其中：ts表示顺序测试的总测试时间，tp表示并行测试的总测试时间。相应的测试任务在测试资源上的分配的甘特图如图9所示。

图9 测试任务执行顺序图

图的横轴表示测试时间，以秒为单位；纵轴表示板卡资源序号，矩形中心表示具体的测试任务，矩形表示相应的执行的过程。它直观地展示了所有测试任务随时间的执行顺序，反映了在整个测试过程中测试任务与板卡资源的占用情况。

表4为顺序测试与并行测试在资源利用率上的比较图，其中计算资源利用率的公式为：

表4 顺序测试与并行测试资源利用率的比较

(7)

其中：twi为资源wi在测顺序测试或并行测试时工作的总时间，t表示顺序测试或并行测试的总测试时间。

由表4可以看出并行测试的资源利用率均比顺序测试的资源利用率高，平均利用率提高了24.27%。IAGA算法可以显著提高资源的利用率，从而节约了测试成本。

4.2.4 与其他算法对比

4.2.4.1 与基本遗传算法对比

在实验条件相同的情况下，设置基本遗传算法的变异概率为0.6，并且其他参数与IAGA算法相同，分别运用基本遗传算法与改进的自适应遗传算法(IAGA)求解任务调度。

由图10可以看出，基本遗传算法在38代左右才找到最优解，而IAGA算法在20代就找到了最优解。可见，IAGA算法的收敛速度以及搜索能力均比基本遗传算法好。

图10 基本遗传算法与IAGA算法对比图

4.2.4.2 与人工蜂群算法等算法对比

人工蜂群算法(artificial bee colony algorithm，简称ABC算法)是一种模拟蜂群行动准则的启发式搜索算法，具有收敛速度快、搜索效率高的特点。各工种的蜂群在搜索空间中进行局部寻优行为，找到问题中的可行解，并比较优劣，逐渐找到全局最优解[18-19]。由于人工蜂群算法与遗传算法同属于启发式搜索算法，理论上，人工蜂群算法的局部寻优能力和收敛速度要强于遗传算法，但全局搜索能力弱于遗传算法，所以采用人工蜂群算法来作比较实验，验证IAGA算法的搜索速度以及局部寻优能力[20-21]。

设置人工蜂群算法的采蜜蜂为40，跟随蜂为40，侦察蜂为24，迭代次数限定为100次。在实验条件相同的情况下，人工蜂群算法、基本遗传算法、TaskScheduler-T算法、IAGA算法均运行30次，实验结果如表5所示。

表5 不同算法仿真结果

由表可得出：TaskScheduler-T算法一般都能找到全局最优解，但搜索速度太慢，随机性太强。基本遗传算法总体效果均不如IAGA算法。在不考虑运行时间的情况下人工蜂群算法与IAGA算法的性能相当。通过比较人工蜂群算法的运行时间较长，因为人工蜂群算法在搜索最优解时，速度会逐渐减慢，后期寻优能力较弱。

综合来看，IAGA算法求解的效果最好，即IAGA算法是可行且有效的。可以说明，本算法采用排序分组的思想能使种群往更好的方向进化，采用自适应的变异概率和禁忌搜索手段，可以提高算法收敛速度以及增加种群的多样性，防止算法陷入局部最优。

4.3 并行测试模块实现

飞控产品要在不同的环境下多次测试，测试环境达到十多种，比如高低温测试、不同方向的轴振动测试等。在每个环境下的测试中，每个测试任务执行完成的时间由于受其影响也有所不同。因此，开发一款专门的软件界面提供给用户在不同环境下配置并行测试的执行流程是必要的。系统中的软件可以在不同环境下设置测试任务的时间常数，通过这些时间常数自动生成最佳调度序列，并嵌入自动测试模块中供用户使用。

该软件与信息处理单元测试系统软件界面保持一致性，依旧基于VS2010中MFC框架开发，而任务调度算法通过Matlab平台被编译为动态链接库，以提供给测试软件使用。

图11 并行测试模块界面

5 结束语

本文完成了新型信息处理单元测试系统的总体方案设计工作，采用模块化设计思想，将测试系统划分为测控系统、供电单元与接口单元。实现了对系统有着关键影响的并行测试模块，引入并行测试技术，从系统的实际测试环节入手，通过模型中的任务资源矩阵和任务之间的时序约束矩阵，得到测试系统所有可能的调度序列。为了解决普通遗传算法的收敛速度慢，容易陷入局部解的问题，对算法进行了改进，提出IAGA算法。使用IAGA算法进行了最优任务调度策略求取，成功得到了总测试时间最短、资源利用率最高的调度序列。在常温测试条件下，与串行测试策略相比，采取并行策略的测试系统的测试效率提高了43.57%。然后与其他算法对比，验证了IAGA算法的有效性和优越性。