信息技術(shù)的進步與發(fā)展進一步推動了社會生產(chǎn)力的發(fā)展。新興產(chǎn)業(yè)得到了很大的發(fā)展,每時每刻各個行業(yè)數(shù)據(jù)量都發(fā)生著的巨大變化,數(shù)據(jù)量的快速增長推動了大數(shù)據(jù)產(chǎn)業(yè)和高性能計算領(lǐng)域的快速發(fā)展。圖計算方法被廣泛的應(yīng)用到大數(shù)據(jù)問題的處理中,其中廣度優(yōu)先搜索算法（Breadth First Search,BFS）是圖計算中的一個經(jīng)典問題,也是高性能計算機benchmark Graph500基準(zhǔn)測試的核心。BFS算法具有訪存數(shù)據(jù)量大,計算復(fù)雜度低等特征,這與大數(shù)據(jù)問題非常相似;除此之外,由于BFS算法自身重復(fù)判斷的問題也會導(dǎo)致它的訪存不規(guī)律,空間局部性差,進一步造成計算機的Cache失效率上升,因此無法達到高時效高性能的要求;并且Graph500測試的生成圖的規(guī)模巨大,經(jīng)常會因為計算機內(nèi)存不足而出現(xiàn)數(shù)據(jù)越界的問題。為了解決這一系列問題,可以從程序的內(nèi)存和訪存兩個方面進行優(yōu)化,在提高Graph500基準(zhǔn)測試程序的計算效率的同時減小程序運行過程中對內(nèi)存空間的消耗。在內(nèi)存優(yōu)化方面,采用壓縮生成圖變量數(shù)據(jù)類型的方法使得優(yōu)化后的生成圖能更加適合BFS算法的搜索;在訪存優(yōu)化方面,對生成圖數(shù)據(jù)的格式分配程序進行降位處理,... 

【文章來源】：中國科學(xué)院大學(xué)(中國科學(xué)院深圳先進技術(shù)研究院)廣東省

【文章頁數(shù)】：64 頁

【學(xué)位級別】：碩士

【部分圖文】：

超級計算機的發(fā)展歷程及代表

面向Graph500圖遍歷的存儲結(jié)構(gòu)和訪存優(yōu)化研究表2.1Graph500測試基準(zhǔn)的7個版本基本信息數(shù)據(jù)規(guī)模scaleedgefacter所需存儲空間Toy261617.6128GBMini2916140.6974GBSmall32161.0995TBMedium361617.5922TBLarge391640.7375TBHuge42161.0995EB2.2Graph500測試基準(zhǔn)的設(shè)計原理Graph500基準(zhǔn)測試程序的設(shè)計原理是將測試模塊與被測試的生成圖數(shù)據(jù)模塊分離設(shè)計，這種設(shè)計滿足高內(nèi)聚低耦合的程序設(shè)計要求。Graph500基準(zhǔn)測試程序主要分為生成圖數(shù)據(jù)、建立被測數(shù)據(jù)/建圖、BFS搜索驗證和數(shù)據(jù)結(jié)果輸出4個模塊。Graph500基準(zhǔn)測試程序流程如圖2.1所示。圖2.1Graph500基準(zhǔn)測試程序流程圖生成圖數(shù)據(jù)：Graph500基準(zhǔn)測試程序的圖生成方式是采用R-MAT（多遞歸生成器）方法生產(chǎn)一個特殊的張量積克羅內(nèi)克無向圖用于BFS算法搜索，并14

第2章Graph500基準(zhǔn)測試程序分析依據(jù)設(shè)定的圖規(guī)模（即圖的頂點數(shù)和邊數(shù)）來界定圖的性質(zhì)�？刂茍D的規(guī)模的參數(shù)有兩個，分別是scale和edgefactor，其中scale控制圖的頂點數(shù)，表示生成圖的頂點數(shù)以2為底的對數(shù)；edgefactor用來控制生成圖的邊數(shù)，表示圖的頂點數(shù)與邊數(shù)的比值；假如分別用N和M表示生成圖頂點數(shù)和邊數(shù)，則生成圖的頂點數(shù)是N=2，邊數(shù)是M=edgefactor×N。Graph500基準(zhǔn)測試程序中默認(rèn)scale等于14、edgefactor等于16，即標(biāo)準(zhǔn)條件。圖生成算法可以將生成的克羅內(nèi)科圖規(guī)約成一系列邊的元組信息，圖中每個頂點相關(guān)聯(lián)邊的存儲位置區(qū)間從start_edge_index到end_edge_index-1，用于存儲邊集合的數(shù)組長度是end_edge_index-start_edge_index，每條邊都是由頭頂點head_vertex和尾頂點end_vertex構(gòu)成。這部分代碼在文件generator/graph_generator.c中，代碼在OpenMP和CrayXMT上是并行的。建立被測數(shù)據(jù)：這個模塊的主要任務(wù)是把邊元組信息轉(zhuǎn)換成順序表（list）和行壓縮矩陣（csr）兩種不同的圖數(shù)據(jù)結(jié)構(gòu)，這一部分生成后不能被后面的搜索程序改變，這部分內(nèi)容主要在文件Graph500.c中。這一部分和前面的圖生成部分均屬于數(shù)據(jù)的準(zhǔn)備部分，下圖2.2是Graph500測試基準(zhǔn)數(shù)據(jù)準(zhǔn)備流程圖。圖2.2Graph500測試基準(zhǔn)數(shù)據(jù)準(zhǔn)備流程圖圖中設(shè)置圖的大小指的是根據(jù)不同的機器設(shè)置不同的scale值和edgefactor值，以免出現(xiàn)取值太小造成數(shù)據(jù)精度不足，或者取值太大造成數(shù)組越界。BFS遍歷及驗證：此過程中程序隨機選定一個根頂點，以該頂點為源點，對15

【參考文獻】：
期刊論文
[1]高性能計算應(yīng)用驅(qū)動發(fā)展研究分析[J]. 顧蓓蓓.  科研信息化技術(shù)與應(yīng)用. 2019(04)
[2]基于大數(shù)據(jù)挖掘的企業(yè)智能知識管理與決策的研究[J]. 趙艦波.  經(jīng)濟研究導(dǎo)刊. 2018(15)
[3]高性能計算系統(tǒng)性能評測方法及其應(yīng)用[J]. 魏敏,孫婧,沈瑜,肖華東,李娟.  應(yīng)用氣象學(xué)報. 2013(06)
[4]高性能計算在工業(yè)工程領(lǐng)域的應(yīng)用[J]. 王普勇,丁峻宏.  科研信息化技術(shù)與應(yīng)用. 2012(06)
[5]由具體嘗試到抽象分析——歐拉解決哥尼斯堡七橋問題的思路與方法[J]. 趙樹智.  中學(xué)數(shù)學(xué). 1985(07)

博士論文
[1]計算機輔助的酶的底物虛擬篩選和底物生長系統(tǒng)的設(shè)計與開發(fā)[D]. 姚志強.華東理工大學(xué) 2016

碩士論文
[1]面向圖搜索的流寄存器文件設(shè)計與協(xié)同BFS算法優(yōu)化[D]. 葉帥.國防科學(xué)技術(shù)大學(xué) 2015



本文編號：3365767