Menu Close

数字集成电路组合逻辑自动测试模式生成ATPG_3

组合逻辑自动测试模式生成ATPG_3

 

先进的组合式ATPG算法

FAN-多重回溯(1983)

TOPS–主导者 (1987)

SOCRATES –学习(1988)

合法赋值(1990)

EST –搜索空间学习(1991)

BDD测试生成(1991)

蕴涵图和传递闭路(1988-97)

递归学习(1995)

测试生成系统

测试压缩

总结

 

范-藤原和下野 FAN — Fujiwara and Shimono (1983) 

新概念:

立即分配特别确定的信号

独特的敏化

在标题行停止回溯

多次回溯

 

路径导向的决策PODEM(Path-Oriented Decision Making)无法确定唯一信号

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\fansig.tif

回溯操作无法将门L的所有3个输入都设置为1, 造成不必要的搜索

图 1     路径导向的决策无法确定唯一信号

 

FAN – 早期确定独特信号

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\fansig.tif

立即确定当前决策所隐含的所有独特信号, 避免不必要的搜索

图 2    早期确定独特信号

PODEM进行不明智的信号分配

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\fanunique.tif

由于分配J = 0阻止缺陷传输

图 3    PODEM进行不明智的信号分配

 

无需搜索即可对FAN进行独特的识别

%title插图%num

FAN立即设置必要的信号以传输缺陷

图 4    无需搜索即可对FAN进行独特的识别

 

标号

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\fanheadline.tif

标号H和J将电路分为3个部分,可以独立进行测试完成

图 5    独立进行测试生成

 

对比决策树

%title插图%num

图 6    PODEM 决策树

 

多重回溯

%title插图%num

 

图 7    多重回溯

 

与门表决传输

%title插图%num

与门

最容易控制的输入– 0的个数是 = 输出0的个数; 1的个数是 = 输出1的个数

所有其他输入 – 0的个数是 0 ;1的个数是 = 输出1的个数

 

图 8    与门表决传输

 

多回溯扇出茎表决

%title插图%num

图 9    多回溯扇出茎表决

 

多重回溯算法

重复 从current_objectives中删除条目(s,vs);

如果(s是head_objective),则将(s,vs)添加到head_objectives;

否则,如果(不是扇出柄茎也不是输入) 对门 s的输入进行表决;

如果(门s的输入I是扇出分支) 对茎驱动I进行表决;

将驱动I的茎添加到stem_objectives中;

否则将I添加到current_objectives;

 

其余的多重回溯

如果(stem_objectives不为空)

k,n0(k),n1(k))=来自stem_objectives的最高级别茎;

如果(n0(k)> n1(k))vk = 0;

否则vk = 1;

if((n0(k)!= 0)&&(n1(k)!= 0)&&(k没在缺陷锥区域))

返回(k,vk);

将(k,vk)添加到current_objectives;

返回(multiple_backtrace(current_objectives));

从head_objectives中删除一个目标(k,vk);

返回(k,vk);

TOPS –主导者

柯克兰与默瑟 Kirkland and Mercer(1987)

 

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\dominate.tif

g的主导者–从g到输出的所有路径都必须通过主导者

绝对主导- k占主导地位

相对主导- 仅控制到给定输出的路径

如果缺陷主宰变为0或1,则回溯

图 10    主导者

 

SOCRATES学习(1988)

%title插图%num

a, 来自a = 1的含义 b, 来自f = 0的含义

图 11    SOCRATES学习

 

静态和动态学习: a= 1 %title插图%num f = 1意味着我们学习f = 0 %title插图%num a = 0

通过应用布尔对立定理

首先将每个信号设置为0,然后设置为1

发现影响

学习准则:仅在以下情况下记住f = vf:

f= vf要求f的所有输入都是非控制的

前向蕴涵有助于f = vf

改进的独特敏化步骤

%title插图%num

a, 应用指令1的例子                                                                       b, 应用指令2的例子

图 12    改进的独特敏化步骤

 

当a仅是D边界信号时,找到a的主导者并将其输入从a设置为1

找到单个D边界信号a的主导者,并使公共输入信号不受控制

 

构建性困境

 

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\construct.tif

图 13    构建性困境

 

%title插图%num

