扫描链阻塞技术中TSP问题的算法研究与实现

论文字数:14246,页数:28 有开题报告，任务书

摘 要

 由于近二十年芯片密度快速增长，功耗成为大规模集成（VLSI）电路设计的最重要的因素之一。而且，数字系统的测试功耗被认为要高于正常工作中的功耗。特别地，在扫描测试中，所有的扫描单元时钟切换时所产生的大量能耗可能会烧毁芯片。因此，许多技术被用于最小化功耗或功耗限制下的测试。
 测试功耗与被测电路的时钟频率和测试中晶体管的跳变数成正比，因此，降低时钟频率和晶体管的跳变数能降低测试功耗。扫描链阻塞技术能有效地降低测试功耗。在这种技术里，扫描链被分组成N个子扫描链。在某些时刻，仅有一个或者一部分扫描链是活跃的，从而电路的平均功耗和总功耗降低。我们在先前的文章里提出了一种新的方案，在这个方案里，在扫描测试的任意时刻（包括扫描移位周期和捕获周期），仅有一个子扫描链活跃，电路的平均功耗，总功耗和峰值功耗都显著降低。但对有些电路，这个方法的测试应用时间增加。经过初步研究，我们发现如果适当调整测试向量的顺序能显著的降低测试应用时间，求最小的测试应用时间等价于TSP问题。实验结果表明，我们的方法能有效地降低测试应用时间。
 
关键词：确定性测试，全扫描测试，扫描链阻塞，旅行商问题，低功耗测试
A Low Power Deterministic Test Using Scan Chain Disable Technique Based on a TSP Approach
 Abstract
 Due to the chip density increasing drastically through the last decade, power dissipation becomes one of the most important factors of very large scale integration design. Furthermore, power and energy consumption of digital systems are considerably higher in test mode than in normal mode. In particular, in the case of scan test, the power dissipation due to clocking all the scan flip-flops is so excessive that it may burn the chip .Hence, many techniques have investigated power minimization or power constrains test.
 Test power dissipation depends directly on the global clock frequency and switching transitions of the circuit under test. Therefore, decreasing both the clock frequency and the switching activity can reduce test power. Scan chain disable technique can reduce test power efficiently. In the technique, the flip-flops are grouped into N scan chains. At sometime, just one scan chain or some of the scan chains are active. Average power is reduced. We previously proposed a low power deterministic test methodology. In this method, only a scan chain is active during both shift and capture cycles. Both peak power and average power are reduced drastically. However, the test application time of some benchmark circuits is increased. We find that if we reorder the test set, the test application time can be reduced. The problem to achieve shortest test application time is equivalent to a TSP problem. Experimental results show that our approach can efficiently reduce test application time.
 
Key Words: deterministic test, full scan testing, scan chain disable, traveling salesman problem, low power testing
 目录
1. 绪论 1
1.1本课题的目的和意义 1
1.2扫描链阻塞术技术 1
1.3文章的组织 2
2. 低功耗测试方案 4
2.1基本流程 4
2.2测试应用时间的问题 5
3. 测试流程 7
4. 扫描单元和测试立方分组 9
4.1提出问题 9
4.2禁忌搜索算法 9
4.3扫描单元分组 11
4.4测试立方分组 12
5. TSP算法 14
5.1 TSP概念 14
5.2 TSP问题的基本性质 14
5.3 LKH实现 15
6. TSP在阻塞扫描测试中的应用 17
6.1 原方法的局限性 17
6.2 改进的方法 18
6.3 LKH算法的应用 18
6.4 实验平台 19
6.5 实验步骤 19
7. 实验结果与结论 21
总结与展望 22
致谢 23
参考文献 24