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

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

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

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

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

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

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