探索確定性的共享內(nèi)存并行編程模型.pdf

1、多核處理器的興起使得并行軟件變得越來越重要，但是目前并行軟件的發(fā)展遠(yuǎn)遠(yuǎn)落后于并行硬件。作為一種主流的并行編程環(huán)境，共享內(nèi)存并行編程中存在大量的不確定性，這些不確定性增加了并行編程的復(fù)雜性，嚴(yán)重阻礙了并行程序的發(fā)展。
　　 共享內(nèi)存并行編程中的不確定性大多數(shù)是由于編程模型的不確定性導(dǎo)致的，為此本文探索一個確定性共享內(nèi)存編程模型，目標(biāo)是在保證確定性的同時保持較好的性能。本文探討并完成了以下工作：
　　 1、設(shè)計了一個確定性的

2、共享內(nèi)存編程模型—DetSM。
　　 本文首先以dedup為例分析、總結(jié)共享內(nèi)存并行編程中共享資源的訪問模式。然后根據(jù)總結(jié)的訪問模式，本文提出了一個確定性共享內(nèi)存并行編程模型——DetSM（deterministic shared memory programming model）。DetSM提供了一個特殊的抽象數(shù)據(jù)結(jié)構(gòu)——SMU(Shared Memorv Unit)，用于進(jìn)程間通信。SMU的特點是：多期和權(quán)限傳遞。一個SMU

3、的生命期可以分為多個期——periods，為了保證確定性，每個期最多只能有一個寫者。當(dāng)某個SMU的一個期結(jié)束以后，該SMU的寫權(quán)限就可以被傳遞給下一個期的寫者進(jìn)程。
　　 2、在SMU上拓展了一個確定性的并行數(shù)組數(shù)據(jù)結(jié)構(gòu)DetArray。
　　 為了支持這種數(shù)組訪問模式——不同進(jìn)程能夠并行地訪問數(shù)組的不相交部分，筆者對SMU進(jìn)行了拓展，提出了一種適合于這種特殊應(yīng)用的數(shù)組類型DetArray（deterministic a

4、rray data structure）。DetArray的特點是：可以被確定性地并行操作。DetArray在物理內(nèi)存上不一定連續(xù)，不能用邏輯索引來計算其物理地址。一個DetArray可以被分為多個部分(sections)，每個部分都有自己的讀者和寫者。不同寫者進(jìn)程可以并行地操作一個DetArray的不同部分。
　　 3、在Determinator上對DetSM和DetArray進(jìn)行了實現(xiàn)和實驗測試。
　　 筆者在Det

5、erminator上利用SPMC（single-producer multiple-consumer）虛擬內(nèi)存基礎(chǔ)實現(xiàn)了DetSM和DetArray，然后用DetSM重寫了dedup，用DetArray改寫了歸并排序。dedup的實驗結(jié)果表明：在較大輸入集上，DetSM的性能和Pthreads相當(dāng)，甚至好于Pthreads。DetArray的例子表明：DetArray不僅能為并行編程提供方便，而且還具有較好的性能，它具有非常好的可擴(kuò)展性