（计算机系统结构专业论文）基于寄存器传输级层次模型的测试生成研究.pdf

基于寄存器传输级层次模型的测试生成研究：摘要 摘要 集成电路( h l t e 蓼a t e dc i r c m t ，简称i c ) 的设计验证和测试是确保数字系统正常工 作的必要手段。无论是设计验证还是芯片测试，测试生成都作为其主要内容而被广泛关 注。本文首先综述了集成电路的测试和设计验证的基本原理和方法；其次针对设计所采 用的寄存器传输级( r e o s t e rt r a n s f c rl e v e l ，简称r t l ) 行为描述方式，介绍了若干已 有的高层次测试生成方法；最后提出了一种可行的r t l 级测试生成算法，所产生的测 试序列可有效地应用于电路的功能测试或设计验证。 本文工作贡献主要有以下三个方面： 1 建立了一种有效的r t l 行为模型。 本文从电路的控制结构和数据路径两方面出发，建立了电路的控制流图和数据流图 两层次模型：第一层通过控制流图反映电路语句间的连接关系；第二层通过控制流图中 的每一结点所对应的数据流图，反映语句的具体操作。该模型实现了对电路的分层描述， 相对于以往的电路模型具有形式简单、规模小、易于处理的优点，便于根据测试的具体 需求处理相应的模型层次，从而降低处理复杂性，提高系统效率。此外，该模型具有良 好的通用性，基于该模型可进行电路模拟、测试生成、验证等操作。 2 制定了一种语句可测性测度。 为了能更好地把握语句执行，本文从语句的功能实现和执行时序两方面出发考虑语 句性能，定义了静态时序深度和动态时序深度概念，分别度量语句的功能实现和执行时 序，并给出了相应算法。由此将语句执行的横向、纵向相结合反映电路性能，为高层次 测试生成提供了方便。 3 提出了一种基于测试用例的r t l 级钡8 试生成方法。 本文基于控制流图数据流图两层次模型，以分支覆盖、位功能覆盖以及语句可观 覆盖为目标，给出一高层次测试用例生成算法，即通过两个子过程的交替进行生成电路 的测试角例块。并在此基础上，采用定填充策略填充未知位，生成满足覆盖需求的、 一定长度的测试序列，实现测试生成a 实验数据表明，本文测试生成系统的执行时间相对于基于遗传算法的r t l 测试生成 p 6 n c e 系统、基于电路结构的无回溯的t i d e 系统均有所缩减，且可生成较短的测试序 列，获得与其它方法相当或略低的门级固定型故障覆盖率；此外由于该方法采用了测试 用例技术，可通过不同的用例填充、组合方式得到不同的测试序列，从而具有良好的可 扩展性。 关键词：集成电路，自动测试生成，寄存器传输级，测试用例 墨王堂壁墨堡塑堑堡姿堡型塑塑塑生壁堕塞：垒! ! 巡 t e s tg e n e r a t i o nb a s e do n h i b e r a r c h ym o d e l a tr e g i s t e rt r a n s f e rl e v e l g a o y a h ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db yp r o f s h e nl i a b s t r a c t d e s i g nv e r i f i c a t i o n a n dt e s to fi n t e g r a t e d c i r c u i t s ( i c s ) a r en e c e s s a r yt e c h n i q u e st o g u a r a n t e et h ev a l i d i t yo fad i g i t a ls y s t e m t h e r e i n t ob e i n gap r i m a r yp a r to ft h e m ，t e s t g e n e r a t i o ng e t sb r o a da t t e n t i o n t h i sd i s s e r t a t i o nf i r s t l ys u m m a r i z e st h et h e o r ya n dm e t h o do f t e s ta n d v e r i f i c a t i o n ；s e c o n d l yi n t r o d u c e ss o m eh i g hl e v e lt e s t i n gm e t h o d sa tr e g i s t e rt r a n s f e r l e v e l ( r t l ) ；l a s t l yd e s i g n saf e a s i b l er t l t e s tg e n e r a t i o nm e t h o dw h i c hc a n g e n e r a t eu s e f u l t e s ts e q u e n c e sf o rf i m c t i o nt e s to rv e r i t c a t o n t h e o r i g i n a li d e a sa r ee x p l a i n e da sf o l l o w ： 1 c r e a t i n ga n e f f e c t i v er t lb e h a v i o r a lm o d e l b a s e do nt h ec o n t r o ls t r u c t u r ea n dd a t ap a t ho fc i r c u i t s ，ad e wt w o l e v e lr t lm o d e li s r e p r e s e n t e d ，t e r m e dc o n t r o lf l o wg r a p l 佃a t af l o wg r a p h ( c f g d f g ) a tt h ef i r s tl e v e l ，t h e c o n n e c t i o no fs t a t e m e n t si se x p r e s s e d b yc f g ；a t t h es e c o n dl e v e l ，t h ed e t a i lo fas t a t e m e n ti s e x p r e s s e db yi t sd f g t h u st h em o d e lr e a l i z e st h eh i b e r a r c h y d e s c r i p t i o no fc i r c u i t s ，w h i c h b e n e f i t ss i m p l ef o r m ，s m a l ls i z ea n df a c i l eo p e r a t i o nc o m p a r i n gw i t ho t h e rm o d e l s haw o r d ， i tn o to n l yc a nd e c r e a s et h ec o m p l e x i t ya n di m p r o v et h ee f f i c i e n c ya c c o r d i n gt op r a c t i c a l s i t u a t i o n ，b u ta l s oc a nb eu s e d i ns i m u l a t i o n ，t e s t i n ga n dv e r i f i c a t i o nu n i v e r s a l l y 2 d e f i n i n g a t e s t a b i l i t ym e a s u r eo f s t a t e m e n t t oe x e c u t es t a t e m e n t sr i g h t l y , s t a t i cs e q u e n t i a ld e p t ha n dd y n a m i cs e q u e n t i a ld e p t h a r ed e f i n e db a s e do nt h ef u n c t i o na n de x e c u t i o ns e q u e n c eo fs n t e m e n t s a tt h es a m e t i m e ，t h e c o r r e s p o n d i n ga l g o r i t h m s a r ep r e s e n t e dr e s p e c t i v e l y b a s e do i lt h et e s t a b i l i t ym e a s u r e ，a p e r f o r m a n c e o fc i r c u i tc n nb er e f l e c t e d h o r i z o n t a l l y a n d v e r t i c a l l y w h i c h p r o v i d e s c o n v e n i e n c ef o rr t lt e s tg e n e r a t i o n 3 p r e s e n t i n g ar t la t p g a l g o r i t h m b a s e do l lt e s t c a s e a i m e da tb r a n c hc o v e r a g e ，b i t f u n c t i o nc o v e r a g ea n ds t a t e m e n t o b s e r v a b i l i t yc o v e r a g e m e a s l e s ，ag e n e r a t i o nm e t h o do fh i 曲l e v e lt e s t c a s ei sr e p r e s e n t e du s i n gc f g d f g m o d e l t h o u 咖t h em e t h o d ，ab l o c ko f t e s t c a s ec a nb eg e n e r a t e db ye x e c u t i n gt w os u b p r o c e d u r e s a l t e r n a t e l y t h e nu s i n gs o m ei n p u tm e a s u r e ，t e s ts e q u e n c eo f ac e r t a i nl e n 舀hc a l lb eg o t t e n ， w h i c hr e a l i z e st h et e s t i n gw h o l l y 基于寄存器传输级层次模型的测试生成研究：a b s t r a c t e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e da t p gm e t h o dc a nd e c r e a s et h ec p u t i m e c o m p a r i n gw i t h t h eg e n e t i c a l g o r i t h m b a s e dr t l a t p g ( p r i n c e la n dt h eb a c k t r a c k f l e e r t l a t p g ( t i d e ) ，i tc a l lg e n e r a t et h el e s st e s ts e q u e n c ea n dg e tt h ec o m p a r a t i v eo rl e s s r e s u l t so f g a t e l e v e ls t u c k a tf a u l tc o v e r a g e f u r t h e r m o r e ，b a s e do nt e s t c a s e ，t h en e wm e t h o d c a ng e td i f f e r e n tt e s ts e q u e n c e sb yd i f f e r e n ti n p u t i n gm e a s u r e so fx _ b i to rd i f f e r e n tb u i l t u p w a y so f t e s t c a s e ，t h u si th a sag o o de x p a n s i b i l i t y k e y w o r d s ：i n t e g r a t e dc i r c u i t so c s ) ，a u t o m a t i ct e s tp a t t e mg e n e r a t i o n ( a t p g ) ，r e g i s t e r t r a n s f e rl e v e l ( r t l ) ，t e s t c a s e 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 十 作者签名： 局娈曼 日期：z 鲫o ，2 腭 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名：高熬导师签名：渺l 日期： 2 鲫 2 、，孑 第一章引言 1 1 研究背景 第一章引言 随着二十世纪六十年代初第一块集成电路( i n t e g r a t e dc i r c u i t ，简称i c ) 的诞生， 集成电路技术以惊人的速度、迅速地蓬勃发展起来，它不仅极大地改变了人们的生活水 平，同时也带动了信息技术、电子技术等相关领域的发展。其发展速度正如1 9 6 5 年i n t e l 公司创始人之一的g o r d o nm o o r e 所预计的那样：芯片的容量每1 s 个月增加一倍。这就 是著名的m o o r e 定理，按照这一推理发展下去，计算能力将在个较短的时间内呈指数 规律增长。虽然许多物理学家曾预言过集成电路发展的极限，以试图说明m o o r e 定理的 局限链，但至今为止这一趋势一直延续著保持着其正礁性。 伴随着集成电路的飞速发展，人们对电路产品可靠性的需求也与日俱增。为了确保 数字系统的正常工作，就必须对集成电路进行充分的测试，这包括对其设计的验证 ( v a l i d a t i o no rv e r i f i c a t i o n ) 和对电路芯片i c 的测试( t e s t ) 两部分内容。自二十世纪 六十年代国外学者就开始了对集成电路验证、测试问题的研究，到七十年代初期国内也 逐渐着手相关的工作。 在诸多科研工作者的不懈努力下，经过几十年的发展，电路设计验证和测试方面的 知识由无到有、由不成熟到今天的日渐丰富，其中不乏许多成熟的研究成果应用于工业 实践，这都表明集成电路的发展己取得了巨大的进步。但在实际应用中，集成电路验证 和测试技术的发展总是相对滞后于电路设计和生产技术的发展。且2 0 世纪9 0 年代以来， 在市场的驱动下，不断的推出性能高、功能多、可靠性高、成本低、开发周期短的集成 电路( i c ) 产品，并预计到2 1 世纪前十年将进入到纳米技术和系统芯片( s o c ) 时期。 此外，电子技术的不断革命使得i c 测试费用在i c 产品成本中所占的比重愈来愈高，乃 至高于制造成本，从而寻求验证、测试的新方法、新技术，缩小与设计技术间的差距势 在必行，得蜀了学术界和工业界的极大关注。 在工业界，具体到芯片的整个生存周期，从最初的需求分析阶段一直到最后芯片的 生产、应用，验证或测试无处不在。一般验证包含两部分内容：一是指设计和需求之间 一致性的检验( 称为v a l i d a t i o n ) ，旨在判剐设计是否符合需求以及判别需求自身的完善 性、是否存在遗漏；其次指检验不同设计形式的一致性，以保证最初设计思路的贯彻执 行。只有通过了严格的验证，芯片方可以进入生产阶段。而测试就是面对生产阶段，尽 可能的检测出具有故障或缺陷的芯片，以保证电路产品的质量。最后只有经过严格测试 判为无误的芯片才能进入应用阶段，流入市场。 为了减少验证和测试的代价，在保证芯片质量的前提下缩短芯片的生存周期，可验 证性设计( d e s i g nf o rv e r i f i c a t i o n ，简称d f v ) ( b e n i 0 0 和可测性设计( d e s i g nf o r 1 中国科学院博士学位论文基于寄存器传输级层次模型的测试生成研究 t e s t a b i l i t y ，简称d f t ) b u s h l 0 0 应运而生。可验证性设计是在硬件描述语言( h a r d w a r e d e s c r i p t i o nl a n g u a g e ，简称h d l ) 产生后被提出的，主要针对电路的高层次描述形式， 通过套设计规则规范设计人员的设计，从而使设计出的电路便于进行验证。但此项技 术因受制于通用的设计规则而般难以应用。 与此同时，可测性设计相对而言发展已比较成熟，有诸多实际可用的技术，如测试 点插入( t e s t p o i n t i n s e r t i o n ) w i l l y 7 3 、扫描设计( s c a n d e s i g n ) e i c h b 9 1 】 w i l l w 8 2 】、 内建自测试( b u i l t i n - s e l f - t e s t ) a g r a v 9 3 a g r a v 9 3 b k o e n b 8 0 、边界扫描( 国际标准 i e e e l l 4 9 1 ) l e e e 9 4 p a r k p 9 8 等。可测性设计以增加芯片的硬件开销，如面积、性能、 功耗等为代价，在一定程度上简化了测试、降低了测试代价，对于解决实际应用中的测 试难题，具有很好的应用前景，得到了工业界的广泛采用。因而，如何进一步提高可测 性设计的效率、降低硬件开销一直作为可测性设计的重点问题被密切关注。 无论是验证还是测试，测试生成都是其主要内容，其中自动测试生成( a u t o m a t i c t e s t p a t t e r n g e n e r a t i o n ，简称a t p g ) 即自动地生成电路的输入激励( 向量或序列，v e c t o ro r t e s ts e q u e n c e ) ，它是进行测试的必备条件。关于测试的具体实现，可从电路功能，电路 结构等方面考虑。从功能角度出发，一种最直接的方法就是穷举测试法( e x h a u s t i v e t e s t i n g ) ，即对电路所有的输入情况做测试，以检验电路功能的正确性。虽然此方法在 测试小电路时有良好效果，但对于具有庞大输入空间的大电路而言是不适用的，从而人 们提出了若干基于电路结构的测试方法。 我们知道测试生成本身是个n p 完全问题 f u j i i - 1 8 2 i b a r h 7 5 1 ，算法的执行效率一直 是人们所追求的目标，从电路结构出发，已有若干成熟的技术可确保获得一定的测试效 率，如d 算法 r o t h p 6 6 r o t h p 6 7 ，f a n 算法 f u j i h 8 3 等，这些算法都因其良好的性能 在工业界得到了广泛应用。虽然组合电路的测试技术发展己相对成熟，但时序电路由于 其内在的结构特点而难于测试 m i z c 0 8 3 ，测试效率低。通常对于时序电路，我们通过可 测性设计来辅助提高测试效果，但可测性设计并不能检验芯片性能等方面的故障，即不 能产生针对芯片功能的测试向量，所以一般需要结合一定的功能测试来共同完成此类芯 片的测试任务。所以无论采用何种测试技术，针对电路自身的测试生成必不可少。 同时，针对电路自身的测试生成对设计验证而言也是不可缺少的。对于针对需求确 认的验证v a l i d a t i o n ，只有通过对设计进行模拟( s i m u l a t i o n ) 和仿真( e m u l a t i o n ) 的方 式进行检验。这就需要一定的源于电路本身的测试向量，在定的工作平台上对其进行 多次操作，直至达到一定的结果。而针对设计正确性的验证v e r i f i c a t i o n ，主要包含两大 类：形式化方法和基于模拟的方法。其中形式化验证方法虽不需要验证的测试用例或向 量，是一种理论上的完全方法，但在具体应用时，由于计算复杂性过高，而仅能处理小 规模电路，适用范围小。通常设计验证采用基于模拟的方法，通过测试向量对设计进行 模拟或仿真，即是将测试同时输入被测模型( m o d e lu n d e rt e s t ) 和参考模型( r e f e r e n c e m o d e l ) 一并做模拟，比较二者运行结果以发现错误的模拟对比过程。此法多采用直接 第一章引言 手动或随机的方式产生激励数据，虽简单易行却检测不到大多设计错误，从而验证覆盖 率低、效果差。因此无论是针对需求确认还是针对设计正确性验证，如何生成测试将直 接影响验证效果的好坏。 所以无论是从集成电路发展的大局考虑，还是从具体方法可行性的细节考虑，测试 生成具有不容忽视的作用。本文就围绕电路的测试，主要讨论时序电路的测试生成问题。 1 2 研究现状 经过研究者们几十年的努力，电路的测试技术得到了快速的发展，测试生成算法多 种多样，从不同的角度出发，便会有不同的划分方式。其中按照电路的结构特点划分， 有组合电路测试和时序电路测试两种。目前组合电路的测试理论已发展比较成熟，若干 研究成果已转换为产品投入到实际应用中；而时序电路不仅存在初始化问题 ( c h e n t 9 1 m u t h p 7 6 】，而且因其电路输入具有时序性，当前状态由当前输入和以往输入 共同决定，从而使得测试生成难以实现 a b r a m 9 4 1 。 若从电路整体来看，功能测试( f t m c t i o n a lt e s t ) 不必考虑电路的具体结构，通过对 电路功能的检测，以确保电路操作与其描述的对应。其最简单的方式就是穷举测试 ( e x h a u s t i v e 钯s f i n g ) ，即对电路的初级输入组成的输入空闻做检测。虽然此方法易于理 解，但对实际电路而言很难实现空间的穷举。 通常电路故障仅存在于电路内部，故障电路相对于正常电路丽言，一般只存在部分 差异的情况下保持大部分电路功能的一致，并不是完全不同。因而结构测试即是在假设 设计正确的情况下，通过检测电路结构，以发现生产所造成的电路故障。 结构测试一般要对电路故障模型化，基于模型化后得到的电路故障，测试变得相对 简单、易实现。而故障模型的定义方式种类繁多，其中最通用的一种是门级的固定型故 障模型( s t u c k a t f a u l t m o d e l ) a b r a a 8 6 c h e n t 9 9 h a y e p 8 5 ，它不仅能较好的反映电路 实际故障，而且由其生成的测试序列对单故障、多故障 h u g u a 8 4 h u g h a 8 6 t i m o c 8 3 乃至其它类型故障 m e i y c 7 4 m i l l d s 8 都有很高的故障覆盖率( f a u l tc o v e r a g e ) ，还能切 实检测芯片的物理缺陷。为了便于测试生成，在此基础上又提出了单固定型故障( s i n g l e s t u c k a tf a u l t ，简称s s f ) 概念，并产生了一系列相关的测试方法。 对于具体的测试算法，从电路的时序方面考虑，有组合电路测试生成和时序电路测 试生成两部分内容。 组合电路指的是没有时钟信号的电路，通常易于测试。在组合电路测试发展历程中， d 算法是第一个完全算法 r o t h p 6 6 r o t h p 6 7 ，它是在d 立方和立方代数的基础上，针 对一给定故障，通过故障激活( a c t i v a t e ) ，保证输入向量和中间信号一致的同时，将故障 效应( f a u l te f f e c t ) 传播到电路输出的一种路径敏化( p a t hs e n s i t i z a t i o n ) 方法。d 算法 串霉科学院博士学位论文基于毒存器传输蔹层次模型豹测试生成研究 对于可测故障，总能找到相应的测试；而对于不可测故障，总能判定其为不可测。 尽管d 算法在理论上已经完善，但在具体应用时，由于d 算法的实现过程是对由 所有电路线为分量所组成向量空间的搜索过程，因而其执行效率随着电路规模的增大而 下降 f u j i h 8 5 。同时，在算法执行过程中，故障效应传播所涉及的选择随意性也大大降 低了算法的执行效率，影响了算法的实现。继而出现了主路径敏化法魏7 8 1 魏8 2 哥d 九 值算法f m u t k p 7 6 对选择的随意性做了改进。尽管如此，以上方法仍是搜索的以电路节 点为坐标的布尔空间，必然会由于回溯的存在而降低效率。 1 9 8 1 年，基于n 个初级输入变量构成的n 维向量空间的p o d e m 算法首次被提出 g o e l p 8 1 。由于初级输入相互无关，相对于d 算法中相互关联的布尔空间搜索，p o d e m 算法缩小了空间搜索范围，减少了回溯的次数。同时，p o d e m 算法运用隐式枚举( i m p l i c i t e n u m e r a t i o n ) 和分支限界( b r a n c h a n d b o u n d i n g ) 法优化搜索过程，即在搜索的过程中， p o d e m 算法运用“回退( b a c k r a c e ) ”动态确定输入变量的判定顺序；运用“蕴涵”判别 非解空问，对判决树进行剪枝。总之，p o d e m 算法通过逐个确定初级输入值的策略为 给定的故障产生测试，减少了盲目试探和回溯，是一个效率较高的完全算法。 虽然p o d e m 算法没有给出一个有效的初级目标选择策略，但在p o d e m 算法以后， 基于输入空间搜索的测试产生算法和技术就成为了面向故障确定性测试方法的主要研 究方向，相继出现了一系列的测试算法。其中f a n 算法 f u j i h 8 3 1 是最为成功的一例， 它是在p o d e m 算法的基础上，针对输入空间的搜索以及回溯做了很多的优化，引入了 头线( h e a d l i n e s ) 概念，以及立即蕴涵、唯敏化、多路回退等策略。事实证明，实行 有效的剪枝技术明显减少了国溯的次数，提高了测试生成的效率。 f a n 算法后，人们在利用电路结构信息的基础上又提出了若干新算法：如能加速信 号立即赋值的t o p s 算法 k i r k t 8 7 ：基于静态学习和动态学习知识的s o c r a t e s 方法 s c h h 8 8 s c h h 8 8 b s c h u h 8 9 ：通过局部敏化避免大量搜索的s a b a t p g 方法 李9 3 ； 以及运用蕴涵图建模逻辑门级行为的n n a t p g 算法 c h a k t 9 0 c h a k t 9 1 1 ，t r a n 算法 a d v a c 0 0 c h a k t 9 3 等都实现了对搜索的优化，进一步提高了算法效率。 除了以上介绍的面向故障的确定性测试方法之外，还有非确定性的方法，此类方法 不是针对某一具体故障做测试，而是针对多个故障以同时产生可检测一故障集的测试集 为目标，其中临界路径法( c r i t i c a l p a t h ) 是此类方法的一个典型范例，这里所谓的临界 是针对信号线的取值而言的。该方法就是从每个输出线出发，运用临界立方( c r i t i c a l c u b e ) r a b r o m 9 0 反向回退并确定输入线值，最后得到相应故障的测试向量，虽然不是 一完全算法，但也有一定的应用价值。 时序电路比组合电路要难测的多，虽然已进行了诸多研究，得到了许多测试方法， 但始终由于时序电路自身的特殊性而难以应用于实践中，其中比较常用的方法有：时间 帧扩展法( t i m e f r a m ee x p a n s i o nm e t h o d ) k u b o h 6 8 p u t z r 7 1 】和基于模拟的方法 4 第一章引言 ( s i m u l a t i o n - b a s e d m e t h o d ) a g r a d 7 2 b r e u a 7 1 。 基于时间帧扩展法源于将组合电路的a t p g 算法应用于时序电路的测试产生，通过 把时序电路按时间帧展成一个大的组合电路，然后借助于组合电路的测试方法做测试生 成。所谓按时间帧展开，对于同步电路即是把时序电路一个时钟周期的动作看作组合电 路的次动作，而把它在连续多个时钟周期的动作看作一组合电路多次动作的连接，从 而可看为多个组合电路的连接，电路规模以单个组合电路规模为基数进行扩展，随时间 帧扩展的倍数增大。此方法需要设定第一帧的状态输入，即在测试生成之前初始化电路 状态，实际处理此问题时，一般是由时序电路的复位输入完成。但是对于大规模电路而 言，庞大的搜索空间直接影响此方法的效率，注定了其有限的适用范围。 就时间帧扩展法的具体实例而言，有通过限定每个故障的测试时间，放弃难测故障 而提高执行效率的g e n t e s t 方法 b e n c r 9 1 c h e n t 8 9 1 ；有将帧的正、反扩展相结合， 分别做故障激活和故障效应的传播，并运用并行故障模拟器模拟，可得到较高故障覆盖 率和系统效率的h t t e c 方法 n i e r m 9 1 j 。 相对而言，基于模拟的方法避免了时间帧扩展法所带来的庞大搜索空间，它在满足 一定准则或度量函数的前提下，通过模拟的方式选出好的测试向量加入到测试序列，逐 步完成测试任务，其中如何得到初始选择向量、如何制定评价准则是其关键内容。此类 方法的最大优点在于：经过模拟，可确定一向量为测试向量。 目前，大多采用随机生成初始选择向量，并运用故障模拟器判断序列质量 b r e u a 7 1 s c h u m 7 5 的非确定性方法，此类方式虽然简单易行，但却因随机性过高而效 率不高。此外，通过评价函数构造初始向量的方法，在一定程度上提高了执行效率。而 不同的系统有不同的评价函数，应用最多的还是通过遗传算法( g e n e t i ca l g o r i t h m ) 的 自适应函数( f i t n e s sf u n c t i o n ) 优化选择向量 g o l d e 8 9 s a a b g 9 6 】。 遗传算法是种应用广泛的优化算法m a z u p 9 9 r u d a m 9 7 ，在硬件的测试生成中 p r i n p 9 4 r u d n m 9 4 s h e n l 9 9 s r i n m 9 3 ，它在确定最初的样本序列后，运用模拟和自适 应函数评估向量质量，周而复始的在已有序列的基础上提高序列质量，并最终得到测试 序列，其中自适应函数的定义对算法效率起着关键性作用。虽然运用遗传算法能有效实 现向量选优，并快速生成新样本，但大量的故障模拟却使得该算法的时间代价过高。 基于模拟的测试生成方法可应用于组合或时序所有电路类型，其最大的优点就是可 以处理时序电路，尤其是异步时序电路( 由于不可忽略异步电路信号的时间信息，因而 时闰帧扩展法一般难以实现) 。因而对于基于模拟的方法，任何电路可被模拟测试，具 有广泛的应用，且遗传算法在此类方法中得到了最好的应用。 就i c 设计技术而言，2 0 世纪8 0 年代前，主流技术是电路图描述和门级设计；9 0 年代后逐步向硬件描述语言( h d l ) 和高层次综合( h s l ) 过度，但是测试技术包括测 试向量自动生成( a t p g ) 和可测试性设计( d f t ) 大多仍基于门级，不论是组合电路 中国科学院博士学位论文基于寄存器传输级层次模型的测试生成研究 还是时序电路，大多成熟、稳定的测试方法都是在门级或较低的级别上进行的。因此为 了与高层次设计保持同步，对高层电路进行测试设计是必不可少的；同时高层描述方式 相对原来的门级描述，描述规模小，可尽早的考虑测试生成，减少测试生成时间。就这 样，高层次测试生成得到了越来越多研究者的关注，并取得了部分研究成果 m i c h d 9 0 p f i n p 9 4 b r a m a s 9 4 y a d a s 9 5 】。 由于寄存器传输级( r e g i s t e rt r a n s f e rl e v e l ，简称r t l ) 相对门级而言描述简洁， 缩小了电路的描述规模；能更好的体现电路特性( 如时钟信息) ，并可借用工具软件实 现综合，在此描述方式下易于对电路进行处理、分析，从而r t l 作为一种高层描述方 式被设计者广泛应用于实际的系统设计中，所以相应的高层测试生成也应在此r t l 描 述方式下进行。与门级测试类似，高层测试也有确定性测试和非确定性测试两大类。 确定性测试，即面向某一故障，对于可测故障生成测试向量，否则对于不可测故障 必需明确判为不可测。目前高层次的确定性测试方法仍很欠缺，大多研究属于非确定性 的测试，从不同的角度出发可得到不同的方法，具体包含以下几种： 1 电路层次化测试方法。 这里所说的层次指的是电路描述上的层次结构，其基本思想是 a b a d s s 5 d e y s 9 8 【m a k r y 9 8 m a k r y 0 0 ：通过把个大电路划分成若干子功能模块，先对每个功能模块做 局部测试生成，然后将局部测试翻译成全局测试以满足由电路的初级输入测试电路功能 的目的。 2 基于电路功能的测试方法。 基于电路功能的测试方法一般从电路的功能实现出发，首先将电路的描述由硬件描 述语言描述转化为其他的描述方式，继而通过定的策略( 故障模型、覆盖准则等) 进 行测试产生。 如：f c h e n t 9 6 实现了电路由v h d l 描述到扩展有限状态机( e x t e n d e df i n i t e s t a t e m a c h i n e ，简称e f s m ) 的转换，并在此基础上生成了可覆盖每一高层描述语句至少一 次的功能向量，此向量可应用于设计验证、生产测试或功耗估计。而中科院计算所的 l i 在状态机的基础上对状态进行了聚类 l h u a w 0 1 l h u a w 0 2 】，在行为阶段聚类描述 ( b e h a v i o r a lp h a s ec l u s t e r i n gd e s c r i p t i o n ) 的基础上建立了行为阶段转换故障模型，并 由此给出了基于聚类的测试算法。 3 基于电路结构的测试方法。 此类方法是从电路的行为描述出发，在一定内部模型的基础上，对电路故障模型化， 针对故障做测试生成。它与门级的测试方法相似，也包括激活故障，敏化故障，将故障 效应传至输出，从而得到电路的测试序列。 如文献 g h o s l 0 1 中就是借用门级的测试方法，在高层次综合后得到的赋值判决图 6 第一章引言 ( a s s i g n m e n t d e c i s i o nd i g r a m ) 的基础上将r t l 行为描述结构化，分析电路节点的可控 性和可观性，利用门级的激活故障、敏化故障等概念，对r t l 元素做测试、求向量， 然后按照元素间的关系做连接得到整个系统的测试。 4 基于模拟的方法。 简单地说，就是通过采用一定数量的向量对电路进行模拟，根据模拟结果选择、确 定最后测试序列的方法，其中，随机生成模拟向量是最简单的生成方式，此方式虽方便 快捷，但一般模拟效果不好；通常采用一定的策略指导模拟向量的生成以保证测试序列 的质量。目前对于高层次测试来讲，应用最多的是利用遗传算法对向量进行筛选、优化 c o m f 9 6 】 c o m f 9 6 b c o r n f 0 0 b c o r r t f 0 1 ，以确定最终的测试序列。 5 基于软件测试的方法。 利用硬件描述语言与高级语言的相似性，可将软件测试方法用于硬件测试生成中。 从大方面看，软件测试的“黑盒法( b l a c k b o x ) ”、“白盒法( w h i t e b o x ) ”与硬件测试的 中的“功能测试”、“结构测试”相似，同时软件测试的“灰盒法( g r a yb o x ) ”，也对应 于硬件测试中功能测试和结构测试的混合形式。从具体算法角度看，已有若干文章借用 了软件测试中的语句覆盖 c o m f 9 7 c o m f 9 9 、分支覆盖 c h i u s 9 8 c h i u s 9 9 c h i u s 9 9 b 、 语句及部分路径覆盖 r u d n m 9 8 等策略，但大多执行效率低或没有完全实现系统的自动 化。 以上各类方法之间是可以相互交错、结合的，没有明确的界限划分，如：可将满足 一定覆盖规则的测试向量作为初始模拟向量，利用遗传算法，模拟得到测试序列。但总 的来说高层次测试生成方法的研究还处于起步阶段，仍没有较为通用的策略，且研究结 果距离工业界的实际应用还有很大的差距，其中时序电路的测试问题尤为突出，处理上 难度较大。正是由于高层次测试仍存在诸多未解决的问题，从而吸引了大量的研究人员 投入到此领域的研究。 总之，将测试技术向高层次推进，提高测试的效率已成为测试技术发展的必然要求， 具有极重要的理论价值和实际意义。 1 3 论文的主要内容 为了适应电路高层次测试发展的需要，寄存器传输级即r t l 级测试作为测试领域 中的一个新兴方向正在不断地发展壮大。纵观电路设计的描述层次，r t l 级描述比传统 的门级描述抽象、规模小：且对于更高的级别( 如算法级) 则描述相对具体； r t l 级 同时还具有便于综合的特性，因而面对当前大规模的电路设计，r t l 级描述以其自身良 好的特性而被设计者广泛采用。 为了尽早的发现设计错误，降低测试成本，面向r t l 级描述的测试必不可少，由 中国科学院博士学位论文基于寄存器传输级层次模型的测试生成研究 此产生的测试向量不仅可检测电路的功能，而且可检测电路设计上的错误或结构故障。 此外，对于r t l 级同一层次上的不同描述方式，我们发现r t l 级的行为描述比结构描 述能更直接地表达设计者的设计方案，更好地体现电路行为，从而更有利于检测到设计 中的错误以及电路中的故障。 本文就是针对电路的r t l 行为描述，提出了一个方便可行的基于测试用例的时序 电路测试生成方法。 首先以电路的r t l 级行为描述为输入，基于一自由编译软件i c a r u sv e r i l o g w i l l s 】 的中间生成结果，提取电路的结构信息，建立控带流图( c o n t r o l f l o wg r a p h ，简称c f g ) 和数据流图( d a t af l o wg r a p h ，简称d f g ) 二层次模型，即一方面通过控制流图反映电 路的控制结构( i 蹑序结构或分支结构) ，其中图中每一结点表示一个语句；另方面控 制流图的每个结点又与一个表示算术或布尔表达式的数据流图相关，通过数据流图反映 每一语句的具体操作，描述语句的数据源、运算关系等。因此，此模型在考虑控制结构 的同时考虑数据路径，分层次地把握电路特性，相对于以往的电路模型( 二叉判定图 b d d 、有限状态机f s m 、控制数据流图c d f g 等) 具有形式简单、规模小、易于处理 的优点，便于根据测试的具体需要在相应层次上进行处理，从而降低了处理复杂性，提 高了系统效率。 具体到电路中的每一语句，为了能更好地把握语句执行，本文从语句的功能实现和 执行时序两方面出发考虑语句性能，制定了有关语句的可测性测度。对于语句的功能实 现，理想状态是语句中的每一变量在给定的值域内能取任意值，每一位既能取1 又可取 0 。而语句的执行时序则用于表明电路各语句的执行顺序，反映在哪一拍次下可执行语 句。由此，本文相应定义了静态时序深度、动态时序深度概念，分别度量语句的功能实 现和执行时序，通过将语句执行的横向、纵向相结合反映电路性质，为高层次测试生成 提供了方便。 基于电路r t l 级行为描述的控制流图数据流图层次模型，在电路自身结构信息( 语 句静态复杂性、静态可观信息等) 的辅助下，本文提出了一高层次测试用例生成算法， 即在有关语句可观信息的指导下，以实现控制流图的分支覆盖和数据流图的位功能覆盖 为目标，生成含有未知位的测试用例块，由此一方面把握电路的性能，另方面为后继 工作提供了一较大的操作空间。此算法具体包含主驱动过程和重引导过程两部分，其中， 主驱动过程在连续的时钟拍下对电路进行处理，而重引导过程则是通过在已处理语句记 录的基础上确定候选分支语句，调整候选分支语句走向，尽可能地完善没有覆盖的分支 和位值。通过此两子过程的交替运行，算法最大可能地满足覆盖要求，直至满足算法终 止条件成功结束或超出执行条件放弃为止。