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

摘 要

由于近二十年芯片密度快速增长，功耗成为大规模集成（VLSI）电路设计的最重要的因素之一。而且，数字系统的测试功耗被认为要高于正常工作中的功耗。特别地，在扫描测试中，所有的扫描单元时钟切换时所产生的大量能耗可能会烧毁芯片。因此，许多技术被用于最小化功耗或功耗限制下的测试。
测试功耗与被测电路的时钟频率和测试中晶体管的跳变数成正比，因此，降低时钟频率和晶体管的跳变数能降低测试功耗。扫描链阻塞技术能有效地降低测试功耗。在这种技术里，扫描链被分组成N个子扫描链。在某些时刻，仅有一个或者一部分扫描链是活跃的，从而电路的平均功耗和总功耗降低。我们在先前的文章里提出了一种新的方案，在这个方案里，在扫描测试的任意时刻（包括扫描移位周期和捕获周期），仅有一个子扫描链活跃，电路的平均功耗，总功耗和峰值功耗都显著降低。但对有些电路，这个方法的测试应用时间增加。经过初步研究，我们发现如果适当调整测试向量的顺序能显著的降低测试应用时间，求最小的测试应用时间等价于TSP问题。实验结果表明，我们的方法能有效地降低测试应用时间。

关键词：确定性测试，全扫描测试，扫描链阻塞，旅行商问题，低功耗测试
虽然这种模式把电路看成是一个单一的时钟域，但是同样可以应用于多时钟域和多扫描链。对于多时钟域的电路，时钟控制器和扫描链被用来控制多时钟。门栅插入技术能解决扫描测试中的时钟不平衡的问题。如果同一时钟域中的扫描单元分组成一些扫描链，扫描测试中的时钟不平衡的问题将会被最小化，在捕获的时候也没有难处理的时钟不平衡的问题。One-hot时钟方案，即在捕获操作时同一个时钟域中的扫描链活跃的，对于处理多时钟电路的问题相当有效。但是，这个方案的测试时间比较长且峰值功耗比较高。
测试过程总结如下：首先，一些向量以以下的方式被扫描进扫描链。通过给Cs设置合适的值，就可以使扫描链轮流处于活跃状态。其次，设置合适的Cs值，只有一条扫描链捕捉测试响应。如果下一个向量有同样的值输入阻塞的扫描链，Cs会保存同样的值。根据活跃的扫描链，我们改变向量的位，交换测试响应直到向量阻塞扫描链不同于上一个向量。我们继续按照上面的流程接受下一个向量直到所有测试完成。最后，输出最后一个活跃的扫描链的测试响应结果。
注意其它降低能耗的技术，比如重新排序测试向量，扫描单元重组和最小化跳变填充，这些技术都适于这种方案。如果我们在这种方案中使用一种或者多种技术，平均功耗和最高功耗都将显著降低。这种方案可以改进，例如利用多扫描树[19]可以大量降低测试应用时间。 [来源：http://www.think58.com]
虽然提出的这种模式有这些优点，但是如果故障的响应不能传递给活跃的扫描链，故障的响应也不能被捕获。这样，为了达到传统全扫描算法相同的故障覆盖率，我们必须重复应用这些测试向量，直到捕获故障响应的一个扫描链活跃。
2.2测试应用时间的问题
如果我们应用每个测试向量N次，对于这N个相同的向量N个测试链在同一时刻只有一个是活跃，测试将会取得和传统的全扫描算法相同的故障覆盖率。虽然它降低了平均能耗和峰值功耗，但是测试应用时间太长了。幸运的是，主要有两种信息。
通常，当一个测试向量被应用时，几个扫描单元捕获一个故障的测试响应。只有一个扫描单元是活跃的，这就足够用于测试那个故障了。
通常，一个测试集中的几个测试向量能够同时测试一个故障。我们使用这些测试向量中的任一个去测试这个故障就够了。
如果我们有效的处理这些信息，测试应用时间将被大幅度降低。第四章将继续讨论这方面的问题。
扫描单元和测试立方分组
4.1提出问题
文献[18]中提出下面的问题。
问题1：通过这种原理减少电路测试时间。更正式的陈述如下：
输入：一个时序电路，它的检测捕获信息，扫描链个数N。
输出：多扫描链和它的M个相容的测试集，它为了达到：
目标：最小化测试应用时间。

[版权所有：http://think58.com]

这个问题十分复杂，文献[18]中用禁忌搜索算法求近似最优解。
4.2禁忌搜索算法
禁忌搜索算法[20]是局部领域搜索算法的推广，是由Glover在1986年首次提出。的，并进而形成一套完整的算法。禁忌搜索算法一开始主要是运用于组合优化领域，后来被推广到连续函数的全局优化。禁忌搜索算法的特点是运用了禁忌技术，就是禁止重复以前的工作。为了避免局部领域搜索算法陷入局部最优的问题，禁忌搜索算法用一个禁忌表记录下己经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地选择搜索这些点，以此来跳出局部最优点。禁忌搜索算法是一种人工智能算法。
禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索 以最终实现全局优化。迄今为止，TS算法在组合优化、生产调度、机器学习、电路 计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多 的研究，并大有发展的趋势。局部搜索算法是基于贪婪思想持续地在当前解的领域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于领域结构和初解，尤其窥陷入局部极小而无法保证全局优化性。针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构如TSP的2opt扩展到k-opt；多点并行搜索，如进化计算；变结构领域搜索；另外，就是采用TS的禁忌策略尽量避免迂回搜索，它 是一种确定性的局部极小突跳策略。禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的 思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环)，从而保证对不同的有效搜索途径的探索。禁 忌搜索涉及到领域(neighborhood)、禁忌表、禁忌长度、候选解(candidate)、藐视准则(candidate)等概念，我们首先用 一个示例来理解禁忌搜索及其各重要概念，而后给出算法的一般流程。 组合优化是TS算法应用最多的领域。置换问题，如TSP、调度问题等，是一大批组 合优化问题的典型代表，在此用它来解释简单的禁忌搜索算法的思想和操作。对于 n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数 字，而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。首先，我们对置换问题定义一种邻域搜索结构，如互换操作(SWAP)，即随机交换两个点的位置，则每个状态的邻域解有 =n(n－1）/2个。称从一个状态转移到其邻域中的另一个状态为一次移动(move)，显然每次移动将导致适配值(反比于目标函数值)的变化。其次，我们采用一个存储结构来区分移动的属性，即是否为禁忌?以下示例中：考虑7元素的置换问题，并用每一状态的相应21个邻域解中最优的5次移动(对应最佳的5个适配值)作为候选解；为一定程度上防止迂回搜索，每个被采纳的移动在禁忌表中将滞留3步(即禁忌长度)，即将移动在以下连续3步搜索中将被视为禁忌对象；需要指出的是，由于当前的禁忌对象对应状态的适配值可能很好，因此在算法中设置判断，若禁忌对象对应的适配值优于它，则无视其禁忌属性而仍采纳其为当前选择，也就是通常所说的藐视准则(或称特赦准则)。可见，简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历 的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。需要指出的是： [来源：http://think58.com]
(1)首先，由于TS是局部领域搜索的一种扩充，因此领域结构的设计很关键，它 决定了当前解的领域解的产生形式和数目，以及各个解之间的关系。
(2)其次，出于改善算法的优化时间性能的考虑，若领域结构决定了大量的领域 解(尤其对大规模问题，如TS的SWAP操作将产生 个领域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。
(3)禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进 而影响整个算法的搜索进程和行为。同时，以上示例中，禁忌表中禁忌对象的替换 是采用FIFO方式（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。
(4)藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。
(5)对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。
(6)为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则 来结束整个搜索过程。
think58好，好think58

[资料来源：http://www.THINK58.com]