導讀
近日，美國麻省理工學院計算機科學與人工智能實驗室（CSAIL）設計出一種新設備，採用了在智能手機中使用的廉價閃存（Flash），只需要一臺個人電腦就可以處理大規模圖數據。
背景
如今，人類已進入大數據時代。在大數據時代，我們需要更加快速、有效、節能地處理和存儲數據。
下面，讓我們先來認識一種特殊的數據結構：圖（graph），它是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。在圖中的數據元素，我們稱之為頂點（Vertex），頂點集合有窮非空。在圖中，任意兩個頂點之間都可能有關係，頂點之間的邏輯關係用邊來表示，邊集可以是空的。
分析圖這種數據結構將帶來廣泛的應用，例如：網頁排名、社交網絡分析、大腦中神經結構的繪製等等。然而，大型的圖可以由數以億記的頂點與邊組成，其數據容量可以達到太字節。一般來說，圖的數據處理需要多個耗電的服務器，在昂貴的動態隨機存取存儲器（DRAM）中進行。
創新
近日，美國麻省理工學院計算機科學與人工智能實驗室（CSAIL）設計出一種新設備，採用了在智能手機中使用的廉價閃存（Flash），只需要一臺個人電腦就可以處理巨型的圖。
一般來說，在圖的數據處理方面，Flash比DRAM慢許多。但是，研究人員開發出一種由Flash芯片陣列和計算“加速器”組成的設備，有望幫助Flash達到類似DRAM的性能。
這個設備強大之處在於一個新算法，它可以將圖的所有數據訪問請求，排序為順序次序，便於Flash快速簡單地訪問。它也可以合併一些請求來減少排序開銷（計算時間、存儲器、帶寬和其他計算資源的結合）。
描述該設備的相關論文發表於計算機體系結構國際研討會（ISCA）。
技術
研究人員將設備處理幾種巨型圖的表現，與幾個傳統的高性能系統相比較，這些大型圖包括巨型的網絡數據共享超鏈接圖（Web Data Commons Hyperlink Graph），它含有35億個頂點和1280億條邊。為了處理這個圖，傳統的系統都需要價值幾千美元且含有128吉字節DRAM的服務器。然而，研究人員將兩個設備（1吉字節的DRAM和1太字節的Flash）插入到計算機中，就實現了同樣的性能。更進一步說，通過結合幾個設備，他們可以處理的巨型圖將達到40億個頂點和1280億條邊，而128吉字節服務器上的其他系統無法處理這種巨型圖。
論文第一作者、CSAIL 研究生 Sang-Woo Jun 表示：“底線是，我們能夠通過更小、更少、更冷（溫度和功耗方面）的機器保持住性能。”
論文合著者之一、計算機科學工程系教授 Arvind 表示：“圖處理是一個非常普遍的想法。網頁排名與基因檢測有什麼共同之處？對於我們來說，它們是同一個計算問題，只是不同的圖具有不同的意義。開發出的應用程序的類型將決定它對社會的影響。”
在圖分析中，一個系統主要基於該頂點與其他頂點之間的聯繫，搜索並更新頂點的值。例如，在網頁排名中，每個頂點代表一個網頁。如果頂點A具有很高的值，並連接到頂點B，然後頂點B的值也會增加。
傳統系統將所有的圖數據存儲於DRAM中，從可以更快速地處理數據，但是這樣也會增加成本和能耗。某些系統會將一些數據存儲到Flash中，雖然Flash更加便宜，但是它卻更慢且效率更低。研究人員設計出的設備運行於他們稱為“排序-歸約”（sort-reduce）的算法之上，這種算法解決了採用Flash作為主存儲源的主要問題：浪費。
圖分析系統需要跨越海量稀疏的圖結構，訪問相互之間距離非常遙遠的頂點。系統通常需要直接訪問4到8個字節的數據來更新頂點值。DRAM提供了一種非常快速的直接訪問。然而，對於Flash來說，只能在4千字節到8千字節的數據塊中訪問數據，但仍然只是更新幾個字節的數據。對於每次請求，跨越巨型的圖反覆訪問，會浪費帶寬。Jun 表示：“如果你需訪問整個的8千字節，卻只使用8字節，並丟棄其餘的，你最終將喪失1000倍的性能。”
取而代之的是，“排序-歸約”算法會接收所有的直接訪問請求，並通過標識符將它們按順序排列。標識符顯示出請求的目的地，例如將對於頂點A的所有更新分為一組，然後頂點B的再分為一組，以此類推。然後，Flash 可以一次響應幾千次請求，訪問千字節大小的數據塊，從而使得效率提高許多。
為了進一步節約計算機的能耗與帶寬，算法同步地將數據結合到最小的分組中。無論算法什麼時候記錄匹配的標識符，都會將那些加到單個數據包中，例如A1和A2變成A3。它持續地這麼做，創造出越來越小的含有匹配標識符的數據包，直到創造出最小的數據包用於排序。這樣可以顯著地減少重複請求的訪問量。
在兩個巨型圖上採用“排序-歸約”算法，研究人員將Flash中需要更新的數據總量減少了約90%。
“排序-歸約”算法對於主機來說是計算密集型的，然而研究人員在設備中實現了一個定製的加速器。加速器可作為主機和Flash芯片之間的中間點，為算法執行所有的計算。這樣使得許多功耗都由加速器來承擔，從而可以採用一個低功耗的個人電腦或筆記本電腦充當主機，管理經過排序的數據和執行其他小型任務。Arvind 表示：“加速器可以幫助主機計算，但是我們已經【通過計算】取得了很大進展，主機已變得不那麼重要。”
價值
在一系列應用中，這種新型設備可用於降低與圖分析相關的成本和能耗，甚至改善性能。例如，研究人員目前正在設計一個可以識別引發癌症的基因的程序。大型技術公司例如谷歌，利用這種設備可以降低能源足跡，因為運行這種分析所需的機器要少很多。
美國德克薩斯大學阿靈頓分校的計算機科學教授 Keshav Pingali 表示：“MIT 的研究展示了一種在巨型圖上展開分析的新途徑。他們研究利用Flash存儲圖，並利用‘現場可編程門陣列’【定製集成電路】以一種巧妙的方法展開分析和數據處理，從而更有效地利用Flash。從長遠來看，這將帶來能在筆記本電腦或臺式機上更加有效地處理大量數據的系統，變革我們處理大數據的方法。”
Jun 表示，因為主機的功耗可以變得如此的低，長期目標就是為客戶創造出通用平臺和軟件庫，使他們可以為圖分析以外的應用開發自己的算法。他說：“你可以將這個平臺插入到筆記本電腦中，下載【軟件】，並在你的筆記本電腦上寫一些簡單程序，獲取某些服務器類的性能。”
關鍵字
大數據、存儲器、集成電路
【1】http://news.mit.edu/2018/device-allows-personal-computer-process-huge-graphs-0531
閱讀更多 環球創新智慧 的文章