如果对一个i = 0的赋值0和1两者都被隐含,则i = 0被隐含地与a无关。

 

采取模式 (Modus Tollens) 和动态主导者 

采取模式:

%title插图%num

动态主导者:

在每个决策步骤后计算主导者和动态学习的含意

计算上太昂贵

 

EST-动态编程(Giraldi和Bushnell)

电子边界–部分电路功能分解

相当于BDD中的一个节点

在带有已知标签的电路部分和带有X信号标签的电路部分之间进行切割

EST在ATPG期间学习电子边界并将其存储在哈希 hash table表中

动态编程–当根据变量赋值的含义生成新的分解时,将其在哈希表中查找

避免重复已经进行的搜索

当分解匹配时终止搜索:

导致测试的那个较早的(检索存储的测试)

导致回溯的那个较早的

加速SOCRATES近5.6倍

 

缺陷 B 钳滞在1

%title插图%num

图 14    缺陷B 钳滞在1

 

缺陷h 钳滞在1

%title插图%num

图 15    缺陷h 钳滞在1

 

蕴涵图ATPG Chakradhar等 (1990) 

使用蕴涵图对逻辑行为进行建模

每个文字及其互补的节点

从文字a到文字b的弧表示如果a = 1,则b也必须为1

扩展了使用图型传递闭合算法的含义 – 查找边缘的路径

做出比早期ATPG搜索算法更好的决策

使用拓扑图排序来确定ATPG期间设置电路变量的顺序

示例和含义图

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\chak16.tif

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\chak17.tif

图 16    图型传递闭合算法

 

图型传递闭合

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\chak17.tif

当d设置为0,将d的边添加到非d,这意味着如果d为1,则存在冲突

可以推论(非a = 1)==》F 

当d设置为1时,将非d的边缘添加到d

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\chak17.tif

图 17    图型传递闭合

 

F = 1的结果

布尔缺陷函数F(输入d和e)具有deF

对于F = 1,将边非F –》F,因此deF 减小到d e

要使de = 0,我们添加边:e –》非d和d –》非e

现在,我们在图b –》非b中找到一条路径

所以b不能为0,否则存在冲突

因此,b = 1是F = 1的结果

C:\WINNT\Profiles\bushnell\bookfoils\advanceatpg\chak21.tif

图 18    F = 1的结果

 

相关贡献 

Larrabee– NEMESIS –使用可满足性和蕴涵图进行测试生成

Chakradhar,Bushnell和Agrawal – NNATPG – ATPG使用神经网络和蕴涵图

Chakradhar,Agrawal和Rothweiler – TRAN-传递封闭测试生成算法

Cooper和Bushnell –开关级ATPG

Agrawal,Bushnell和Lin –使用传递闭合的冗余识别

斯蒂芬(Stephan)等人。 – TEGUS –可满足性的ATPG

Henftling等,和Tafertshofer等 –蕴涵图中的ANDing节点可提供有效的解决方案

递归学习

昆兹和普拉丹(1992)

递归应用SOCRATES类型学习

最大递归深度rmax决定了从电路中学到的知识

rmax中的时间复杂度指数

内存随rmax线性增长

 

递归学习算法

对于每条不合理的线

对于每个输入:调整

分配控制值; 提出影响并建立新的不合理路径清单;

如果(一致)Recursive_Learning();

if(对于所有一致的证明,> 0表示f的值都为V的f)

学会f = V;

对所有学到的价值产生影响;

如果(所有理由不一致)

了解当前值分配不一致;

递归学习

 

i1 = 0和j = 1不合理–进入学习

%title插图%num

图 19   递归学习

 

证明i1 = 0 

选择2个可能的分配中的第一个g1 = 0

%title插图%num

图 20    证明i1 = 0

 

表示e1 = 0和f1 = 0 

给出 g1 = 0

%title插图%num

图 21    e1 = 0和f1 = 0

 

证明a1 = 0,第一种可能性 

鉴于g1 = 0,这是两种可能性之一

%title插图%num

图 22    证明a1 = 0

暗示a2 = 0 

鉴于g1 = 0和a1 = 0

%title插图%num

图 23    暗示a2 = 0

 

表示e2 = 0 鉴于g1 = 0和a1 = 0

%title插图%num

图 24    表示e2 = 0

 

