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

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

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

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

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

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

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