科学网—标签

相关帖子	版块	作者	回复/查看	最后发表

accsys 2019-12-9 07:43

姜咏江现在的人工智能以网络为主，在时间迅速的要求上，往往仍然不尽人意。产生这方面问题的根本原因，现有计算机缺乏真正并行处理能力。串行与并行是人类处理问题的基本方式。多台计算机组网，必须有管理工作的主机进行任务分配和调度，这实际是不完善的串并行组织方式。如果能够在同一台计算机上实现串并行执行任务，就可以免去那些额外的时间消耗，达到高速、准确及时的效果。串并行一体计算机包括串行处理器 CPU 和并行处理器 SPU ，当然也可以增添 GPU 等处理器。这种计算机串并行数据能够实现共享，因而不必象多机联合那样，要将数据传来传去。目前，计算机并未加装并行处理器，因而有诸多离散的数据分析处理，都要通过基础的串行方式解决，耗时无法忍受。如果能够在现行的计算机上，安装能够真正实现并行处理的处理器，这些问题都可以在极短的时间内计算出结果。 CPU 一次能够处理一个或两个固定位数的二进制数。而并行处理器 SPU 可以一次处理 2 n 个固定位数的二进制数。这就是并行处理器 SPU 快速的硬道理。由于计算机处理的问题需要编程，对于顺序处理和并行处理的部分，分别交给 CPU 和 SPU 来处理，而将它们处理好的数据，放在共同可以访问的存储设备中，岂不方便快捷！现在，适用的仿量子计算机，方兴未艾。认识它，支持它，参与其中，将会使我们的计算机历程大放光彩，将会使人工智能的研发，登上更加适用需要的愿景。 2019/12/9

个人分类: 仿量子计算机|1621 次阅读|0 个评论

完备计算机

accsys 2019-6-11 06:53

