【摘要】：最近十年,隨著信息與通信技術(shù)的蓬勃發(fā)展,人類社會步入了大數(shù)據(jù)時代。每時每刻,海量的信息都正在被生成,并累積為“數(shù)據(jù)金礦”。在這些海量的數(shù)據(jù)當中,實際上,許多的各種類型的信息可以很自然地被抽象為圖結(jié)構(gòu)數(shù)據(jù),例如,社交網(wǎng)絡(luò)圖,網(wǎng)頁鏈接圖,消費者-產(chǎn)品關(guān)系圖等,從而相應(yīng)的實際問題可以很自然地轉(zhuǎn)換為圖計算問題。最近幾年,隨著圖結(jié)構(gòu)數(shù)據(jù)的規(guī)模越來越大,高效地分析和處理大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)能夠帶來越來越顯著的科研、經(jīng)濟以及社會效益,大規(guī)模圖計算問題正受到學術(shù)界和工業(yè)界的廣泛關(guān)注。大規(guī)模圖計算問題涉及到圖算法、存儲以及計算等方面,作為一名計算機系統(tǒng)結(jié)構(gòu)研究者,我們主要關(guān)注計算與存儲。以系統(tǒng)結(jié)構(gòu)研究者的視角來看,高能效的大規(guī)模圖計算系統(tǒng)本質(zhì)上主要包含兩方面挑戰(zhàn):如何高效地處理圖數(shù)據(jù),如何高效地存儲和快速地訪問圖數(shù)據(jù)。對于第一個方面的挑戰(zhàn),我們提出了 StreamGraphChi和Mernmaid兩個系統(tǒng),旨在提升基于磁盤的單機大規(guī)模圖計算系統(tǒng)性能。由于摩爾定律和縮放定律逐漸失效,“異構(gòu)計算”正愈發(fā)受到青睞。我們提出了 TuNao,旨在利用圖計算專用硬件促進大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)的高能效處理。對于第二個方面的挑戰(zhàn),我們主要以圖數(shù)據(jù)庫中常用的“哈希查找表”數(shù)據(jù)結(jié)構(gòu)為切入點,提出了 FAHT,旨在加速數(shù)據(jù)庫的查詢性能。具體地,我們主要做了如下工作:· StreamGraphChi:基于“邊為中心”流處理的單機大規(guī)模圖計算系統(tǒng)。在本工作中,我們設(shè)計并實現(xiàn)了新的圖計算編程框架和執(zhí)行引擎,遵循“邊為中心”圖計算模式,支持流式地訪問磁盤并避免了產(chǎn)生大量中間臨時數(shù)據(jù)。并且,針對計算平臺物理內(nèi)存容量限制和輸入數(shù)據(jù)集規(guī)模大小,我們實現(xiàn)了 IM-StreamGraphChi和OM-StreamGraphChi兩類執(zhí)行引擎,依據(jù)現(xiàn)實世界大規(guī)模圖數(shù)據(jù)所具有的“長尾”特征,系統(tǒng)能自適應(yīng)地選擇合適的執(zhí)行引擎處理輸入圖結(jié)構(gòu)數(shù)據(jù)。StreamGraphChi旨在進一步提升磁盤帶寬利用率和減少磁盤訪問量,進而促進圖計算系統(tǒng)性能提升。· Mermaid:基于混合計算模式的單機大規(guī)模圖計算系統(tǒng)。以“頂點為中心”和以“邊為中心”是兩種常見的圖計算模式。在本工作中,我們分析了這兩種計算模式的優(yōu)缺點,得到“頂點為中心”模式適用于度高的頂點而“邊為中心”模式適用于度低的頂點的結(jié)論�，F(xiàn)實世界大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)的頂點度的分布常呈現(xiàn)出“長尾”現(xiàn)象,已有的圖計算系統(tǒng)常使用其中一種計算模式,未能有效發(fā)掘“長尾”特性。因此,我們在IM-StreamGraphChi引擎的基礎(chǔ)上,重新設(shè)計圖結(jié)構(gòu)數(shù)據(jù)的表示方法、編程框架和執(zhí)行引擎,使得兩種圖計算模式巧妙整合到一起,充分利用“長尾”特性提升系統(tǒng)性能�！� TuNao:高能效的可重構(gòu)圖計算加速器。當前,采用定制化硬件加速器來提升特定領(lǐng)域應(yīng)用處理的能效已獲得學術(shù)界和工業(yè)界的普遍認可。幸運地,現(xiàn)實世界大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)處理遵循類似的計算框架,使得設(shè)計大規(guī)模圖計算硬件加速器成為可能。本工作中,在采用現(xiàn)有內(nèi)存存儲技術(shù)的前提下,我們主要圍繞訪存、計算和適用性三方面進行設(shè)計,并充分利用現(xiàn)實世界圖結(jié)構(gòu)數(shù)據(jù)特性。在訪存方面,盡可能減少隨機訪問,盡可能利用數(shù)據(jù)局部性,減少片外訪存。在計算方面,盡可能采用流水線技術(shù),提高并行性。在適用性方面,采用可重構(gòu)技術(shù)以適應(yīng)不同的圖計算應(yīng)用。· FAHT:快速近似哈希查找表。哈希查找表是一種常見的數(shù)據(jù)結(jié)構(gòu),被廣泛運用于需要依據(jù)關(guān)鍵字快速查詢與其相匹配的數(shù)據(jù)值的應(yīng)用中,包括圖數(shù)據(jù)庫等。傳統(tǒng)哈希表中,查詢操作過程與“關(guān)鍵字”相關(guān)的開銷,主要包括存儲開銷、訪問開銷和計算開銷。哈希表中“關(guān)鍵字”存在的目的,主要是為了確保哈希查詢操作所返回的結(jié)果總是正確的。隨著哈希表的規(guī)模擴大,以及在一些哈希關(guān)鍵字比較大的場景下,由關(guān)鍵字帶來的這些開銷不容忽視。一些工作提出,哈希表表項中只存儲數(shù)據(jù)值而不存儲關(guān)鍵字將能明顯提升查詢性能。當然,這意味著難以確保查詢操作總能返回正確的結(jié)果。在現(xiàn)實世界中,不少應(yīng)用是能夠容忍一定錯誤率的。因此,我們重新設(shè)計哈希查找表動態(tài)插入、動態(tài)刪除和查找算法,并采用雙層存儲結(jié)構(gòu),期望在提升查詢性能的同時盡可能地減少查詢錯誤發(fā)生概率。同時,我們對FAHT所需的存儲空間大小和查詢操作錯誤發(fā)生的概率進行理論分析,并給出了相應(yīng)的計算公式。理論分析和模擬實驗表明,FAHT明顯優(yōu)于已有工作。
[Abstract]:......
【學位授予單位】：中國科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：TP311.13

