科学网—标签 - 并行处理器

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

热度 4 accsys 2019-6-13 07:04

2018 年初，我完成了能够真正实现并行计算计算机的设计与验证。直到现在为止，我还没有听说有那家计算机公司推出数据并行处理器。数据并行处理器能够将密码破解一类的重大问题，分秒之间破解。意义是否重大？我是一个退休的教师，投资？申请专利？自己办公司？一切都需要一个字，我无法办到。特别是后续工作，绝非一人之力所能承担。我试图将我的发明写成材料送到科技部，费了很大力气，希望能够将材料转到有关部门。然而就在门卫处被拦了下来，他们联系了有关部门，得到的答复是不接受材料。我后来又到工信部递交材料，希望工信部出面组织一个小规模的评价。工信部有关领导很是支持，并将材料转给了行业专家。经过一段时间，给了答复，“理论没有问题”。这已经使我欢欣鼓舞了，因为一些基本理论是我自己搞的。我要求对我设计制作的验证机进行鉴定。然而专家们实在是没有时间。再后来我将 PPT 给了二院研究生院的校长，请他代我转给专家，希望借助他们的力量，将我的发明实际应用起来。再后来，我将 PPT 在科学网上公开，希望找到知音。一年多的时间过去了，我寻找不到支持，似乎有些气馁。华为的处境对我多少有些刺激。这项超水平的计算机发明，若能够得到国家支持，其后果可想而知。量子计算机任重而道远。我的 SPU 计算机具有量子计算机的效果，就没有人感兴趣吗？希望得到国家关注。姜咏江 2019-6-13

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

完备计算机

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 个评论

计算机科学P/NP问题并行计算处理器研制成功!

热度 1 accsys 2018-1-20 12:38

纯离散数据并行处理运算器计算机征询合作者姜咏江现在的计算机处理器，本质上是一种顺序处理方式的产物。这种计算机处理连续数据的问题非常有效，但处理象哈密顿回路、超大规模集成电路可靠性、密码破译、人工智能、基因准确计算等一系列纯离散数据类型的问题时，计算的时间复杂度都是指数型的，超长的耗时是难以忍受的。处理这类超长时间才能解决的问题，人们自然想到多处理器并行，于是搞起超级多处理器计算机，借助于网络，搞多处理机协同操作。但从效率，投入、易用等诸多方面来看，都有些不尽人意。这就迫切需要研发轻便、易用、类似个人计算机规模，既能够处理连续数据，也能够并行处理纯离散型数据，功能超快超强的计算机。如果您了解计算机科学的最大难题 —— P Versus NP problem ，您就一定知道，构造一种能够快速处理 SAT 问题的处理器是何等的重要。 2015 年，在理论上我找到了完成求 SAT 问题全解的“子句标志消去法”（已在科学网博客中发表，简介请见后面介绍）。该方法是不是多项式时间算法，关键取决于计算机能否在 2 n 个可能解中，在一个计算机节拍，就能消去所有包含这个子句的那些可能解。理论的成功，并不能给企业带来更大的收益，而技术的创新，会为企业带来源源不断的财富。这不论对硬件还是软件的公司来说，历史已经证明都是对的。为了不使理论落空，也为了国家和个人计算机事业的发展。经过了几十年的艰苦研究，终于制造成功了 SAT 运算器。 SAT 运算器会使那些用现在的计算机要算上百年、千年的问题，有望在极短的时间内获得解决。 SAT 处理器存在的计算机一定是当今世界最先进的计算机系统。 SAT 问题最直接的应用就是数字集成电路可靠性检测，密码破解，基因计算，求解哈密顿回路，人工智能等方面。在数字智能芯片应用如此广泛的时代，特别在航天、军事领域，杜绝器件不可靠性该是何等的重要。本公司已经完成了带有 SAT 处理器及其指令系统的验证计算机制造，下一步要在三年时间内完成这种世界上最先进的计算机系统制造。目前正在征求确有实力计算机制造企业合作，也愿意接受国内投资人参与。详细问题可面谈商定。附录：子句标志消去法简介数字集成电路的各点电压可靠性检测，可以通过 The Tseytin transformation 转化成 SAT 问题求解。如何求得 SAT 的全部解？我这里给出一个 3-SAT 的例子（文字用0、1表示），只要读者将右面的 n 位数中含有左面子句的数码且位置相同数同子句一起逐一消去（ n 位数没有时，只消去子句）。当所有子句消去之后，剩下的 n位数的反码都是解！这里n=5，有底纹的部分表示消去了。可以将得到的那些 n位数（左面下面的3个5位二进制数）带入上面 SAT进行验证，可知完全正确。 K 个文字的子句最多有 2的k次方乘以n取k的组合数，即为2 k C k n ，这是关于 n的k次多项式。也就是说该算法时间复杂度为O(n k )。需要说明，右面的n位二进制数是装在每一个熟悉二进制表数人的心中的，正如我们熟悉十进制数的数码在什么位置一样。莫把右面的2 n 个数看成算法操作的一部分。这正如同 x是2 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 1 1 0 1 0 　 19 　 1 0 0 1 1 1 0 1 1 1 　 20 　 1 0 1 0 0 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 电话： 13651184072 ， 13522984778 2018 年 1 月 19 日

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

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

关闭安全验证

标签: 并行处理器

相关帖子

相关日志

关闭 安全验证

标签: 并行处理器

相关帖子

相关日志

关闭安全验证