麻省理工學(xué)院計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室（CSAIL）的研究人員設(shè)計(jì)出一種設(shè)備，使用廉價(jià)的閃存，僅使用一臺(tái)個(gè)人電腦就能處理大量的圖形，達(dá)到與數(shù)千美元的傳統(tǒng)服務(wù)器一致的性能。研究者認(rèn)為，這將徹底改變我們處理大數(shù)據(jù)的方式。

在數(shù)據(jù)科學(xué)的說(shuō)法中，圖（graph）是指用于映射大量復(fù)雜的數(shù)據(jù)關(guān)系的節(jié)點(diǎn)（nodes）和連接線（connecting lines）的結(jié)構(gòu)。分析graph在許多應(yīng)用中非常有用，例如網(wǎng)頁(yè)排名、分析社交網(wǎng)絡(luò)以獲取政治見(jiàn)解，或者繪制大腦的神經(jīng)元結(jié)構(gòu)。

然而，由數(shù)十億個(gè)節(jié)點(diǎn)和線組成的大型 graphs 大小可以達(dá)到TB級(jí)。通常來(lái)說(shuō)，圖數(shù)據(jù)的處理需要跨多個(gè)耗電量大的服務(wù)器，在昂貴的動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器（DRAM）中進(jìn)行。

最近，麻省理工學(xué)院計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室（CSAIL）的研究人員設(shè)計(jì)出一種設(shè)備，使用廉價(jià)的閃存（智能手機(jī)中使用的那種），僅使用一臺(tái)個(gè)人電腦就能處理大量的圖形。

該設(shè)備包含一個(gè)閃存芯片陣列（圖中黑色的8個(gè)芯片）和一個(gè)計(jì)算“加速器”（芯片陣列左邊）。研究人員提出一種新算法，將圖形數(shù)據(jù)的所有訪問(wèn)請(qǐng)求排序?yàn)殚W存可以輕松訪問(wèn)的順序，同時(shí)合并一些請(qǐng)求以減少排序開(kāi)銷。

閃存芯片陣列+計(jì)算加速器，在個(gè)人電腦達(dá)到服務(wù)器級(jí)性能

在處理圖數(shù)據(jù)時(shí)，閃存通常比DRAM慢得多。但研究人員開(kāi)發(fā)出一種由閃存芯片陣列和計(jì)算“加速器”組成的設(shè)備，可以使閃存達(dá)到類似于DRAM的性能。

驅(qū)動(dòng)該設(shè)備的是一種新的算法，它可以將圖數(shù)據(jù)的所有訪問(wèn)請(qǐng)求排序?yàn)殚W存可以快速、輕松訪問(wèn)的順序。它還將一些請(qǐng)求合并，以減少排序的開(kāi)銷——組合計(jì)算時(shí)間、內(nèi)存、帶寬和其他計(jì)算資源。

研究人員使用該設(shè)備與幾個(gè)傳統(tǒng)的高性能系統(tǒng)一起處理幾個(gè)大型圖，包括龐大的Web Data Commons Hyperlink Graph，該Graph有35億個(gè)節(jié)點(diǎn)和1280億個(gè)連接線。為了處理這個(gè)Graph，傳統(tǒng)的系統(tǒng)需要耗資數(shù)千美元的服務(wù)器，以及128GB的DRAM。研究人員將兩臺(tái)新設(shè)備（總計(jì)1GB的DRAM和1TB的閃存）接入臺(tái)式電腦，獲得了同樣的性能。此外，通過(guò)合并幾個(gè)設(shè)備，可以處理更大的圖——多達(dá)40億個(gè)節(jié)點(diǎn)和1280億個(gè)連接線——而其他系統(tǒng)無(wú)法在128G的服務(wù)器上處理這些圖。

研究人員將兩臺(tái)設(shè)備（總計(jì)1GB的DRAM和1TB的閃存）接入一臺(tái)臺(tái)式電腦，獲得了與數(shù)千美元的傳統(tǒng)服務(wù)器同樣的性能。

CSAIL的研究生、論文第一作者Sang-Woo Jun說(shuō)：“最重要的是，我們可以用更小功耗、更少、溫度更低的設(shè)備保持一樣的性能。”該研究發(fā)表在今年的國(guó)際計(jì)算機(jī)體系結(jié)構(gòu)研討會(huì)（ISCA）上。

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

“圖形處理（graph processing）是一個(gè)很普遍的想法，”該研究的合作者、計(jì)算機(jī)科學(xué)工程系教授Arvind說(shuō)，“網(wǎng)頁(yè)排名和基因檢測(cè)有什么共同之處呢？對(duì)我們來(lái)說(shuō)，它們是相同的計(jì)算問(wèn)題，只不過(guò)不同的graph表達(dá)的含義不同。”

論文合著者還有CSAIL的兩名研究生Shuotao Xu和Andy Wright，以及電子工程與計(jì)算機(jī)科學(xué)系的Sizhuo Zhang。

sort-reduce算法