完备计算机姜咏江世界的事物处理过程无非两种方式。一是顺序处理方式，二是并行处理方式。电子计算机用二进制处理事物，自然也要模拟这两种方式。直至目前为止，人们使用的计算机运算器还只能模拟具有先后顺序的处理方式。对于并行的过程，计算机需要转化成顺序处理方式才能够实现。将并行的过程转化成顺序过程来处理，在时间上消耗增加是必然的代价。这样对那些数据量大一些的可并行处理的问题（例如密码破解、集成电路可靠性检测（ SAT ）、哈密顿回路等），基本上还束手无策。不能够实现并行处理数据的计算机结构，体现了计算机设计的不够完备性。大量的并行处理问题，成为了计算机科学的最大难题。这些问题的有效短时间处理，是计算机设计理论和方法的最大挑战。能够具有顺序和并行两种处理器的计算机无疑应该是完备的计算机。带有 SPU 处理器的计算机就是一款完备计算机。 SPU 处理器是并行计算求出 SAT 问题满足解的处理器，它毫无疑问使当今的计算机进入了完备计算机时代。该计算机处理器采用存储计算模式，能够在多项式时间计算出 SAT 问题满足解。其原理，发明人几年前把它叫做“子句标志消去法”，现在看，叫“包含子句消去法”更为恰当。下面是作者 2016 年写的设计并行处理器 SPU的原理。现在作者已经将包含 SPU 设计的完备计算机带进了课堂。经过一年多的验证检验，提供给学生们的验证计算机使他们欢心鼓舞，未来的发展会让他们无可限量。 K-SAT FLAG AND ANSWER 姜咏江，中国北京 100013 摘要用k-SAT标志消去法能轻而易举地能够求出全部解。关键词 k-SAT, 子句消去法，子句标志消去法如果你熟悉用二进制表示数，那么 k-SAT 标志消去法的求解就很容易理解了。 1. 子句消去法用二进制数表示的 k-SAT ，如果将一个变量的值设定为 0 或 1 ，那么所有含有该变量具有相同值的子句都可以消去，然后对剩余部分继续这样求解，直至全部的变量值都设定完为止。如果这一过程的最后没有剩余子句了，那么所设的变量值全体就是这个 k-SAT 的满足解，否则 k-SAT 没有满足解。什么情况下会有剩余子句不能消去？假如有子句 x i x j x k ，如果这 3 个变量的值都设定了，并且 3-SAT 中有子句 x i ’x j ’x k ’ （这里的“ ’ ”表示求反运算），那么这个子句肯定会剩下。 x i x j x k 与 x i ’x j ’x k ’ 称为互反子句。互反子句有一个特性：没有反子句的子句变量值是满足解的组成部分。 n 个变量的 k-SAT 最多有对互反子句。如果每个变量的值都必须设定，那么有互反子句存在的那些变量，不论怎样设定值都会有剩余子句存在，因而 k-SAT 也不会有满足解。当设定一组 n 个变量值时，刚好 k-SAT 中没有这组值中组成的子句的反子句，那么就不会有剩余子句。于是 n 个变量的这组值就是 k-SAT 的满足解。我们的问题是怎样找到这组值？ 2. 解标志二进制数表示的子句如果是一个 n 位数的对应组成部分，称这个子句在这个 n 位数中。二进制数表示的互反子句一定在不同的 n 位数中。若包含互反子句的 n 位二进制数存在，则这些 n 位二进制数就不会是 k-SAT 的满足解，而 k-SAT 中没有反子句的子句，一定是某个满足解的组成部分。我们可以将 k-SAT 的每个子句能够构成的 n 位二进制数找出来。如果有一个 n 位二进制数不包含任何 k-SAT 的子句，说明这个在 k-SAT 中没有这些子句的反子句。于是就可以用这个位二进制数能够组成的子句的反子句值做为满足解。 n 元变量的 k-SAT 能够表明相关子句的 n 位数叫解标志。任何一个 k-SAT 的子句在解标志中，解标志为 1 ，否则为 0 。 3. 求出 K-SAT 的全部解用二进制数码来表示 k-SAT 的格式如表 1 左面所示，其中每个子句单独占一行。如果逻辑变量有 n 个，那么 k-SAT 的解标志就有 2 n 个，用二进制数码表示，就如同表 1 右面所示的那样 2 n 个 n 位二进制数。表 1 3-SAT 和解标志 … x4 x3 x2 x1 x0 NO x4 x3 x2 x1 x0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 2 0 0 0 1 0 1 1 1 3 0 0 0 1 1 0 0 1 4 0 0 1 0 0 1 1 0 5 0 0 1 0 1 1 1 1 6 0 0 1 1 0 0 0 0 7 0 0 1 1 1 1 0 1 8 0 1 0 0 0 1 1 0 9 0 1 0 0 1 0 1 1 10 0 1 0 1 0 1 1 1 11 0 1 0 1 1 0 0 0 12 0 1 1 0 0 0 1 0 13 0 1 1 0 1 1 0 0 14 0 1 1 1 0 1 1 0 15 0 1 1 1 1 0 0 1 16 1 0 0 0 0 17 1 0 0 0 1 18 1 0 0 1 0 AS.5' 1 1 0 1 0 19 1 0 0 1 1 AS.8' 1 0 1 1 1 20 1 0 1 0 0 AS.24' 0 0 1 1 1 21 1 0 1 0 1 22 1 0 1 1 0 23 1 0 1 1 1 24 1 1 0 0 0 25 1 1 0 0 1 26 1 1 0 1 0 27 1 1 0 1 1 28 1 1 1 0 0 29 1 1 1 0 1 30 1 1 1 1 0 31 1 1 1 1 1 求 k-SAT 的解过程十分简单。只要将包含子句的标志删除，那么全部子句处理完成，剩余的解标志为 0 的那些 n 位二进制数的反码，就是 k-SAT 的满足解。 4. 结论 k-SAT 标志消去法是一个多项式时间复杂度的算法。 n 个变量的 k-SAT 最多有2 k C n k 个子句。因为每个子句只进行一次消去解标志的操作，因而可知 k-SAT 求满足解的过程是一个 O( n k ) 时间复杂度的算法。实际上不难看出，标志消去法是一个求 k-SAT 所有解的算法。 2016-6-26

个人分类: 机器计算|1833 次阅读|0 个评论

用数据的眼光看待计算机根基

热度 1 accsys 2018-8-18 06:34

