博文
芯片潜在隐患与解决之道
|||
芯片潜在隐患与解决之道
姜咏江
芯片这个名词现在几乎无人不知了，集成电路芯片的功能更是让人耳目一新。但集成电路存在潜在的隐患，恐怕知道的人是少之又少。集成电路芯片的隐患是可靠性！
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替代，其中每行都是 一个子句。
表 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 的行都是一个子句。不难看出，有一个变量取值与子句对应的0或1相同，就可以将该行消去，合取范式的取值由剩余的部分确定。如果一组变量的取值能够将全部子句消去，那么这组变量值就是合取范式的满足解。
3. 可能解空间
将所有变量的取值顺序列成表2的形式叫表1的解空间。解空间的一行叫可能解。子句中的数码与可能解对应位置数码相同，称为可能解包含子句。
表 2 合取范式解空间
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。运用子句包含消去法，逐一消去子句和包含该子句的那些可能解，最后剩余的可能解01000和11000，它们的反码10111和00111才是表1合取范式的满足解。表1最上一行就是得到的一个满足解。此题全部满足解只有两个，都可以用子句消去法验证。
4. 并行运算器SPU
如果将k个子句同每个可能解进行对比确定是否包含，这无疑是k2n这种指数时间，n较大时，运算的时间会相当长。如果我们能够设计一种对于一个子句，一次就可以确定所有的n元可能解中，哪些可能解包含这个子句，那么计算时间显然就由k来决定！
并行运算器SPU就是基于子句包含消去法原理，运用电子电路能够并行执行的特性，对解空间全部可能解一次性完成比较，并且消去那些包含子句的可能解，全部子句处理完，剩下的那些可能解的反码就是合取范式的全部满足解。如此一来，SAT问题的求解时间就只与子句数k有关，而与最大范围内的变量数无关了。
5. SPU的理论意义
SAT并行运算器的设计使只能顺序处理数据运算的计算机，有了并行进行数据运算的设备，从而使计算机完备了。在理论上，通过子句包含消去法，通过SPU完成了多项式时间处理指数时间的问题，通过计算机资源的扩充，对多年未解决的P/NP问题，画上了圆满的句号。在实践中，对集成电路芯片的安全可靠性解决，找到了切实可行的方法。通过转化，密码破解、哈密顿回路等一系列问题，也可迎刃而解。
2019-6-12
https://wap.sciencenet.cn/blog-340399-1184537.html
上一篇：完备计算机
下一篇：我的重大发明如何才能获得国家支持？
