大規(guī)模圖計算系統(tǒng)關鍵技術研究.pdf

1、最近十年，隨著信息與通信技術的蓬勃發(fā)展，人類社會步入了大數(shù)據(jù)時代。每時每刻，海量的信息都正在被生成，并累積為“數(shù)據(jù)金礦”。在這些海量的數(shù)據(jù)當中，實際上，許多的各種類型的信息可以很自然地被抽象為圖結構數(shù)據(jù)，例如，社交網(wǎng)絡圖，網(wǎng)頁鏈接圖，消費者-產品關系圖等，從而相應的實際問題可以很自然地轉換為圖計算問題。最近幾年，隨著圖結構數(shù)據(jù)的規(guī)模越來越大，高效地分析和處理大規(guī)模圖結構數(shù)據(jù)能夠帶來越來越顯著的科研、經濟以及社會效益，大規(guī)模圖計算問題正受

2、到學術界和工業(yè)界的廣泛關注。
　　大規(guī)模圖計算問題涉及到圖算法、存儲以及計算等方面，作為一名計算機系統(tǒng)結構研究者，主要關注計算與存儲。以系統(tǒng)結構研究者的視角來看，高能效的大規(guī)模圖計算系統(tǒng)本質上主要包含兩方面挑戰(zhàn):如何高效地處理圖數(shù)據(jù)，如何高效地存儲和快速地訪問圖數(shù)據(jù)。對于第一個方面的挑戰(zhàn)，提出了StreamGraphChi和Mermaid兩個系統(tǒng)，旨在提升基于磁盤的單機大規(guī)模圖計算系統(tǒng)性能。由于摩爾定律和縮放定律逐漸失效，“異構計

3、算”正愈發(fā)受到青睞。提出了TuNao，旨在利用圖計算專用硬件促進大規(guī)模圖結構數(shù)據(jù)的高能效處理。對于第二個方面的挑戰(zhàn)，主要以圖數(shù)據(jù)庫中常用的“哈希查找表”數(shù)據(jù)結構為切入點，提出了FAHT，旨在加速數(shù)據(jù)庫的查詢性能。具體地，主要做了如下工作:
　　StreamGraphChi:基于“邊為中心”流處理的單機大規(guī)模圖計算系統(tǒng)。在本工作中，設計并實現(xiàn)了新的圖計算編程框架和執(zhí)行引擎，遵循“邊為中心”圖計算模式，支持流式地訪問磁盤并避免了產生大

4、量中間臨時數(shù)據(jù)。并且，針對計算平臺物理內存容量限制和輸入數(shù)據(jù)集規(guī)模大小，實現(xiàn)了IM-StreamGraphChi和OM-StreamGraphChi兩類執(zhí)行引擎，依據(jù)現(xiàn)實世界大規(guī)模圖數(shù)據(jù)所具有的“長尾”特征，系統(tǒng)能自適應地選擇合適的執(zhí)行引擎處理輸入圖結構數(shù)據(jù)。StreamGraphChi旨在進一步提升磁盤帶寬利用率和減少磁盤訪問量，進而促進圖計算系統(tǒng)性能提升。
　　Mermaid:基于混合計算模式的單機大規(guī)模圖計算系統(tǒng)。以“頂點為

5、中心”和以“邊為中心”是兩種常見的圖計算模式。在本工作中，分析了這兩種計算模式的優(yōu)缺點，得到“頂點為中心”模式適用于度高的頂點而“邊為中心”模式適用于度低的頂點的結論?，F(xiàn)實世界大規(guī)模圖結構數(shù)據(jù)的頂點度的分布常呈現(xiàn)出“長尾”現(xiàn)象，已有的圖計算系統(tǒng)常使用其中一種計算模式，未能有效發(fā)掘“長尾”特性。因此，在IM-StreamGraphChi引擎的基礎上，重新設計圖結構數(shù)據(jù)的表示方法、編程框架和執(zhí)行引擎，使得兩種圖計算模式巧妙整合到一起，充分利

6、用“長尾”特性提升系統(tǒng)性能。
　　TuNao:高能效的可重構圖計算加速器。當前，采用定制化硬件加速器來提升特定領域應用處理的能效已獲得學術界和工業(yè)界的普遍認可。幸運地，現(xiàn)實世界大規(guī)模圖結構數(shù)據(jù)處理遵循類似的計算框架，使得設計大規(guī)模圖計算硬件加速器成為可能。本工作中，在采用現(xiàn)有內存存儲技術的前提下，主要圍繞訪存、計算和適用性三方面進行設計，并充分利用現(xiàn)實世界圖結構數(shù)據(jù)特性。在訪存方面，盡可能減少隨機訪問，盡可能利用數(shù)據(jù)局部性，減少片

7、外訪存。在計算方面，盡可能采用流水線技術，提高并行性。在適用性方面，采用可重構技術以適應不同的圖計算應用。
　　FAHT:快速近似哈希查找表。哈希查找表是一種常見的數(shù)據(jù)結構，被廣泛運用于需要依據(jù)關鍵字快速查詢與其相匹配的數(shù)據(jù)值的應用中，包括圖數(shù)據(jù)庫等。傳統(tǒng)哈希表中，查詢操作過程與“關鍵字”相關的開銷，主要包括存儲開銷、訪問開銷和計算開銷。哈希表中“關鍵字”存在的目的，主要是為了確保哈希查詢操作所返回的結果總是正確的。隨著哈希表的規(guī)

8、模擴大，以及在一些哈希關鍵字比較大的場景下，由關鍵字帶來的這些開銷不容忽視。一些工作提出，哈希表表項中只存儲數(shù)據(jù)值而不存儲關鍵字將能明顯提升查詢性能。當然，這意味著難以確保查詢操作總能返回正確的結果。在現(xiàn)實世界中，不少應用是能夠容忍一定錯誤率的。因此，重新設計哈希查找表動態(tài)插入、動態(tài)刪除和查找算法，并采用雙層存儲結構，期望在提升查詢性能的同時盡可能地減少查詢錯誤發(fā)生概率。同時，對FAHT所需的存儲空間大小和查詢操作錯誤發(fā)生的概率進行理論