浅说限位数横向理论与计算机SPU设计

姜咏江

1.       背景

计算机数值运算器的设计原理是运用了限位数纵向的性质。对于纯离散的用“有与无”抽象的逻辑值，就需要用限位数的横向性质来进行设计。实数具有连续性，因而可以进行近似计算，逻辑值是没有连续性的，因而不可以运用实数来进行近似计算。

鉴别事物有与无可以用逻辑值1和0来表示。从事物组成的角度分析，有可以将其中的元素有与无也用1和0来表示。分析事物元素构成是我们生活中常见的活动，当事物组成元素很多的时候，分析各个组成元素是否存在，用处理实数处理器的计算机做起来耗时过长，会长到人们无法忍受的程度。这类问题被称作“P/NP问题”，是计算机科学中最大的难题。

进过人们长时间的研究，发现P/NP问题可以归结到“布尔逻辑电路问题”。通俗地讲，“布尔逻辑电路问题”就是逻辑电路正常工作，各个逻辑节点的值应该是多少？由于逻辑电路可能存在不稳定等原因，有可能在某些输入值或某种工作环境变换中发生异常，即某些节点的逻辑值不是我们设计的理想值，如此就会在特定的时候产生严重的后果。能够知道逻辑电路是否会发生异常，这叫可靠性检测。由于这种检测需要动态，且节点数量成千上万，人工是无法进行的，而用现在的计算机检测，也不能在可以忍受的时间内完成。有什么方法能够快速地实现逻辑电路可靠性检测？这就需要改造当前设计制造的计算机，增加可以快速处理“布尔逻辑电路问题”的处理器。限位数横向理论为制造“布尔逻辑电路问题”处理器设计奠定了基础。

2.      二进制限位数的性质

限位数是用数码表示位数确定的数。假设数码的数量就固定为3，数码0不能省略，那么就是3位的限位数，二进制有8个这样的数。写出来为：000、001、010、011、100、101、110、111。我们将两个数码之和为最大数码的叫互为反码。二进制中0和1是互为反码。

我们将对应位置数码相反的限位数叫反码数。横向观察，显然，（000、111，001、110，…，011、100）是互为反码数，而且相互唯一。进一步观测，只要不是反码数，它们之间至少有一位的数码相同。

二进制中3位的限位数总共有2³=8个，如果是k位二进制数，那么总共就有2^k个，其中每一放置数码的位置都有2^k-1个0和1。

全部最高位是0（或者是1）的k位二进制数，去掉最高位0（或者1），得到的是k-1位二进制限位数全体。

3.      问题的深入

二进制限位数横向属性是不是太简单了？问题都是由简单向着复杂的方向发展的。表1是不同位置的限位数组合，每一个限位数叫子句，同样位置的子句组成子句块。限位数占用的位置数叫阶，限位数的二进制数码又叫文字。可见表1中有1阶2阶或3阶的子句块。有一个子句的子句块也在实际问题中经常出现。不论是什么样的子句，只要数码出现在相同的位置，我们就说子句块关联。

科学界早已经证明了，任何逻辑电路节点检测都可以转化成表1的形式，这种转化叫崔斯汀变换。在表1中设定每个逻辑变量的值，当子句变量位置有这个值的时候，就将这个子句消去。问是否可以找到一组逻辑变量值，能够最终将所有子句消去？这就是“布尔逻辑电路问题”求解的来源。

表 1  组合的3位限位数

“布尔逻辑电路问题”看似简单，在变量很少的情况下，只要逐一设定变量的可能值形成的数，总能够得到答案。但是在短时间内解决一个上百个变量的答案，就是用计算机程序执行运算，几乎都是不可忍受的。所以“布尔逻辑电路问题”成为了世界难题之一。

一种最简单基本的方法，就是将n个变量的全部可能值一一进行验证，这就是一般所说的暴力破解法。如果问题中有100个逻辑变量，则需要测试2¹⁰⁰次，即使是用现在世界上最快的计算机，这种测试找到一个满足解，最坏的情况需要几百年，更不要说将“布尔逻辑电路问题”的全部解求出来了。这就是所谓的指数时间运算问题。

4.      子句块与SAT的解