【相似文獻】

相關(guān)期刊論文 前10條

1 鄭立剛,楊學軍;頁遷移:一種動態(tài)開發(fā)數(shù)據(jù)局部性的方法[J];計算機工程與科學;1999年05期

2 黃麗君;文志強;;基于色彩分類的查找表圖像逆半調(diào)方法[J];湖南工業(yè)大學學報;2013年05期

3 羅海坤;王永慶;吳嗣亮;;基于壓縮查找表的高精度正弦信號生成算法[J];系統(tǒng)工程與電子技術(shù);2012年02期

4 鄒云偉;李冰;;動態(tài)查找表設(shè)計方案研究[J];電子與封裝;2007年12期

5 方成,喻壽益,曹衛(wèi)華;一種新穎的基于多值化查找表的彩色目標搜索法[J];電腦與信息技術(shù);2002年01期

6 劉曉虹;孔月萍;;一種改進的查找表逆半調(diào)算法[J];計算機技術(shù)與發(fā)展;2007年04期

7 孔月萍;何波;曾平;徐培培;;查找表與神經(jīng)網(wǎng)絡(luò)相結(jié)合的圖像逆半調(diào)算法[J];計算機工程與科學;2007年04期

8 孫容磊;也談磁盤文件的一些特殊管理辦法[J];微電子學與計算機;1989年07期

