基于扫描链二次排序组合的低功耗测试方法

焦铬　范双南

摘要：减少SoC的测试时间是降低测试成本的有效方法。提出一种二次排序组合的扫描链平衡算法以减少IP核测试时间。算法首先对内部扫描链按升序排列，然后对其进行mod n（封装后扫描链的条数）划分，得到n个余数序列，将余数为0的序列按降序排列，与其它余数序列组合成新的序列；对新序列再进行一次mod n划分，再次得到n个余数序列，最后对各余数序列分别求和，求和的结果即为n条扫描链封装后的扫描链长度。在ITC02基准电路上的实验结果表明，该算法能有效地缩短IP核测试时间。

关键词：划分SoC测试；扫描链平衡；二次排序组合

中国分类号：TP391 文献标识码：A 文章编号：1009-3044（2014）29-7000-03

Abstract： Reducing SoC test time is an effective way to reduce testing costs.This paper proposes a scan chain balance algorithm based on two times reordering and combination for minimizing IP testing time. Firstly， the internal scan chains in ascending order， then its mod n （the number of packaged scan chain） division， get the n remainder sequence， the remainder of the sequence 0， in descending order， and other than a few sequences combined into a new sequence； once again for the new sequence mod n is divided to obtain a sequence of residues n again， and finally the remainder of the respective sequences are summed， the result is the sum of the length n of the scan chain after scan chains package.Experimental results on ITC'02 benchmark circuits show that the method can effectively reduce the test time.

Key words： SoC test； scan chain balance； two times reordering and combination

1 概述

随着超大规模集成电路设计技术的发展，集成度和复杂度的不断提高，SoC的测试问题也越来越突出。对SoC的测试实际上就是对单个IP（intellectual property）核的测试，如果能减少IP核的测试时间，就能有效地缩短SoC的测试时间。IP核的扫描测试时间由测试壳中最长的扫描链决定。因此，扫描链的平衡处理是有效降低IP核测试时间的有效方法之一。

2 相关研究工作

已有很多学者提出了各种扫描链平衡的算法来降低SoC的测试时间。文献[1]提出了一种最佳递减匹配（best fit decrease，BFD）算法，该算法对IP核内部的扫描链进行逐条分配，具有运行效率高、结构简单的优点，在扫描链平衡处理中应用广泛。但是该算法只能得到局部最优解，存在很大的改进空间。文献[2]提出了一种基于平均值（mean value approximation，MVA）的扫描链平衡算法，MVA算法以Wrapper扫描链的平均值为基准，分配时利用平均值对结果进行预估和控制，能得到相对较好的结果，但是当遇到内部扫描链长度的分布离散程度较大时，结果不理想。文献[3]提出了一种基于差值2次分配的扫描链平衡算法，其主要思想是选择一个基准扫描链，分别选择长度大于和小于基准的扫描链与之做差，按差值进行2次分配，该算法实现简单，算法复杂度低。

针对上述扫描链平衡算法所存在的不足，该文提出了一种基于二次排序组合的扫描链平衡的测试优化方法，该方法可以有效地缩短SoC的测试时间，降低测试成本。

4 实验与结果分析

为了验证本文算法的有效性，以ITC02基准SoC内的所有IP核作为实验对象。ITC02基准SoC包含12个SoC、186个IP核，对于每一个IP核，用本文算法与BFD算法、MVA算法分别计算提供扫描链数目为2～64时的11718（186×63）种情况下，3种方法能够得到最优解的个数。同一个IP核，在相同的扫描链数目约束下，3种方法得到的测试时间的最小值为最优解。如果3种方法得到的测试时间相等，那么对于3种算法都是最优解，这表明3种算法的最优解存在交集。

图2 3种算法的最优解分布

3种算法的最优解个数分布如图2所示。从图中可以看出：

1）区域内的数字表示最优解的个数，最优解总共有11718个；

2） BFD算法得到的最优解的个数为：11393+45+7+29=11474，占所有最优解的97.92%；

3） MVA算法得到的最优解的个数为：11393+76+7+12=11488，占所有最优解的98.04%；

4）本文算法得到的最优解的个数为：11393+45+76+156=11670，占所有最优解的99.59%。

以上数据表明本文提出的方法在ITC02基准测试集的所有IP核上都能取得较好的效果。

5 结论

SoC扫描链的平衡化处理是减少SoC测试时间较好的方法。该文针对SoC封装测试中的扫描链平衡问题，提出了基于二次排序组合的方法，该方法通过对内部扫描链进行两次排序、两次模运算、两次重新组合，最后对各余数序列分别求和，得到n条扫描链封装后的扫描链长度。该算法具有时间复杂度低、实现简单等优点。实验结果表明，该文方法能有效地减少测试时间，较其它方法更为高效。

参考文献：

[1] IYENGAR V，CHAKRABARTY K，MARINISSEN E J.Test wrapper and test access mechanism co-optimization for system-on-chip[A].ITC International Test Conference[C].Baltimore：IEEE Comp.Soc.Test Technology Technical Council，2001：1023-1032.

