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

在數據科學的說法中，圖（graph）是指用于映射大量復雜的數據關系的節點（nodes）和連接線（connecting lines）的結構。分析graph在許多應用中非常有用，例如網頁排名、分析社交網絡以獲取政治見解，或者繪制大腦的神經元結構。

然而，由數十億個節點和線組成的大型 graphs 大小可以達到TB級。通常來說，圖數據的處理需要跨多個耗電量大的服務器，在昂貴的動態隨機存取存儲器（DRAM）中進行。

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

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

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

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

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

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

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

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

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

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

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

sort-reduce算法

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

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

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

圖分析系統需要通過大量的、稀疏的圖結構訪問彼此間距離很遠的節點。系統通常請求直接訪問4到8字節的數據，以更新節點的值。DRAM提供了非常快速的直接訪問。然而，閃存只能訪問4KB到8KB的數據塊，但仍然只更新幾個字節。在跳過圖形時，重復訪問每個請求會浪費帶寬。

sort-reduce算法轉而采用所有的直接訪問請求，并按照標識符的順序對它們進行排序，標識符顯示請求的目的地——例如將節點A的所有更新分成一組，全部分配給節點B。這樣，閃存就可以同時訪問數千個kilobyte大小的chunks的請求，從而大大提高效率。

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

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

定制加速器

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

Arvind說：“加速器本來是用來幫助主機進行計算的，但是目前的結果顯示，主機變得不那么重要了?！?/p>

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

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