CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

芯片潜在隐患与解决之道

已有 587 次阅读 2019-6-12 13:35 |个人分类:机器计算|系统分类:科研笔记| 子句包含消去法, SAT问题, 解空间

 

芯片潜在隐患与解决之道

姜咏江

芯片这个名词现在几乎无人不知了,集成电路芯片的功能更是让人耳目一新。但集成电路存在潜在的隐患,恐怕知道的人是少之又少。集成电路芯片的隐患是可靠性!

1. 问题的由来

芯片核心主要是逻辑电路。逻辑电路是否可靠?理论上是可以测试的,可以将逻辑的与、或、非门等,通过崔辛变换,转换成合取范式求满足解的问题。这可以通过对逻辑电路设置检测点,检测点是逻辑变量,这些变量可以换成合取范式。通过输入输出检测,会知道各个点的逻辑值。如果这些点的逻辑值,与计算出的逻辑值相符,那么该逻辑电路芯片是可靠的,如果与计算值不符,该芯片在运行中缺乏可靠性。

现在的问题是,对成千上万的检测点形成的合取范式,即使用现行最快的计算机进行计算,也不能够在人们的有生之年得出合取范式的满足解!理论的正确性和实践之间居然有这么大的差距,如何解决是计算机设计最大的课题。

毫无疑问,解决芯片可靠性计算问题,必须从计算机计算速度上下手。理论上已经证明了,用现行顺序计算的处理器来计算,是一个计算时间与数据量成指数函数上升的关系。要想在短时间内完成合取范式满足解计算,必须要有对数据并行处理器的处理器。求合取范式满足解的问题,通常叫SAT问题。人们已经从理论上证明了众多难解问题,都可以快速转化成SAT问题计算。因而能够设计出并行处理SAT问题的处理器,是解决这些问题的关键。

2. SAT并行计算原理

某逻辑电路合取范式如下(括号内的叫子句):

SAT-CNF_1=(x4’+x3’)(x4+x3’+x2’)(x4+x3’+x2)(x4+x3+x2)(x4’+x2’+x1)(x4+x2+x1’)(x4+x3+x0) (x4’+x3’+x0’)(x3+x2’+x1)(x3+x2+x1’)(x3’+x2+x1) (x3+x2+x1) (x3’+x2’+x1’) (x2’+x1+x0’) (x2+x1’+x0’) (x2+x1+x0’) (x2’+x1’+x0).

式中x’x的非。能够使合取范式的结果为1()的一组变量值称为满足解。

若用1表示x,用0表示x’,该合取范式可以用表1替代,其中每行都是 一个子句。

合取范式的二进制表示

0

0

1

1

1

x4

x3

x2

x1

x0

0

0




1

0

0



1

0

1



1

1

1



0


0

1


1


1

0


1

1



1

0

0

0

0

0


1

0

1



1

1

0



0

1

1



1

1

1



0

0

0




0

1

0



1

0

0



1

1

0



0

0

1

将表1 的行都是一个子句。不难看出,有一个变量取值与子句对应的01相同,就可以将该行消去,合取范式的取值由剩余的部分确定。如果一组变量的取值能够将全部子句消去,那么这组变量值就是合取范式的满足解。

3. 可能解空间

将所有变量的取值顺序列成表2的形式叫表1的解空间。解空间的一行叫可能解。子句中的数码与可能解对应位置数码相同,称为可能解包含子句。

合取范式解空间

x4

x3

x2

x1

x0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

0

1

0

0

1

0

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

0

1

0

1

1

1

0

0

1

1

1

1

1

0

0

0

0

1

0

0

0

1

1

0

0

1

0

1

0

0

1

1

1

0

1

0

0

1

0

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

4. 子句块与性质

变量相同的子句称为子句块。能够将子句块中所有子句消去的那些子句变量值叫子句块的解。数码互反的两个子句叫互反子句。

显然,合取范式的某个子句块无解,那么这个合取范式一定无解。除此之外,子句块有一些特殊的性质十分有用。

性质1. 不是互反子句,至少有一个位置的数码相同。

性质2. 反子句不在子句块,那么这个子句是该子句块的解。

性质3. 互反子句都不在所属子句块,它们都是该子句块的解。

性质4. 互反子句都在子句块中,它们都不是子句块的解。

5. 子句包含消去法

定理:将子句和包含子句那些可能解都消去,剩余的可能解反码是合取范式的满足解。

证明:因为剩余的可能解都由不在合取范式中的那些子句构成,其中或者是子句块中子句的反子句,或者都不在子句块中,根据性质2、3,则取反之后的可能解,一定由在子句块的子句或都不在子句块中的子句构成,则取反之后的可能解一定能将全部子句消去,不是子句变量的值不影响合取范式子句的消去。

上面的定理就是子句包含消去法。

对于表1的合取范式,解空间为表2。运用子句包含消去法,逐一消去子句和包含该子句的那些可能解,最后剩余的可能解0100011000,它们的反码1011100111才是表1合取范式的满足解。表1最上一行就是得到的一个满足解。此题全部满足解只有两个,都可以用子句消去法验证。

4. 并行运算器SPU

如果将k个子句同每个可能解进行对比确定是否包含,这无疑是k2n这种指数时间,n较大时,运算的时间会相当长。如果我们能够设计一种对于一个子句,一次就可以确定所有的n元可能解中,哪些可能解包含这个子句,那么计算时间显然就由k来决定!

并行运算器SPU就是基于子句包含消去法原理,运用电子电路能够并行执行的特性,对解空间全部可能解一次性完成比较,并且消去那些包含子句的可能解,全部子句处理完,剩下的那些可能解的反码就是合取范式的全部满足解。如此一来,SAT问题的求解时间就只与子句数k有关,而与最大范围内的变量数无关了。

5. SPU的理论意义

SAT并行运算器的设计使只能顺序处理数据运算的计算机,有了并行进行数据运算的设备,从而使计算机完备了。在理论上,通过子句包含消去法,通过SPU完成了多项式时间处理指数时间的问题,通过计算机资源的扩充,对多年未解决的P/NP问题,画上了圆满的句号。在实践中,对集成电路芯片的安全可靠性解决,找到了切实可行的方法。通过转化,密码破解、哈密顿回路等一系列问题,也可迎刃而解。

2019-6-12

 




http://blog.sciencenet.cn/blog-340399-1184537.html

上一篇:完备计算机
下一篇:我的重大发明如何才能获得国家支持?

1 刘钢

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-6-26 22:03

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部