意大利米兰理工提出新型计算电路,或超越量子计算

想象一下,假如回到中学时代,你是如何解线性方程组的?我想你用的是高斯消元法。对于一个有3个变量x、y、z的线性方程组,你会一步一步地消去其中一个方程中的两个变量,从而解出剩下的那个变量,再返回去用相同的方法解出其余两个变量。

计算机也是这么做的。对于一个三元线性方程组,它能很快地给出计算结果,但是随着方程的增多,它所需要的时间将迅速增加。用计算机科学的语言说,它的时间复杂度O(N3),意味着计算机的运行时间随方程数量的三次方增加,如果解一个包含10个变量的线性方程组需要的时间是1,那么解一个包含100个变量的线性方程组需要的时间是1000。在实际应用中,比如运行在超级计算机上的气候模拟、基因分析、材料合成,涉及的变量数可能达百万量级,那么解线性方程组的时间将会是1018。即使时间单位是一纳秒(十亿分之一秒),1018也意味着十亿秒,约三十年。这么慢的计算速度是难以忍受的,人们通常通过部署多个处理器,利用并行计算来缩短计算时间,但是相对于时间复杂度的增长速度,这些改变都不是本质的。

量子计算可以为解线性方程组带来本质的改变。于2008年提出的HHL量子算法可以以O(logN)的时间复杂度解线性方程组,这就意味着,如果解一个包含10个变量的线性方程组需要的时间是1,那么解一个包含一百万个变量的线性方程组需要的时间也仅是6,从而实现计算速度的指数级增长。量子计算看起来非常有前景,但由于存在工作温度极低和量子退相干等重重困难,量子计算机(尤其是可商业化的量子计算机)的实现遥遥无期。另外一方面,尽管量子计算已能实现指数提速,但其实可能存在一种更快的计算方式,即时间复杂度O(1),意味着解不同大小的线性方程组所花的时间是相同的。

近日,意大利米兰理工大学的一支研究团队报道了这样一个计算电路,可以实现一步解线性方程组,耗时只需几十纳秒。这样的计算性能,不仅优于传统的数字计算机,也优于未来的量子计算机。同时,该团队表示,基于这项发明,他们很快将开发出革新人工智能技术的新一代计算加速器。

该项研究于最近发表在国际顶级期刊《美国科学院院刊》。关于这项研究的具体内容,该项目的负责人Daniele Ielmini解释:“解线性方程组指的是,找出满足方程Ax=b的未知向量x,A是系数矩阵,b是已知向量。”要解这类问题,“常规的数字计算机根据一个特定的算法,需要很多步操作才能完成,也就意味着需要相当的计算时间和能耗”,Daniele Ielmini强调。

作为欧洲研究委员会旗下项目的一部分,该电路通过把矩阵A存储在一种特别的器件(忆阻器)里,以一种名为存内计算的新型计算方式解线性方程组。Daniele Ielmini继续解释,“忆阻器可以存储模拟数值,因此利用忆阻器构成的矩阵可以映射一个系数矩阵A,从而实现极速计算。此外,除了解线性方程组,忆阻器电路还可以解矩阵的特征向量等问题。” “所有的这些操作都只需一步就能完成。”他强调。

论文的第一作者孙仲表示,“现实生活中的很多问题本质上是一个线性方程组,比如谷歌公司的网页排序算法PageRank,本质上就是求解一个随机矩阵的特征向量,那么用我们的电路可以一步完成计算,从而为这些搜索引擎提供加速。”“我们的电路已经在大量的代数问题上测试并得到验证,甚至包括复杂的微分方程,比如解一个电子的量子波函数的薛定谔方程。”他补充道。

忆阻器电路求解薛定谔方程概念图

由于可以一步完成不同的计算任务,该电路非常有应用前景。不同于量子计算,该电路所利用的技术、产品在工业上均已非常成熟或者正在市场化,包括Intel和Micron近几年推出的3D XPoint存储技术。去年,该团队在学校与德勤举办的产品转化大赛上展示了他们基于该线性方程组求解电路和机器学习电路的项目,赢得了大赛唯一的Disruptive Innovation奖。目前,团队正在学校孵化器和德勤等咨询公司的帮助下,准备把技术带向市场。

团队成员展示他们的产品转化大赛Disruptive Innovation奖

 


理论量子计算AI加速器意大利米兰理工计算电路
3
相关数据
排序算法技术

排序算法是将一串数据依照特定排序方式进行排列的算法,最常用到的排序方式是数值顺序以及字典顺序。基本上,排序算法的输出必须遵守下列两个原则:输出结果为递增序列(递增是针对所需的排序顺序而言);输出结果是原输入的一种排列、或是重组。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

概念图技术

概念图(CGs)是知识表示的形式主义。 在第一篇关于CG的论文中,John F. Sowa用它们来表示数据库系统中使用的概念模式。 关于CGs的第一本书(Sowa 1984)将它们应用于人工智能、计算机科学和认知科学等广泛的主题。

量子计算技术

量子计算结合了过去半个世纪以来两个最大的技术变革:信息技术和量子力学。如果我们使用量子力学的规则替换二进制逻辑来计算,某些难以攻克的计算任务将得到解决。追求通用量子计算机的一个重要目标是确定当前经典计算机无法承载的最小复杂度的计算任务。该交叉点被称为「量子霸权」边界,是在通向更强大和有用的计算技术的关键一步。

推荐文章
暂无评论
暂无评论~