面向多核的串行程序并行化關鍵技術研究.pdf

1、隨著計算機硬件的迅速發(fā)展，多核處理器已經(jīng)廣泛應用于工業(yè)設計和日常生活中。理論上增加處理器的核數(shù)，則可執(zhí)行的指令數(shù)就將有成倍的增長，但是在多核處理器上運行現(xiàn)存的大量串行程序并沒有獲得預期加速的效果，這是由于串行程序在多核處理器上并不能自動并行而獲得加速。因此如何利用多核處理器加速已有的串行程序已經(jīng)成為學術界和工業(yè)界關注的熱點研究問題。
　　事務存儲技術和線程級推測技術成為提高串行程序在多核處理器上執(zhí)行效率的關鍵技術。事務存儲技術有效

2、地解決了傳統(tǒng)并行編程模型中采用鎖和信號量機制實現(xiàn)線程間的同步/互斥以及對共享資源的訪問所帶來的死鎖、優(yōu)先級反轉(zhuǎn)等諸多問題。線程級推測技術打破了線程間依賴對線程并行執(zhí)行的限制，可以進一步挖掘程序的并行性，有效提高程序的可擴展性。
　　論文圍繞串行程序并行化技術，重點從事務存儲和線程級推測技術兩個方面展開深入研究，主要研究工作與創(chuàng)新點如下：
　　為了高效實現(xiàn)嵌套軟件事務存儲(Nested software transaction

3、al memory,NSTM)系統(tǒng)，分析研究了事務之間的沖突依賴關系，對比了積極沖突檢測/懶惰沖突檢測、讀透明/讀可見等檢測方法，提出了NSTM的語義模型、基于讀可見-懶惰沖突檢測策略的沖突檢測方法，以及基于動態(tài)優(yōu)先級的隨機退避(Random Back-off of Dynamic Priority, RBDP)機制。將RBDP沖突消解策略和常用沖突消解策略進行對比測試，RBDP沖突消解策略明顯優(yōu)于其他沖突消解策略。
　　在軟件事

4、務存儲的基礎上，提出了一種基于路徑的貪婪線程劃分算法，該算法采用亂序激發(fā)的策略實現(xiàn)函數(shù)、循環(huán)區(qū)域和非循環(huán)區(qū)域的線程劃分。同時給出了基于事務的循環(huán)調(diào)用推測執(zhí)行模型和函數(shù)調(diào)用推測執(zhí)行模型，并針對基于事務的線程推測機制中存在的線程間并行、線程內(nèi)并行和嵌套事務并行的依賴沖突提出了支持線程級推測的嵌套事務存儲系統(tǒng)的沖突檢測和消解策略，有效的降低了事務之間的沖突概率。
　　在研究線程級推測技術和現(xiàn)有事務存儲模型理論的基礎上，設計實現(xiàn)了一個支持

5、線程級推測技術的軟件嵌套事務存儲系統(tǒng)(software nested thread level speculation based on transactional memory, SNTLTM)系統(tǒng)。SNTLTM系統(tǒng)采用Swiss TM系統(tǒng)作為基系統(tǒng)并結合 SUIF2編譯器進行原型開發(fā)。SNTLTM系統(tǒng)采用Write Buffer的方法進行版本管理，采用支持線程級推測的嵌套事務沖突檢測策略實現(xiàn)沖突檢測，采用RBDP策略實現(xiàn)沖突消解，采

6、用基于路徑的貪婪線程劃分算法實現(xiàn)函數(shù)、循環(huán)和非循環(huán)區(qū)域的線程劃分。采用8線程和STAMP基準對SNTLTM系統(tǒng)進行測試，測試表明SNTLTM比Swiss TM的加速比平均提高了14.8％，事務的放棄率下降了3.9%。
　　將SNTLTM應用于基于機器視覺的機械零件檢測中，運用SNTLTM的定制優(yōu)化開發(fā)接口設計并實現(xiàn)了I-SNTLTM圖像增強預處理系統(tǒng)，該系統(tǒng)支持灰度校正、灰度變換、直方圖規(guī)定化、直方圖均衡化、均值濾波、中值濾波、梯