扫描链阻塞技术中TSP问题的算法研究与实现(含开题+任务书+PPT)

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

摘 要

由于近二十年芯片密度快速增长，功耗成为大规模集成（VLSI）电路设计的最重要的因素之一。而且，数字系统的测试功耗被认为要高于正常工作中的功耗。特别地，在扫描测试中，所有的扫描单元时钟切换时所产生的大量能耗可能会烧毁芯片。因此，许多技术被用于最小化功耗或功耗限制下的测试。

测试功耗与被测电路的时钟频率和测试中晶体管的跳变数成正比，因此，降低时钟频率和晶体管的跳变数能降低测试功耗。扫描链阻塞技术能有效地降低测试功耗。在这种技术里，扫描链被分组成N个子扫描链。在某些时刻，仅有一个或者一部分扫描链是活跃的，从而电路的平均功耗和总功耗降低。我们在先前的文章里提出了一种新的方案，在这个方案里，在扫描测试的任意时刻（包括扫描移位周期和捕获周期），仅有一个子扫描链活跃，电路的平均功耗，总功耗和峰值功耗都显著降低。但对有些电路，这个方法的测试应用时间增加。经过初步研究，我们发现如果适当调整测试向量的顺序能显著的降低测试应用时间，求最小的测试应用时间等价于TSP问题。实验结果表明，我们的方法能有效地降低测试应用时间。

关键词：确定性测试，全扫描测试，扫描链阻塞，旅行商问题，低功耗测试

目录

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