Page 103 - My FlipBook

Brochure 2020

在中長期的目標中，我們將基於將 crash-deterministic 固態硬碟的儲存系統，進一步發展
高效能兼高可靠度圖形計算處理系統。由於圖形在運算時，會於記憶體層級與儲存層級之
間產生大量的資料搬移。我們接續的目標是減少大量的資料搬移藉以提升整體系統效能。
圖形運算中資料存取的行為主要取決於圖形的架構 (Graph Layout) 以及圖形演算法 (Graph
Algorithm) 的設計。圖形的架構主要是由一群點 (Nodes) 及邊 (Edges) 建構而成。在社群網
路或網際網路中，圖形的架構通常為無尺度圖 (Scale-Free Graph)，這類圖中存在少數的中
樞節點 (Hub Nodes)，其邊的個數為一般節點邊的數十位甚至數百倍。我們觀察到，無尺
度圖若為有向圖 (Directed Graph)，其入度 (In-Degree) 與出度 (Out-Degree) 的個數將有極大
的差異。相較於一般節點，中樞節點具有極高的入度。這也代表，在對一張無尺度的圖進
行分析運算時，如果能有效的辨別中樞節點，將其預先搬入快取記憶體並將其有效的鎖在
記憶體中，將能避免大量的資料搬移。因此針對圖形架構的部分，我們將提出一套有效的
中樞節點辨識及鎖定機制。此外，為了避免記憶體的浪費，我們也會提出相關的中樞節點
預測及剔除機制，以適應執行期間動態變化的圖形存取行為。

而針對執行期間圖形節點及邊會經常變動的應用中，我們將整合本計畫所發展的 crash-
deterministic 固態硬碟及其驗證過的固態硬碟管理系統，進一步強化圖形節點及邊在修改
並寫入固態硬碟的效能，並且能簡化驗證的複雜度的前提下，就能保證圖形資料能夠在斷
電或當機後，仍能正確並且快速的回復，並且驗證及正確性。因此，最後我們將把三年的
成果整合實現成一個 GraphStor 的系統，實現一個兼顧「高效率」和「高可靠度」的圖形
處理系統。

101