分布式環(huán)境下的圖劃分算法研究
發(fā)布時間：2021-07-23 16:45
自20世紀80年代開始,復雜系統(tǒng)的研究逐漸興起,它被認為是解決各個領域研究面臨的困難的一個重要突破點。而復雜網絡是研究復雜系統(tǒng)的一個重要工具,如物流運輸、道路規(guī)劃、社交網絡、生物研究等問題在研究的過程中,都可以抽象成由邊和頂點組成的復雜網絡,借助于復雜網絡的相關技術對其進行研究。但系統(tǒng)中基本單元常常達到成千上萬甚至是數以億計,這就使得復雜網絡的研究不得不借助于高效的計算工具來解決實時的、規(guī)模足夠大的計算問題。分布式計算技術是現在最成熟、應用最廣、最可行的計算加速技術之一。因此研究復雜網絡的分布式計算技術具有十分重要的意義。在做分布式計算之前,需要將原始復雜網絡劃分成若干個子網絡,保證各個子網絡規(guī)模相對均衡和網絡間的通信開銷最小化是分布式計算性能好壞的關鍵。圖劃分技術就是解決這一問題的有效手段。圖劃分算法按照劃分方式的不同,可以分為點劃分算法和邊劃分算法。數據量的快速增長對圖劃分算法的劃分質量和劃分效率提出了新的要求。本文主要工作體現在以下方面:（1）針對當前點劃分算法劃分質量較低的問題,本文提出了基于滑動窗口的流式圖劃分模型（Graph Win）,該模型通過引入滑動窗口機制,根據當前劃...
【文章來源】：重慶大學重慶市 211工程院校 985工程院校 教育部直屬院校
【文章頁數】：58 頁
【學位級別】：碩士
【部分圖文】：
圖1.1分布式環(huán)境下的圖劃分算法研究背景Fig.1.1Streamingpartitioningmodel
結果割邊率比較大。Grid算法[17]、DBH算法[18]、HDRF算法[19]都屬于此類算法。②當前邊劃分算法仍存在效率低的問題。邊劃分算法雖然使用到圖數據的其他局部信息，能夠獲得較好的劃分結果，但該類算法由于使用啟發(fā)式算法在全局圖數據上尋找較優(yōu)劃分方案，計算時間復雜度比較大。例如，使用Metis算法對超過14億條邊的Twitter數據集做劃分時，劃分后的結果割邊率為35.96%，但劃分時間卻高達8.5小時[23]，這在許多要求實時響應的應用場景下是無法容忍的。所以如何提高邊劃分算法的劃分效率是當前亟待解決的問題。圖1.2各類算法在劃分質量和分區(qū)劃分上的對比Fig.1.2Comparisonofvariousalgorithmsinpartitionqualityandpartitiontime1.4本文的研究內容本文對復雜網絡劃分做了研究，首先調研了當前已有的圖劃分算法，并分析了這些算法的優(yōu)缺點，其次針對現有算法存在的不足，提出了基于滑動窗口的流式圖劃分模型（GraphWin）和基于GPU加速的圖劃分模型（GraphGPU），并結合已有的圖劃分算法對兩個模型分別做了對比試驗。本文具體研究內容如下：①研究了圖劃分算法的發(fā)展歷史，分析了圖劃分算法中的核心概念。之后研究了圖劃分的幾種常用算法，包括傳統(tǒng)的靜態(tài)圖劃分算法和流式圖劃分算法。針對點劃分算法和邊劃分算法存在的問題，本文分別提出了基于滑動窗口的流式圖
重慶大學碩士學位論文2圖劃分算法的相關研究82圖劃分算法的相關研究圖劃分是圖論中經典的問題之一，它在多個領域中有著廣泛的應用，例如并行計算[24]、復雜網絡[25-31]、道路規(guī)劃[32-35]、圖像分割[36-38]、超大規(guī)模集成電路設計[39-42]等�，F實中的很多問題可以抽象為圖劃分問題，圖劃分可以將原始問題分解成多個小問題，再對每個小問題分別求解，從而能夠進一步提高處理效率。本章首先給出了圖劃分的定義，之后詳細介紹了經典的圖劃分算法和分布式計算平臺。2.1圖劃分定義定義（割邊）：給定兩個分區(qū)Pi和Pj，其中i≠j。如果這兩個分區(qū)中的任意兩點u和v存在邊，而稱這條邊為一條割邊。{(,)|,,}ijedgeCuteuveEuPvP（2.1）定義（圖劃分）：給定圖數據G=(V,E)和一個正整數k,V是圖G的頂點集合，E是圖G的邊集合,k是分區(qū)個數。圖劃分問題就是將圖數據G劃分成k個互不相交的集合P={P1,…Pk}，每個集合稱為一個分區(qū)，同時圖劃分還需要滿足兩個重要原則:①負載均衡。盡量使劃分后各分區(qū)的頂點數目大致相同，避免因任務分配不均造成資源浪費，即使得：||1,...,iVVikk（2.2）②割邊數盡可能校分區(qū)間的割邊數量直接影響通信開銷，因為分區(qū)與分區(qū)之間的通信開銷完全取決于網絡，而且比分區(qū)內的通信代價高，所以為了減少總體的通信開銷，需要優(yōu)化割邊數量，關于割邊數的優(yōu)化目標如下：1,0((,))nijMininizeedgeCutij（2.3）圖2.1基于edge-cut劃分問題示例Fig.2.1Anexampleofpartitioningproblembasedonedge-cut
【參考文獻】：
期刊論文
[1]BHP:面向BSP模型的負載均衡Hash圖數據劃分[J]. 周爽,鮑玉斌,王志剛,冷芳玲,于戈,鄧超,郭磊濤. 計算機科學與探索. 2014(01)
本文編號：3299662
【文章來源】：重慶大學重慶市 211工程院校 985工程院校 教育部直屬院校
【文章頁數】：58 頁
【學位級別】：碩士
【部分圖文】：
圖1.1分布式環(huán)境下的圖劃分算法研究背景Fig.1.1Streamingpartitioningmodel
結果割邊率比較大。Grid算法[17]、DBH算法[18]、HDRF算法[19]都屬于此類算法。②當前邊劃分算法仍存在效率低的問題。邊劃分算法雖然使用到圖數據的其他局部信息，能夠獲得較好的劃分結果，但該類算法由于使用啟發(fā)式算法在全局圖數據上尋找較優(yōu)劃分方案，計算時間復雜度比較大。例如，使用Metis算法對超過14億條邊的Twitter數據集做劃分時，劃分后的結果割邊率為35.96%，但劃分時間卻高達8.5小時[23]，這在許多要求實時響應的應用場景下是無法容忍的。所以如何提高邊劃分算法的劃分效率是當前亟待解決的問題。圖1.2各類算法在劃分質量和分區(qū)劃分上的對比Fig.1.2Comparisonofvariousalgorithmsinpartitionqualityandpartitiontime1.4本文的研究內容本文對復雜網絡劃分做了研究，首先調研了當前已有的圖劃分算法，并分析了這些算法的優(yōu)缺點，其次針對現有算法存在的不足，提出了基于滑動窗口的流式圖劃分模型（GraphWin）和基于GPU加速的圖劃分模型（GraphGPU），并結合已有的圖劃分算法對兩個模型分別做了對比試驗。本文具體研究內容如下：①研究了圖劃分算法的發(fā)展歷史，分析了圖劃分算法中的核心概念。之后研究了圖劃分的幾種常用算法，包括傳統(tǒng)的靜態(tài)圖劃分算法和流式圖劃分算法。針對點劃分算法和邊劃分算法存在的問題，本文分別提出了基于滑動窗口的流式圖
重慶大學碩士學位論文2圖劃分算法的相關研究82圖劃分算法的相關研究圖劃分是圖論中經典的問題之一，它在多個領域中有著廣泛的應用，例如并行計算[24]、復雜網絡[25-31]、道路規(guī)劃[32-35]、圖像分割[36-38]、超大規(guī)模集成電路設計[39-42]等�，F實中的很多問題可以抽象為圖劃分問題，圖劃分可以將原始問題分解成多個小問題，再對每個小問題分別求解，從而能夠進一步提高處理效率。本章首先給出了圖劃分的定義，之后詳細介紹了經典的圖劃分算法和分布式計算平臺。2.1圖劃分定義定義（割邊）：給定兩個分區(qū)Pi和Pj，其中i≠j。如果這兩個分區(qū)中的任意兩點u和v存在邊，而稱這條邊為一條割邊。{(,)|,,}ijedgeCuteuveEuPvP（2.1）定義（圖劃分）：給定圖數據G=(V,E)和一個正整數k,V是圖G的頂點集合，E是圖G的邊集合,k是分區(qū)個數。圖劃分問題就是將圖數據G劃分成k個互不相交的集合P={P1,…Pk}，每個集合稱為一個分區(qū)，同時圖劃分還需要滿足兩個重要原則:①負載均衡。盡量使劃分后各分區(qū)的頂點數目大致相同，避免因任務分配不均造成資源浪費，即使得：||1,...,iVVikk（2.2）②割邊數盡可能校分區(qū)間的割邊數量直接影響通信開銷，因為分區(qū)與分區(qū)之間的通信開銷完全取決于網絡，而且比分區(qū)內的通信代價高，所以為了減少總體的通信開銷，需要優(yōu)化割邊數量，關于割邊數的優(yōu)化目標如下：1,0((,))nijMininizeedgeCutij（2.3）圖2.1基于edge-cut劃分問題示例Fig.2.1Anexampleofpartitioningproblembasedonedge-cut
【參考文獻】：
期刊論文
[1]BHP:面向BSP模型的負載均衡Hash圖數據劃分[J]. 周爽,鮑玉斌,王志剛,冷芳玲,于戈,鄧超,郭磊濤. 計算機科學與探索. 2014(01)
本文編號：3299662
本文鏈接：http://sikaile.net/kejilunwen/ruanjiangongchenglunwen/3299662.html
