義大利米蘭理工提出新型計算電路,啟發新一代AI加速器
想象一下,假如回到中學時代,你是如何解線性方程組的?我想你用的是高斯消元法。對於一個有3個變數x、y、z的線性方程組,你會一步一步地消去其中一個方程中的兩個變數,從而解出剩下的那個變數,再返回去用相同的方法解出其餘兩個變數。
計算機也是這麼做的。對於一個三元線性方程組,它能很快地給出計算結果,但是隨著方程的增多,它所需要的時間將迅速增加。用電腦科學的語言說,它的時間複雜度是 O ( N 3 ),意味著計算機的執行時間隨方程數量的三次方增加,如果解一個包含10個變數的線性方程組需要的時間是1,那麼解一個包含100個變數的線性方程組需要的時間是1000。在實際應用中,比如執行在超級計算機上的氣候模擬、基因分析、材料合成,涉及的變數數可能達百萬量級,那麼解線性方程組的時間將會是10 18 。即使時間單位是一納秒(十億分之一秒),10 18 也意味著十億秒,約三十年。這麼慢的計算速度是難以忍受的,人們通常通過部署多個處理器,利用平行計算來縮短計算時間,但是相對於時間複雜度的增長速度,這些改變都不是本質的。
量子計算可以為解線性方程組帶來本質的改變。於2008年提出的HHL量子演算法可以以 O (log N )的時間複雜度解線性方程組,這就意味著,如果解一個包含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獎