在圖分析中，系統(tǒng)根據(jù)節(jié)點(diǎn)與其他節(jié)點(diǎn)的連接以及其他度量指標(biāo)來(lái)搜索和更新節(jié)點(diǎn)的值。例如，在網(wǎng)頁(yè)排名中，每個(gè)節(jié)點(diǎn)代表一個(gè)網(wǎng)頁(yè)。如果節(jié)點(diǎn)A具有較高的值并連接到節(jié)點(diǎn)B，那么節(jié)點(diǎn)B的值也會(huì)增加。

傳統(tǒng)的系統(tǒng)將所有圖數(shù)據(jù)存儲(chǔ)在DRAM中，這使得它們?cè)谔幚頂?shù)據(jù)時(shí)速度很快，但也導(dǎo)致成本昂貴而且耗電。有些系統(tǒng)將部分?jǐn)?shù)據(jù)存儲(chǔ)卸載到閃存上，這種方式更便宜，但速度更慢，效率更低，因此仍需要大量的DRAM。

CSAIL研發(fā)的新設(shè)備運(yùn)行在被稱為“sort-reduce”的算法上，該算法解決了使用閃存作為主要存儲(chǔ)源的一個(gè)主要問(wèn)題：浪費(fèi)。

圖分析系統(tǒng)需要通過(guò)大量的、稀疏的圖結(jié)構(gòu)訪問(wèn)彼此間距離很遠(yuǎn)的節(jié)點(diǎn)。系統(tǒng)通常請(qǐng)求直接訪問(wèn)4到8字節(jié)的數(shù)據(jù)，以更新節(jié)點(diǎn)的值。DRAM提供了非常快速的直接訪問(wèn)。然而，閃存只能訪問(wèn)4KB到8KB的數(shù)據(jù)塊，但仍然只更新幾個(gè)字節(jié)。在跳過(guò)圖形時(shí)，重復(fù)訪問(wèn)每個(gè)請(qǐng)求會(huì)浪費(fèi)帶寬。

sort-reduce算法轉(zhuǎn)而采用所有的直接訪問(wèn)請(qǐng)求，并按照標(biāo)識(shí)符的順序?qū)λ鼈冞M(jìn)行排序，標(biāo)識(shí)符顯示請(qǐng)求的目的地——例如將節(jié)點(diǎn)A的所有更新分成一組，全部分配給節(jié)點(diǎn)B。這樣，閃存就可以同時(shí)訪問(wèn)數(shù)千個(gè)kilobyte大小的chunks的請(qǐng)求，從而大大提高效率。

為了進(jìn)一步節(jié)省計(jì)算力和帶寬，該算法同時(shí)將數(shù)據(jù)合并到盡可能最小的分組中。只要算法記錄了匹配的標(biāo)識(shí)符，它就將這些數(shù)據(jù)加載到一個(gè)數(shù)據(jù)包中——例如將A1和A2合并成A3。這種做法重復(fù)多遍，用匹配的標(biāo)識(shí)符創(chuàng)建越來(lái)越小的數(shù)據(jù)包，直到產(chǎn)生可進(jìn)行排序的最小數(shù)據(jù)包。這大大減少了訪問(wèn)重復(fù)請(qǐng)求的數(shù)量。

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

定制加速器

然而，對(duì)于主機(jī)來(lái)說(shuō)， sort-reduce算法的計(jì)算量很大。因此，研究人員在設(shè)備中添加一個(gè)定制加速器。加速器在主機(jī)和閃存芯片之間充當(dāng)中間點(diǎn)，執(zhí)行算法的所有計(jì)算。這為加速器大大減少了電量消耗，以至于可以用一個(gè)低功耗的PC或筆記本電腦作為主機(jī)，用來(lái)管理已排序的數(shù)據(jù)并執(zhí)行其他次要任務(wù)。

Arvind說(shuō)：“加速器本來(lái)是用來(lái)幫助主機(jī)進(jìn)行計(jì)算的，但是目前的結(jié)果顯示，主機(jī)變得不那么重要了。”

“MIT的這個(gè)工作展示了一種在非常大的圖上執(zhí)行分析的新方法：利用閃存存儲(chǔ)圖形，并利用FPGA（定制的集成電路）以巧妙的辦法執(zhí)行所需的數(shù)據(jù)處理和分析，“德克薩斯大學(xué)奧斯汀分校計(jì)算機(jī)科學(xué)教授Keshav Pingali說(shuō)，“從長(zhǎng)遠(yuǎn)來(lái)看，這可能使得系統(tǒng)能夠在筆記本電腦或臺(tái)式機(jī)上有效地處理大量數(shù)據(jù)，這將徹底改變我們處理大數(shù)據(jù)的方式。”

MIT的研究人員說(shuō)，由于主機(jī)的耗能很低，他們的長(zhǎng)期目標(biāo)是創(chuàng)建一個(gè)通用的平臺(tái)和軟件庫(kù)，以便用戶為圖分析之外的應(yīng)用開(kāi)發(fā)自己的算法。Jun說(shuō)：“你可以把這個(gè)平臺(tái)插入筆記本電腦，下載這個(gè)軟件，然后編寫簡(jiǎn)單的程序，就可以在你的筆記本電腦上獲得服務(wù)器級(jí)的性能。”