基于优化ATPG的可测试性设计与实现

发布时间：2017-10-16 01:09

  本文关键词：基于优化ATPG的可测试性设计与实现

  更多相关文章： 可测性设计 代数方法 二叉判决图 可满足性 自动测试模式生成 故障覆盖率 测试模式

【摘要】：自动测试模式产生(Automatic Test Pattern Generation:ATPG)技术在针对芯片制造缺陷的生产测试中得到广泛应用。ATPG作为测试向量的生成工具,它能根据输入的故障模型,生成简洁、高覆盖率的测试向量(Test Vectors)。但是传统的基于结构化搜索的ATPG算法,如果要提高测试故障覆盖率,需要对电路进行大量的试探性的反复回溯搜索,这样就要耗费大量冗余时间,使得测试成本非常昂贵。而本文提出基于代数公式的二叉判决图和布尔可满足性SAT这两种算法能有效压缩测试时间,它通过将门级电路模块转化为数学逻辑,用求解命题逻辑的代数问题,来达到快速遍历的目的,这样既能解决冗余回溯搜索的时间过长问题,又能提高覆盖率。但对于单纯基于布尔可满足性SAT的算法,由于是以整个变量空间的回溯搜索为基本框架,所以搜索空间很大,时间复杂度较高,会导致算法超时。因为搜索空间越大,就需要越多的回溯搜索时间,特别是对于未知的故障时间将更长。而那些只基于二叉判决图BDD的算法又在构造二叉判决图BDD时可能导致内存溢出等棘手问题,为改善上述缺陷,本文又提出一种不同于遍历式搜索的启发式策略,用增量的方法尽早识别出不可测故障,节省不必要的搜索判定时间。这种二叉判决图BDD与可满足性SAT相混合的一种代数方法,采用布尔差分方程的思想,有效发挥BDD和SAT的各自在时间和空间上的优势,在结点数上做阀值判断,做启发式策略进行算法的互相切换、替代运行。同时避免了在设计BDD时会出现的内存溢出问题和SAT算法超时问题。本研究采用BDD算法的工具开发包CUDD和SAT操作的工具包Zchaff,编写了C++语言代码在基准电路上实现了上述混合算法的仿真验证和应用分析,通过和其他算法的数据对比,发现这种使用智能启发式策略的混合算法比传统的搜索算法或者单一的SAT算法在测试运行时间、回溯次数、故障传递路径、内存占有率上性能都有大幅提升,还能提高ATPG工具生成向量的效率。通过该算法在Tetra MAX工具平台上的实践验证,证明该智能式策略能预先识别冗余故障、不可测故障,又能对难测故障的搜索树进行有效修剪,删除将导致失败的路径和节点赋值模式,使测试生成过程的回溯次数最少,提高了测试生成速度和ATPG的处理效率。最后分析了实验结果和算法的先进性,总结了本人在该算法设计与实现上的主要工作,梳理了算法的创新点和实用性,并对下一步的继续研究工作进行了说明,展望了半导体测试将在系统复杂度、模块间的同步等方面遇到的挑战以及测试技术的研究趋势。
【关键词】：可测性设计 代数方法 二叉判决图 可满足性 自动测试模式生成 故障覆盖率 测试模式
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TN407
【目录】：

• 摘要5-7
• ABSTRACT7-11
• 第一章 绪论11-17
• 1.1 研究的背景与意义11-12
• 1.2 研究现状12-14
• 1.2.1 测试技术挑战12-13
• 1.2.2 半导体测试产业的困难13
• 1.2.3 传统ATPG测试生产算法的局限13-14
• 1.3 研究任务14-15
• 1.4 论文结构15-17
• 第二章 基于ATPG的芯片测试介绍17-36
• 2.1 芯片故障模式17-18
• 2.2 芯片基本测试原理与可测试性设计18-21
• 2.3 ATE测试介绍21-26
• 2.3.1 ATE测试向量22-23
• 2.3.2 ATPG简介23-25
• 2.3.3 EDA工具自动生产向量Partten25-26
• 2.4 ATPG测试向量生成的设计在芯片中的应用26-28
• 2.4.1 自动测试模式生成(ATPG)技术26-27
• 2.4.2 ATPG生成中的问题处理27-28
• 2.5 ATPG的应用以及主要算法介绍28-33
• 2.5.1 ATPG技术的应用过程28
• 2.5.2 ATPG的主要过程28-30
• 2.5.3 基于搜索方法的ATPG三种算法30-33
• 2.6 ATPG代数方法及相关定义33
• 2.7 两种代数公式算法的基础介绍33-35
• 2.7.1 二叉判决图（BBD）33-34
• 2.7.2 可满足性(SAT)34-35
• 2.8 本章小结35-36
• 第三章 基于可满足性SAT的ATPG应用36-44
• 3.1 芯片的故障模型36-38
• 3.2 布尔可满足性SAT方法简介38
• 3.3 总体流程38-40
• 3.4 建立模型40
• 3.5 基于SAT的ATPG方法的其他应用40-42
• 3.6 基于SAT的ATPG方法优点42-44
• 第四章 结合BDD与SAT的ATPG产生方法44-54
• 4.1 基于布尔方程的ATPG代数方法44-45
• 4.2 结合BDD与SAT的测试产生方法45-53
• 4.2.1 基于BDD和基于SAT的测试产生算法45-49
• 4.2.2 两种算法之间的启发式选择策略49-51
• 4.2.3 结合BDD与SAT的测试产生方法51-53
• 4.3 本章小结53-54
• 第五章 混合HYBRID算法的实验验证和应用实现54-63
• 5.1 运行时间对比56-57
• 5.2 回溯次数对比57
• 5.3 二叉图结点个数对比57-58
• 5.4 内存占用率对比58
• 5.5 实验结果分析58-59
• 5.6 新算法的ATPG向量生成实践59-62
• 5.7 本章小结62-63
• 第六章 总结与展望63-66
• 6.1 成果与工作总结63
• 6.2 论文创新点63-64
• 6.3 下一步研究计划64
• 6.4 技术展望64-66
• 致谢66-67
• 参考文献67-70
• 附录A 本课题研究实现的部分流程伪码70-73

【相似文献】

中国期刊全文数据库 前10条

1 曾成碧,段述江,陈光，

本文编号：1039757