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

在數(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)隨機(jī)存取存儲器(DRAM)通常處理。

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

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

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

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

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

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

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

論文的共同作者是CSAIL研究生Shuotao Xu，Andy Wright和Sizhuo Zhang，CSAIL的兩名研究生和電氣工程與計算機(jī)科學(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算法對于主機(jī)來說是計算密集型的，因此研究人員在設(shè)備中實現(xiàn)了自定義加速器。加速器充當(dāng)主機(jī)和閃存芯片之間的中間點，執(zhí)行算法的所有計算。這會給加速器帶來如此大的功率，主機(jī)可以是低功率PC或筆記本電腦，管理分類數(shù)據(jù)并執(zhí)行其他小任務(wù)。

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

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

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