MIT開發的新設備幫助數據科學家用「筆記本」分析大規模圖形數據

一般來說，在處理圖形數據時快閃記憶體要比 DRAM 慢得多。但現在，麻省理工學院計算機科學和人工智慧實驗室 (CSAIL) 的研究者們已經設計出了一種由快閃記憶體晶元陣列和計算「加速器」組成的新設備，它使用廉價的快閃記憶體（和智能手機里用的類型一樣），僅需一台個人電腦就能處理大量圖形。

該設備由一種新穎的演算法驅動，它把圖形數據的所有訪問請求進行分類，從而變成便於快閃記憶體快速訪問的順序。它還能合併一些請求以減少排序的開銷，比如組合的計算時間、內存、帶寬和其它計算資源。

研究人員將該設備與幾個傳統高性能系統放在一起進行比較，來分別處理幾個大型圖表。其中包括巨大的 Web 數據共享超鏈接圖（Web Data Commons Hyperlink Graph），這個圖形擁有 35 億個結點和 128 億條連接線。為了處理這個圖表，傳統系統全都需要一個耗資數千美元的伺服器，並且包含 128 千兆位元組的 DRAM。

而通過把兩個器件（總計 1 千兆位元組的 DRAM 和 1 個太位元組的快閃記憶體）插入台式計算機，新設備實現了同樣的性能。此外，通過組合多個設備，他們可以處理大量圖形，高達 40 億個節點和 128 億條連接線，沒有其它系統能在 128 GB 的伺服器上操作這麼多的信息。

「最重要的是，我們可以用溫度更低和能量消耗上更少的機器來保持同樣的性能」，CSAIL 的研究生傳相佑（Sang-Woo Jun）說。他是介紹該設備的論文的第一作者。

該設備可用於削減與圖形分析相關的成本和能耗，甚至可以拓展它的適用範圍。比如說，研究人員正在創造一個程序，它可以識別哪些基因會導致癌症。像谷歌這樣的大科技公司，也可以通過使用比以前少得多的機器，來減少他們運行分析時所帶來的能源消耗。

「圖形處理是一個很普遍的概念」，論文的共同作者 Arvind 教授說，「網頁排序與基因檢測有哪些共同之處呢？對於我們來說，這是相同的計算問題，它們只是具有不同含義的不同圖表。某人開發的應用類型，將決定它給社會帶來的影響。」

「分類和減少」演算法

在圖形分析中，系統基於某個結點與其它結點、在其它度量中的關係來尋找和更新結點值。打個比方，在網頁排序里，每個結點代表一個網頁。如果結點 A 的值很高，並且與結點 B 相聯繫，那麼結點 B 的值也會相應提高。

傳統的系統把所有圖形數據都儲存在 DRAM 里，因此它們處理速度快，但是價格昂貴、耗能多。有一些系統將部分數據內存分流到快閃記憶體上，這種方式更便宜，但速度更慢、效率也更低，因此它們仍需要使用大量的 DRAM。

而新研究使用一種被稱之為「分類-減少」（sort-reduce）的演算法，它解決了把快閃記憶體作為主要存儲源的一個大問題：浪費。

圖形分析系統需要在巨大且鬆散的圖形結構中，訪問彼此可能相距很遠的結點。系統通常要求直接訪問譬如 4 到 8 位元組的數據來更新結點的值。DRAM 可以提供非常快速的直接訪問，而快閃記憶體只訪問 4 到 8 千位元組的數據塊，並且只能更新其中的幾個位元組。在圖表之內跨越時，如果每次訪問請求都要重複這一過程，會造成帶寬的浪費。「如果你需要訪問整個 8 千位元組，但是只用了 8 個位元組，然後把其餘部分亂扔，那麼你相當於浪費了整整 1000 倍的性能。」傳相佑說。

「分類-減少」演算法則採用所有直接訪問請求，並且按照標記符號的順序把它們分類和排序。標記符號會顯示請求的目的地，比如說，把各個結點的所有更新都分到一組。於是，快閃記憶體能同時訪問數千個請求的、千位元組大小的數據塊，因此工作效率比以前高了許多。

為了進一步節省計算能力和帶寬，這個演算法同時也會儘可能把數據合併到最小的分組中。只要演算法發現了相匹配的標記符，它就將這些數據放到同一個數據包里，例如 A1 和 A2 變成了 A3。它持續這樣做，根據匹配的標記符創建越來越小的數據包，直到產生可能範圍內最小的數據包來進行排序。這大大減少了訪問重複請求的數量。

使用這個演算法來處理兩個大圖形，研究人員把需要在快閃記憶體中更新的總數據減少了大約 90%。

計算分流

然而，由於「分類-減少」演算法需要在主機上進行高強度計算，於是研究者們在設備里放入了一個定製的加速器。作為主機和快閃記憶體晶元的中間點，加速器為演算法執行所有運算。於是，很大一部分能耗被分流到了加速器上，主機因而可以成為一台低功耗的個人電腦或筆記本，用於管理分類的數據和執行其它次要任務。

「本來加速器是用來幫助主機的，但我們不小心（在計算上）走得太遠，以至於主機變得不重要了」Arvind 說。

圖丨Arvind 教授

「麻省理工學院的這個項目展示了一種在非常大的圖形上執行分析的新方法：他們利用快閃記憶體來儲存圖形，並且巧妙使用 FPGA 來執行有效使用快閃記憶體所需的分析和數據處理」，德克薩斯大學奧斯汀分校的計算機科學教授 Keshav Pingali 說，「長遠看來，這可能促生一個能在筆記本或台式電腦上有效處理大量數據的系統，並將徹底改變我們進行大數據處理的方式。」

據傳相佑介紹，由於主機耗能很少，他們的長期計劃是創建一個通用平台和軟體庫，讓消費者能開發出圖形分析之外的、屬於他們自己的演算法。「你可以把這個平台插到筆記本里，下載軟體，並編寫簡單的程序，從而在自己的電腦上實現伺服器級別的性能」，他說。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！