多核環(huán)境下面向數(shù)據(jù)并行編程模型的性能和可伸縮性研究.pdf

1、近10年來(lái)對(duì)于大規(guī)模數(shù)據(jù)處理的需求變的日益迫切,等待處理的數(shù)據(jù)如雪崩一般不斷增長(zhǎng)。據(jù)權(quán)威咨詢公司IDC于2007年統(tǒng)計(jì),截至2006年存儲(chǔ)于電子介質(zhì)中的數(shù)據(jù)量達(dá)到驚人的161艾字節(jié)(Exabyte),并且預(yù)計(jì)至2010年這一數(shù)字將來(lái)到998艾字節(jié)。毫無(wú)疑問(wèn)數(shù)據(jù)密集型應(yīng)用己經(jīng)成為當(dāng)今最為重要的計(jì)算機(jī)應(yīng)用之一。
　　與此同時(shí),隨著多核技術(shù)的日益普及,片上核數(shù)目的快速增長(zhǎng),多核平臺(tái)在大規(guī)模數(shù)據(jù)處理領(lǐng)域呈現(xiàn)出極為廣闊的應(yīng)用前景。然而這些以

2、多核形式提供的強(qiáng)大計(jì)算能力,只有通過(guò)并行程序才能得以充分利用,發(fā)揮出與核數(shù)目的增長(zhǎng)一致的實(shí)際效果。高效并行程序的編寫(xiě)歷來(lái)是困擾程序員的難題,因?yàn)槌藰I(yè)務(wù)邏輯本身,程序員還必須面對(duì)包括數(shù)據(jù)分布、可伸縮性、負(fù)載平衡和系統(tǒng)容錯(cuò)在內(nèi)的大量與并行性相關(guān)的復(fù)雜問(wèn)題。權(quán)威調(diào)研機(jī)構(gòu)Gartner于2008年列出了未來(lái)25年IT市場(chǎng)面臨的七大挑戰(zhàn),多核時(shí)代的并行編程位居第二。
　　面向數(shù)據(jù)并行編程模型無(wú)疑是這一挑戰(zhàn)的最好解答,通過(guò)合理的抽象向應(yīng)用程

3、序員隱藏并行性相關(guān)問(wèn)題,在將業(yè)務(wù)邏輯開(kāi)發(fā)留給應(yīng)用程序員的同時(shí),將實(shí)現(xiàn)并行的挑戰(zhàn)留給并行計(jì)算專家。然而現(xiàn)有的面向數(shù)據(jù)并行編程模型和運(yùn)行時(shí)支持大多針對(duì)集群平臺(tái)設(shè)計(jì)和實(shí)現(xiàn),并沒(méi)有充分考慮到多核平臺(tái)的自身特點(diǎn),比如高速核間通信、共享緩存競(jìng)爭(zhēng)和整機(jī)故障模型等,因此也就不能有效的利用多核技術(shù)帶來(lái)的強(qiáng)大計(jì)算能力。此外,現(xiàn)有的并行編程模型設(shè)計(jì)更多的關(guān)注于通用性而缺乏針對(duì)性,限制了模型在某些應(yīng)用領(lǐng)域和計(jì)算需求下的執(zhí)行效果。
　　本文在深入分析現(xiàn)有M

4、apReduce并行編程模型在多核平臺(tái)上存在的性能和可伸縮性問(wèn)題的基礎(chǔ)上,提出了一個(gè)系統(tǒng)的解決方案。首先以MapReduce模型為基礎(chǔ)采用分治策略針對(duì)多核平臺(tái)特點(diǎn)進(jìn)行擴(kuò)展,然后基于分治MapReduce模型提出了針對(duì)內(nèi)存占用、緩存局部性和任務(wù)并行性三個(gè)方面的多個(gè)優(yōu)化,最后以在線聚集計(jì)算和增量計(jì)算為例分析并驗(yàn)證了分治MapReduce模型對(duì)于不同領(lǐng)域和不同需求應(yīng)用的高效支持。相對(duì)于之前的研究而言,該研究致力于設(shè)計(jì)和實(shí)現(xiàn)針對(duì)多核平臺(tái)的面向數(shù)

5、據(jù)并行編程模型,充分利用資源獲得與之相匹配的性能和可伸縮性,并為更多的領(lǐng)域和應(yīng)用提供高效地支持。
　　具體而言,本文的主要貢獻(xiàn)如下:
　　1.從面向數(shù)據(jù)并行編程模型的角度深入分析多核平臺(tái)與集群平臺(tái)間存在的主要差異,并在此基礎(chǔ)上揭示了面向集群平臺(tái)設(shè)計(jì)的MapRedlice并行編程模型在多核平臺(tái)上存在的主要問(wèn)題。提出利用分治策略對(duì)MapReduce并行編程模型進(jìn)行擴(kuò)展,將大型任務(wù)分解為多個(gè)子任務(wù)迭代執(zhí)行,并改進(jìn)原有的容錯(cuò)機(jī)制,以

6、達(dá)到充分適應(yīng)多核平臺(tái)特點(diǎn)的目標(biāo)。2.提出基于分治MapReduce模型,涉及內(nèi)存、緩存和處理器三個(gè)方面的多個(gè)運(yùn)行時(shí)優(yōu)化。采用動(dòng)態(tài)數(shù)據(jù)加載和緩沖區(qū)重用技術(shù)減少并縮短內(nèi)存資源占用,采用面向非一致緩存/內(nèi)存訪問(wèn)(NUCA/NUMA-aware)的調(diào)度策略提高緩存局部性,采用軟件流水線技術(shù)(SoftwarePipeline)和任務(wù)竊取技術(shù)(WorkStealing)消除處理器空閑。
　　3.基于分治MapReduce模型以及相關(guān)運(yùn)行時(shí)優(yōu)化

7、,在多核平臺(tái)設(shè)計(jì)并實(shí)現(xiàn)了名為Ostrich的原型系統(tǒng)。深入評(píng)測(cè)的結(jié)構(gòu)表明,分治MapReduce模型的接口擴(kuò)展相對(duì)于其它MapReduce模型實(shí)現(xiàn)并不會(huì)對(duì)程序員產(chǎn)生額外負(fù)擔(dān)。其次,在16核Intel處理器構(gòu)成的測(cè)試平臺(tái)上,Ostrich運(yùn)行時(shí)不但在所有基準(zhǔn)測(cè)試中都具有更好的可伸縮性,并且在性能測(cè)試中節(jié)省高達(dá)85％的內(nèi)存,降低3.1倍至7.1倍的緩存缺失率,以及提高整體性能1.2倍至3.3倍。
　　4.利用分治MapReduce模型