大規(guī)模圖計(jì)算系統(tǒng)關(guān)鍵技術(shù)研究.pdf

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

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

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

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

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

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

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

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