基于多目标差分进化的测试封装扫描链设计

朱爱军，李　智，朱望纯，许川佩

(1．桂林电子科技大学电子工程与自动化学院，广西桂林　541004；2．西安电子科技大学机电工程学院，陕西西安　710071)

0　引言

差分进化算法由R．Storn[1]在1997年提出的，由于其原理简明，控制参数较少，使用方便，因此在各个领域得到了广泛的应用。封装扫描链的优化设计，经典的方法是IYENGAR V提出的BFD(Best Fit Decreasing)方法[2]，虽然该方法快速简捷，但是它只有局部优化的能力，并且它是针对二维SoC，并没有考虑TSV的使用。文献[3]提出了MVA(Mean Value Approximation)方法来改善该方法；文献[4]提出了MVAR(Mean-Value Allowance Residue)方法，但是余量的选择针对不同的IP核变化较大；文献[5]提出了BBO方法，不过复杂度也相应提高了。以上几种方法都是针对二维封装扫描链设计的，且没有对测试时间与使用TSV资源使用之间的平衡进行考虑。

随着近年来3D(Three-Dimension)集成电路出现，以及基于嵌入式IP核的设计越来越有可能变成3D集成电路的设计风格。3D 集成电路多层芯片间采用硅直通(Through Silicon Vias，TSV)技术，采用垂直的连线方式代替早期的边缘走线方式，使得3D 集成电路的内部连线大大缩短，从而降低了传输功耗和传输延时，进一步加大了集成芯片的封装密度。因此迫切需要研究三维封装扫描链设计优化问题。

文中采用群体智能的多目标差分进化方法，对三维封装扫描链的设计进行优化。

1　差分进化算法

差分进化算法采用遗传算法类似的形式[7]，原理也相似，它包括交叉，选择和变异。标准遗传算法中的选择策略一般采用轮盘赌，而差分进化算法算法中采用锦标赛选择策略；对于交叉操作来说，差分进化算法大体上和遗传算法类似，但对于变异操作来说，差分进化算法采用了完全不同的策略：利用两个不同个体之间的差分向量进行缩放，从而实现对个体的扰动变异，这可以弥补遗传算法中变异方式的缺点。

一般来说，优化问题分为最大化和最小化问题两类，而最大化问题可以转化为最小化问题。不失一般性，这里只考虑最小化问题：

minf(x1，x2，x3，…，xd)

(1)

差分进化算法一般从一个初始化的种群开始，经过变异操作、交叉操作和选择操作完成当前代的操作，直到最大迭代数进化才结束，得到最优解，以下详细介绍各个部分：

(1)初始种群的获得：一般来说，进化计算中初始种群是通过随机获得，差分进化也不例外。初始种群

R={X1，X2，…，Xk，…，XNP}

则：

(2)

(2)变异操作的实现：在大多数的进化算法中，一般采用随机化产生一个可行域中的一个个体来实现变异操作；而在差分进化算法中采用差分策略产生个体的变异。在标准的差分策略中，首先随机选择3个不相同的个体，将其中2个个体的向量差采取缩放操作后与第3个个体进行向量合成，如下

Vi(g+1)=Xr1(g)+F·[Xr2(g)-Xr3(g)]

r1≠r2≠r3≠i

(3)

该差分策略也称为DE/rand/1/bin，它是目前应用最广的差分策略之一，因为其在保持群体多样性方面有较强的优势

(3)交叉操作的实现：对于第g代种群{X1(g)，X2(g)，…，Xk(g)，…，XNP(g)}和它的变异体Vi(g+1)进行个体之间的交叉，具体如下：

(4)

式中：CR表示交叉概率；jrand为1到d之间产生的随机整数。

(4)选择操作的实现：差分进化采用贪婪算法的策略对下一代种群的个体进行选择，即交叉操作后的个体如果比原来的个体更好，则选取交叉操作后的个体，否则保持原来的个体不变

(5)

