設(shè)備允許個人計算機處理大圖

在數(shù)據(jù)科學(xué)的說法中，圖形是節(jié)點和連接線的結(jié)構(gòu)，用于映射復(fù)雜數(shù)據(jù)關(guān)系的分?jǐn)?shù)。分析圖表對于廣泛的應(yīng)用程序非常有用，例如對網(wǎng)頁進(jìn)行排名，分析社交網(wǎng)絡(luò)以獲取政治見解，或繪制大腦中的神經(jīng)元結(jié)構(gòu)。

然而，由數(shù)十億個節(jié)點和線組成，大圖可以達(dá)到太字節(jié)的大小。的圖形數(shù)據(jù)在跨多個耗電服務(wù)器昂貴的動態(tài)隨機存取存儲器(DRAM)通常處理。

麻省理工學(xué)院計算機科學(xué)與人工智能實驗室(CSAIL)的研究人員現(xiàn)在設(shè)計了一種設(shè)備，該設(shè)備使用廉價的閃存存儲 - 智能手機中使用的類型 - 僅使用一臺個人計算機處理大量圖形。

在處理圖形數(shù)據(jù)時，閃存通常比DRAM慢得多。但研究人員開發(fā)出一種由閃存芯片陣列和計算“加速器”組成的設(shè)備，可幫助閃存實現(xiàn)類似DRAM的性能。

為設(shè)備供電是一種新穎的算法，可以將圖形數(shù)據(jù)的所有訪問請求按順序排序，閃存可以快速輕松地訪問。它還合并了一些請求以減少開銷 - 組合計算時間，內(nèi)存，帶寬和其他計算資源的排序。

研究人員針對幾個處理幾個大型圖形的傳統(tǒng)高性能系統(tǒng)運行該設(shè)備，其中包括大量的Web Data Commons Hyperlink Graph，它有35億個節(jié)點和1280億個連接線。為了處理該圖，傳統(tǒng)系統(tǒng)都需要一臺價值數(shù)千美元且包含128千兆字節(jié)DRAM的服務(wù)器。研究人員通過將兩臺設(shè)備(總計1千兆字節(jié)的DRAM和1兆字節(jié)的閃存)插入臺式計算機，實現(xiàn)了相同的性能。此外，通過組合多個設(shè)備，他們可以處理大量圖形 - 高達(dá)40億個節(jié)點和1280億個連接線 - 這是其他系統(tǒng)無法在128千兆字節(jié)服務(wù)器上處理的。

“最重要的是，我們可以在更低，更少，更冷的情況下保持性能，如溫度和功耗 - 機器，”CSAIL研究生Sang-Woo Jun和描述該設(shè)備的論文的第一作者Sang-Woo Jun說。正在國際計算機體系結(jié)構(gòu)研討會(ISCA)上發(fā)表。

該設(shè)備可用于降低與圖形分析相關(guān)的成本和能源，甚至可以在廣泛的應(yīng)用中提高性能。例如，研究人員目前正在創(chuàng)建一個可以識別導(dǎo)致癌癥的基因的程序。谷歌等大型科技公司也可以通過使用更少的機器來運行分析來利用這些設(shè)備來減少能源占用。

“圖形處理是一個普遍的想法，”共同作者，計算機科學(xué)工程的約翰遜教授Arvind說。“頁面排名與基因檢測有什么共同之處?對于我們來說，它是相同的計算問題 - 只是具有不同含義的不同圖表。某人開發(fā)的應(yīng)用程序類型將決定它對社會的影響。”

論文的共同作者是CSAIL研究生Shuotao Xu，Andy Wright和Sizhuo Zhang，CSAIL的兩名研究生和電氣工程與計算機科學(xué)系。

在圖形分析中，系統(tǒng)將基本上根據(jù)與其他節(jié)點的連接以及其他度量來搜索和更新節(jié)點的值。例如，在網(wǎng)頁排名中，每個節(jié)點代表一個網(wǎng)頁。如果節(jié)點A具有高值并連接到節(jié)點B，則節(jié)點B的值也將增加。

