【摘要】：最近十年,隨著信息與通信技術(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ì)算問題正受到學(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和Mernmaid兩個(gè)系統(tǒng),旨在提升基于磁盤的單機(jī)大規(guī)模圖計(jì)算系統(tǒng)性能。由于摩爾定律和縮放定律逐漸失效,“異構(gòu)計(jì)算”正愈發(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)。在本工作中,我們?cè)O(shè)計(jì)并實(shí)現(xiàn)了新的圖計(jì)算編程框架和執(zhí)行引擎,遵循“邊為中心”圖計(jì)算模式,支持流式地訪問磁盤并避免了產(chǎn)生大量中間臨時(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ù)所具有的“長(zhǎng)尾”特征,系統(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)為中心”和以“邊為中心”是兩種常見的圖計(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)出“長(zhǎng)尾”現(xiàn)象,已有的圖計(jì)算系統(tǒng)常使用其中一種計(jì)算模式,未能有效發(fā)掘“長(zhǎng)尾”特性。因此,我們?cè)贗M-StreamGraphChi引擎的基礎(chǔ)上,重新設(shè)計(jì)圖結(jié)構(gòu)數(shù)據(jù)的表示方法、編程框架和執(zhí)行引擎,使得兩種圖計(jì)算模式巧妙整合到一起,充分利用“長(zhǎng)尾”特性提升系統(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ù)局部性,減少片外訪存。在計(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ī)模擴(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)行理論分析,并給出了相應(yīng)的計(jì)算公式。理論分析和模擬實(shí)驗(yàn)表明,FAHT明顯優(yōu)于已有工作。
[Abstract]:......
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 鄭立剛,楊學(xué)軍;頁遷移:一種動(dòng)態(tài)開發(fā)數(shù)據(jù)局部性的方法[J];計(jì)算機(jī)工程與科學(xué);1999年05期
2 黃麗君;文志強(qiáng);;基于色彩分類的查找表圖像逆半調(diào)方法[J];湖南工業(yè)大學(xué)學(xué)報(bào);2013年05期
3 羅海坤;王永慶;吳嗣亮;;基于壓縮查找表的高精度正弦信號(hào)生成算法[J];系統(tǒng)工程與電子技術(shù);2012年02期
4 鄒云偉;李冰;;動(dòng)態(tài)查找表設(shè)計(jì)方案研究[J];電子與封裝;2007年12期
5 方成,喻壽益,曹衛(wèi)華;一種新穎的基于多值化查找表的彩色目標(biāo)搜索法[J];電腦與信息技術(shù);2002年01期
6 劉曉虹;孔月萍;;一種改進(jìn)的查找表逆半調(diào)算法[J];計(jì)算機(jī)技術(shù)與發(fā)展;2007年04期
7 孔月萍;何波;曾平;徐培培;;查找表與神經(jīng)網(wǎng)絡(luò)相結(jié)合的圖像逆半調(diào)算法[J];計(jì)算機(jī)工程與科學(xué);2007年04期
8 孫容磊;也談磁盤文件的一些特殊管理辦法[J];微電子學(xué)與計(jì)算機(jī);1989年07期
9 孫文英;龍丹;;再談恢復(fù)被誤刪除的文件[J];微型機(jī)與應(yīng)用;1990年07期
10 張秉才;;磁盤文件定位探索[J];河北地質(zhì)學(xué)院學(xué)報(bào);1991年04期
相關(guān)會(huì)議論文 前5條
1 胡欣;王剛;王自成;羅積潤(rùn);;一種新的基于二維查找表技術(shù)的基帶預(yù)失真[A];2011年全國(guó)微波毫米波會(huì)議論文集（下冊(cè)）[C];2011年
2 諶先敢;李凱揚(yáng);周利;;DSA系統(tǒng)中查找表及后處理的應(yīng)用[A];中國(guó)生物醫(yī)學(xué)工程學(xué)會(huì)第六次會(huì)員代表大會(huì)暨學(xué)術(shù)會(huì)議論文摘要匯編[C];2004年
3 胡乃真;;微機(jī)磁盤文件保護(hù)方法[A];第四次全國(guó)計(jì)算機(jī)安全技術(shù)交流會(huì)論文集[C];1989年
4 于博;李建中;王宏志;高宏;;超大有向圖上Top-k頂點(diǎn)度查詢的一種有效處理方法[A];第二十三屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2006年
5 謝湘?zhèn)?周文靜;李暉;王珊;張孝;;基于數(shù)據(jù)庫的視頻數(shù)據(jù)隨機(jī)訪問方法[A];第二十五屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（一）[C];2008年
相關(guān)重要報(bào)紙文章 前7條
1 記者 王端鵬;山東科學(xué)發(fā)展綜合考核群眾滿意度隨機(jī)訪問啟動(dòng)[N];濟(jì)南日?qǐng)?bào);2009年
2 郭振海;Scandisk使用詳解[N];電腦報(bào);2001年
3 田勝平 李小東;落實(shí)法規(guī)就得丁是丁卯是卯[N];解放軍報(bào);2012年
4 ;英文軟件下載TOP10[N];中國(guó)電腦教育報(bào);2005年
5 浙江 劉保國(guó);巧解BT空間占用問題[N];電腦報(bào);2003年
6 湖北 簡(jiǎn)友鑄;磁盤整理三幫手[N];中國(guó)電腦教育報(bào);2000年
7 一兵;談?wù)動(dòng)脖P故障的預(yù)防[N];人民政協(xié)報(bào);2001年
相關(guān)博士學(xué)位論文 前1條
1 周金紅;大規(guī)模圖計(jì)算系統(tǒng)關(guān)鍵技術(shù)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年
相關(guān)碩士學(xué)位論文 前10條
1 代爾衛(wèi);一種異構(gòu)感知的糾刪碼歸檔方法研究[D];華中科技大學(xué);2016年
2 金真;基于多維信息顏色查找表的計(jì)算彩色成像[D];北京理工大學(xué);2015年
3 戴上杰;Crossbar交換單元輸出調(diào)度和查找表的設(shè)計(jì)與實(shí)現(xiàn)[D];西安電子科技大學(xué);2015年
4 葉德剛;圖像逆半調(diào)技術(shù)中查找表模板優(yōu)化方法研究[D];湖南工業(yè)大學(xué);2016年
5 鄭帥;基于新型查找表的數(shù)字預(yù)失真技術(shù)的設(shè)計(jì)與實(shí)現(xiàn)[D];華中科技大學(xué);2016年
6 田濤;關(guān)于樹的能量的若干結(jié)果[D];集美大學(xué);2015年
7 葛劍飛;頂點(diǎn)帶屬性網(wǎng)絡(luò)的鏈接預(yù)測(cè)研究[D];揚(yáng)州大學(xué);2015年
8 焦智慧;圖中頂點(diǎn)不相交的圈[D];山東大學(xué);2016年
9 宋少瑩;不確定圖的代表實(shí)例發(fā)現(xiàn)算法[D];哈爾濱工業(yè)大學(xué);2016年
10 侯方圓;幾類圖的度距離研究[D];大連海事大學(xué);2017年
，
本文編號(hào)：
2295608
