（信息与通信工程专业论文）基于遗传算法的测试生成在fpga上的研究与实现.pdf

硕f j 学位论文 摘要 随着数字集成电路设计及制造工艺技术的发展，集成电路的规模越来越大， 结构日益复杂，电路的测试变得越发困难。解决测试问题的一个好办法是使用可 测性设计。内建自测试是一种重要和常用的可测性设计技术，其关键在于测试向 量生成器的设计。 本文在阐述数字集成电路测试和遗传算法基本理论的基础上，针对当前内建 自测试技术中存在的一些问题，着重研究了一种由被测电路自己产生测试向量的 测试生成方法，并采用遗传算法进行适应性搜索以寻求一种最优的反馈方式。但 是，采用软件实现的方法在速度上往往受到本质是串行计算的计算机制约，因此 采用硬件化设计具有重要的意义。本文的主要工作如下： ( 1 ) 对当前常用的测试向量生成器进行了详细的研究，并分析了这些技术的 优缺点，并对f p g a 设计方法和特点作了深入的探讨； ( 2 ) 在对遗传算法的基本理论进行了深入研究的基础上，提出了一种基于遗 传算法的测试生成方法的硬件结构。从系统结构设计、遗传算子实现、适应度模 块实现等方面，详细说明了该系统的设计思想和实现方案，并对关键模块进行了 优化，其优化方法包括：采用流水线设计提高时钟频率，引入选择模块及适应度 模块并行结构，使用双端口内存模块增加数据读写速度等； ( 3 ) 在深入分析故障模拟基本理论的基础上，结合f p g a 自身的特点，使用 注入故障的电路和双端口内存存储故障列表的方法，设计并实现了一种具有故障 选择和故障摘除功能的故障模拟器； ( 4 ) 在q u a r t u s i i 和m o d e l s i m 环境下对该系统进行了模块级和系统级的仿真 和验证，在a l t e r a 公司的s t r a t i x 系列的e p l s 4 0 f 1 0 2 0 c 5 芯片上实现。实现后的 测试表明：基于遗传算法的测试生成方法和故障模拟器的f p g a 实现能够在较高 的频率下运行，设计方案在资源利用率和速度方面达到了较好的平衡，有效减少 了运行时间，达到了预期的设计目的。 关键词：测试生成；遗传算法；故障模拟；反馈 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ed e s i g n f o rd i g i t a li n t e g r a t e d c i r c u l t sa n dt h e t e c h n i q u eo fc r a f t ，t h es c a l eo fi n t e g r a t e dc i r c u i t sb e c o m em o r ea n dm o r el a r g e ，t h e s t l l l c t u r eb e c o r u e si n c r e a s i n g l yc o m p l e x ，t h et e s tf o ri n t e g r a t e dc i r c u i t s l sb e c o m i n g i n c r e a s i n g l yd i f f i c u l t t h ed e s i g n - f o r t e s t a b i l i t y ( d f t ) t e c h n i q u e i sag o o dm e t h o dt o s 0 1 v et e s tp r o b l e m b u i l d i ns e l f - t e s t ( b i s t ) i sa k i n do fm o s ti m p o r t a n ta n dw l d e l y u s e dd f tt e c h n o l o g i e s ap r o p e rt e s tp a t t e ng e n e r a t o r ( t p g ) i st h e e s s e n t l a lp a r t1 n a n yb i s tt e c h n i q u e o nt h eb a s i so fi n t r o d u c i n gt h ep r i n c i p l eo fd i g i t a li n t e g r a t e dc i r c u i t st e s t m g a n d g e n e t i ca l g o r i t h m ( g a ) ，t h i st h e s i sf o c u s e s o na na u t o m a t i ct e s tg e n e r a t em e t h o du s m g t e s tv e c t o r sa p p l i e db yc i r c u i t u n d e r - t e s t ( c u t ) a u t o m a t i c a l l y t oa d d r e s ss o m e c u r r e n tt e c h n i c a lp r o b l e m s t of i n daa p p r o x i m a t e l yo p t i m a lf e e d b a c k c o m b l n a t l o n ， t h eu s eo fg ad o i n ga d a p t i v es e a r c h ，b u tu s i n gs o f t w a r et oa c h i e v e t h i sc o m p i e x1 s s u e i sa l w a v s ；e s t r i c t e db yc o m p u t e rs y s t e mw h i c h i se s s e n t i a l l ys e r i a la ts p e e d t h e r e f o r e , i th a sag r e a tm e a n i n gf o rh a r d w a r ei m p l e m e n t a t i o n t h e m a i na c c o m p l i s h e dt a s k so f t h i st h e s i si n c l u d i n gt h ef o l l o w i n gp a n s 一一 ( 1 ) t h ec u r r c n tc o m m o n l yu s e dt p g i sr e s e a r c h e di nd e t a i l ，a na n a l y s l so ft h e a d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s et e c h n i q u e s a tt h es a m et i m e ，f p g ad e s l g n m e t h o d sa n dc h a r a c t e r i s t i c sa r ed e p t ho fd i s c u s s i o n - ( 2 ) t h eb a s i ct h e o r yo fg e n e t i ca l g o r i t h mi s s t u d i e dd e e p l y , ak i n do fh a r d w a r e c i r c u i ta r c h i t e c t u r ea b o u tt e s tg e n e r a t i o n m e t h o db a s e do ng au s i n gf p g ai s p r o p o s e d f r o ms e v e r a la s p e c t s ，s u c ha ss y s t e ma r c h i t e c t u r ed e s i g n ，g e n e n co p e r a t o r r e a l i z a t i o n ，t h et h e s i sd e t a i l st h es y s t e md e s i g nt h i n k i n ga n dr e a l i z a t i o np r o c e s s a n d t h ec o m p l e xm o d u l e sa r eo p t i m i z e d ，t h e s em e t h o d s o fo p t i m i z a t i o ni n c l u d e s ：p i p e l l n e t e c h n i q u ei su s e dt or a i s i n gt h ec l o c kf r e q u e n c y , s e l e c t i o n m o d u l ea n df i t n e s sm o d u l e p a r a l l e lt e c h n i q u ei si n t r o d u c e d ，t h eu s e o fd u a l p o r tm e m o r ym o d u l et oi n c r e a s et h e s p e e do f d a t ar e a d i n ga n dw r i t i n g ( 3 ) t h eb a s i ct h e o r yo ff a u l ts i m u l a t i o ni s s t u d i e dd e e p l y ，c o m b i n e dw i t hf p g a o w n e dc h a r a c t e r i s t i c s ，u s i n gf a u l ti n j e c t i o n c i r c u i t sa n dd u a l 。p o r tm e m o r ys t o 咖g f a u l tl i s t af a u l ts i m u l a t o ri sd e s i g n e da n di m p l e m e n t e d ，w h i c hh a s f a u l ts e l e c t i o na n d f a u l td e le t ef u n c t i o n s i l l 硕卜学位论文 m ii1i 1 1= ii = ! g ( 4 ) t h ew h o l es y s t e m i ss i m u l a t e da n dv e r i f i e di nq u a r t u s i ia n dm o d e l s i m e n v i r o n m e n t t h eh a r d w a r es y s t e mp r o c e s s o rh a sb e e ni m p l e m e n t e di na l t e r af p g a s t r a t i xe p1s 4 0 f10 2 0 c 5 t h ev h d li su s e dt od e s c r i b et h ew h o l es y s t e m t h er e s u l t s s h o wt h a t ：t e s tg e n e r a t i o nm e t h o db a s e do ng aa n df a u l ts i m u l a t o ru s i n gf p g ac a n o p e r a t eu n d e rh i g h e rf r e q u e n c y t h ed e s i g na c h i e v e daw e l lu t i l i z a t i o no fr e s o u r c e s a n ds p e e do fs t a t ea n dc a ne f f i c i e n t l yr e d u c et h er u nt i m e ，t h ee x p e c t a n td e s i g na i mi s 如1 6 l l e d k e yw o r d s ：t e s tg e n e r a t i o n ；g e n e t i ca l g o r i t h m ；f a u l ts i m u l a t i o n ；f e e d b a c k i v 幕于遗传算法的测试生成柏：f p g al ：的研究j 实现 插图索引 图1 1 内部异或线性反馈移位寄存器4 图1 2 外部异或线性反馈移位寄存器一4 图1 3l f s r 生成的测试向量数与故障覆盖率的关系4 图1 4 自顶而下的设计思想7 图1 5 硬件开发板实物图8 图2 1 测试基本原理l l 图2 2 一个单固定型故障的例子1 3 图2 3 遗传算法的流程1 5 图3 1c 1 7 电路的自测试结构2 l 图3 2 系统硬件结构图2 2 图3 3 流水线技术的示例2 4 图3 4 存储器模块的结构2 4 图3 5c a 的结构图一2 6 图3 6 规则9 0 1 5 0 线性c a 的硬件结构2 6 图3 7 选择模块结构图2 8 图3 8 交叉变异模块结构图2 8 图3 9 适应度模块结构图2 9 图3 1 0 后继向量模块结构图3 0 图3 1 1 分时复用的后继向量模块3 l 图4 1 故障模拟问题3 3 图4 2 故障模拟示意图3 5 图4 3 故障模拟器硬件结构图3 6 图4 4 三种故障注入单元3 7 图4 5 故障注入链的例子3 7 图4 6 故障编码3 8 图4 7 改进的三种故障注入单元3 8 图4 8 改进的注入故障的电路3 9 图4 9 双端口内存配置图3 9 图4 1 0 控制模块的工作状态4 0 图5 1 随机数模块仿真图4 1 v i l 硕i ：学位论丈 v i i l 2 2 3 3 4 4 5 4 4 4 4 4 4 4 图 图 真图真图 图图仿真仿真图真真块仿块仿真仿仿模块模器仿块块异模量拟块模模变度向模模制择叉应继障层 控选交适后故顶 2 3 4 5 6 7 8 5 5 5 5 5 5 5图图图图图图图 基f 遗f 算法的测试生成n ：f p g af ：的研究j 实现 附表索引 表4 1b e n c h m a r k8 5 基准电路固定故障的等价故障压缩3 4 表5 1 系统综合报告4 5 表5 2 系统测试结果表4 6 表5 3 故障模拟器综合报告4 6 表5 4 故障模拟器测试结果表4 6 i x 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 钟妊懦、 日期：西年多月g 日 | 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1o 保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：叶蜂诲，1 翩签名：穴咪 日期：4 年月眵日 日期乡年6 月扩日 硕士学位论文 1 1 研究背景及任务 第1 章绪论 随着集成电路的规模f 1 益增大，复杂性和集成度不断提高，数字集成电路测 试变得越来越困难。虽然对测试理论和方法的研究一直没有间断和停止过，但 由于对大型数字集成电路的测试日趋迫切，现有的测试方法仍然远远满足不了实 际的需求。为此，人们提出了可测性设计，即在电路设计的同时，就充分考虑到 测试的需求。可测试性设计在近年来取得了很大的发展，常用的内建自测试技术、 扫描设计技术都是热门的研究领域。 内建自测试技术关键在于测试向量生成器的设计，它决定了整个内建自测试 方案能够达到的故障覆盖率以及所需的面积开销和测试时间的大小。现在常用的 硬件测试向量生成方法有线性反馈移位寄存器( l r s r ) 、细胞自动机、l f s r 与r o m 结合的方法等。这些测试生成方法都试图在硬件面积开销、测试应用时间和故障 覆盖率这三个重要的评价指标之间寻求一种平衡，但都不尽如人意。 针对当前常用测试生成技术的不足，文献 2 】提出一种由被测电路自己产生测 试向量的自动测试生成方法，它是一种新颖、有效的测试生成方法。该方法将被 测电路当成一种可利用的资源，而不仅仅是被测试的对象。通过捕获电路部分内 部节点对当f ； 测试向量的响应，反馈到原始输入端形成下一个测试向量，使得电 路可以在施加了初始向量后，可以自动的生成一个完整的测试集。该方法相比较 当前常用的一些测试生成方法，在某些方面具有一定的优势。 该方法的研究重点是如何找出一种符合要求的反馈方式，该反馈方式生成的 测试集能够在较短的测试向量长度下检测出尽可能多的故障。但当电路的规模较 大时，所有反馈方式的组合方案无疑是一个巨大的天文数字。针对如何寻找符合 要求的反馈方式问题，文献 2 】采用了遗传算法进行适应搜索，以搜索到一个最优 或近似最优的反馈方式。 然而，用一般的软件来实现这种基于遗传算法的测试生成方法会比较慢，并 且对于较大规模的电路，往往需要很长的时间。因此，为了提高该方法的处理速 度，可以用硬件来实现加速，因此需要寻求一种提高系统运行速度的硬件化模块， f p g a 芯片便是目标硬件的理想选择之一。针对该问题，本文提出一种在f p g a 上实现基于遗传算法的测试生成方法的硬件化方案，为提高测试生成方法的速度 提供了新的思路和解决方法。 本文将对基于遗传算法的测试生成方法硬件化的结构，以及流水线操作和并 基于遗传算法的测试生成在f p g a 上的研究与实现 行化问题进行具体的研究，为进一步进行由被测电路自己产生测试向量的内建自 测试技术研究的硬件化奠定基础。同时，本文的研究也可以为在遗传算法以及相 应变种算法在其它工程领域的应用起到一定的推动作用。 1 2 测试向量生成方法的研究概况 随着现代集成电路设计中门数量的急剧增加，一个大型电路的测试数据规模 也在快速的增加。同时，由于电路系统时钟频率的不断增加，对于当前的一些高 性能设备和芯片，如何保证对于传输故障( t r a n s i t i o nf a u l t s ) 或者是路径延迟故障 ( p a t hd e l a yf a u l t s ) 的全速测试( a t s p e e dt e s t i n g ) 成为提高测试质量的关键问题之一。 通常而言，实现传输故障和路径延迟故障的全速测试所需的测试集一般是单固定 故障模型下测试向量集大小的好几倍，测试响应的规模也大幅度提高。于是，对 全速测试的测试需求无疑又加快了测试数据规模变大的趋势。因此集成电路生产 出来以后常常很难被测试，需要使用十分昂贵的测试仪器和很长的测试时间，而 且很难做到全面的测试。解决测试问题的一个好方法是使用可测性设计技术【3 5 】， 即在集成电路设计的同时考虑对它的测试问题，使得集成电路在生产出来以后能 够较容易地被测试。其中内建自测试( b u i l t i ns e l ft e s t ，b i s t ) 和扫描设计( s c a n d e s i g n ) 是两种很重要的和常用的可测性设计技术。 b i s t 因其可以提高可测性、可实现全速测试和减少对外部测试设备的依赖而 成为可测性设计的主流。b i s t 技术最早由a g r a w a l 和k i m e 6 7 】提出，它的基本思 想是在制造芯片的电路中加入一些额外的自测试电路。b i s t 通常要在被测电路内 部设置测试向量生成器( t e s tp a t t e r ng e n e r a t o r ，t p g ) 和输出响应分析器( o u t p u t r e s p o n s ea n a l y z e r ，o r a ) 。t p g 使用某种方法生成一组测试向量，并把它们施加 到被测电路的输入端。o r a 对被测电路在测试向量激励下所产生的输出响应进行 分析，判断是否有故障。 b i s t 技术关键在于t p g 的设计，它决定了整个内建自测试方案能够达到的 故障覆盖率以及所需的面积开销和测试时间的大小。目前所采用的硬件测试向量 生成方法如下【i 】： 1 二进制计数器。一个二进制计数器可以生成一个穷举的测试码序列，但如 果输入的数量较大时会耗费太多的测试时间。这种类型的测试向量生成器必须进 行划分。另外，二进制计数器比典型的线性反馈移位寄存器测试向量生成器需要 更多硬件。 2 用于r o m 存储的测试生成。这种方法是在芯片上的r o m 中保存一个好 的测试向量集合，在测试过程中，存储的测试向量被依次施加到被测电路中，对 电路进行测试。这种方法虽然适用于任何类型的故障并且有很高的故障覆盖率， 但对于一般规模的电路测试数据通常都是很大的，这在芯片面积方面的费用较为 2 硕士学位论文 昂贵，所以在实际工程当中很少被应用。 3 改进的计数器。改进的计数器作为测试向量生成器也是成功的，但它们也 需要较长的测试序列。 4 l f s r 。使用线性反馈移位寄存器( l f s r ) 生成伪随机测试码，这经常需要 1 0 0 万或者更多的测试码序列以获得较高的故障覆盖率。这种方法只使用很少的 硬件，是目前首选的测试向量生成方法。l f s r 的问题是由于随机向量难测故障 ( r a n d o mp a t t e r nr e s i s t a n tf a u l t s ) 的存在，经常需要很长的测试向量序列和很长的测 试应用时间才能达到较高的故障覆盖率。 5 l f s r 和r o m 相结合。最有效的方法之一是用一个l f s r 作为原始测试模 式，然后用一个自动测试向量生成程序生成针对l f s r 序列漏掉的故障的测试向 量。这些增加的少量测试向量可以保存在芯片上的一个小r o m 中，作为第二个 测试阶段嵌入在l f s r 的输出，或者嵌入在一个扫描链中以将固定故障覆盖率增 加到10 0 。这样既保证了很高的故障覆盖率，又克服了大容量r o m 费用高的问 题。 6 细胞自动机( c e l l u l a ra u t o m a t a ，c a ) 。在这种方法中，每个测试向量生成 器单元有少量的逻辑门，一个触发器和仅与临近的门相连接。单元被复制以产生 单元自动机。在集成电路的伪随机测试中用c a 取代l f s r 将会获得更高的故障 覆盖率。 由于l f s r 在b i s t 测试生成中有很广泛的应用，所以接下来介绍l f s r 的工 作原理及其相关的研究成果。可以通过向由d 触发器组凰，蜀，i 组成的移位 寄存器添加线性反馈来获得n 阶的l f s r 。在实际应用中，主要用到两种类型的 l f s r ，即内部异或型和外部异或型【8 】。 在一个内部异或l f s r 中，移位寄存器的最后一个触发器的输出1 ，被反 馈到触发器组选定自己的输入端，如图1 1 所示。用一个反馈多项式，如式1 1 厂( x )- - - 1 + h i x + h 2 x 2 + + h n - i x 厅1 + 石n ( 1 1 ) 来表示反馈关系。对于i = 0 ，1 ，z 一1 ，| l f - l 表示在触发器置的输入端存在反馈， 而h 尸0 表示不存在反馈。 通过在触发器置1 和五之间加入一个两输入异或门可以得到疋，输入端的反 馈，异或门的输入端连接反馈信号和1 的输出信号，而异或门的输出则连接的 是置的的输入端。如果 严0 就表示不存在这种异或门，因为在这种情况下疋的 输入端没有反馈信号。 一个外部异或的l f s r 寄存器与内部异或的l f s r 寄存器工作状态完全相反。 如图1 2 所示。在这种情况下，选定的触发器组子集的输出结合成一个单一的信 号，这个信号反馈到移位寄存器的第_ 个触发器1 的输入端。而且也有一个反 基于遗传算法的测试生成在f p g a 上的研究与实现 馈多项式来表示这个反馈关系。对于i = 0 ，l ，n 1 ，办f - 1 表示在触发器咒的输入 端存在反馈，而五尸o 表示不存在反馈。 x p 2x h i 图1 1 内部异或线性反馈移位寄存器 l蜀 蜀 图1 2 外部异或线性反馈移位寄存器 如果l f s r 能够生成除了全0 外的所有2 ”一1 个不同的向量序列，则称该l f s r 的特征多项式为本原特征多项式，该l f s r 为最大长度的l f s r 。对于不同的n 一定有不同的本原多项式，而对于同一个拧值可能也有不同的多项式( 即本原多项 式不具有唯一性1 ，本原多项式的求法是比较复杂的。 虽然l f s r 具有硬件代价较小、易于实现的特点，但是，它产生的伪随机测 试向量序列中包含有大量的对检测故障没有作用的测试向量。图1 3 表示了l f s r 产生的测试向量数与故障覆盖率的关系。所以要达到较高的故障覆盖率需要较长 的测试时间。 图1 3l f s r 生成的测试向量数与故障覆盖率的关系 为了进一步提高测试效率，相继出现了改变被测电路和改变测试向量生成的 方法两类。比如，文献 9 】所提出的测试点插入技术是一种改变被测电路的方法， 它只芾摹增加少量的硬件就可以提高插入点的控制性和观察性，从而提高故障覆 4 硕士学位论文 盖率，但缺点是有些电路不允许或不容易被修改，而且这种修改可能会影响电路 的时延特性。 目前，研究人员把研究重点放在改变测试向量生的方法上来，出现了一些有 效的测试向量生成方法。加权伪随机测试向量生成( w e i g h t e dr a n d o mp a t t e r n t e s t i n g ，w r p t ) 1 0 】的发明是为了使用较短的测试码长度( 也就是较短的测试时间) 达到较高的故障覆盖率。为了在缩短测试码长度的同时改进故障覆盖率，对这种 测试向量生成器可以调节在每个输入产生0 或者1 的概率。这种测试向量生成器 可以有效地处理难检测故障。在加权伪随机内建自测试中，这些概率被调整到使 测试码更可能检测到难检测故障。一种方法是通过对难检测故障的概率统计分析 使用软件来确定单个或多个权重集合】，另一种方法是使用启发式方法产生一 个初始权重组合，并依靠自动测试程序生成系统产生附加的权重集合【l2 1 。权重可 以通过逻辑实现，也可以放在r o m 中。而且对每个集合必须生成很多随机测试 向量。多个权重集合导致了过多的测试向量生成器的硬件开销。 为了解决l f s r 故障覆盖率不高的问题，可以采用更换l f s r 种子的办法， 使得l f s r 产生的测试向量之间的相关性变小。于是，可以在测试生成过程中， 改变l f s r 的种子的办法，来得到新的可以提高故障覆盖率的向量序列，这种技 术称为l f s r 重播种【1 3 。1 7 】技术。该方法的关键是如何选取种子，使得它得到的向 量序列对前面已经产生的测试向量是一个有益的补充。 随着l f s r 重播种技术的发展，相继出现了基于多重多项式线性反馈移位寄 存器( m u l t i p l e p o l y n o m i a ll f s r ，m p - l f s r ) 的重播种【1 4 1 、变长种子( v a r i a b l e l e n g t h s e e d ) 重播种【1 5 1 以及动态的部分重播种( d y n a m i cp a r t i a lr e s e e d i n g ) t 1 6 ，1 7 】等方法。还 有一种技术是将硬件映射与重播种相结合的方法，用映射逻辑( m a p p i n gl o g i c ) 博 i 卅 或者位修订( b i t f i x i n g ) 2 0 】的办法，改变l f s r 产生的无用向量的若干位去检测那 些难测的故障。基于l f s r 重播种技术的测试向量生成器存在以下问题，如为减 少种子存储数而需要插入冗余向量，导致测试应用时间和测试功耗增加，并需要 额外的硬件开销存储种子，种子数和测试功耗之间存在着折中的关系。 作为测试向量生成器，c a 在理论和集成电路测试应用中已经被广泛深入的 研究。c a 被认为比l f s r 具有更好的随机性，作为b i s t 中测试向量生成器有可 能检测出一些l f s r 所不能检测的抗随机测试的故障【2 。 实际应用时，大多数采用的测试向量生成器是将l f s r 和r o m 技术结合起 来使用 2 2 , 2 3 】，以求得在性能和硬件开销方面的平衡。使用测试向量压缩技术将那 些确定性的测试向量进行压缩，使其达到对随机测试向量难于检测的故障进行检 测所需的最小数目是十分重要的。但就目前来看，测试应用时间长，测试功耗大 等问题仍然没有得到很好的解决。 基于遗传算法的测试生成在f p g a 上的研究与实现 1 3f p g a 开发概述 1 3 1f p g a 技术 f p g a 是英文f i e l dp r o g r a m m a b l eg a t ea r r a y 的缩写，即现场可编程门阵列， 它是在p a l 、g a l 、p l d 等可编程器件的基础上进一步发展的产物【2 4 1 。它是作为 专用集成电路( a s i c ) 领域中的一种半定制电路而出现的，既解决了定制电路的不 足，又克服了原有可编程器件门电路数有限的缺点。 自l9 8 5 年x i l i n x 公司推出第一片f p g a 至今，f p g a 已经历了二十多年的发 展历史。在这二十多年的发展过程中，以f p g a 为代表的数字系统现场集成技术 取得了惊人的发展。目前，国际上现场可编程逻辑器件的著名厂商x i l i n x 公司、 a l t e r a 公司又陆续推出了数百万门乃至上千万门的f p g a 芯片，将现场可编程器 件的集成度提高到了一个新的水平【2 5 1 。随着工艺技术的发展和市场需求的扩大， 超大规模、高速、低功耗的新型f p g a 不断推陈出新。新一代的f p g a 甚至集成 了中央处理器或数字处理器内核【2 6 1 ，在一片f p g a 上进行软硬件协同设计，为实 现片上可编程系统提供了强大的硬件支持。 f p g a 是由存放在片内r a m 中的程序来设置其工作状态的，因此，工作时需 要对片内的r a m 进行编程。用户可以根据不同的配置模式，采用不同的编程方 式。加电时，f p g a 芯片将e p r o m 中数据读入片内编程r a m 中，配置完成后， f p g a 进入工作状态。掉电后，f p g a 恢复成白片，内部逻辑关系消失，因此， f p g a 能够反复使用。f p g a 的编程无需专用的f p g a 编程器，只须用通用的 e p r o m 、p r o m 编程器即可。这样，同一片f p g a ，不同的编程数据，可以产生 不同的电路功能。因此，f p g a 的使用非常灵活。 由于f p g a 具有功耗低、体积小、集成度高、速度快、开发周短、费用低、 用户可定义功能及可重复编程和重复擦写等许多优点，它在通信、数据处理、网 络、仪器、工业控制、军事和航空航天等众多领域得到了广泛应用。随着功耗和 成本的进一步降低，f p g a 还将进入更多的应用领域。 1 3 2f p g a 设计方法 一个完整的硬件设计任务首先由总设计师划分为若干个可操作的模块，编制 出相应的模型，通过仿真加以验证后，再把这些模块分配给下一层的设计师，这 就允许多个设计者同时设计一个硬件系统中的不同模块，其中每个设计者负责自 己所承担的部分，而由上一层设计师对其下层设计者完成的设计，用行为级上层 模块对其所做的设计进行验证。自顶而下的设计是从系统级丌始，把系统划分为 基本单元，然后再把每个基本单元划分为下一层次的基本单元，一直这样做下去， 直到可以直接用e d a 元件库中的元件来实现为止。图1 4 为自顶而下的设计思想 6 硕士学位论文 示意图。与传统的设计方法相比， 自顶而下的设计方法有以下的优点： 系统设计 图1 4 自顶而下的设计思想 ( 1 ) 完全符合设计人员的设计思路，从功能描述开始，到物理实现的完成便 于设计、处理大规模、复杂电路； ( 2 ) 设计可再利用，易于设计的更改； ( 3 ) 设计周期缩短，生产率大大提高，产品上市时间提前，性能明显提高， 产品竞争力加强。据统计，采用自顶而下的设计方法的效率可达到传统设计方法 的数倍。 1 3 3f p g a 实现技术的优点 f p g a 的实现技术与软件的实现技术相比有很多的优点。软件实现技术即在 通用的计算上用c 、c + + 等编程直接实现算法。虽然用软件实现具有灵活、方便 可靠的优点，但是受其自身的局限性( 程序只能顺序执行) 速度太慢。由于f p g a 可编程的特点，它不但可以在芯片上实现大量的计算机算法，且可以按照算法的 需求将这些部件移植到芯片上去，比如图像压缩算法，数字信号处理算法，大部 分都是采用单片f p g a 作为实现方案。当然也有采用软硬件结合的方式来实现， 如计算较密集的部分采用f p g a 来实现，编码部分用d s p 芯片等来实现【27 1 。而 传统的a s i c 实现方法，由于实现成本太高，并且缺乏必要的灵活性，不能在系 统启动后进行再配置，严重地限制了它的应用。采用f p g a 实现技术的优势有： ( 1 ) f p g a 具有的硬件高速性，使得实现特定算法时，专用处理单元的速度能 够获得很大幅度的提高，加上结构的可灵活调整，保证算法高效的运行； ( 2 ) f p g a 是按数据流方式进行编程的，可以将所设计的系统直接移植到芯片 上。这种方式比将其转化为按指令的顺序流编程的d s p 代码更加的容易； ( 3 ) f p g a 能够实现数字信号处理算法、图像压缩算法等所需的大量计算机算 法，这些算法可以利用供应商提供的内核来实现，这样能够使算法快速的实现； ( 4 ) f p g a 的各种设计工具可以让设计者在速度和面积资源之间做出平衡，提 7 基f 遗传算法的测试生成在f p g a 的研究与实m 高系统设| + 的性价比。 基于f p g a 实现技术的这幽优点，并使用q u a r t u s l i 丌发平台和m o d e l s i m 仿 真工其，整个设计采片j 硬件描述语言v h d l 描述，本文没冉采用# 他芯片束脚助 完成，而是直接在单片f p g a 芯片上实现了基于遗传算法的测试生成方法。图15 为本文所用的硬件丌发板。板上嵌入的足f p g a 芯片是a l t e r a 公司的s t t i 系列 的e p ls 4 0 f 1 0 2 0 c 5 芯片。 图15 硬件开发板实物图 i 4 论文主要工作及组织结构 f p g a 芯片 奉课题展开的研究受到了国家自然科学基金项目r 项目编号：6 0 7 7 3 2 0 7 ) “由 被测电路自己产生测试向量的内建自测试技术研究”的资助，幸要工作有： 本文分析了当前土流的测试向量，+ 成器技术，针对这些设计技术的缺点，着 重研究了一种由被测电路自动生成测试向量的测试生成方法。该方法的关键是如 何在较短的时问内找出蛙佳的反馈方式 测试向量长度下检测出尽可能多的故障 最佳的反馈方式。 醵反馈方式生成的测试集能够在较短的 并采用遗传算法进行适应性搜索以寻求 针对较大规模的电路，若采用软件实现泼打法往往在速度上受到本质是串行 的计算机系统的制约，需要过长的时间，甚至导致无法实现。所以，在充分考虑 f p g a 结构特点的情况下，本文设计并在f p g a 上实现了一种基于遗传算法的测试 生成的方法。本文从系统结构设计、遗传算子模块、适应度模块、控制模块等方 向，详细说明了浚系统的设计思恕和实现方案，并对关键模块进行了优化，整个 硕士学位论文 系统采用流水线设计提高了时钟频率，选择模块和适应度模块采用并行化的设计 方案，大大提高了系统的运行速度。通过b e n c h m a r k8 5 基准电路作为被测电路的 功能测试和性能分析，证明了所设计的硬件系统能够在较短时问内寻找到一种较 好的反馈方式，该反馈方式所确定的测试集能在较短的向量长度下达到较高的故 障覆盖率，与软件实现相比较要快2 3 个数量级，充分体现了硬件实现的速度优势。 所设计的系统由于采用反馈方式生成的测试集能检测到故障总数作为适应度 函数，因此，本文设计并实现了一种具有故障选择和故障摘除功能的硬件故障模 拟器。所设计的故障模拟器采用存储器存储故障编码的方式来存储故障列表，并 用故障注入单元进行故障注入，与故障选择译码器和存储器模块相结合，实现了 故障选择和故障摘除功能。通过b e n c h m a r k8 5 基准电路作为原始电路的功能测试 和性能分析，证明了所设计的故障模拟器占用较少的硬件资源，并可以在较高时 钟频率下运行，测试结果表明，与h o p e 相比大大减少了故障模拟的时间。 本文共分5 章，后4 章的主要内容以及组织结构如下： 第2 章主要介绍数字集成电路测试和遗传算法的基本理论，包括测试基本原 理、故障、故障模型、以及遗传算法的相关知识等。在此基础上，介绍了将遗传 算法应用到测试生成方面的一些研究成果。在这一章的最后，深入分析了当前遗 传算法硬件化技术。 第3 章以i s c a s 8 5 基准电路中的c 1 7 电路为例，详细介绍了本文着重研究的 测试向量生成方法的基本原理和具体的实施过程。深入研究了遗传算法的结构， 在f p g a 上实现基于遗传算法的自动测试生成方法。主要包括系统的总体框架设 计及选择模块、交叉变异模块和适应度模块等功能模块的设计思想和实现方案。 第4 章对故障模拟器原理和功能进行了深入分析，详细介绍了基于f p g a 的 故障模拟器的实现方法，包括故障注入单元、控制模块、存储模块等功能模块的 设计思想和实现方案。 第5 章分析了本文所设计的系统及各模块的功能测试及性能分析结果。 9 基于遗传算法的测试生成在f p g a 上的研究与实现 第2 章数字集成电路测试和遗传算法基本理论 随着超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t ，v l s i ) 的发展以及 “纳米 时代的到来，现在v l s i 技术的复杂度已经可以在单芯片上集成上亿个 晶体管，同时工作频率可以达到g h z 的数量级，越来越多的新技术应用到生产中。 集成电路中平均每个芯片输入输出的管脚上集成的门数从几个增加到几百个，甚 至更多，较大的v l s i 和专用集成电路不仅包含随机逻辑，同时也包括r a m 、 r o m 、p l a 、数据通道、多路转换器和像微处理器那样复杂的宏单元，电路变得 日益复杂，使得芯片的测试也越来越困难。随着大规模集成电路技术的飞速发展， 数字集成电路己经应用于各行各业，因此集成电路的测试具有重要的理论价值和 现实意义。 另一方面，鉴于遗传算法在解决系统优化计算的方面的成功应用，在过去的 几年中，国外的一些学者提出了基于遗传算法的测试生成方法【2 舡3 1 1 ，该类方法作 为目前的优化类方法之一，受到了众多学者的关注，目前己成为集成电路测试生 成领域内的热门研究课题之一。当前遗传算法的硬件化技术研究也在不断的发展， 大大提高了算法的运行速度。 本章主要介绍了数字集成电路测试和遗传算法的相关内容。首先简单地介绍 了测试基本原理、基本概念、故障和故障模型等数字集成电路测试的基础知识。 然后介绍了遗传算法的基本原理，在此基础上，介绍了将遗传算法应用于测试生 成技术，最后简述了国内外遗传算法的硬件化技术的研究情况。 2 1 数字集成电路测试基础 2 1 1 基本原理 在数字集成电路的设计、制造和应用阶段，不可避免的会出