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

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

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

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

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

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

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

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

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

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

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

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

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

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

sort-reduce算法

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

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

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

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

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

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

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

定制加速器

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

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

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

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