資源描述：
《基于眾核平臺(tái)子圖匹配算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、基于眾核平臺(tái)子圖匹配算法研究王峰2016年1月中圖分類號(hào)：TP391UDC分類號(hào)：004.9基于眾核平臺(tái)子圖匹配算法研究作者姓名王峰學(xué)院名稱計(jì)算機(jī)學(xué)院指導(dǎo)教師祝烈煌教授答辯委員會(huì)主席周永彬申請(qǐng)學(xué)位工學(xué)碩士學(xué)科專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)位授予單位北京理工大學(xué)論文答辯日期2016年1月7日ResearchofMany-core-basedSubgraphMatchingAlgorithmCandidateName：WangFengSchoolorDepartment:SchoolofComputerScienceF
2、acultyMentor:Prof.ZhuLieHuangChair,ThesisCommittee：ZhouYongbinDegreeApplied:MasterofScienceMajor：ComputerScience&TechnologyDegreeby:BeijingInstituteofTechnologythTheDateofDefense：7,January,2016研究成果聲明本人鄭重聲明：所提交的學(xué)位論文是我本人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作獲得的研究成果。盡我所知，文中除特別標(biāo)注和致
3、謝的地方外，學(xué)位論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得北京理工大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)所使用過(guò)的材料。與我一同工作的合作者對(duì)此研究工作所做的任何貢獻(xiàn)均已在學(xué)位論文中作了明確的說(shuō)明并表示了謝意。特此申明。簽名：日期：摘要在大數(shù)據(jù)時(shí)代，信息的數(shù)量和復(fù)雜性呈幾何式增長(zhǎng)，因此信息的表示也變得愈加復(fù)雜。圖作為一種常用的建模模型，提供了一個(gè)很自然的數(shù)據(jù)結(jié)構(gòu)，可以對(duì)自然科學(xué)和社會(huì)科學(xué)中許多領(lǐng)域的問(wèn)題進(jìn)行恰當(dāng)?shù)拿枋龊徒?。因此圖在大數(shù)據(jù)時(shí)代中發(fā)揮著不可替代的作用。在大規(guī)模圖中，能夠高效地對(duì)數(shù)據(jù)進(jìn)
4、行挖掘，檢索出所需要的部分對(duì)于信息的處理有非常重要的意義。但傳統(tǒng)的CPU硬件平臺(tái)很難提供高效的計(jì)算速率。在高性能計(jì)算領(lǐng)域，GPU眾核設(shè)備由于具有線程多，并行度高的特點(diǎn)，成為主流眾核計(jì)算平臺(tái)。為此，本文通過(guò)GPU眾核平臺(tái)，實(shí)現(xiàn)高效率的子圖匹配算法。算法首先通過(guò)GPU在大圖中搜索出與查詢圖的中心節(jié)點(diǎn)具有相同性質(zhì)的節(jié)點(diǎn)，然后在以這些節(jié)點(diǎn)為中心，查詢圖的半徑長(zhǎng)度為半徑，使用眾核的最短路徑算法，在大圖上截取待匹配子圖。然后再使用眾核對(duì)所獲得待匹配子圖與查詢圖進(jìn)行匹配操作。本算法的主要工作如下：（1）在截取子圖的過(guò)程中
5、，針對(duì)大規(guī)模圖的最短路徑（SSSP）問(wèn)題，本文提出了把節(jié)點(diǎn)度值統(tǒng)一化的數(shù)據(jù)預(yù)處理操作，圖數(shù)據(jù)經(jīng)過(guò)預(yù)處理，GPU中每個(gè)線程的任務(wù)量相同從而減少了計(jì)算資源的浪費(fèi)。圖數(shù)據(jù)經(jīng)過(guò)度值統(tǒng)一化操作后，又經(jīng)過(guò)一次轉(zhuǎn)置操作，提升了線程讀取內(nèi)存地址凝聚性，從而提高了SSSP的計(jì)算速率。（2）我們提出了數(shù)據(jù)塊迭代的計(jì)算方法，來(lái)替代傳統(tǒng)方法中通過(guò)原子操作對(duì)全局變量的進(jìn)行讀寫(xiě)操作以避免“寫(xiě)后寫(xiě)”錯(cuò)誤，數(shù)據(jù)塊迭代計(jì)算的方法既保證了結(jié)果正確性，又能提升計(jì)算速率。（3）在子圖匹配過(guò)程中，我們采用通過(guò)鄰居連接信息進(jìn)行節(jié)點(diǎn)匹配判定的VF2算法
6、，使用眾核設(shè)備并行對(duì)多個(gè)待匹配節(jié)點(diǎn)對(duì)使用VF2算法，實(shí)現(xiàn)子圖匹配過(guò)程的加速。關(guān)鍵詞：GPU；最短路徑問(wèn)題；統(tǒng)一度；子圖匹配；VF2算法。IAbstractInthetimeofbigdata,thescaleandcomplexityofinformationareinexponentialgrowth.Therepresentationofinformationisbecomingmorecomplex.Graphprovidesanaturaldatastructure,asacommonmodel.S
7、o,graphplaysanirreplaceableroleinthetimeofbigdata.Inlargescalegraph,itisimportanttocarryoutdataminingandretrievetherequiredinformation.ItisdifficultfortraditionCPUhardwareplatformtoprovideefficientcomputingspeed.Intheareaofhighperformancecompute,GPUisacomm
8、onmany-coreplatformforitshighparallelismandmultiplethreads.Inthispaper,weimplementahighefficiencysubgraphmatchingalgorithmforlargescalegraphwiththeGPUplatform.Thealgorithmfirstfindsthevertexinthelargegraphwit