(5)非可行域解的操作：在差分进化过程中，为了保证解的有效性，必须判断每个个体的每一个基因是否在规定的范围内。如果当前个体存在某个基因不在可行域内，则用类似产生初始种群个体的方法，随机产生一个新个体来代替该个体。

3　基于多目标差分进化算法的封装扫描链设计

多目标优化问题一般有2个以上的目标函数，通常有最大化和最小化问题两种，文中为最小化问题。多目标差分是在单目标差分的基础上改变而成，主要区别在选择操作上有所不同：单目标差分中交叉操作后的个体如果比原来的个体更好，则选取交叉操作后的个体，否则保持原来的个体不变；而多目标差分中交叉操作后的个体Pateto 支配原来的个体，则选取交叉操作后的个体，否则保持原来的个体不变。Pateto 支配定义如下：

定义1：(Pateto 支配)。一个可行解xsPateto支配另一个可行解xt，即xs

(1)在全体目标函数中，可行解xs不比可行解xt差，即对于任意的整数i，i∈[1，k]，fi(xs)≤fi(xt)，其中k为目标函数的个数；

(2)在全体目标函数中，至少存在一个目标函数，使得可行解xs严格比可行解xt好，即：∃整数i∈[1，k]，fi(xs)

3．1算法描述

基于多目标差分进化的封装扫描链设计算法描述：

Step(1)：根据IP核的内部扫描链条数n确定解空间的维数d，根据需要设计的封装扫描链的条数确定w的值，设置缩放因子F的值，设置交叉概率Pc的值，设置种群规模NP的值，设置最大迭代代数MaxG的值。

Step(2)：在可行域内随机生成一种群规模为NP的父初始种群，利用式(6)和式(7)，计算初始种群中每一个个体的目标函数值。

Step(3)：根据利用公式(3)产生变异体种群，其种群规模为NP.

Step(4)：对变异体种群中每一个个体的每一个基因进行边界检测，如果小于1则将其值修改为1，如果大于w，则将其值修改为w.

Step(5)：对NP个个体的每一个基因，产生随机数rand(0，1)，如果rand(0，1)大于交叉概率Pc，则子种群当前个体的该基因值选取父种群相应个体对应的基因值，否则子种群当前个体的该基因值选取变异种群相应个体对应的基因值。

Step(6)：根据式(6)和式(7)计算子种群NP个个体的目标函数值。

Step(7)：对NP个父种群个体，如果子种群的当前个体Pateto 支配父种群相应个体，则用子种群的当前个体代替父种群相应个体，否则保持不变。

Step(8)：由Step(7)得到新一代的种群：父种群，根据式(6)和式(7)计算父种群NP个个体的目标函数值。

Step(9)：迭代代数到达MaxG否，没有达到则转Step(3)。

Step(10)：将父种群NP个个体按照成本函数值非支配排序，得到Pateto最优解。

3．2整数向量编码

定义2：每一个个体定义为一个可行解，即

式中：i=1，2，…NP；d为解空间的维数；NP为群体规模。

文中采用整数向量编码方案，具体见文献[6]

3．3目标函数……

定义3：ObjectiveF1目标函数1，使得封装扫描链中的最长扫描链最短，从而减少测试时间，定义为：

(6)

式中：L(Pi)表示第i条封装扫描链的长度；L(Si)表示第j条内部扫描链的长度；k∈[1，NP]。

目标函数1的值越小，表示适应度越大，该待选可行解越好。

定义4：ObjectiveF2目标函数2，使得总的使用TSV数量最少，定义为：

(7)

式中，NTSVi表示第i条封装扫描链使用TSV的数目；k∈[1，NP]；i∈[1，w]。

NTSVi的计算如式(8)：

NTSVi=2×Max1≤j≤x(Layij)

(8)

式中：Layij为第i条封装扫描中第j条内部扫描链所在的层数；x为第i条封装扫描中内部扫描链的条数，封装扫描链的起始处都是最底层，假设最底层的所在层为第0层。

4　试验结果

