發(fā)布時(shí)間：2017-11-20 20:08

  本文關(guān)鍵詞：基于多核的Ramsey數(shù)算法研究

  更多相關(guān)文章： 并行計(jì)算 MapReduce Phoenix++ Ramsey數(shù)

【摘要】：隨著大數(shù)據(jù)時(shí)代的到來,傳統(tǒng)的數(shù)據(jù)處理方式已經(jīng)無法滿足越來越大的計(jì)算需求。按照處理器超線程和多核化的發(fā)展趨勢,基于集群的分布式編程和基于多核的多線程并發(fā)編程已經(jīng)成為提升計(jì)算性能的兩個(gè)最重要的途徑。(Google公司提出了一種能夠并發(fā)處理海量數(shù)據(jù)的并行編程模型MapReduce,可用于處理數(shù)據(jù)密集型任務(wù)。目前,已經(jīng)有多種不同的MapReduce模型的具體實(shí)現(xiàn),其中基于多核共享存儲的Phoenix++系統(tǒng)的執(zhí)行效率較高。 圖的Ramsey數(shù)在信息論和理論計(jì)算機(jī)科學(xué)中有重要的應(yīng)用,但是確定它的準(zhǔn)確值是NP困難問題。在研究Ramsey數(shù)時(shí),隨著圖的頂點(diǎn)個(gè)數(shù)的增加,需要考慮的著色情況會以指數(shù)級增加。由于計(jì)算量的急劇增大,利用單核CPU的計(jì)算機(jī)難以在較短時(shí)間內(nèi)求解出該問題。因此,本文對基于多核共享存儲的Ramsey數(shù)求解算法進(jìn)行研究。 首先對MapReduce編程模型的原理與執(zhí)行過程、MapRedu ce模型的不同實(shí)現(xiàn)和基于多核的MapReduce模型的Phoenix++系統(tǒng)進(jìn)行了詳細(xì)介紹。然后設(shè)計(jì)了單核CPU下的圈集對完全圖的Ramsey數(shù)求解算法,并采取數(shù)據(jù)預(yù)處理、合理的任務(wù)劃分以及鍵值對設(shè)計(jì)等措施將其改進(jìn)為基于Phoenix++系統(tǒng)的多核并行算法。通過試驗(yàn)對并行算法的正確性進(jìn)行了驗(yàn)證,并對其性能進(jìn)行了評估。試驗(yàn)結(jié)果表明,在4核CPU平臺上,隨著頂點(diǎn)數(shù)的增加,該并行算法的加速比最高達(dá)到了3.70,執(zhí)行效率相應(yīng)增大到92.50%。最后,利用該多核并行算法分別計(jì)算R(C≤n),Kn+1)(4≤n≤13)以及R(C≤n, Kn+2)(4≤n≤12)的上下界,從而確定了他們的準(zhǔn)確值。
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP311.13;TP332

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前7條

1 許進(jìn),張雷;DNA計(jì)算機(jī)原理、進(jìn)展及難點(diǎn)(Ⅰ):生物計(jì)算系統(tǒng)及其在圖論中的應(yīng)用[J];計(jì)算機(jī)學(xué)報(bào);2003年01期

2 陳國良;孫廣中;徐云;呂敏;;并行算法研究方法學(xué)[J];計(jì)算機(jī)學(xué)報(bào);2008年09期

3 李雨生;通訊頻道的Shannon容量,圖的Ramsey數(shù)和Erd銉s的一個(gè)猜想[J];科學(xué)通報(bào);2001年18期

4 臧冬松;霍菁;梁棟;孫功星;;基于MapReduce的高能物理數(shù)據(jù)分析系統(tǒng)[J];計(jì)算機(jī)工程;2014年02期

5 王永貴;李鴻緒;宋曉;;MapReduce模型下的模糊C均值算法研究[J];計(jì)算機(jī)工程;2014年10期

6 代亮;許宏科;陳婷;錢超;梁殿鵬;;基于MapReduce的最小二乘支持向量機(jī)回歸模型[J];計(jì)算機(jī)應(yīng)用研究;2015年04期

7 李芳;關(guān)于程序正確性證明的進(jìn)一步探討[J];信息技術(shù)與信息化;2005年04期

，

本文編號：1208345