（计算机软件与理论专业论文）hdl电路中基于进化测试的数据生成及压缩技术.pdf

摘要 集成电路规模的扩大，集成度的提高导致测试电路所需的测试向量空间指数 级爆炸，如何在有限的时间和资源条件下对电路达到所需的测试效果是目前面临 的一个重要的问题。集成电路设计越来越复杂，使用硬件描述语言设计复杂集成 电路成为一种趋势，从e d a 技术的发展趋势上看，直接采用c 语言设计 c p l d f p g a 将是一个发展方向。软件测试中已经有很多很成熟的测试数据生成的 方法，将软件测试的方法引入到用硬件描述语言所设计的电路的测试中来可以对 电路测试达到很好的效果。 本文通过利用m o d e l s i m 的编程语言接口( p l i ) 搭建测试平台，实现了c c + + 程序与v e r i l o g 硬件描述语言的互相调用，来将软件测试中的测试数据生成的方法 应用到电路测试中来，改进了进化测试算法，动态生成测试数据。通过调整序列 顺序，抛弃无关测试向量，使测试向量收敛。改进数据压缩算法，提高测试效率。 分析和实验证明了该算法相对于其他已有算法的高效性。 关键词：硬件测试进化测试数据压缩测试数据生成 a b s t r a c t t h ei n t e g r a t e dc i r c u i td i m e n s i o na n dt h e d e n s i t yo fi n t e g r a t i o nh a v e b e e n e x p a n d i n g ，w h i c hl e a dt ot h et e s tv e c o u sn e e d e db yt h et e s tc i r c u i tt oi n c r e a s eg r e a t l y t h ei m p o r t a n tp r o b l e mw em u s tf a c en o wi st h a th o wt om a k et h ec i r c u i tt oa c h i e v et h e a n t i c i p a n tt e s tr e s u l tu n d e rl i m i t e dt i m ea n ds o u r c ec o n d i t i o n t h ei n t e g r a t e dc i r c u i t d e s i g nh a sb e e nb e c o m i n gm o r ea n dm o r es o p h i s t i c a t e da n du s i n gh a r d w a r ed e s c r i p t i o n l a n g u a g et od e s i g nc o m p l e xi n t e g r a t e dc i r c u i th a sa l s ob e e nat e n d e n c y c o n s i d e r i n g f r o mt h ed e v e l o p m e n to fe d a t e c h n o l o g y , u s i n gt h ecl a n g u a g et od e s i g nc p l d f p g a w i l lb et h ep r o g r e s sd i r e c t i o n t h e r eh a v eb e e nm a n ym a t u r et e s td a t ag e n e r a t i o n m e t l l o d si ns o f t w a r et e s ta n dm e a s u r e m e n t t oi n t r o d u c et h es o f t w a r et e s tm e t h o dt ot h e t e s to fc i r c u i tw h i c hi sd e s i g n e db yt h eh a r d w a r ed e s c r i p t i o nl a n g u a g ec a ng e tb e t t e r r e s u l t s t h ep a p e rp r e s e n t st ob u i l dt e s t p l a t f o r mb yu s i n gm o d e l s i mp r o g r a m m a b l e l a n g u a g ei n t e r f a c e t h ec c + + p r o g r a m ea n dt h ev e r i l o gh a r d w a r ed e s c r i p t i o nl a n g u a g e c a l lt r a n s f e re a c ho t h e r a n da p p l yt h et e s td a t ag e n e r a t i o nm e t h o d si ns o t t w a r et e s tt o t h ec i r c u i tt e s ti m p r o v et h e e v o l u t i o n a r yt e s t i n ga l g o r i t h m ，c r e a t et h et e s td a t a m o d i f y i n gt h es e q u e n c eo d e ra n da b a n d o n i n gi r r e s p e c t i v et e s tv e c t o rt om a k et h et e s t v e c t o rc o n v e r g e p r o m o t et h ed a t ac o m p r e s sa l g o r i t h ma n df i n a l l yi m p r o v et h et e s t e f f i c i e n c y e x p e r i m e n tr e s u l tp r o v e st h a tt h i sa l g o r i t h mh a sm o r ee f f e c t i v i t yt h a no t h e r s k e y w o r d ： h a r d w a r et e s t i n g e v o l u t i o n a r yt e s t i n g d a t ac o m p r e s s i o n t b s td a t ag e n e r a t i o n 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： ，途主当聋。日期巡：! ：2 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属，于保密在一 本人签名：虚妾 i ；聋 剔醛轹斗 年解密后适用本授权书。 日期少昭，7 第一章绪论 第一章绪论 1 1 研究背景 随着社会的发展，科学技术的不断进步，集成电路的生产技术越来越先进， 产品的生产周期越来越短，集成度越来越高，规模越来越大。这常常使得穷尽模 拟所有的输入组合是计算上不可行的。如何在占用合理的时间和计算资源的基础 上达到最理想的验证效果，这是一个具有实际意义的问题。 g l e n f o r dj m y e r s 在软件测试的艺术一书中提到“软件测试或系统测试大 约占用5 0 的项目时间和超过5 0 的总成本”i l 】，尽管软件在发布之前需要投入 大量的时间和精力进行充分的测试，然而在测试数据生成领域，现阶段仍然主要 依靠测试工程师手工构造测试数据而非工具自动生成，即使一名经验丰富的测试 工程师面对庞大的程序代码、复杂的业务逻辑，并且在紧迫的工期、有限的项目 资金限制下很难对软件进行充分的测试。显然，发布的软件中遗留着较多的错误， 后续的升级和维护的成本也将大幅增加。此外，采用人工测试所需要的测试周期 以及资金成本都是自动化软件测试中所消耗的许多倍，这无疑给软件研发的企业 或机构带来巨大的压力。 软件可以在发布后再进行后续的升级和维护，但硬件必须在投片或投入市场 前进行严格的测试，不能出错误，否则将会对客户和公司都造成严重的损失。2 0 0 4 年九月i b m 公司宣布该公司将在全球范围内召回部分笔记本电脑型号所使用的交 流电电源适配器，因为这些存在问题的产品可能会因过热而起火或者导致使用者 触电。2 0 0 7 年八月诺基亚宣布由于存在过热隐患，该公司将在全球召回4 6 0 0 万块 松下制造的电池。诺基亚此次召回电池的成本最高可达1 亿欧元。这些都是电路 故障对公司和客户造成损失的案例。因此，对于电路系统，尤其是关键系统必须 对电路进行严格的测试来找出潜伏在其中的问题，进而保障电路的质量。如果我 们能够研制测试工具，使其自动为被测程序按照测试准则的要求完成测试数据生 成等任务，将会在很大程度上降低测试的成本，缩短测试的周期，提高产品的质 量。进化测试技术就是戴姆勒一克莱斯勒奔驰公司所倡导的一项新兴且具有潜力的 测试数据自动生成技术，该技术通过将测试数据生成问题转化为最优化搜索问题， 通过定义在测试目标之上的适值函数的导向，利用进化算法的全局搜优能力，可 以在被测程序指数级的测试输入空间内找到目标测试数据。众多实践表明，进化 测试能够在巨大的测试输入空间中根据覆盖准则以较低的代价自动生成高质量的 测试数据，从而发现错误。 2 h d l 电路中基于进化测试的数据生成及压缩技术 1 2 国内外研究现状 在过去的3 0 年中，围绕h d l 测试问题，国内外进行了长期和大量的研究，研 究内容主要包括测试数据自动生成技术以及数据压缩技术等方面。 目前有多种自动生成测试数据的方法，按照测试的方法，可以分为静态法和 动态法。静态法不用执行程序本身，而是采用符号执行【2 ，3 】等方法将程序路径上的 所有( 判断) 语句转换成约束系统，然后进行求解，静态法所建立的约束系统包括了 满足条件的全部解，它主要包括符号执行【2 捌和区间算术法，他们都不能用于黑盒 测试。符号执行采用符号分析而不是具体的变量值来执行程序，因此符号执行技 术在遭遇到数组，循环，函数调用等问题时由于状态空间的巨大或者不确定而无 法执行。 与静态法不同，动态法是依赖程序的具体执行过程来产生测试数据的。基于 动态执行的测试数据生成能够执行程序，并对程序执行过程中的行为分析来生成 测试数据，克服了符号执行在处理数组，循环，函数调用方面的不足。但是，当 求解的问题有解时，动态法不能保证总能找到。动态法测试数据生成方法主要有 随机测试，局部搜索法，目标制导法，应用模拟退火法，进化测试等。随机测试 ( r a n d o mt e s t i n g ) 是简单的通过随机的程序输入来运行被测程序，然后再观察被 测程序的执行，随机测试数据生成技术常作为其他测试数据生成技术的初始化时 使用。1 9 7 6 年，m i l l e r 和s p o o n e r 【4 】两人第一次真正把搜索技术引入到了程序的 实际执行的过程中。k o r e l 在1 9 9 0 年扩展了m i l l e r 和s p o o n e r 方法中的适值函数 【1 2 】，提出了分支距离的概念。k o r e l 在他的原工作的基础上在1 9 9 2 年又提出了目标 制导法( t h eg o a l o r i e n t e da p p r o a c h ) 【引。t r a c e y 和c l a r k 在1 9 9 8 年提出用模拟 退火方法来代替以前的局部搜索方法来对结构测试生成测试数据，以解决使用局 部搜索所带来的一些弊端1 6 ，7 】。x a n t h a k i s 等人在1 9 9 2 年第一次把进化算法引入到 了测试数据的自动生成问题中【8 1 。因为进化算法非常善于对付由于软件本身的非线 性所导致的测试数据的搜索空间不连续、非线性、多峰的特性，在这些情况下， 进化算法要远远优越于类似模拟退火等其他很容易陷入局部最优解的邻域搜索算 法，这和用进化算法在函数优化问题上的优势是一致的。由于进化算法能力的强 大，它们越来越多的用在基于搜索的软件工程的动态搜索部分上。 另外，在数据压缩技术方面，空白压缩( n u l ls u p p e r s s i o n ) 是最早研究的数据 压缩技术之一。算法的基本思路是压缩文本中连续出现的空格或空白。游程编码 ( r u n l e n g t he n c o d i n g ) 剀是使用较广的一种数据压缩技术。这种方法可以被认为 是空白压缩的推广，它可以压缩源数据流中连续出现的任何字符。哈夫曼编码1 1 0 】 是一种基于统计的编码方式，该方式可提供最好的定长变长的编码效果。可通过 第一章绪论 构造哈夫曼树来实现哈夫曼编码，但它是一种动态编码，这就增加了测试设备和 解码电路之间实际传输的数据量。g o l o m b 编码】是在传统的游程编码基础上发展 起来的一种改进算法，其最大的改进之处在于改变了原来从变长到定长的编码方 式，而选择了变长一变长的方案。代码字分为前缀和后缀两部分，前缀代表了分组信 息，而后缀则是位串长度相对信息。 h d l 测试问题也是国内研究关注的焦点之一，研究热点多集中在h d l 功能测 试，以及测试平台的相关技术上。 湖南大学研究了h d l 测试平台，提出了测试平台的设计，以及陈俊、黎福海 等人对h d l 功能测试方面做了些工作，提出了语义有限状态机覆盖测试的方法。 中科院计算所李晓维博士在v l s i s o c 设计验证与测试方向做了很多工作。 国内在h d l 功能测试以及测试平台的方法与技术方面进行了研究和探索，但 在研究深度和应用上与国外仍有一定的差距。在基于进化算法的测试数据生成方 面，国内研究还处于起步阶段。 1 3 论文的主要工作及组织结构 本文主要工作集中于h d l 测试数据自动生成与测试数据向量压缩技术研究。 改变传统符号执行利用逻辑系统进行约束推导产生测试输入或者通过随机产生生 成测试输入的思路，将测试输入的产生问题转化为一个全局优化搜索问题，并通 过进化算法的应用进行测试输入的产生。论文完成的工作概述如下： 1 、 通过运用v e r i l o g 的编程语言接口( p l i ) 实现了实现c c 抖与v e r i l o g 程 序的调用，将软件测试中的一些测试数据生成方法引入到硬件测试中来，达到硬 件测试自动化的目的。 2 、通过比较几种静态测试向量的生成方法和动态测试向量生成的方法，提出 了基于遗传算法的测试数据生成方法，对海量测试数据进行处理。有效地节省了 测试的时间并提高测试效率。 3 、分析比较空白压缩、游程编码、g o l o m n 编码，并提出了改进的测试数据 压缩算法。通过实验检验，有效的提高了测试效率。 本文的组织结构为：第一章是绪论，对项目研究背景和国内外研究现状等做 了简单的介绍；第二章为h d l i 贝i j 试的分析与设计，并给出了h d l 澳i j 试中所使用的一 些基本覆盖准则，测试数据生成和压缩的基本技术；第三章为面向h d l 电路测试的 进化算法数据生成，介绍了测试平台搭建的详细过程和步骤，并实现了基于遗传 算法的电路测试向量生成；第四章给出了防止测试向量爆炸的方法，改进了目前 的测试数据压缩算法，理论推导与实验分析证明了该算法的有效性；第五章为结 束语，是对本文的概括和总结，并指出了本文存在问题及进一步研究方向。 第二章h d l 测试的分析与设计 第二章h d l 测试的分析与设计 h d l 和传统的原理图输入方法的关系就好比是高级语言和汇编语言的关系。 h d l 的可移植性好，使用方便，但效率不如原理图；原理图输入的可控性好，效 率高，比较直观，但设计大规模c p l d f p g a 时显得比较烦琐。 2 1 v e r i l o gh d l 目前最主要的硬件描述语言是v h d l 和v e r i l o gh d l 。v h d l 发展的较早，语 法严格，而v e r i l o gh d l 是在c 语言的基础上发展起来的一种硬件描述语言，语法 较自由。v h d l 和v e r i l o gh d l 两者相比，学习v h d l 比学习v e r i l o g 难一些， 但v e r i l o g 自由的语法也使得的初学者容易上手但也容易出错。国外电子专业通常 在本科阶段教授v h d l ，在研究生阶段教授v e r i l o g 。从国内来看，v h d l 的参考书 很多，便于查找资料，而v e r i l o gh d l 的参考书则很少，这给学习v e r i l o gh d l 带 来不少困难。 下面例子是一个用v e r i l o gh d l 实现的二选一的模块，其功能是在两个输入端 选取其一，作为输出。 m o d u l e m u x _ b e h ( o u t , a , b ，s e l ) ； 夺o u t p u to u t ； ：i n p u ta , b s e l ； a s s i g no u t = ( s e l 一0 ) ? a ：b ； e n d m o d u l e 图2 1 二选一功能模块行为描述 行为描述模块中的a s s i g n 语句在v e r i l o gh d l 中称之为连续赋值语句，它的作 用，熟悉c 语言的读者一看即知，但需要特别说明的是，它在物理上代表了在s e l 的控制下，信号o u t 与信号a 、b 之间的硬件连接关系，每当s e l 、a 、b 三个信号有 任何变化，都将被随时反映到输出端o u t 信号上来，这就是连续赋值语句的含义所 在，在c 语言等其他计算机语言中，没有相应的赋值语句与之相对应。 6 h d l 电路中基于进化测试的数据生成及压缩技术 m o d u l em u x _ s t r ( o u t ，a , b ，s e l ) ； 咚 o u t p u to u t ； 专 i n p u ta , b s e l ； ： n o tg a t e l ( n e t i ，s e l ) ； 夸 a n dg a t e 2 ( n e t 2 ，a ，n e t1 ) ； a n dg a t e 3 ( n e t 3 ，b ，s e l ) ； o rg a t e 4 ( o u t ，n e t 2 ，n e t 3 ) ； ：e n d m o d u l e 图2 2 二选一功能模块结构描述 以上图2 1 和图2 2 两段v e r i l o g 程序实现的功能是完全一样的，图2 1 是从行 为级对二选一功能模块进行表述，图2 2 是从结构上对功能模块进行了描述。 图2 3 二选一m u x 逻辑图 对结构描述模块来说，将它的v e r i l o gh d l 描述与图2 3 所示中的逻辑图加以 对照，可以发现v e r i l o gh d l 只是忠实地将图形方式逻辑连接关系转变为相应的文 字表达而已。在对一个逻辑电路进行结构描述前，先给电路中的每个元件取一个 名字，并以同样方式给每条内部连线也取上相应的名字，如图2 3 中给各个逻辑单 元取名g a t e 至g a t e 4 ，以及用n e t l 至n e t 3 给每条内部连线取名，然后再依据逻辑 图中给出的连接关系，确定各单元端口间的信号连接，完成描述的全过程。由于 结构描述与逻辑图存在着一一对应的关系，因而只要给出电路的结构描述，就可 以复原出相应的逻辑结构图，二者是完全等价的。 用v e r i l o gh d l 写的测试模块如图2 4 所示。 第二章h d l 测试的分析与设计 7 图2 4 二选一m u x 的测试模块 图2 4 所示的测试模块，先调用了图2 1 所示的二选一电路，然后将a 赋值为 0 ；b 赋值为1 ；s 赋值为0 ：然后在1 0 个时间单位后，将a 的值改为1 ；再1 0 个 时间单位后将b 的值改为0 ；再l o 个时间单位后s 的值改为1 ；再1 0 个时间单位 后b 的值改为1 ；再1 0 个时间单位后a 的值改为o ；再1 0 个时间单位后结束。目 的就是测试是否能在使能端s 的控制下输出a 和b 的值。 用v e r i l o gh d l 进行硬件设计的过程实质上是把构成硬件系统的各功能模块 进行v e r i l o g 描述，这种描述可以是行为描述，也可以是结构描述，前者刻画模块 所具有的行为特征，后者侧重反映模块内部的具体构造。通常一个硬件系统是由 多个不同的功能模块连接起来，这个模块就是系统的顶层模块。相对与顶层模块， 其它的模块就是低一层次的模块。在对低一层次的模块进行描述时，如果有必要， 可以同样用结构描述的方法，把模块的内部构造进一步具体地刻画出来，相对于 顶层模块而言，用于构造低一层次模块的结构单元就属于更低一个层次。因而， 随着设计过程的展开，一个硬件系统的构造逐渐由顶层走向低层，各个功能模块 的内部结构逐级得到深化和细化，整个设计过程因而被称之为一个自顶向下的分 级设计过程。 在这个自顶向下的设计过程的任何阶段，都可以利用仿真工具对仍处于设计 过程中的系统描述进行性能评估与正确性检测，方法就是为顶层模块编写一个测 试模块。它包括对模块的调用，相关观察手段的提供，以及用于测试的激励信号 的产生。 在自顶向下的设计过程中，对于上层模块来说，只需知道某个模块的名称与 端口类型，就可把它作为自己的一个下层模块进行调用。至于下层模块的具体实 现方式，或者从一种实现方式转换到另一种实现方式，都不会对上层模块的描述 8 h d l 电路中基于进化测试的数据生成及压缩技术 产生任何影响。这是自顶向下设计方法的一个突出的优点。在设计过程中，通过 仿真测试，如果发现性能不够理想，或发现任何错误，我们只需对存在问题的低 层模块的描述或实现方式进行修改或调整，而不必对上层结构进行任何改变。所 谓的顶层和低层都是相对的。在实际设计过程中，总是把当前正在实现的模块作 为一个局部的项层模块，在完成描述后，先单独对它进行仿真测试，在验证其正 确性后再加入需要调用它的模块中，而成为整个系统设计中某一个层次的功能模 块。一个大的电子系统设计就是这样从顶层到低层，边设计，边仿真，并依据仿 真结果，反复调整或优化的过程。 模拟验证能力是用硬件描述语言进行电子系统设计的最重要的优点之一。一 方面，在电子系统设计与制造实现的各个阶段，都需要人力、物力的大量投入， 如果设计中存在错误，发现得越晚，损失就越大。这也就是手工设计成本高、周 期长的原因所在。采用h d l 描述进行设计时，在每个抽象层次上都可进行模拟仿 真，及时发现可能存在的设计错误，从而保证整个设计过程的正确性。另一方面， 目标系统性能的好坏，也只有通过仿真才能反映出来，因而描述的可模拟性也是 实现e d a7 - 具中各类优化技术的基础和保证。 综上所述，正由于h d l 具有以上的一些特点，我们可以将软件测试中的一些 数据生成的方法用到h d l 测试中，我们的目标是实现用c c + + 程序生成测试向量， 调用v e r i l o g 电路，对其进行测试。 2 2 覆盖评估准则 验证是保证硬件设计可靠性的重要环节。虽然形式验证为此提供了理想的解 决之道，但在大规模的设计中还不适用。迄今为止，模拟是集成电路设计验证的 主要方法。在大型芯片的设计中，功能验证或模拟通常占据整个验证工作量的 4 0 7 0 ，这种状况有可能还会持续下去，尤其是对验证r t l ( r e g i s t e r - t r a n s f e r l e v e l ) 电路更是如此。 目前集成电路设计的规模越来越大，这常常使得穷尽模拟所有的输入组合是 计算上不可行的。如何在占用合理的时间和计算资源的基础上达到最理想的验证 效果，这是一个具有实际意义的问题。通常的做法就是在模拟验证中运用覆盖评 估准则。本节将总结现有的覆盖评估准则1 1 2 1 。 在模拟验证中，覆盖评估能够量化度量模拟矢量集的完备性。其次，能够诊 断出对于当前的矢量集来说，那部分设计尚未充分验证。这有助于后续矢量的编 写。最后，有助于压缩矢量集，这一点在于实现模拟矢量自动生成的过程中尤为 重要。虽然目前还没有通用的错误模型来刻划设计中的错误，但是覆盖评估对于 模拟验证的重要意义已经是勿庸置疑的。 第二章h d l 测试的分析与设计 9 提高覆盖率会增强对设计正确性的信心。如果覆盖准则与错误类型之间有直 接对应，那么对该准则实现完全覆盖的矢量集可以检测到所有潜在的该类型错误。 然而对设计错误缺少公认的形式特性，使得这种对应非常困难。 目前的模拟验证领域中存在多种评估准则。对于准则之间的“复杂度”，很难给 出形式上的定义。即使准则m 1 包含了m 2 ，但是达到1 0 0 m 1 覆盖的输入激励并 非一定比达到1 0 0 m 2 覆盖的激励发现错误的能力强【1 3 】。准则与其发现错误的能 力之间的关系，更多的是靠直觉和经验来判断。 1 代码覆盖准则 代码覆盖准则原本是软件测试中的概念。由于用h d l ( h a r d w a r ed e s c r i p t i o n l a n g u a g e ) 所写的硬件设计和用高级语言编写的软件在形式上非常类似，此类准则 被借鉴到硬件的设计验证之中。 代码覆盖准则动机非常纯朴：达到一定的代码覆盖率，也就表明了h d l 程序 中的该类代码结构中有足够比率的结构已经验证过。最简单的结构如一行语句或 一个不包含任何分支的语句块。复杂一些的结构如分支、表达式、和路径。 代码覆盖的涵义易于理解，而且评估所需的开销较小，有许多商业工具都支 持，所以实际中一般都会做代码覆盖评估。然而与软件测试不同的是，硬件验证 中达到完全的代码覆盖只是一个很低的要求。原因在于，代码覆盖准则与其激励 发现设计错误的能力之问没有直接联系，达到一定的代码覆盖率，只是意味着代 码覆盖准则所对应的代码结构在模拟中被执行过。而且，硬件设计是高度并发的， 在某一个时刻可能有多个代码段被激活，但是代码覆盖并不涉及硬件设计的这个 本质特性。 2 电路结构覆盖准则 此类准则与代码覆盖准则的出发点是类似的，所不同的是，代码覆盖准则是 从设计语言的角度选择其欲覆盖的结构，而电路结构覆盖准则是从硬件电路的角 度考虑。 此类准则中最简单的就是翻转覆盖( t o g g l ee o v e r a g e ) l l o 确定硬件设计中的信号 包括线( n e t ) 和寄存器( r e g i s t e 卜在模拟中是否都经历了”0 - 1 ”和”1 - 0 的 跳变。翻转覆盖从更细的粒度上评估电路的各个部分是否被充分验证。 针对具体电路设计的特性，可以定义更复杂的电路结构覆盖准则。例如，覆 盖每个可能的“寄存器寄存器”通路，或者覆盖控制信号和状态信号的所有可能的 组合。将电路分为数据通路( d a t ap a t h ) 和控制通路( c o n t r o lp a t h ) ，对于定义此 类中更复杂的准则来说是有用的。 这一类覆盖准则也是易于理解和使用的。与代码覆盖一样，满足此类覆盖准 则也只是所需模拟量的下限。由于电路结构覆盖准则是从更细的粒度上评估验证， 与代码覆盖准则相比，其结构的不可控制性分析起来较复杂，而且这些信息难以 10 h d l 电路中基于进化测试的数据生成及压缩技术 准确地自动地提取出来。 3 可观测性覆盖准则 在模拟的过程中，虽然所有变量的值都是可见的，但是随着电路设计规模的 不断扩大，了解设计中所有变量的正确行为，其数据量之大对于验证工程师来说 几乎是不现实的。所以，欲监测模拟时所有变量的取值及其变化，以此来判断设 计中是否存在错误，是非常困难的。另外，硬件设计在模拟过程中，其变量的状 态通常是一串0 、1 序列，可读性差。所以，在模拟验证中选择合适的可观测点， 例如，模块的输入和输出，是一种合理的做法。( 某点“可观测”是指，验证者或者 监视器应该能够区分出该点的正确响应和错误响应) 。在这种情况下，考虑硬件设 计的可观测性就非常重要了。这一点在图2 5 中一目了然。选择信号c 的值决定了 输入信号在可观测点q 处能否被观测到。可观测性要求并不意味着要求设计的某 个部分必须表现出错误，也不要求必须人为注入错误来模拟。只是要求该部分必 须在某些时钟周期内影响可观测点的值。 a b q c 图2 5 二选一功能模块 考虑可观测性的准则有：可观测代码覆盖，可观测变量覆盖等等。为了评估 可观测代码覆盖，d e v a d a s 等人【1 4 】对h d l 代码中的每个赋值语句做标记，只有某 个语句的标记在模拟过程中可以传播到可观测的变量，那么该语句才可认为被覆 盖到。f a l l a h 等人【1 5 】改进了可观测代码覆盖的评估算法，在计算效率上有很大提高。 与前两类覆盖准则相比，可观测性覆盖准则的评估能力更加全面。代码覆盖 和电路结构覆盖都没考虑可观测性问题，这可能导致表面上很高的覆盖率数据， 其蕴含的可靠性却不高。然而可观测性覆盖准则通常不会单独使用，而是与代码 覆盖等其它准则相结合。对可观测性覆盖准则的研究正处在发展初期。 4 f s m 覆盖准则 f s m 作为一种成熟的数学模型，是刻画离散系统的有力工具。在硬件设计领 域中，f s m 常常用来对控制逻辑建模。常见相关准则包括，覆盖有限状态机系统 中的每个状态、跳变、或者一定长度的路径。f s m 依据其来源可以分为两个大类： 第二章h d l 测试的分析与设计 手写的f s m 和从设计方案中自动提取的f s m 。 自动提取的f s m ，通常先指定一组状态变量，将设计映射到该集合上，得到 一个抽象的f s m 。这种方法的特点是易于实施，不需要过多的人力干预。 手写f s m 的特点是不依赖硬件设计的实现细节，可以在更高的层次上抽象， 更简洁的刻画设计的行为特性。但是构造和维护这样的f s m 需要更多的人力。经 验显示，在提高此类覆盖率的过程中，发现了许多其他准则难以发现的错误1 1 6 j 。 构造f s m 要在所包含的信息量与其易用性之间折衷。这样的选择是与设计相 关的。在f s m 中加入更多的信息，就会增加覆盖准则的准确性，但是也会使得理 解覆盖数据更加困难。而且，如果f s m 太复杂，要达到路径覆盖等准则的高覆盖 率是比较难的，但是f s m 中的路径覆盖还是应该考虑的，因为那是对硬件设计的 时序行为的反映。 代码、电路结构以及可观测性覆盖准则都是从静态结构的角度来定义的，所 以它们量化时序行为的能力必定受限制。在这一点上，f s m 覆盖有着其它类准则 不可比拟的优势。另外，f s m 覆盖准则的应用范围也很灵活。 5 错误模型覆盖准则 此类准则与测试中的故障覆盖准则非常相似，从设计错误中抽象出逻辑模型， 评估模拟验证的矢量集对于模型化错误的覆盖率。这是一种理想的覆盖准则的定 义方法，由于准则与某一类设计错误模型对应，那么实现了对该准则的完全覆盖， 就可以确保设计中不存在该类错误。 然而对设计错误建模并非易事。固定型故障模型之所以取得成功，很大程度 上是由于集成电路中的金属线和逻辑电路中的互连之间具有直接对应关系。而 h d l 行为描述、r t l 描述与电路结构之间并不存在这样的对应。h d l 描述中的语 句可能与成百个门和线相对应。所以对高层设计中的错误建模难以从物理电路中 获得帮助，常常依靠设计者或者验证者的经验。a l - a s a a d 【1 7 j 对门级组合电路定义 了四类简单的错误模型：门类型错误、门数目错误、输入数目错误和输入信号错 误，并将错误模型映射到s s l ( s i n g l es t a c k a tl i n g ) 故障，借助于针对s s l 故障 模型的a t p g 工具间接的产生测试设计错误的矢量集。c a m p e n h o u t o s 提出了更复 杂的错误模型，并针对电路的r t l 设计手工产生模拟矢量集。实验数据表明对模 型化错误达到完全覆盖的测试集可以检验出一大部分实际的设计错误。 如果能够提出高质量的设计错误模型，那么覆盖准则在模拟验证中的作用就 能够充分发挥，但是，目前逻辑错误模型的质量是由对该模型达到1 0 0 覆盖的矢 量所能检测的单固定型故障的数目来评定的。这样，所提出的模型是争取尽可能 高的固定型故障覆盖率，而不是发现h d l 描述中的错误。而且，激励集的有效性 不能直接在功能级评估。 与可观测性覆盖准则相同，错误模型覆盖准则也处于研究阶段。其它类型的 1 2 h d l 电路中基于进化测试的数据生成及压缩技术 覆盖准则还有故障覆盖和功能覆盖等等。 故障模拟能够提供矢量集对h d l 代码的覆盖率，但是进行故障模拟需要将 h d l 代码综合到门级，而且对于大规模的设计和矢量集来说，故障模拟是很耗时 的。另外，故障覆盖评估针对的是逻辑门的输入输出上的故障，这通常与h d l 设 计中的错误没有直接联系。 目前，功能覆盖技术通常仅应用于特定类型的设计，如：验证处理器时要求 覆盖其每条指令。 覆盖评估提供了度量模拟矢量集的量化方法，在一定程度上弥补了模拟验证 的不完备性；利用其反馈信息指导后继模拟矢量的编写，可以避免对已检验过的 部分设计进行重复验证，有助于合理利用有限的资源；覆盖评估也是矢量压缩的 前提条件，是模拟验证中的不可或缺的技术。 2 3 测试数据生成相关技术 因为电路的许多行为在静态的时候是很难分析的，比如说时钟序列问题，这 些都是符号执行所不能解决的，要处理该问题就需要程序的动态运行，所以动态 结构测试数据生成( d y n a m i cs t r u c t u r a lt e s td a t ag e n e r a t i o n ) 的方法便出现了。下 面我们简要回顾一下它里面的一些重要的方法： 2 3 1 随机测试 随机测试( r a n d o mt e s t i n g ) 是简单的通过随机的程序输入来运行被测程序， 然后在观察被测电路的执行( 比如对被测电路各个可观测点的覆盖) 。对于简单的 电路这个办法是很好用的，但是对于大多数的实际电路来说，是会存在一些通过 随机产生的测试输入是很难覆盖到的电路分支，这时候如果单纯只用随机测试， 就会让电路测试的不充分，即有些存在测试数据可以覆盖到的可观测点却没有被 覆盖到。 v o i dr a n d o m ( i n tb i t ，i n tt i m e s ) b i t 为生成测试向量的位数。t i m e s 为测试次数。 s r a n d ( ( u n s i g n e d ) t i m e ( n u l l ) ) ；用时间作为种子，使得随机效果更好。 i n tt e s t v e c t o r ；佣来存储测试向量 f o r ( i n ti = l ；i 以上这段程序就实现了随机生成测试向量的算法。 2 3 2 进化测试 自从上个世纪七十年代以来，如何自动地为被测程序生成测试数据便一直是 软件工程师的重要研究课题之一，然而，由于软件测试数据自动生成一般情况下 是一个不可判定问题，因此，这个领域的进展一直非常缓慢。即使在工程实践中 实际有意义的程序都是有限状态的，其测试数据搜索空间仍然随着程序输入参数 个数的变化以及参数取值范围的变化而成指数级增长。故而，在这样一个爆炸的 测试输入空间中，进行穷举搜索显然是不可能的。只有应用启发式算法，我们才 有可能在近似多项式的时间内找到满足指定覆盖准则的测试数据。不幸的是，由 于软件本身的非线性，这个测试数据的搜索空间往往是不连续的、非线性的、多 峰的，在这种情况下，类似模拟退火等邻居搜索算法往往就很容易陷入局部最优 解，从而导致测试数据搜索的失败，为了克服局部最优的问题，进化算法例如遗 传算法等便被用于测试数据的搜索l s 】。 进化算法代表一类建立在自然遗传以及达尔文生物进化理论的自适应搜索技 术。其中，遗传算法( g e n e t i c a l g o r i t h m ) 是一类借鉴生物界的进化规律( 适者生 存，优胜劣汰遗传机制) 演化而来的随机化搜索方法。它是由美国的j h o l l a n d 教 授1 9 7 5 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数 连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优 方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定 的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信 号处理、自适应控制和人工生命等领域。 而在软件测试领域的应用，其主要思想在于将测试数据的生成问题转换为最 优化的搜索问题。首先需要将测试目标转换为搜索的目标，在此之上定义一个最 优化搜索的目标函数也称为适值函数。之后，进化测试按照如下步骤来生成测试 数据： 种群中的第一批个体被随机产生，被测程序中的参数被编码成种群中的个体。 首先，将种群中的个体解码为参数并作为输入来执行被测程序，通过监控被测程 序的执行，被测程序的参数对目标的偏离程度将为种群中的个体计算出适值。然 后，进化算法根据个体的适值来进行选择哪些个体将作为父本来生成下一代，在 这里主要利用进化算法中的交叉算子和变异算子。需要注意的是，在生成下一代 1 4 h d l 电路中基于进化测试的数据生成及压缩技术 中的个体对应的参数也要在被测程序的输入范围内。生成的下一代对应的测试数 据同样需要作为被测程序的输入来被考核并依据进化算法的选择标准被回插入到 待进化的种群中瞵】。从此开始，整个进化过程将反复进行，一直到生成目标测试数 据或者满足进化算法的终止条件。 把进化算法应用到测试数据的自动生成中便是所说的进化测试( e v o l u t i o n a r y t e s t ) 。x a n t h a k i s 等人在1 9 9 2 年第一次把进化算法引入到了测试数据的自动生成 问题中i l 引。因为进化算法非常善于对付由于软件本身的非线性所导致的测试数据 的搜索空间不连续、非线性、多峰的特性，在这些情况下，进化算法要远远优越 于类似模拟退火等其他很容易陷入局部最优解的邻居搜索算法，这和用进化算法 在函数优化问题上的优势是一致的。由于进化算法能力的强大，它们越来越多的 用在基于搜索的软件工程的动态搜索部分上。我们也将进化测试引入到h d l 测试 中。在静态测试数据的基础上，采用进化算法，通过覆盖评估准则来进行验证， 反复进行整个过程，达到生成目标测试数据或者完成对电路的测试的目的。我们 将在后续研究中重点研究用进化测试来动态生成测试向量检测目标电路。 2 4 测试数据收敛技术 随着集成电路规模的扩大，测试电路所需的测试向量空间急剧扩大。如何在 海量的数据中挑选有用的测试数据，抛弃无关测试向量，节省测试时间，提高测 试和资源利用的效率，是集成电路测试中面临的很实际的问题。目前硬件测试中 多采用数据压缩技术，将测试数据中的无关位根据压缩的需要进行人为指定，减 少测试向量数目，提高连续序列长度，达到删除数据中的冗余信息，保留有用信 息，提高压缩效率，节省测试时间，达到对电路进行有效测试的目的。 2 5h d l 测试方案总体设计 随着集成电路设计越来越复杂，使用语言设计复杂p l d f p g a 成为一种趋势， 目前最主要的硬件描述语言是v h d l 和v e r i l o gh d l 。v h d l 发展的较早，语法严 格，而v e r i l o gh d l 是在c 语言的基础上发展起来的一种硬件描述语言。语法较自 由，目前a c s i 设计多采用v e r i l o g 语言。因此本文针对用v e r i l o g 设计的电路进行 测试，提出用c 语言生成测试用例，调用v e r i l o g 电路进行测试，将软件测中的 测试数据生成的算法引入到硬件测试中来 综上，整体思路如图2 6 所示。 第二章h d l 测试的分析与设计 1 5 图2 6 测试设计方案 本文在静态测试向量测试的基础上，根据覆盖评估准则来判断对电路测试的 情况，再利用进化算法动态生成测试数据，对电路进行测试，直到满足所需的覆 盖率，达到在有效的时间和计算资源的基础上进行有效的测试的目的。 2 6 本章小结 本章介绍了v e r i l o gh d l ，分析了为什么可以将软件测试中的数据生成方法应 用到硬件测试中来。引出了如何判断对一个电路达到了有效的测试，给出了判断 标准。同时介绍了我们后续章节将用到的数据生成的算法以及如何节省测试时间 提高测试效率。最后给出了整个测试方案的总体设计。后续章节中将实现各个环 节。 第三章面向h d l 电路测试的进化算法数据生成 1 7 第三章面向h 0 1 _ 电路测试的进化算法数据生成 上一章中分析了h d l 测试所需的各项技术，并提出了整体解决方案。本章将 通过举例实现c c + + 程序和v e r i l o g 电路的调用，搭建测试平台。对静态测试向量 的生成进行分析。在覆盖评估准则的评估标准下，通过改进遗传算法动态生成测 试数据。 3 1 测试平台搭建 本节将搭建一个测试平台，实现c c + + 程序对v e r i l o g