并行樹(shù)和圖計(jì)算框架的分布式實(shí)現(xiàn).pdf

1、樹(shù)(如二叉樹(shù)或一般樹(shù))是一種重要的數(shù)據(jù)結(jié)構(gòu),它經(jīng)常被用來(lái)表示像數(shù)學(xué)表達(dá)式或結(jié)構(gòu)性文檔(如XML)這樣的分層數(shù)據(jù)結(jié)構(gòu)。雖然樹(shù)結(jié)構(gòu)被廣泛應(yīng)用在串行程序中,但由于其不規(guī)則和不平衡的結(jié)構(gòu)特點(diǎn),使得開(kāi)發(fā)有效率的在樹(shù)上進(jìn)行計(jì)算的并行程序變得很困難。雖然目前已經(jīng)存在不少關(guān)于樹(shù)的并行化研究,但設(shè)計(jì)高效的適合于分布式系統(tǒng)的樹(shù)并行化算法仍然是個(gè)挑戰(zhàn)。
　　另一方面,大型的網(wǎng)絡(luò)(圖)開(kāi)始普遍存在于很多領(lǐng)域中,如生物、物理、化學(xué)、通訊和社交網(wǎng)絡(luò)等。人們?nèi)?/p>

2、益增長(zhǎng)的對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行分析的需求對(duì)圖并行化的研究提出了挑戰(zhàn)。很多圖優(yōu)化問(wèn)題(如最大權(quán)重獨(dú)立集問(wèn)題)是NP困難的。解決這樣的圖問(wèn)題需要的計(jì)算復(fù)雜度通常和圖的大小呈指數(shù)關(guān)系,即與圖上的頂點(diǎn)數(shù)或邊數(shù)成指數(shù)關(guān)系。對(duì)于那些大規(guī)模的圖,極高的計(jì)算復(fù)雜度使得這些圖問(wèn)題即使利用計(jì)算機(jī)集群也很難計(jì)算出結(jié)果。幸運(yùn)的是,研究者發(fā)現(xiàn),很多圖上的NP困難問(wèn)題在具有有限樹(shù)寬的圖上可以使用動(dòng)態(tài)規(guī)劃技術(shù)和樹(shù)分解在多項(xiàng)式時(shí)間內(nèi)進(jìn)行求解。
　　本課題對(duì)國(guó)內(nèi)外樹(shù)并

3、行化和圖并行化相關(guān)的工作進(jìn)行了研究。通過(guò)擴(kuò)展第三同態(tài)定理在樹(shù)上的應(yīng)用和zipper結(jié)構(gòu),提出了適合于分布式環(huán)境并可應(yīng)用于MapReduce模型上的樹(shù)并行框架。由于樹(shù)分解從數(shù)據(jù)結(jié)構(gòu)角度來(lái)看是樹(shù)結(jié)構(gòu),本課題提出了把樹(shù)分解上自底向上的動(dòng)態(tài)規(guī)劃算法轉(zhuǎn)化為在zipper結(jié)構(gòu)上的并行算法的方法。通過(guò)結(jié)合所提出的樹(shù)并行化框架和樹(shù)分解技術(shù),提出了適用于分布式環(huán)境的圖并行化框架,從而實(shí)現(xiàn)了圖優(yōu)化類(lèi)問(wèn)題的高效并行化。
　　本論文的主要貢獻(xiàn)有如下幾個(gè)方