9 孫文英;龍丹;;再談恢復(fù)被誤刪除的文件[J];微型機與應(yīng)用;1990年07期

10 張秉才;;磁盤文件定位探索[J];河北地質(zhì)學院學報;1991年04期

相關(guān)會議論文 前5條

1 胡欣;王剛;王自成;羅積潤;;一種新的基于二維查找表技術(shù)的基帶預(yù)失真[A];2011年全國微波毫米波會議論文集（下冊）[C];2011年

2 諶先敢;李凱揚;周利;;DSA系統(tǒng)中查找表及后處理的應(yīng)用[A];中國生物醫(yī)學工程學會第六次會員代表大會暨學術(shù)會議論文摘要匯編[C];2004年

3 胡乃真;;微機磁盤文件保護方法[A];第四次全國計算機安全技術(shù)交流會論文集[C];1989年

4 于博;李建中;王宏志;高宏;;超大有向圖上Top-k頂點度查詢的一種有效處理方法[A];第二十三屆中國數(shù)據(jù)庫學術(shù)會議論文集（技術(shù)報告篇）[C];2006年

5 謝湘?zhèn)?周文靜;李暉;王珊;張孝;;基于數(shù)據(jù)庫的視頻數(shù)據(jù)隨機訪問方法[A];第二十五屆中國數(shù)據(jù)庫學術(shù)會議論文集（一）[C];2008年

相關(guān)重要報紙文章 前7條

1 記者 王端鵬;山東科學發(fā)展綜合考核群眾滿意度隨機訪問啟動[N];濟南日報;2009年

2 郭振海;Scandisk使用詳解[N];電腦報;2001年

3 田勝平 李小東;落實法規(guī)就得丁是丁卯是卯[N];解放軍報;2012年

4 ;英文軟件下載TOP10[N];中國電腦教育報;2005年

5 浙江 劉保國;巧解BT空間占用問題[N];電腦報;2003年

6 湖北 簡友鑄;磁盤整理三幫手[N];中國電腦教育報;2000年

7 一兵;談?wù)動脖P故障的預(yù)防[N];人民政協(xié)報;2001年

相關(guān)博士學位論文 前1條

1 周金紅;大規(guī)模圖計算系統(tǒng)關(guān)鍵技術(shù)研究[D];中國科學技術(shù)大學;2017年

相關(guān)碩士學位論文 前10條

1 代爾衛(wèi);一種異構(gòu)感知的糾刪碼歸檔方法研究[D];華中科技大學;2016年

2 金真;基于多維信息顏色查找表的計算彩色成像[D];北京理工大學;2015年

3 戴上杰;Crossbar交換單元輸出調(diào)度和查找表的設(shè)計與實現(xiàn)[D];西安電子科技大學;2015年

4 葉德剛;圖像逆半調(diào)技術(shù)中查找表模板優(yōu)化方法研究[D];湖南工業(yè)大學;2016年

5 鄭帥;基于新型查找表的數(shù)字預(yù)失真技術(shù)的設(shè)計與實現(xiàn)[D];華中科技大學;2016年

6 田濤;關(guān)于樹的能量的若干結(jié)果[D];集美大學;2015年

7 葛劍飛;頂點帶屬性網(wǎng)絡(luò)的鏈接預(yù)測研究[D];揚州大學;2015年

8 焦智慧;圖中頂點不相交的圈[D];山東大學;2016年

9 宋少瑩;不確定圖的代表實例發(fā)現(xiàn)算法[D];哈爾濱工業(yè)大學;2016年

10 侯方圓;幾類圖的度距離研究[D];大連海事大學;2017年

，

本文編號：2295608