發(fā)布時間：2021-06-29 14:26

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

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

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

【學位級別】：碩士

【部分圖文】：

云計算體系結構圖

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

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


本文編號：3256606