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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

卸載計(jì)算

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

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

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

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