多核下可擴(kuò)放確定性并行的MapReduce.pdf

1、MapReduce是支持?jǐn)?shù)據(jù)并行的簡(jiǎn)單有效的編程模型，它最初為集群編程而設(shè)計(jì)。隨著多核處理器的日益普及，研制面向多核的MapReduce編程庫(kù)以充分利用多核單機(jī)系統(tǒng)的計(jì)算資源也變得十分重要?，F(xiàn)有的面向多核的MapReduce庫(kù)，如Phoenix等，大都使用Pthreads庫(kù)在CPU核間分派任務(wù)，依靠共享內(nèi)存進(jìn)行任務(wù)間通信。由于線程交織運(yùn)行的不確定性，當(dāng)Reduce函數(shù)不可交換時(shí)，會(huì)導(dǎo)致基于這些庫(kù)的MapReduce應(yīng)用在執(zhí)行時(shí)產(chǎn)生不確定

2、的、甚至是錯(cuò)誤的行為。
　　本文旨在設(shè)計(jì)和實(shí)現(xiàn)一個(gè)確定的面向多核的MapReduce庫(kù)，它不僅保證MapReduce應(yīng)用程序確定地并行執(zhí)行，而且具有好的性能。本文的主要貢獻(xiàn)如下:
　　(1)用確定的消息傳遞多線程編程庫(kù)DetMP設(shè)計(jì)實(shí)現(xiàn)了與Phoenix編程接口兼容的、確定的MapReduce庫(kù)DMR。為保證并行的確定性，DMR采用靜態(tài)劃分確定地將任務(wù)指派給各個(gè)Map和Reduce線程;并利用DetMP使線程之間缺省地內(nèi)存隔

3、離，只能通過(guò)顯式聲明的確定性通道進(jìn)行通信。為提升并行執(zhí)行的性能，對(duì)DMR進(jìn)行了一些優(yōu)化，包括面向應(yīng)用的調(diào)度等。
　　(2)基于DMR的開(kāi)發(fā)以及用DetMP改寫(xiě)Pthreads程序dedup的經(jīng)驗(yàn)，總結(jié)了DetMP的可編程性和編程規(guī)則。DetMP適合編寫(xiě)具有流水線并行的應(yīng)用程序。利用DetMP簡(jiǎn)單的通道編程接口，程序員無(wú)須管理線程間數(shù)據(jù)流的存儲(chǔ)和并發(fā)訪問(wèn)細(xì)節(jié)，簡(jiǎn)化了編程。但是，DetMP不能支持個(gè)別Phoenix應(yīng)用中出現(xiàn)的堆共享等

4、特征，DMR針對(duì)此擴(kuò)展了Phoenix應(yīng)用編程接口并給出了相應(yīng)的實(shí)現(xiàn)對(duì)策。
　　(3)在32核機(jī)器上對(duì)DMR進(jìn)行性能評(píng)估，并分析DetMP的不同實(shí)現(xiàn)機(jī)制對(duì)程序性能的影響。本文使用Phoenix測(cè)試程序集評(píng)估Phoenix和DMR的性能，實(shí)驗(yàn)表明，DMR僅在kmeans上性能略差，而在其余6個(gè)程序上有與Pthreads相當(dāng)或者更優(yōu)的性能。原有的DetMP實(shí)現(xiàn)是建立在確定的共享內(nèi)存模型SPMC之上，本文進(jìn)一步用Pthreads共享內(nèi)存