傳統(tǒng)系統(tǒng)將所有圖形數(shù)據(jù)存儲在DRAM中，這使得它們能夠快速處理數(shù)據(jù)，但也昂貴且耗電。一些系統(tǒng)將一些數(shù)據(jù)存儲卸載到閃存，這更便宜但速度更慢且效率更低，因此它們?nèi)匀恍枰罅康腄RAM。

研究人員的設(shè)備依賴于研究人員所稱的“排序 - 減少”算法，該算法解決了使用閃存作為主要存儲源的一個主要問題：浪費。

圖形分析系統(tǒng)需要訪問跨越龐大，稀疏圖形結(jié)構(gòu)的彼此相距很遠(yuǎn)的節(jié)點。系統(tǒng)通常要求直接訪問例如4到8個字節(jié)的數(shù)據(jù)以更新節(jié)點的值。DRAM提供了非常快速的直接訪問。但是，F(xiàn)lash只訪問4到8千字節(jié)塊的數(shù)據(jù)，但仍然只更新幾個字節(jié)。跳過圖表時重復(fù)對每個請求的訪問會浪費帶寬。“如果你需要訪問整個8千字節(jié)，并且只使用8個字節(jié)然后扔掉其余部分，你最終會丟掉1000倍的性能，”Jun說。

sort-reduce算法改為采用所有直接訪問請求，并按標(biāo)識符順序?qū)λ鼈冞M(jìn)行排序，標(biāo)識符顯示請求的目的地 - 例如將節(jié)點A的所有更新，節(jié)點B的所有更新等組合在一起，依此類推。然后，F(xiàn)lash可以同時訪問數(shù)千個請求的千字節(jié)大小的塊，從而提高效率。

為了進(jìn)一步節(jié)省計算能力和帶寬，該算法同時將數(shù)據(jù)合并到可能的最小分組中。每當(dāng)算法記錄匹配標(biāo)識符時，它將它們加到單個數(shù)據(jù)包中 - 例如A1和A2變?yōu)锳3。它繼續(xù)這樣做，創(chuàng)建越來越小的具有匹配標(biāo)識符的數(shù)據(jù)包，直到它產(chǎn)生最小的可能數(shù)據(jù)包進(jìn)行排序。這大大減少了重復(fù)的訪問請求數(shù)量。

在兩個大圖上使用sort-reduce算法，研究人員將需要在閃存中更新的總數(shù)據(jù)減少了大約90%。

卸載計算

然而，sort-reduce算法對于主機來說是計算密集型的，因此研究人員在設(shè)備中實現(xiàn)了自定義加速器。加速器充當(dāng)主機和閃存芯片之間的中間點，執(zhí)行算法的所有計算。這會給加速器帶來如此大的功率，主機可以是低功率PC或筆記本電腦，管理分類數(shù)據(jù)并執(zhí)行其他小任務(wù)。

“加速器應(yīng)該可以幫助主機計算，但是我們已經(jīng)[計算]到目前為止主機變得不重要了，”Arvind說。

“麻省理工學(xué)院的工作展示了一種在非常大的圖形上執(zhí)行分析的新方法：他們的工作利用閃存存儲圖形并利用”現(xiàn)場可編程門陣列“[定制集成電路]以巧妙的方式執(zhí)行分析和有效使用閃存所需的數(shù)據(jù)處理，“得克薩斯大學(xué)奧斯汀分校計算機科學(xué)教授Keshav Pingali說。“從長遠(yuǎn)來看，這可能會導(dǎo)致系統(tǒng)能夠在筆記本電腦或臺式機上高效處理大量數(shù)據(jù)，這將徹底改變我們進(jìn)行大數(shù)據(jù)處理的方式。”

Jun表示，由于主機功能如此低，Jun的長期目標(biāo)是為消費者創(chuàng)建一個通用平臺和軟件庫，為超出圖形分析的應(yīng)用開發(fā)自己的算法。“你可以將這個平臺插入筆記本電腦，下載[軟件]，并編寫簡單的程序，以便在筆記本電腦上獲得服務(wù)器級性能，”他說。