面向多核的串行程序并行化關(guān)鍵技術(shù)研究.pdf

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

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

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

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

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

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