现在尝试b1 = 0,第二个选项

鉴于g1 = 0

%title插图%num

图 24    尝试b1 = 0

 

表示b2 = 0和e2 = 0 鉴于g1 = 0和b1 = 0

%title插图%num

图 25     b2 = 0和e2 = 0

 

两种情况都使e2 = 0,所以要了解

%title插图%num

图 26     e2 = 0

 

证明f1 = 0 尝试c1 = 0,这是两个可能的分配之一

%title插图%num

图 27     尝试c1 = 0

 

暗示c2 = 0  鉴于c1 = 0,是两种可能性之一

%title插图%num

图 28     c2 = 0

 

表示f2 = 0  鉴于c1 = 0和g1 = 0

%title插图%num

图 29     f2 = 0

 

尝试d1 = 0 尝试d1 = 0,两种可能性中的第二种

%title插图%num

图 30     尝试d1 = 0

 

暗示d2 = 0 假设d1 = 0和g1 = 0

%title插图%num

图 31     暗示d2 = 0

 

表示f2 = 0 假设d1 = 0和g1 = 0

%title插图%num

图 32     f2 = 0

 

由于无论哪种情况,f2 = 0,所以学习f2 = 0

%title插图%num

图 33     f2 = 0

表示g2 = 0

%title插图%num

图 34     g2 = 0

 

表示i2 = 0和k = 1

%title插图%num

图 35     i2 = 0和k = 1

 

证明h1 = 0 使i1 = 0的两种可能性中的第二种

%title插图%num

图 36     h1 = 0

 

暗示h2 = 0 假设h1 = 0

%title插图%num

图 37     h2 = 0

 

表示i2 = 0和k = 1 给出2个可能的分配中的第二个h1 = 0

%title插图%num

图 38     i2 = 0和k = 1

 

两种情况都引起 k = 1(给定j = 1),i2 = 0 因此,请分别学习

%title插图%num

图 39     k = 1(给定j = 1),i2 = 0

 

其他ATPG算法 

法律任务ATPG(Rajski和Cox)

维护每个节点{0、1,D,非D,X}上可能分配的功次方集

基于BDD的算法

投石车(Gaede,Mercer,Butler,Ross)

海啸(Stanion和Bhattacharya)– 沿缺陷传输路径维护BDD碎片并逐步扩展

由于BDD本质上是无限的,因此无法进行高度收敛的电路(并行乘法器)

 

缺陷覆盖率和效率

缺陷覆盖率 =检测到的缺陷数/缺陷总数

缺陷效率 = 检测到的缺陷数/(缺陷总数 – 检测不到的缺陷数)

到效率的缺陷数 总共#条缺陷-#条未检测到的缺陷

 

测试生成系统

%title插图%num

图 40     测试生成系统

 

测试压缩

和生成相反的顺序模拟缺陷测试模式

ATPG模式优先

随机生成的模式最后使用(因为它们的覆盖范围可能较小)

当覆盖率达到100%时,丢弃剩余模式(无用的随机模式)

大大缩短了测试流程– 降低了经济成本

 

时序的静态和动态压缩

静态压实缩

ATPG应将未分配的输入保留为X

两种模式兼容–如果任何输入的值都没有冲突

将两个测试ta和tb合并为一个测试 tab= ta+tb, 使用D-交叉

检测通过ta和tb检测到的缺陷的并集

动态压缩:

立即处理每个部分完成的ATPG向量

给输入分配0或1以测试其他缺陷

 

压缩实例

t1= 0 1 X, t2 = 0 X 1; t3 = 0 X 0 ,t4 = X 0 1

先组合t1和t3,再组合t2和t4

获取: t13= 0 1 0, t24 = 0 0 1

测试长度从4缩短到2

 

概括

测试桥接,钳滞,延迟和晶体管缺陷

必须处理非布尔型三态器件,总线和双向器件(传输晶体管)

分层式ATPG- 9倍加速(最小)

处理加法器,比较器,选择器MUX

计算传输D多维数据

用这些来传输和证明缺陷影响

对内部缺陷使用内部逻辑描述

40年研究的结果–成熟–方法:

路径敏感性 

基于模拟仿真

布尔可满足性和神经网络

 

Posted in 数字集成电路

1 Comment

发表评论

相关链接