专利名称：SoC测试中基于进化计算的扫描链平衡方法
技术领域：
本发明涉及系统级芯片SoC (System-on-Chip的英文首字符缩写)测试技术领域，具体为一种SoC测试中基于进化计算的扫描链平衡方法。
背景技术：
随着现代半导体制造工艺的发展与纳米技术的应用，大规模集成电路的集成度不断加大，系统级芯片SoC迅猛发展。为了减少SoC的上市时间，同时不降低系统的稳定性和可靠性，使得基于IP核复用的SoC设计逐渐成为主流风格设计。由于SoC集成度和规模的大幅度增加，带来了新的挑战和问题，即SoC测试时间急剧增加，导至SoC的测试费用飞速增长。目前，SoC测试问题已成为制约SoC发展的瓶颈问题。
IYENGAR V、CHAKRABARTY K 和 MARINISSEN E J 发表的论文 “Test Wrapper andtest access mechanism co-optimization for system-on-chip，，(文章中文译名 “SoC 测试的Wrapper和测试访问机制的联合优化”,发表于International Test Conference,USA,2001:1023-1032.)，将Wrapper/TAM及测试调度组合优化问题分成Pw、Paw和Ppaw三个子问题。从该划分不难发现，测试Wrapper的设计是几个子问题的基础。如果测试Wrapper的设计达不到最佳平衡解，那么其它两个子问题必然得不到最优解；而IP核模块的测试时间是由IP核中最长的扫描链决定，因此如何将测试Wrapper扫描链进行平衡优化设计将直接决定了测试的时间和成本。
IYENGAR V 等提出了 BFD (Best Fit Decrease)方法来解决测试 Wrapper 设计问题。BFD方法最早是用于解决装箱问题，虽然它有结构简单和执行效率高等优点，但该方法只有局部优化的能力。造成该缺点的根本原因是在BFD方法中，当把IP核内部扫描链依次加到Wrapper扫描链上时，只考虑当前每条扫描链的长度。
针对BH)方法只具备局部优化的缺点，NIU D H7WANG H，YANG S Y等人发表了期刊论文“Re-optimization algorithm for SoC ffrapper-chain balance using mean-valueapproximation” (中文译名为“采用近似平均值的SoC Wrapper扫描链平衡优化方法”,发表于 Tsinghua Science and Technology, 2007，12 (SI): 61-66)。此文引入了全局优化思想，提出了基于平均值的扫描链平衡设计方法MVA (Mean Value Approximation),用内部扫描链的平均值指导全局优化。但MVA方法也存在一定的问题，即它并不总是优先处理当前最长的内部扫描链。
YU Y, CHENG Y F, PENG Y 的期刊论文 “Wrapper scan chain balance algorithmbased on mean-value allowance”(中文译名为“基于平均值余量的Wrapper扫描链平衡方法”，发表于 Chinese Journal of Scientific Instrument, 2011，32 (10): 2290-2296)提出了一种MVAR(Mean Value Allowance Residue)方法,首先计算内部扫描链的平均值,然后在平均值的基础上添加一个恰当的余量，并以此来指导全局优化，该方法比基于平均值的扫描链平衡设计方法在缩短最长Wrapper扫描链方面有所改进，复杂度稍微有所提高。
申请号为CN201110162065.2的中国发明专利申请“利用差值进行二次分配的扫描链平衡方法”先将IP核内部各扫描链递减排列，找到最大的扫描链s (max)，将S (max)除以调整系数adj的长度作为基准长度Sb，最接近于Sb的扫描链设定为基准的扫描链S(adj);然后，将IP核内部各扫描链的长度与S(adj)的长度进行比较，大于S(adj)则设定为长扫描链S >，小于等于S(adj)则设定为短扫描链S彡，将所有长扫描链S >按照S(adj)的长度进行第一次分配；再计算出每一个长扫描链S >与基准的扫描链S(adj)的差值di’，将所有短扫描链3<与所有差值di’递减排序后，进行第二次分配。改进了基于平均值余量的方法。
以上所述的BFD、MVA、MVAR和采用差值二次分配的方法，思路均是让Wrapper扫描链尽量达到平衡，从而缩短最长Wrapper扫描链的长度，减少IP核的测试时间。但目前不少SoC的IP核内部各扫描链严重不均衡，用现有的方法很难进一步缩短最长Wrapper扫描链的长度，也就无法完成扫描链的平衡。发明内容
本发明的目的是设计一种SoC测试中基于进化计算的扫描链平衡方法，基于群体智能的进化计算，对IP核内部扫描链进行平衡设计，优化Wrapper扫描链，减小IP核最长Wrapper扫描链的长度,从而减少IP核的测试时间，降低SoC的测试成本。
本发明设计的SoC测试中基于进化计算的扫描链平衡方法，包括如下步骤:
步骤1、设置初始化参数
本发明中的术语定义如下:
个体:为一个待选解，是一个d维的整数向量。
种群:为由NP个个体组成的群体。
例如ITC’02Test benchmarks[16]中 d695.soc,它有 11 个模块(IP 核)，模块(IP核)6 中有 16 条内部扫描链(S1, S2,, S1J，其长度为{41，41，40，40，40，40，40，40，40，40，40，40，39，39，39，39}。如果将其分成两条Wrapper扫描链(w=2)，则待选解整数向量(即一个个体)为Z=(l，2，1,2, 1,2, 1,2, 1,2, 1,2, 1,2, 1，2)，表示将奇数系列内部扫描链连接构成第一条Wrapper扫描链,将偶数系列内部扫描链连接构成第二条Wrapper扫描链。
本步骤I设置的初始化参数如 下
根据待测试的SoC的IP核内部扫描链的条数设定整数向量的维数d ；
种群中的个体规模NP，如可设定为50，
最大规定代数MaxGen,如可设定为50,
最大变异概率mmax,如可设定为0.005,
根据当前封装扫描链分配的条数设定w的值。
最大迁入速率I,如可设定为I,
最大迁出速率E,如可设定为I。
步骤2、产生初始种群R和初始相反种群ROP
随机产生一个种群个体规模为NP的初始种群R，
R= (X1，X2，...，Xk,...，Xnp)，其中 Xk= (X1', X2k,...，Xpk,...，Xdk)，
Xpk e [1，w]，k e [I, NP]，P e [I, d]
上式中NP、d和w为步骤I所设值，k、p为整数；
根据公式Υ>1+ _ΧΛ i e [1，d]，产生一个初始相反种群R0P，
ROP= (Y1, Y2，…，Yk,...，Ynp)，k e [1，NP]。
步骤3、计算最终初始种群中所有个体的成本函数值，按照递增排序
分别计算初始种群和初始相反种群中所有个体的成本函数值，根据基于相反点的优化方法，从初始种群R中的任一个体和其初始相反种群ROP中对应的相反个体选择成本函数值较小者作为最终初始种群，即第O代种群的个体。计算第O代种群中所有个体的成本函数值,并且按照递增排序，代数G=O。
基于相反点的优化方法为:已知X为m维空间的一个点，以X为待选解，X= (X1, X2,…，Xm)。设Y= (Y1, Y2,…，Ym)是X= (X1, X2,…，Xm)的相反点，m表示空间维数，如果CF (Y) ( CF (X)，则用Y代替X点，否则，继续采用X进行进化计算；
成本函数为
权利要求
1.SoC测试中基于进化计算的扫描链平衡方法，包括如下步骤: 步骤1、设置初始化参数 根据待测试的SoC的IP核内部扫描链的条数设定整数向量的维数d， 种群中的个体规模NP， 最大规定代数MaxGen, 最大变异概率mmax， 根据当前封装扫描链分配的条数设定w的值， 最大迁入速率I， 最大迁出速率E ; 步骤2、产生初始种群R和初始相反种群ROP 随机产生一个种群个体规模为NP的初始种群R， R= (X1，X2，...，Xk,...，Xnp)，其中 Xk=(X), X2k,Xpk,...，Xdk)，Xpk e [l,w], k e [I, NP], p e [I, d] 上式中NP、d和w为步骤I 所设值，k、P为整数； 根据公式Υ^=1+ _ΧΛ i e [I, d]，产生一个初始相反种群R0P， ROP= (Y1, Y2，...，Yk,...，Ynp)，k e [I, NP]； 步骤3、计算最终初始种群中所有个体的成本函数值，按照递增排序分别计算初始种群和初始相反种群中所有个体的成本函数值，根据基于相反点的优化方法，从初始种群R中的任一个体和其初始相反种群ROP中对应的相反个体选择成本函数值较小者作为最终初始种群，即第O代种群的个体；计算第O代种群中所有个体的成本函数值，并且按照递增排序，代数G=O ；成本函数为
全文摘要
本发明为SoC测试中基于进化计算的扫描链平衡方法，本法产生初始种群R和初始相反种群ROP，计算最终初始种群中所有个体的成本函数值，递增排序；保存第G代成本函数值最小的最优个体；计算第G代每个个体的迁入速率、迁出速率和转移概率；对第G代种群进行迁徙操作；计算变异概率mk；对第G代种群进行变异操作；保存变异操作后的当前代成本函数值最大的最差个体；用第G代最优个体代替当前代最差个体、并插入当前代群体中，其个体按成本函数值递增排列，获G=G+1代种群。代数G达到最大规定代数，即输出内部扫描链平衡最优解。本法通过群体智能的进化计算，对IP核内部扫描链进行平衡设计，缩短最长封装扫描链的长度，减少IP核测试时间。
文档编号G01R31/3185GK103217642SQ20131007067
公开日2013年7月24日 申请日期2013年3月6日 优先权日2013年3月6日
发明者朱爱军, 李智, 许川佩 申请人:桂林电子科技大学