分布式圖并行計(jì)算框架的調(diào)度分析與優(yōu)化.pdf

1、隨著大數(shù)據(jù)時(shí)代的到來，基于大規(guī)模數(shù)據(jù)的信息分析和數(shù)據(jù)挖掘技術(shù)逐漸適用于眾多領(lǐng)域。對(duì)于大規(guī)模數(shù)據(jù)處理的編程模型以及計(jì)算效率的需求一直是研究領(lǐng)域的熱點(diǎn)問題之一。其中，數(shù)據(jù)并行（Data-Parallel）的處理模型（如Map-Reduce等分布式編程框架）的提出與優(yōu)化，在過去的幾年中為大規(guī)模數(shù)據(jù)的并行處理提供了重要的支持；然而，隨著搜索與分析等需求的語(yǔ)義化，數(shù)據(jù)分析的應(yīng)用場(chǎng)景也不斷增多，機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘技術(shù)的興起，也使得分布式應(yīng)用的算法趨

2、向于復(fù)雜化，主要體現(xiàn)為計(jì)算的過程在單元數(shù)據(jù)的順序計(jì)算的基礎(chǔ)上增加了迭代性與關(guān)聯(lián)性。因此，圖并行（Graph-Parallel）的處理模型被提出，并逐漸成為大數(shù)據(jù)時(shí)代的下一個(gè)研究重點(diǎn)。
　　大規(guī)模圖并行處理模型的設(shè)計(jì)本質(zhì)上具有迭代與收斂的計(jì)算特性：輸入數(shù)據(jù)以一個(gè)單元的頂點(diǎn)結(jié)構(gòu)為中心，單元數(shù)據(jù)之間的關(guān)聯(lián)性被抽象為圖結(jié)構(gòu)中的邊，每個(gè)頂點(diǎn)根據(jù)邊的依賴關(guān)系不斷進(jìn)行信息傳遞與迭代計(jì)算，直到達(dá)到平衡的收斂狀態(tài)。由于圖并行處理模式的這種計(jì)算特性，

3、在實(shí)現(xiàn)時(shí)具有同步（Sync）與異步（Async）兩種不同的迭代調(diào)度模式。而這兩種調(diào)度模式在頂點(diǎn)計(jì)算的調(diào)度順序、調(diào)度層的管理結(jié)構(gòu)以及硬件和網(wǎng)絡(luò)資源的利用率等方面都具有顯著的差異。然而，現(xiàn)階段基于這兩種調(diào)度模式的比較與分析的相關(guān)研究仍然十分稀缺，在實(shí)際的圖并行處理應(yīng)用的開發(fā)中，圖計(jì)算編程人員通常需要根據(jù)經(jīng)驗(yàn)選擇同步或異步調(diào)度模式其中之一。這不僅要求編程人員對(duì)于圖并行編程框架的底層實(shí)現(xiàn)具有深入的理解，也使得圖并行應(yīng)用的計(jì)算性能無法得到最優(yōu)的保

4、障。
　　基于這些問題，本文主要進(jìn)行了以下幾個(gè)方面的研究：
　　首先，我們基于同步和異步兩種調(diào)度模式的經(jīng)典實(shí)現(xiàn)框架與一系列典型的圖并行計(jì)算的應(yīng)用，創(chuàng)新性地對(duì)這兩種調(diào)度模式的特性和性能表現(xiàn)進(jìn)行了深入的對(duì)比分析與歸納。我們的研究通過詳細(xì)的性能測(cè)試，展示了這兩種調(diào)度模式在不同的圖并行處理算法、不同的圖劃分算法、不同的計(jì)算執(zhí)行階段、不同的輸入數(shù)據(jù)以及不同的集群性能配置等情況下，具有顯著的性能表現(xiàn)差異。同時(shí)，我們歸納和總結(jié)了不同情況下

5、調(diào)度模式選擇的傾向性，并發(fā)現(xiàn)了潛在的性能提升空間。
　　其次，本文提出了Hsync模式——一種自適應(yīng)切換于同步與異步調(diào)度方式之間的啟發(fā)式的圖并行處理調(diào)度模式，從而嘗試達(dá)到圖并行處理應(yīng)用在性能表現(xiàn)上的最優(yōu)化。Hsync模式會(huì)在應(yīng)用的計(jì)算過程中持續(xù)地收集執(zhí)行時(shí)的系統(tǒng)狀態(tài)，結(jié)合啟發(fā)式的判斷策略，預(yù)測(cè)同步與異步兩種調(diào)度方式的執(zhí)行性能，判斷是否應(yīng)該進(jìn)行狀態(tài)轉(zhuǎn)換從而切換到一個(gè)更優(yōu)的調(diào)度方式繼續(xù)執(zhí)行。
　　本文的研究在經(jīng)典的分布式圖并行計(jì)

6、算框架——PowerGraph框架的基礎(chǔ)上進(jìn)行了修改和擴(kuò)展，實(shí)現(xiàn)了支持Hsync調(diào)度模式的PowerSwitch系統(tǒng)。該實(shí)現(xiàn)的核心主要包括了調(diào)度方式轉(zhuǎn)換的支持模塊，以及用于預(yù)測(cè)兩種方式的調(diào)度性能的在線和線下的采樣分析模塊，并歸納總結(jié)了一系列的啟發(fā)式判斷規(guī)則。
　　此外，我們的研究基于一個(gè)48個(gè)節(jié)點(diǎn)的分布式集群配置，對(duì)于PowerSwitch系統(tǒng)進(jìn)行了詳細(xì)的性能評(píng)測(cè)。評(píng)測(cè)顯示，我們系統(tǒng)的計(jì)算性能優(yōu)于同配置下的同步或異步的單一調(diào)度模式