隨著信息技術(shù)的飛速發(fā)展,網(wǎng)頁檢索、社交網(wǎng)絡(luò)、生物信息科學(xué)等領(lǐng)域所涉及的圖論知識和算法得到了廣泛應(yīng)用和發(fā)展。自然生成的圖數(shù)據(jù)規(guī)模呈現(xiàn)了爆炸式的增長,讓分布式圖計算這一領(lǐng)域成為了學(xué)術(shù)界和工業(yè)界的熱門研究方向。而對于大規(guī)模圖數(shù)據(jù)進行合理的劃分與存儲,能夠減少機器節(jié)點間的通信量,是提升分布式圖計算性能的研究熱點之一。此外,分布式圖計算系統(tǒng)在實現(xiàn)分布式計算模型時的實現(xiàn)方式,往往會存在著冗余計算或冗余通信的問題。因此,分布式計算模型的優(yōu)化及實現(xiàn),也是分布式圖計算系統(tǒng)性能優(yōu)化的關(guān)鍵性問題。本文深入研究了分布式圖數(shù)據(jù)劃分和分布式圖計算模型,探討了分布式圖計算系統(tǒng)性能優(yōu)化技術(shù),重點圍繞基于拓?fù)渲貥?gòu)的分布式圖分割算法和基于增量變化的GAS分布式計算模型展開了深入研究。本文的主要研究工作包括:一、深入研究并分析了分布式圖計算已有的圖數(shù)據(jù)劃分算法,在分析其研究成果的優(yōu)勢時,也揭示了其各自的局限性;深入分析了現(xiàn)有的分布式圖計算模型及其在實際分布式圖計算系統(tǒng)的實現(xiàn),發(fā)現(xiàn)其存在的優(yōu)點和需要改進的方向。二、針對大規(guī)模圖計算的低效分區(qū)問題,提出了基于拓?fù)渲貥?gòu)的分布式圖分割算法。通過對自然生成的圖數(shù)據(jù)進行分析發(fā)現(xiàn),自然圖... 

【文章來源】：國防科技大學(xué)湖南省 211工程院校 985工程院校

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

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

【部分圖文】：

云計算體系結(jié)構(gòu)圖

圖 2.1 BSP 模型處理過程圖 BSP 作業(yè)由 N 個順序執(zhí)行的超步（superstep）組成，來對應(yīng)于行任務(wù)按照超步組織，在超步 Si內(nèi)，各任務(wù)異步接受來自 Si-1的算并發(fā)送消息給下一個超步 Si+1。每次迭代處理的超步包含上圖本地計算、全局通信、柵欄同步。地計算階段：每個處理器進行獨立的計算，處理器計算都利用理器間沒有任何聯(lián)系，不進行通信，獨自完成相應(yīng)的計算。局通信階段：當(dāng)所有的處理器完成局部計算之后，所有的信息塊進行傳輸，該階段沒有任何計算操作。欄同步階段：由于處理器性能差異或每個處理器需要處理數(shù)據(jù)部計算出現(xiàn)完成時間不一致，有的處理器可能很早就完成計算慢的節(jié)點，在通過全局通信階段之后，數(shù)據(jù)到達柵欄同步階段將所有的等待進行同步，可以避免因異步計算導(dǎo)致的死鎖問題成標(biāo)識該次超步結(jié)束，可以進行下次超步。步之間，通過顯式地同步控制，確保所有任務(wù)均已完成超步 Si

國防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文（例如邊<D，B>）成為超點 A'的鄰邊（<D，A'>）。在圖 3.2(b)中描繪了最終的拓?fù)浣Y(jié)構(gòu)，其中超點 A'由 A 和它的 1 跳/2 跳低度鄰點組成。超點仍然被認(rèn)為是低度的，并且它們的邊被分配到目的點。例如，<D，A'>和<A'，E>分別與 A'和 E 一起分配。


本文編號：3256606