最近更新
热门关注
本站推荐
位置导航：首页 -VC设计 - 扫描链阻塞技术中TSP问题的算法研究
扫描链阻塞技术中TSP问题的算法研究
所属栏目：VC设计 发布日期：2011-9-18 10:57:20 文章来源：管理员
【设计说明】该全套毕业设计作品包括：论文＋源代码＋程序＋开提报告＋PPT答辨稿数据流程图、功能模块图、运行界面图、源代码和程序，另附有开题报告、论文全文，按计算机毕业论文格式要求书写，适用于计算机或相关专业毕业设计。
【温馨提示】为防止百度搜取本站内容，故论文内容只贴出部分！
【咨询热线】13545062927
【客服QQ】 920638823
课题名称:扫描链阻塞技术中TSP问题的算法研究
扫描链阻塞术技术
测试功耗与直接取决于频繁的全局时钟频率和芯片的跳变频率成正比。因此，减少时钟频率和芯片的跳变数能减少测试功耗。文献[4]通过减少时钟频率减少了时序电路中平均功耗，这个方法的主要缺点是当时钟频率降低的同时测试应用时间增加了。而且峰值功耗无法降低。
减少功耗的主要研究方向是去降低电路跳变活跃程度。各种各样的技术被用于减少测试中的电路跳变频率。文献[5-8]中方法是把不同测试向量或者扫描单元重新组织成一个测试集来最小化测试功耗。这些技术的基本思想就是去找到一个新的顺序的测试集使得连续的测试向量之间的相关性增加。文献[9][10]中这些方法通过用适合的二进制位0，1填充那些测试立方中的不确定位来寻找新的测试向量。
文献[11-17]中的方法通过使用扫描链阻塞技术降低了被测电路的功耗。Wheltsel [11] 和Saxel 等人[12]提出了两种方法来将扫描链分成N条子扫描链，其中N整数且N>1。在扫描移位时，仅有一个子扫描链的时钟没有被阻塞，扫描移位的功耗被降低成原来的1/N。因此，平均功耗降低了。但是，这些方法没有考虑峰值功耗。在捕获周期中，所有扫描子链是活跃的。在文献[13]中，这种方案通过使用两个不同的时钟（譬如其中一个时钟频率是另一个的一半），使两条扫描链在不同的时钟频率下运行。虽然这种技术有效地少了平均能耗，但它也有文献[11],[12]两种方法的缺点。Bhattacharya等人[14] 提出了一种双扫描树结构，扫描向量被组织成两个完全的k级二进制树，树的叶子节点被两两合并。这种方案中，在扫切换时只有一个扫描路径中的扫描向量时活跃的。平均能耗明显减少了。但是捕获周期中的能量浪费不能降低。在文献[15]中，扫描链被分成两个集合，而给定集合T 被分成两个子集。对于这些测试组，只有一组扫描链时活跃的。因此，这种方法降低了能耗。但是，这种方法同样也没有考虑峰值功耗。文献[16]中的方法扩展了文献[15]中提出的方案。在这种方法中，测试向量被分成一些组。对于每一个组，当这个组的测试向量被激活，扫描链的一个子集通过一种可编程的扫描链阻塞技术被阻塞。这种方法降低平均能耗时很有效。但对于其中一组测试向量以及组与组之间的边界，所有的扫描链都活跃，峰值功耗的降低不能得到保证。为了降低峰值功耗，Basturkmen 等人[17]提出了一种基于扫描电路的低功耗随机BIST方法。这种方法中，扫描链被分成N组，在任何时候（扫描周期和捕获周期），只有一个组中的扫描链是活跃的。因此，平均功耗和峰值功耗都降低了。但是，这种方法增加了测试时间，对确定性测试不太有效。我们先前提出了一种基于扫描链阻塞技术的低功耗确定性测试方法[18]。在这种方法中扫描单元被分组成N条扫描链。在任何时候（扫描周期和捕获周期），只有一个扫描链是活跃的。因此，这种技术即减小了峰值功耗，也降低了平均功耗。
测试应用时间的问题
如果我们应用每个测试向量N次，对于这N个相同的向量N个测试链在同一时刻只有一个是活跃，测试将会取得和传统的全扫描算法相同的故障覆盖率。虽然它降低了平均能耗和峰值功耗，但是测试应用时间太长了。幸运的是，主要有两种信息。
通常，当一个测试向量被应用时，几个扫描单元捕获一个故障的测试响应。只有一个扫描单元是活跃的，这就足够用于测试那个故障了。
通常，一个测试集中的几个测试向量能够同时测试一个故障。我们使用这些测试向量中的任一个去测试这个故障就够了。
如果我们有效的处理这些信息，测试应用时间将被大幅度降低。第四章将继续讨论这方面的问题。
扫描单元和测试立方分组
4.1提出问题
文献[18]中提出下面的问题。
问题1：通过这种原理减少电路测试时间。更正式的陈述如下：
输入：一个时序电路，它的检测捕获信息，扫描链个数N。
输出：多扫描链和它的M个相容的测试集，它为了达到：
目标：最小化测试应用时间。
这个问题十分复杂，文献[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步搜索中将被视为禁忌对象；需要指出的是，由于当前的禁忌对象对应状态的适配值可能很好，因此在算法中设置判断，若禁忌对象对应的适配值优于它，则无视其禁忌属性而仍采纳其为当前选择，也就是通常所说的藐视准则(或称特赦准则)。可见，简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历 的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。需要指出的是：
(1)首先，由于TS是局部领域搜索的一种扩充，因此领域结构的设计很关键，它 决定了当前解的领域解的产生形式和数目，以及各个解之间的关系。
(2)其次，出于改善算法的优化时间性能的考虑，若领域结构决定了大量的领域 解(尤其对大规模问题，如TS的SWAP操作将产生 个领域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。
(3)禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进 而影响整个算法的搜索进程和行为。同时，以上示例中，禁忌表中禁忌对象的替换 是采用FIFO方式（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。
(4)藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。
(5)对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。
(6)为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则 来结束整个搜索过程。
此外，在许多场合禁忌对象的被禁次数也被用于指导搜索，以取得 更大的搜索空间。禁忌次数越高，通常可认为出现循环搜索的概率越大。
本课题:扫描链阻塞技术中TSP问题的算法研究来源于计算机毕业设计网欢迎收藏
