麻省理工學院電腦科學和人工智慧實驗室(CSAIL)最近設計了一套透過便宜的快閃儲存設備,搭配自行開發的排序降低(Sort-reduce)演算法,只需要單機,就能處理大量的圖學(Graph)資料。

在資料科學圈中,圖學資料是由節點和線組成的複雜資料結構,分析圖學資料對許多應用都相當有效,像是網頁排名、分析社群網路,或是了解大腦的神經結構,不過,圖學資料包含了數十億的節點和線,大型的圖學資料規模甚至高達TB級,通常需要用昂貴的動態隨機存取記憶體(DRAM),透過多個耗費資源的伺服器,才能處理大型的圖學資料。

在處理圖學資料上,快閃儲存的處理速度通常會比DRAM慢許多,但是CSAIL的研究員開發了一套搭載快閃晶片陣列的設備和運算加速器,讓快閃儲存裝置達到與DRAM一樣的效能。

研究員開發出新的演算法將存取圖學資料的請求編列成序列排序,讓快閃裝置可以快速又簡單地存取資料,除此之外,研究員開發的演算法也合併了一些存取資料的請求,結合了運算時間、記憶體、頻寬和其他運算資源,來減少運算排序的間接成本。

在研究開發的過程,研究員分別嘗試用數個傳統高效能系統和自行開發的系統,處理了大量的圖學資料,包含Web Data Commons專案提供的大量超連結資料,有35億個節點和1,280億個連接線。

為了處理這個圖學資料,傳統的系統需要數千美元的伺服器搭配128 GB的DRAM,而CSAIL的研究員則是在一臺桌機電腦中,加入1 GB的DRAM和1 TB的快閃記憶體,就能達到一樣的運算效能,甚至,將多個裝置結合再一起之後,系統可以處理高達40億節點和1,280億個連接線的圖學資料。

研究團隊中一名研究生Sang-Woo Jun表示,最重要的是,該系統裝置可以透過更小、更少的資源來維持高效能的表現,像是電腦的功耗和溫度等,該設備能夠減少圖學資料分析的成本和資源,更進一步,還能在許多應用中提高運算效能,像是辨識癌症基因的工作。

在圖學分析的過程中,系統基本上會根據節點本身與其他節點的連結,搜尋並更新每個節點的值,舉網頁排名的分析來說,每個節點代表一個節點,若A節點有較高的值,與A節點連接的B節點的值也會增加。

一般的系統會將所有的圖學資料儲存在DRAM中,雖然處理資料的速度快,但是相對地也需要大量的成本和資源,有些系統會將一些資料儲存到快閃記憶體來降低成本,但是處理的速度就會變慢,效能也會降低,因此,這樣的作法,還是需要大量的DRAM。

CSAIL的研究員採用了稱為排序降低的演算法,來解決用快閃記憶體當成主要儲存設備的問題,也就是浪費資源,排序降低的演算法直接存取請求,按照標籤順序將所有存取請求用序列排序,簡單來說,演算法會將所有對節點A的更新分成一組,快閃記憶體就能同時存取數千個請求,讓系統變得更加有效率。

更進一步,為了要節省運算資源和頻寬,演算法會同時將資料合併成最小的資料包(Data packet),將不同的資料群合併成一個,持續執行合併的工作,直到產生出最小的排序資料包,這個步驟大幅地降低了重複的存取請求。透過排序降低的演算法,在兩個大型圖學資料的分析中,研究員成功地降低了大約需要在快閃記憶體中更新的90%的總資料量。


Advertisement

更多 iThome相關內容