为了比较各种方法的性能，验证该方法的有效性，文中采用国际标准ITC’02 benchmarks[5]。由于大多数的IP核内部扫描链的长度都比较均衡，因此难以比较那种方法更好。为了证明该方法的有效性，文中在ITC’02 benchmarks中选取两个不平衡IP核 (p34392 IP Module 2 和p22810 IP Module 5)。由于ITC’02 benchmarks中不包含内部扫描链所处的层信息，因此文中假设IP核的各个内部扫描链随机分布在三层上，最底层为第0层，依次往上递增，每条封装扫描链的起始处都在第0层。

多目标差分优化系统参数设置：群体规模NP为 50；最大迭代代数MaxG为500；缩放因子F为0．5；交叉概率Pc为0．2；根据封装扫描链的条数设置w；根据IP核中相应的内部扫描链的条数设置解空间的维数d；w为封装扫描链的条数，表1当中，第1列M表示所采用的多目标方法，为了验证该方法MODE (Muti-Objective Differential Evolution )的有效性，文中还采用了多目标算法中广泛使用的NSGAII(Nondominated Sorting Genetic Algorithm II )[9]方法进行对比。NSGAII的使用参数为：最大迭代代数为500，每一代的群体规模为50，子代的交叉概率为0．9。第二列为各种方法获得的Pateto 最优解，第三列和第四列为各种方法获得的Pateto前沿，其中L表示最长封装扫描链的长度，Ntsv表示使用的TSV数目。为了便于对比，在所有的方法中，使得相同内部扫描链所处的层均相同，以下实验参数都采用相同的设置。

从表1，可得当使用相同的TSV个数时，MODE方法能够得到更短的最长封装扫描链。

从表2，同样可得当使用相同的TSV个数时，MODE方法能够得到更短的最长封装扫描链。

……为了比较当w取不同值的时候，两种方法的整体优劣，分别取w=3，…，16，同样得到使用相同的TSV个数时MODE方法能够得到更短的最长封装扫描链。

表1p22810IP核Module5实验结果，w=2

表2　p34392 IP核 Module 2 实验结果，w=2

5　结论

文中提出了一种基于多目标差分进化的方法，用来缩短最长封装扫描链的长度和减少使用TSV数目，从而缩短IP核的测试时间和减少使用TSV使用资源。实验结果表明该方法总体上能够获得更短的封装扫描链和更少的TSV资源。

参考文献：

[1]STORN R，PRICE K.Differential Evolution—A Simple and Efficient Heuristic for Global optimization over Continuous Spaces．Journal of Global ptimization，1997，11 (4 )：341-359．

[2]IYENGAR V，CHAKRABARTY K，MARINISSEN E J．Test Wrapper and test access mechanism co-optimization for system-on-chip．Journal of Electronic testing：Theory and Application，2002，18(2)：213-230．

[3]NIU D H，WANG H，YANG S Y，et al．Re-optimization algorithm for SoC Wrapper-chain balance using mean-value approximation．Tsinghua Science and Technology，2007，12( S1) ：61-66．

[4]俞洋，陈叶富，彭宇．基于平均值余量的Wrapper扫描链平衡算法．仪器仪表学报，2011，32 (10)：2290-2296．

[5]MARINISSEN E J，IYENGAR V，CHAKRABARTY K．A set of benchmarks for modular testing of SOCs．International Test Conference，2002：519-528．

[6]朱爱军，李智，许川佩，等．基于Biogeography的SoC测试Wrapper扫描链设计算法．仪器仪表学报，2012，33(12)：2774-2780．

[7]杨启文，蔡亮，薛云灿．差分进化算法综述．模式识别与人工智能.2008，21(4)：506-513．

[8]潘明，曾春华．基于IP核复用技术的CAN总线SOPC设计．仪表技术与传感器，2011(5)：55-58

[9]DEB K，PRATAP A，AGARWAL S，et al．A fast and elitist multi-objective genetic algorithm NSGA-II．IEEE Transactions on Evolutionary Computation，2002，6(2)：182-197．