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

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

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

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

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

5、線程級(jí)推測(cè)技術(shù)的軟件嵌套事務(wù)存儲(chǔ)系統(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)行版本管理，采用支持線程級(jí)推測(cè)的嵌套事務(wù)沖突檢測(cè)策略實(shí)現(xiàn)沖突檢測(cè)，采用RBDP策略實(shí)現(xiàn)沖突消解，采

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