[2] Niu D H，Wang H，Yang S Y，et al.Re-optimization algorithm for SoC wrapper-chain balance using mean-value approximation[J].Tsinghua Science and Technology，2007，12（S1）：61-66.

[3] 邓立宝，乔立岩，俞洋等.基于差值二次分配的扫描链平衡算法[J].电子学报，2012（2）：338-343.

[4] MULLANE B，HIGGINS M，NAMEE C M.An optimal IEEE 1500 core wrapper design for improved test access and reduced test time[A].IET Irish Signals and Systems Conference[C].Galway，Ireland：Institution of Engineering and Technology，2008：204-209.

[5] BENSO A，DI C S， PRINETTO P，et al.IEEE standard 1500 compliance verification for embedded cores[J].IEEE Transactions on Very Large Scale Integration（VLSI） System，2008，16（4）：397-407.

[6] HIGGINS M，MACNAMEE C，MULLANE B. Design and implementation challenges for adoption of the IEEE 1500 standard[J].IET Computers & Digital Techniques， 2010，4（1）：38-49.endprint

以上数据表明本文提出的方法在ITC02基准测试集的所有IP核上都能取得较好的效果。

5 结论

SoC扫描链的平衡化处理是减少SoC测试时间较好的方法。该文针对SoC封装测试中的扫描链平衡问题，提出了基于二次排序组合的方法，该方法通过对内部扫描链进行两次排序、两次模运算、两次重新组合，最后对各余数序列分别求和，得到n条扫描链封装后的扫描链长度。该算法具有时间复杂度低、实现简单等优点。实验结果表明，该文方法能有效地减少测试时间，较其它方法更为高效。

参考文献：

[1] IYENGAR V，CHAKRABARTY K，MARINISSEN E J.Test wrapper and test access mechanism co-optimization for system-on-chip[A].ITC International Test Conference[C].Baltimore：IEEE Comp.Soc.Test Technology Technical Council，2001：1023-1032.

[2] Niu D H，Wang H，Yang S Y，et al.Re-optimization algorithm for SoC wrapper-chain balance using mean-value approximation[J].Tsinghua Science and Technology，2007，12（S1）：61-66.

[3] 邓立宝，乔立岩，俞洋等.基于差值二次分配的扫描链平衡算法[J].电子学报，2012（2）：338-343.

[4] MULLANE B，HIGGINS M，NAMEE C M.An optimal IEEE 1500 core wrapper design for improved test access and reduced test time[A].IET Irish Signals and Systems Conference[C].Galway，Ireland：Institution of Engineering and Technology，2008：204-209.

[5] BENSO A，DI C S， PRINETTO P，et al.IEEE standard 1500 compliance verification for embedded cores[J].IEEE Transactions on Very Large Scale Integration（VLSI） System，2008，16（4）：397-407.

[6] HIGGINS M，MACNAMEE C，MULLANE B. Design and implementation challenges for adoption of the IEEE 1500 standard[J].IET Computers & Digital Techniques， 2010，4（1）：38-49.endprint

以上数据表明本文提出的方法在ITC02基准测试集的所有IP核上都能取得较好的效果。

5 结论

SoC扫描链的平衡化处理是减少SoC测试时间较好的方法。该文针对SoC封装测试中的扫描链平衡问题，提出了基于二次排序组合的方法，该方法通过对内部扫描链进行两次排序、两次模运算、两次重新组合，最后对各余数序列分别求和，得到n条扫描链封装后的扫描链长度。该算法具有时间复杂度低、实现简单等优点。实验结果表明，该文方法能有效地减少测试时间，较其它方法更为高效。

参考文献：

[1] IYENGAR V，CHAKRABARTY K，MARINISSEN E J.Test wrapper and test access mechanism co-optimization for system-on-chip[A].ITC International Test Conference[C].Baltimore：IEEE Comp.Soc.Test Technology Technical Council，2001：1023-1032.

[2] Niu D H，Wang H，Yang S Y，et al.Re-optimization algorithm for SoC wrapper-chain balance using mean-value approximation[J].Tsinghua Science and Technology，2007，12（S1）：61-66.

[3] 邓立宝，乔立岩，俞洋等.基于差值二次分配的扫描链平衡算法[J].电子学报，2012（2）：338-343.

[4] MULLANE B，HIGGINS M，NAMEE C M.An optimal IEEE 1500 core wrapper design for improved test access and reduced test time[A].IET Irish Signals and Systems Conference[C].Galway，Ireland：Institution of Engineering and Technology，2008：204-209.

[5] BENSO A，DI C S， PRINETTO P，et al.IEEE standard 1500 compliance verification for embedded cores[J].IEEE Transactions on Very Large Scale Integration（VLSI） System，2008，16（4）：397-407.

[6] HIGGINS M，MACNAMEE C，MULLANE B. Design and implementation challenges for adoption of the IEEE 1500 standard[J].IET Computers & Digital Techniques， 2010，4（1）：38-49.endprint