基于GPU的并行鞏膜識別與LDPC譯碼研究.pdf

1、低密度奇偶校驗(yàn)碼(Low Density Parity Check，LDPC)的糾錯性能能夠達(dá)到Shannon極限，但其譯碼算法計算量大，計算時間長。鞏膜識別是新興的生物識別技術(shù)，在可見光條件下的識別性能優(yōu)于虹膜識別，但因其匹配算法計算密度大、耗時長，從而難以應(yīng)用在實(shí)時環(huán)境中。LDPC譯碼和鞏膜匹配都屬于多數(shù)據(jù)集上的非規(guī)則問題（Irregular Problem on Massive Datasets，IPMD），這類問題需要在不同數(shù)據(jù)

2、集上進(jìn)行重復(fù)計算，且同一數(shù)據(jù)集內(nèi)待處理數(shù)據(jù)元素的索引與循環(huán)變量不具有線性關(guān)系。
　　采用GPU（Graphics Processing Unit）能夠加速IPMD計算，但在算法設(shè)計中也面臨著一些挑戰(zhàn)，這些挑戰(zhàn)主要來自三個方面：首先，由于數(shù)據(jù)空間局部性較差，數(shù)據(jù)集內(nèi)難以劃分為獨(dú)立子塊；其次，子任務(wù)及其組合到GPU計算資源之間不易找到最優(yōu)映射；第三，數(shù)據(jù)訪問地址不規(guī)則導(dǎo)致無法進(jìn)行合并存取。本文在研究GPU并行算法分析模型的基礎(chǔ)上，針對

3、上述問題分別提出解決方法，并將這些方法應(yīng)用到LDPC譯碼和鞏膜識別的GPU并行計算中。
　　本文的主要貢獻(xiàn)有：
　　1．在GPU并行算法分析方面，針對GPU部件（CUDA cor e，SFU和LD/S T）間并行、部件內(nèi)采用流水線的工作方式，通過源碼分析，利用DAG圖化簡隱藏并行指令，設(shè)計了多部件流水線的基本分析模型。采用就緒Warp數(shù)、合并存取、同步、程序分支等九個因子對基本模型進(jìn)行校準(zhǔn)，使分析模型既能夠量化反映硬件約束，

4、又能夠充分體現(xiàn)GPU內(nèi)兼有指令并行和Warp并行的特性。應(yīng)用所設(shè)計的分析模型，對LDPC譯碼的三種算法進(jìn)行了分析，得出SPA算法在GPU譯碼中性能最優(yōu)的結(jié)論。
　　2．在IPMD并行算法設(shè)計方面，提出了多級并行的算法設(shè)計方法，該方法的內(nèi)容主要包括：多數(shù)據(jù)集上的計算并發(fā)執(zhí)行；同一數(shù)據(jù)集中的計算限定在一個Block內(nèi)；采用同步指令對計算任務(wù)進(jìn)行分塊；在任務(wù)塊內(nèi)進(jìn)行子任務(wù)劃分和循環(huán)邊界確定。分析指出能夠采用多級并行的IPMD問題應(yīng)滿足兩

5、個條件：多數(shù)據(jù)集應(yīng)能保存在外存儲器中；單個數(shù)據(jù)集上的計算時間要足夠小。結(jié)合鞏膜匹配算法，研究了使IPMD滿足這兩個條件的方法，即設(shè)計Y描述符以減少計算量，設(shè)計WPL描述符以降低存儲空間占用。
　　3．在任務(wù)組塊和映射方面，針對不同的GPU任務(wù)需求，設(shè)計了三種GPU并行任務(wù)組塊和映射模型：任務(wù)均衡模型、可同步模型以及合并存取模型，分析了這三種基本模型及其變形的映射方法和適用條件。將這些模型應(yīng)用到鞏膜匹配的四個階段，通過在每個階段應(yīng)用

6、不同的組塊映射模型，使鞏膜匹配計算全過程達(dá)到了任務(wù)均衡，并使訪存和同步開銷降到了最低。
　　4．在提高IPMD訪存速度方面，提出了加速全局存儲器訪問的方法：一是用較少的信息位量化編碼原有信息，實(shí)現(xiàn)數(shù)據(jù)壓縮；二是通過多組數(shù)據(jù)并行實(shí)現(xiàn)合并存取。其中合并存取的實(shí)現(xiàn)主要通過映射一組大小與Warp相等的數(shù)據(jù)集到同一Warp，從而使Warp內(nèi)原本無序或隨機(jī)的訪問地址能夠被有序訪問。設(shè)計了校驗(yàn)似然比的LDPC譯碼算法中，降低了8位定點(diǎn)數(shù)表示更新