用数据的眼光看待计算机根基姜咏江数据从结构上分，只有了两种，那就是纯离散型和连续型。用电子计算机来处理数据，数据都抽象成了能够用二进制数码表示的点。点与点之间直接相互关联，就可以用连续的实数进行描述。而没有直接关联特征的那些点，是一盘散沙，称为纯离散数据，不能够直接用实数来描述，只能用逻辑值来描述。一切组成成分分析的问题都要经历纯离散数据的确认。如果用图像来解释，直接相互关联的点，可以通过计算机用连续的图像表达出来，而都不连续的点，就无法用连续的图像表示。前者，可以表示成视觉的线形式，用二维实数坐标可以处理成二维图像。纯离散数据，则无法用连续图像表出，至多表示出来的是散列的点，只能用逻辑值来确认其存在与否。开始设计完成的计算机，凭借 CPU 擅长处理一维的连续数据，且速度较快，而对二维连续数据（图像）处理就十分缓慢，对纯离散数据的处理就更是缓慢至极。为了加快对一定范围内图像处理的速度，人们发明了 GPU 。 GPU 是在 CPU 的基础上扩充了图像快速处理功能，并不是对 CPU 的否定。虽然 GPU 完善了计算机对连续型数据处理的快速，但对海量纯离散型数据的处理，仍然十分缓慢，达不到快速的需求。设计成功的 SPU 是秉承 CPU 、 GPU 的功能，引入“未知确定态”，增加了对纯离散数据并行存储计算快速处理设计，消除了以往对纯离散数据处理不可忍受的时间过程。如果将 GPU 看成是 CPU 第一次飞跃，那么 SPU 就是 CPU 的第二次飞跃。第一次飞跃，完成了对连续的二维数据快速处理，但对纯离散数据处理，仍然做不到快速。第二次飞跃就可以解决对纯离散数据的快速处理，从而使计算机能够在平常的时间内（多项式时间），完成对数据的全盘有效的快速处理。 2018/7/27

个人分类: SAT问题|2303 次阅读|2 个评论

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

accsys 2018-6-2 05:44

