1 数字电路测试的神经网络优化模型
把数字电路中的每个节点(信号线)xi用一个神经元i来表示,节点的值是神经元的激活值,记为Vi,V,取0或10根据组合电路测试产生的特点,选用Hopfield神经网络作为电路建模的基础,用网络的能量函数来表征电路的逻辑特性。称符合基本门电路功能函数的取值组合为门的一个相容状态,其他不符合功能函数的取值组合为门的非相容状态。对于门电路的一个相容状态,可选择能量函数E,使此时E的值为某一个非负常数D(例如D=0),而对于所有非相容状态,使E的值大于D。可以证明二输入基本门电路AND、OR等都存在满足这种条件的能量函数,例如对输入为a、b,输出为c的AND门和OR门,其能量函数的一种形式分别为:E=-4c(a+b)+2ab+6c,E=-4c(a+b)+2ab+2a+2b+2c。对电路中的多故障生成测试,为操作方便需构造被测电路的约束电路。约束电路由故障电路(已注入故障),无故障电路和一个接口电路构成。对有k个主输出端的电路,接口电路由k个二输入的XOR门和一个具有k个输入的OR门组成,并且这个OR门的输出为1。这样的限制是保证当约束电路的输入为故障的测试时,被测电路的故障输出与无故障输出不同。被测电路对某一多故障存在测试的充要条件是:在故障点处取与正常电路相反的值,且满足相应逻辑门的真值,使约束电路对应神经网络的能量函数值为0。这样求多故障的测试就归结为计算约束电路的能量函数E的最小值点。
2 测试生成方法及并行实现
用遗传算法(GA)求解约束电路的神经网络能量函数的最小值点,仍设约束电路对应网络的能量函数为E(x),x=(x1,x2,…,xm)T,Xi只取0或1,D=[0,1]m,求故障的测试,即是求解E(x)在D上的最小值点。利用GA的特性设计如下的算法1以用于计算E(x)的最小值点。设种群规模(个体数目)为N,每一个体用位串X=(X1,X2,...,Xm)表示,第t代种群记为Pt。
算法1：①置t=0;随机产生一个由N个位串 (i=1,2,...,N)组成的初始种群P0②计算种群Ps中每一个体对应的能量函数值Ei和适值fi,H=(E1+E2+...+En,fi=1-Ei/H;③计算每一个体的选择率pi,F=(f1+f2+...+fN),Pi=fi/F;进行N次随机试验,从当前种群中选择N对个体;④从第③步选出的个体中随机选择交配对象,随机选择交叉点,产生新的N个个体。交叉的方法为:如果选出的一对个体为A、B随机选择二交叉点,将A、B依次分成A1、A2、A3和B1、B2、B3三部分,则新的个体由A1、B2、A3三部分构成;⑤按变异率Pm对种群中的个体进行变异;⑥在当前种群中随机选出一个个体,将其从种群中去除,把上一代中性能最好的一个个体增加到当前种群中;⑦置t=t+1返回第②步,直至求出E(x)的最小值点或算法的计算时间超过了一预先确定的上限。
为使种群Pt中的个体能较快地收敛到E(x)的最小值点,在算法1的具体实现时,还使用了如下措施:算法第一步中初始种群的选择是任意的,但由于电路测试生成的特殊性,对具体的被测电路,根据它所含基本门的种类和电路的结构特征,通过分析(例如依据故障传播和通路敏化的条件)能找到一个性能较优的初始种群。
下面主要研究如上电路测试的神经网络方法在MIME(多指令流多数据流)并行计算机上的实现。对测试生成方法进行并行化时需要把处理过程分成可并行完成的子任务，这包括对网络能量函数E的处理，以及求E的最小值点两部分。设MIMD系统中有S台处理机，命名为Pi（1≤i≤S）。由于与约束电路相对应的网络能量函数E是由组成它的各基本门的能量函数相加，因此对各基本门的能量函数EAND,EOR,ENAND等的计算量进行分析，同时统计被测电路中基本门的个数，可以在处理机Pi（1≤i≤S）中自动建立起函娄E的划分，记处理机Pi中所处理的部分函数为Ei。对Pi中的Ei，它们的计算量可能略有不同，设其计算量大小顺序为E1≤E2≤...≤Es。如果由每一处理机各自对个体进行遗传操作，去找到性能最优的个体，这样的测试生成过程为异步算法。下面的算法2给出了只生成一个多故障对应测试的这一实现方案。
算法2:初始化:给每一处理机Pi(1≤i≤S)注入故障信号线名称及故障类型,在每一处理机Pi中建立约束电路对应的能量函数E;置遗传最大次数Nmax。测试产生:①处理机P1随机生成一个初始种群,把它尽可能地均分成S组Xi(1≤i≤S)；②P1将Xi传送至处理机Pi(i=2,3,...,S);③处理机Pi对组Xi中的个体进行选择、交叉、变异等遗传操作F④如果Pi(1≤i≤S)中有一新个体使能量函数E达到最小值零,则该个体为对应故障的测试,转第⑥步;否则转第⑤步;⑤处理机pi判断遗传次数是否小于Nmax,若成立则按预先确定的交换原则进行组之间个体的交换,形成新的组,转第③步;若有一台处理机中的遗传次数大于Nmax,则输出不能对故障产生测试的信息,转第⑥步;⑥结束。
算法中如果组Xi中有ti个个体,则种群中个体,总数为(t1+t2+...+ts)。组Xi之间引入个体的交换,目的是为防止处理机Pi中个体的提前收敛即早熟问题,交换的原则为:根据个体的适值大小,把Xi中适值最大的个体与Xj(i≠j)中适值最小的个体相交换,或将组Xi中的个体排成有序的列、方阵等,规则地交换不同组Xi中对应位置上的个体。
在PC586计算机上模拟三台处理机,用算法2求ISCAS'85中电路C17的一个测试集。初始化时,在每一处理机Pi(i=1,2,3)中建立约束电路的神经网络能量函数。取遗传最大次数Nmax=500次,种群规模N=21,变异率Pm=0.001,两个体间的交叉方式采用二点交叉。根据C17电路的特点,初始种群中选定(1,1,1,1,..,1),(1,0,1,0,...,1),(0,1,0,1,...,0)等三个个体,其他个体随机产生。组Xi之间个体的交换规则采用互换组Xi与Xj中分别具有最小,最大适值的个体。产生电路的测试集时,将算法2的计算时间与串行算法1比较,获得的加速为Sp～2.63。这里影响加速的因素除了算法本身之外,还与每一台处理机上使用的遗传操作有关,算法2中每一处理机使用相同的进化方式,实验结果表明,若对每个组Xi采用不同的进化方式则会加快收敛速度,提高算法的加速,这在一定程度上类似于多子群体竞争进化。 |
