基于異構(gòu)體系結(jié)構(gòu)的圖像匹配算法并行設(shè)計(jì)與優(yōu)化研究.pdf

1、計(jì)算機(jī)處理器通過傳統(tǒng)的以提高主頻來提升性能的方式受到了高能耗的挑戰(zhàn)，從而使得并行處理成為處理器體系結(jié)構(gòu)發(fā)展的主流模式。受到不同應(yīng)用需求和功耗限制的驅(qū)動(dòng)，異構(gòu)并行處理器逐漸變得普及起來，其中常見的包含了多核CPU、眾核GPU、協(xié)處理器Intel Xeon Phi等。與串行處理器相比，并行處理器擁有更多的計(jì)算單元，因此它們的峰值計(jì)算能力也得到了顯著提高。
　　在實(shí)際運(yùn)用異構(gòu)計(jì)算過程中，程序員受到了來自多方面的挑戰(zhàn)：其一，隨著異構(gòu)硬件并

2、行性能的提高，系統(tǒng)各個(gè)層次的軟硬件都面臨成為瓶頸的可能，因此要取得令人滿意的高性能并不容易；其二，為了兼顧性能與能耗，硬件發(fā)展呈現(xiàn)出高度異構(gòu)的特點(diǎn)，使得軟件在不同體系結(jié)構(gòu)上的遷移變得十分困難；其三，由于多樣化的應(yīng)用需求，程序員不可避免地需要采用多種異構(gòu)硬件協(xié)同合作完成任務(wù)的方案，進(jìn)一步增加了編程的難度。基于上述原因，異構(gòu)計(jì)算呈現(xiàn)出了系統(tǒng)優(yōu)化跨層面，軟硬件強(qiáng)結(jié)合以及異構(gòu)重協(xié)同的特點(diǎn)。
　　為了更好地利用異構(gòu)硬件強(qiáng)大的計(jì)算能力，就需要

3、對(duì)現(xiàn)有的軟件，尤其是其核心算法進(jìn)行針對(duì)性的設(shè)計(jì)與優(yōu)化。本文從多個(gè)角度研究了基于異構(gòu)架構(gòu)的圖像匹配算法并行設(shè)計(jì)與優(yōu)化的一般性問題，并取得了如下的研究成果：
　　設(shè)計(jì)和實(shí)現(xiàn)了空間效率更高且適合于并行化的圖片像素匹配算法：圖片的像素匹配算法具有高時(shí)間復(fù)雜度和高空間復(fù)雜度的特點(diǎn)。本文從應(yīng)用的角度入手，著手于降低算法的空間復(fù)雜度并提高其并行性能，提出了多錨點(diǎn)像素匹配算法。和原算法相比，它的空間復(fù)雜度降低了一維，從而能夠在不同的異構(gòu)硬件上實(shí)現(xiàn)

4、。本文進(jìn)一步研究了該算法的并行優(yōu)化方法，提出了在多核CPU上的粗、細(xì)兩種粒度的并行化方式，并結(jié)合GPU的特點(diǎn)改進(jìn)了其數(shù)據(jù)結(jié)構(gòu)，取得了明顯的性能提升；
　　?總結(jié)和歸納了圖片特征匹配問題在異構(gòu)架構(gòu)上的性能瓶頸問題：特征匹配問題大量存在于機(jī)器學(xué)習(xí)、機(jī)器視覺等研究領(lǐng)域，具有廣泛的影響力。本文從系統(tǒng)分析的角度入手，測(cè)試了不同匹配算法和數(shù)據(jù)在多種異構(gòu)并行架構(gòu)上的性能，并總結(jié)和歸納了常見的性能瓶頸，如緩存利用率低、內(nèi)存訪問爭(zhēng)用及系統(tǒng)調(diào)用爭(zhēng)用等

5、。通過大量收集運(yùn)行時(shí)數(shù)據(jù)，本文詳細(xì)分析了這些瓶頸產(chǎn)生的原因，提出了分治歸并方法來對(duì)算法處理過程進(jìn)行優(yōu)化，從而規(guī)避了上述瓶頸，并取得了顯著的性能提升；
　　?設(shè)計(jì)和實(shí)現(xiàn)了可動(dòng)態(tài)調(diào)整精度的特征過濾算法：近似算法在特征匹配問題中使用非常普遍，而現(xiàn)有研究中同時(shí)考慮算法并行性和精度問題的還比較少。本文從算法精度的角度入手，結(jié)合它們?cè)诓⑿挟悩?gòu)架構(gòu)上遇到的瓶頸問題，提出了具有通用性的特征過濾算法，可以明顯降低匹配過程中的計(jì)算量和內(nèi)存訪問次數(shù)。同

6、時(shí)，本文設(shè)計(jì)了動(dòng)態(tài)調(diào)整過濾精度的方法以適應(yīng)不同的數(shù)據(jù)分布，從而取得了性能與精度之間的平衡；
　　?設(shè)計(jì)和實(shí)現(xiàn)了基于眾核GPU的高效k-selection選擇算法：研究發(fā)現(xiàn)k-selection選擇算法是特征匹配問題在GPU上實(shí)現(xiàn)時(shí)消耗最多計(jì)算時(shí)間的部分。對(duì)此，本文從算法優(yōu)化的角度入手，針對(duì)GPU架構(gòu)的特點(diǎn)和算法的內(nèi)在特性，設(shè)計(jì)了全新的選擇算法。該算法使用了新的歸并排序隊(duì)列、帶緩沖區(qū)的搜索技術(shù)以及多層劃分技術(shù)，能夠有效提高其在GPU