浅说限位数横向理论与计算机 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 3 =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 位限位数 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 “布尔逻辑电路问题”看似简单，在变量很少的情况下，只要逐一设定变量的可能值形成的数，总能够得到答案。但是在短时间内解决一个上百个变量的答案，就是用计算机程序执行运算，几乎都是不可忍受的。所以“布尔逻辑电路问题”成为了世界难题之一。一种最简单基本的方法，就是将 n 个变量的全部可能值一一进行验证，这就是一般所说的暴力破解法。如果问题中有 100 个逻辑变量，则需要测试 2 100 次，即使是用现在世界上最快的计算机，这种测试找到一个满足解，最坏的情况需要几百年，更不要说将“布尔逻辑电路问题”的全部解求出来了。这就是所谓的指数时间运算问题。 4. 子句块与SAT的解如果能够设定子句块的变量值能将其全部子句消去，就称这些变量值为子句块的解。消去子句的条件是：子句与变量的值的文字相同。很容易理解，“布尔逻辑电路问题”的一个子句块如果无解，那么“布尔逻辑电路问题”一定无解。为此需要先了解子句块的解。我们以 3 阶子句块为例（见表 2 ）。表 2 完全 3 阶子句块 X1 X2 X3 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 “布尔逻辑电路问题”简称为 SAT 问题。可以验证 3 阶子句块变量 x1x2x3 全部可能值为 000~111 。我们将这 8 个值逐一带入 SAT 的变量，消去有相同文字的子句，发现总有子句不能消去。这就是说表 2 的子句块无解。可以由限位数 “不是反码数至少有一位数码相同” 的性质证明子句块如下的一些性质：（ 1 ）子句块中子句的反子句不在，则这个子句是子句块的解；（ 2 ）属于一个子句块的一对互反子句都不在这个子句块中，它们都是这个子句块的解；（ 3 ） K 阶子句块有 m 个子句（ m2 k ），则该子句块有 2 k -m 个解。子句块中的子句就是限位数。因而不是反子句的子句之间至少有一位数码相同，又由于反码数是唯一的，故性质（ 1 ）成立。同样道理，性质（ 2 ）也成立。由性质（ 1 ）（ 2 ）自然就推出了性质（ 3 ）。 SAT 变量设定的一组值可以将其所有子句块的子句消去，这组值就是 SAT 的满足解。有上面的介绍，不难理解，如果 SAT 有 n 个变量，那么如果 SAT 有解，一定是在 0~2 n -1 这 2 n 个数当中，这 2 n 个数就叫解空间。在解空间能不能一下子找到 SAT 满足解？ 5. SAT 全解在解空间中快速找到所有 SAT 满足解的方法，在 2014 年就诞生了。这被描述成了下面的定理。全解定理：解空间中将子句包含在其中的那些可能解消去，剩余的可能解的反码数都是 SAT 的满足解。这个定理的证明并不难：因为不在 SAT 的子句，可能是 SAT 子句块中子句的反子句，或者互反子句都不在 SAT 子句块中。根据上面提到的子句块解是性质（ 1 ）（ 2 ），在可能解空间中消去子句所在的可能解，剩余可能解都是那些不在 SAT 中的子句组成的，这其中包含互反子句都不在 SAT 中。现在对剩下的这些可能解取反，那么得到的这些可能解组成的子句，或是 SAT 各个子句块的子句（其反子句不在），或者是那些不在 SAT 子句块中的互反子句构成的，因而将这些可能解任何一个带到 SAT ，都可以将其全部子句块消去。 6. 现行计算机为什么不能快速计算SAT问题？现行的计算机系统基本上是以串行工作的方式运行的，对于像 SAT 这样的问题，由于解空间十分庞大，运算器要顺序地验证每一个可能解，并将全部解求出，就要验证 2 n 次。当 n 较大时，这个指数函数验证次数十分庞大。每次解决有一个 SAT 问题都要这样验证，顺序来做，自然耗时过长，不能够满足时间上的需要。 7. 必须制造一种能够并行处理SAT的处理器依据 5 的论述，不难理解，如果将 2 n 个中包含每个子句的可能解快速地检测出来，并把这些可能解消去，那么剩下的那些可能解的反码数就是 SAT 的全部解了。如何能够快速做到这一点，这需要设计出能够瞬间实现对子句进行检验的处理器。我们就将这样的处理器简称为 SPU （ SAT Process Unit ）。毫无疑问，一个子句包含在 2 n 个可能解的哪些个当中，要一个个地访问核对，这是是一个指数时间问题。对一个确定的子句，是否可以同时访问这 2 n 个可能解 ? 这就是 SPU 设计制造的关键设想。本文作者既提出了限位数理论，又研制出了能够真正并行对 SAT 求出全部解的计算机。 SPU 利用限位数横向理论，采用的是存储计算模式，从而将指数时间计算的问题，变成了同时计算来完成。 8. 结束语科学界已经证明了像密码破解、基因计算、哈密顿回路、组成分析、顶点覆盖、人工智能等问题，都可以短时间内转化为 SAT 问题处理。世界上每年都有国际 SAT 求解大赛，目的是找到 SAT 多项式时间（快速求解）的方法。可见 SAT 问题求解的重要性。存储计算模式，设计制造本身是复杂的。然而这种模式的 SPU 一经问世，所有可以转化为 SAT 问题的难题，都会短时间迎刃而解。许多密码的问题都能够转化为 SAT 问题，用 SPU 计算机破解密码，将会是分分秒秒的事情。在国际不够太平的今天，其意义重大可想而知。 2018/6/2

个人分类: 限位数|2677 次阅读|0 个评论

再次提示SPU的重要性，信我，这是一片全新的天地

热度 1 accsys 2018-5-18 11:56

一些人劝我将研发的SPU写成文章投到国外的刊物上。我觉得对一个73岁的人没什么必要。既然我创造的是可以让我国在计算机核心技术上超前的东西，何须交到国外？特别是在中美较劲的时候。我深信，能够懂我的年轻人，必将为中国的计算机先进核心技术做出贡献。要创新，必须放弃不能够解决问题的那些理论，寻找全新的理论起点。 2018/5/18

个人分类: 随笔|2346 次阅读|5 个评论

如果密码都能被瞬间破解将会怎样？

热度 1 accsys 2018-2-7 17:10

研究出了SAT同时处理器SPU,我有些害怕了。都说任何的密文都可以变换成合取范式CNF，而SPU处理器可以在分秒之间求出SAT的全部解，这意味从此没有安全的密码了？我不是搞密码的专家，是否果真的如此，我不敢乱讲。但，无论如何，此生，能够创造出一种新的处理器，我心满足。

个人分类: P/NP问题|3190 次阅读|4 个评论

帐号		自动登录	找回密码
密码			注册

关闭安全验证

标签: SPU

相关帖子

相关日志

关闭 安全验证

标签: SPU

相关帖子

相关日志

关闭安全验证