多核下可擴放確定性并行的MapReduce.pdf

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

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

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

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