如果能够设定子句块的变量值能将其全部子句消去，就称这些变量值为子句块的解。消去子句的条件是：子句与变量的值的文字相同。很容易理解，“布尔逻辑电路问题”的一个子句块如果无解，那么“布尔逻辑电路问题”一定无解。为此需要先了解子句块的解。我们以3阶子句块为例（见表2）。

表 2  完全3阶子句块

“布尔逻辑电路问题”简称为SAT问题。可以验证3阶子句块变量x1x2x3全部可能值为000~111。我们将这8个值逐一带入SAT的变量，消去有相同文字的子句，发现总有子句不能消去。这就是说表2的子句块无解。可以由限位数 “不是反码数至少有一位数码相同” 的性质证明子句块如下的一些性质：

（1）子句块中子句的反子句不在，则这个子句是子句块的解；

（2）属于一个子句块的一对互反子句都不在这个子句块中，它们都是这个子句块的解；

（3）K阶子句块有m个子句（m<2^k），则该子句块有2^k-m个解。

子句块中的子句就是限位数。因而不是反子句的子句之间至少有一位数码相同，又由于反码数是唯一的，故性质（1）成立。同样道理，性质（2）也成立。由性质（1）（2）自然就推出了性质（3）。

SAT变量设定的一组值可以将其所有子句块的子句消去，这组值就是SAT的满足解。

有上面的介绍，不难理解，如果SAT有n个变量，那么如果SAT有解，一定是在0~2ⁿ-1这2ⁿ个数当中，这2ⁿ个数就叫解空间。在解空间能不能一下子找到SAT满足解？

5.      SAT全解

在解空间中快速找到所有SAT满足解的方法，在2014年就诞生了。这被描述成了下面的定理。

全解定理：解空间中将子句包含在其中的那些可能解消去，剩余的可能解的反码数都是SAT的满足解。

这个定理的证明并不难：因为不在SAT的子句，可能是SAT子句块中子句的反子句，或者互反子句都不在SAT子句块中。根据上面提到的子句块解是性质（1）（2），在可能解空间中消去子句所在的可能解，剩余可能解都是那些不在SAT中的子句组成的，这其中包含互反子句都不在SAT中。现在对剩下的这些可能解取反，那么得到的这些可能解组成的子句，或是SAT各个子句块的子句（其反子句不在），或者是那些不在SAT子句块中的互反子句构成的，因而将这些可能解任何一个带到SAT，都可以将其全部子句块消去。

6.      现行计算机为什么不能快速计算SAT问题？

现行的计算机系统基本上是以串行工作的方式运行的，对于像SAT这样的问题，由于解空间十分庞大，运算器要顺序地验证每一个可能解，并将全部解求出，就要验证2ⁿ次。当n较大时，这个指数函数验证次数十分庞大。每次解决有一个SAT问题都要这样验证，顺序来做，自然耗时过长，不能够满足时间上的需要。

7.      必须制造一种能够并行处理SAT的处理器

依据5的论述，不难理解，如果将2ⁿ个中包含每个子句的可能解快速地检测出来，并把这些可能解消去，那么剩下的那些可能解的反码数就是SAT的全部解了。如何能够快速做到这一点，这需要设计出能够瞬间实现对子句进行检验的处理器。我们就将这样的处理器简称为SPU（SAT Process Unit） 。

毫无疑问，一个子句包含在2ⁿ个可能解的哪些个当中，要一个个地访问核对，这是是一个指数时间问题。对一个确定的子句，是否可以同时访问这2ⁿ个可能解? 这就是SPU设计制造的关键设想。

本文作者既提出了限位数理论，又研制出了能够真正并行对SAT求出全部解的计算机。SPU利用限位数横向理论，采用的是存储计算模式，从而将指数时间计算的问题，变成了同时计算来完成。

8.      结束语

科学界已经证明了像密码破解、基因计算、哈密顿回路、组成分析、顶点覆盖、人工智能等问题，都可以短时间内转化为SAT问题处理。世界上每年都有国际SAT求解大赛，目的是找到SAT多项式时间（快速求解）的方法。可见SAT问题求解的重要性。

存储计算模式，设计制造本身是复杂的。然而这种模式的SPU一经问世，所有可以转化为SAT问题的难题，都会短时间迎刃而解。许多密码的问题都能够转化为SAT问题，用SPU计算机破解密码，将会是分分秒秒的事情。在国际不够太平的今天，其意义重大可想而知。

2018/6/2