今日PNAS:利用新型存储器阵列一步解线性方程组和特征向量

线性代数存在于几乎所有的科学和工程领域,比如统计学、物理学、信号处理,和机器学习。线性代数中最核心的一个操作是解不同的矩阵方程,包括解线性方程组和特征向量等。在传统计算机上,解矩阵方程需要一些精心设计的算法,如高斯消元法、LU分解法,然后在多项式时间内(比如O(N3),N是矩阵行/列数)获得方程解。


在大数据时代,人们要处理的数据呈爆发式增长,而很多数据处理本质是一个矩阵方程问题,如谷歌的网页排序(PageRank算法)、利用超级计算机模拟量子效应(解薛定谔方程)。随着摩尔定律的失效,以及由于冯诺依曼架构存储、计算分离的固有限制,想更快、更省地完成数据处理变得越来越难,而计算的时间和能耗效率在大数据时代显得尤为重要。


近年来,存内计算(in-memory computing)兴起,通过在存储单元内完成计算将显著提高计算效率。一个典型的存内计算例子是利用阻变存储器(或称忆阻器)的交叉阵列一步完成矩阵-向量乘法的运算,从而快速完成包括训练神经网络在内的大数据任务。然而,一步解矩阵方程,如线性方程组Ax = b,仍然是一个挑战。在我们最新的PNAS文章里,我们报道了利用交叉存储阵列,通过引入反馈电路,可以一步解线性方程组和矩阵的特征向量,进而实现一步解微分方程,包括傅里叶方程、薛定谔方程,和一步完成谷歌的网页排序。


对于解线性方程组Ax = b,我们采用的电路如图1(a)所示。电路中包含了一个交叉存储阵列,阵列中每一个行线和列线之间有一个阻变存储器件,它的电导值一一对应于矩阵中的一个元素值。已知向量b由行线的输入电流表示,通过运算放大器(运放)引入的负反馈机制将使行线虚接地,从而列线上运放的输出电压可以表示未知向量x的解值。由于矩阵A以非易失的形式存储在交叉阵列中,一旦施加输入电流,相应的线性方程组就能一步得到解答。实验中,我们存储的矩阵A如图1(a)所示。图1(b)给出了一个相应的线性方程组的实验解,以及它的解析解。可以看到,实验解十分接近解析解(相对误差在3%),从而证明了我们方案的可行性。逆矩阵也是线性代数中一项非常重要的内容,它也可以通过求解多个线性方程组获得,实验解和解析解的比较如图1(c)所示。

1000 (4).jpg

图1. 线性方程组求解电路及求解结果。

阻变存储器件的电导值只能为正数,因此图1(a)的电路只适用于解系数为正的线性方程组。为了使我们的方案具有普适性,即,解任意实数的线性方程组,我们进一步拓展了电路,如图2(a)所示。图中利用了两个交叉阵列和反相器,实现了两个正矩阵之间的差,从而能够代表任意实数矩阵。基于该普适的线性方程组求解电路,利用有限差分法,我们求解了一个微分方程。如图2(b)所示,在两个电极之间施加一个电压,电极之间导线上的温度分布可以用一维静态傅里叶方程来描述。图2(c)给出了该微分方程的电路解,可以发现与方程的解析解完美重合,从而证明了我们的电路用于快速求解实际问题的可靠性。

1000 (5).jpg

图2. 针对任意实数矩阵的线性方程组求解电路,及求解热传导的一维傅里叶方程。

基于交叉存储阵列和运放的负反馈机制,我们还能求解矩阵方程Ax =λx,λ为矩阵的特征值,x为相应的特征向量。电路如图3(a)所示,矩阵A依然由交叉阵列表示,λ由跨阻放大器的跨导表示,反相器的输出电压即为待解的x,从而实现一步求解特征向量。需要注意的是,图3(a)电路用于求解正特征值的特征向量,而假如求解负特征值的特征向量,将反相器移去即可,负特征值的绝对值依然由跨阻放大器的跨导表示。和线性方程组求解电路一样,特征向量求解电路也可以拓展到任意实数矩阵。谷歌公司的网页排序算法(PageRank)本质上就是求解一个随机矩阵的最大特征值的特征向量,因此,我们的电路可以用于一步实现网页排序,而不需要繁复的迭代算法,从而为搜索引擎提供加速。图3(b)表示了各科技巨头公司的Wikipedia网页之间的连接情况(网页i指向网页j代表网页i引用网页j),图3(c)则给出了电路解的排序结果和解析解之间的比较,可以发现二者排序一致。

1000 (6).jpg

图3. 特征向量求解电路及PageRank。


薛定谔方程HΨ= EΨ是量子力学的基础,为了获得一个量子系统的波函数分布,必须求解相应的薛定谔方程。作为一个微分方程,薛定谔方程可以通过有限差分法转化为一个特征向量问题。图4(a)是一个一维量子势阱,为了求解它的基态波函数,我们将待求解的波函数离散化,从而将哈密顿量H转化为一个矩阵,基态能量E则是最小特征值(负数),而离散化Ψ则是待求解的特征向量。图4(b)给出了该波函数的电路解,可以看到它很好地描述了一维量子势阱基态的波函数分布,因此证明了我们的电路具有很大的潜力用于加速模拟量子系统,比如在新型材料合成和新型药物开发等领域。



图4. 利用特征向量求解电路解一维量子势阱的基态波函数。

在我们的工作中,通过利用非易失的阻变存储器(忆阻器)交叉阵列和引入负反馈机制,常见的线性代数问题,包括解线性方程组、解特征向量、解微分方程可以在一步内完成,从而显著提高计算速度,同时降低计算能耗,为未来的存内计算系统应用于实际的大数据问题中打下了坚实基础。


该工作由来自意大利米兰理工大学的一支团队完成,团队专注于利用新型存储器件加速传统计算和机器学习的开发。孙仲博士为论文的第一作者,Daniele Ielmini教授为论文的通讯作者。


发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注