【摘要】：低密度奇偶校驗碼(Low Density Parity Check,LDPC)的糾錯性能能夠達到Shannon極限,但其譯碼算法計算量大,計算時間長。鞏膜識別是新興的生物識別技術,在可見光條件下的識別性能優(yōu)于虹膜識別,但因其匹配算法計算密度大、耗時長,從而難以應用在實時環(huán)境中。LDPC譯碼和鞏膜匹配都屬于多數(shù)據(jù)集上的非規(guī)則問題(Irregular Problem on Massive Datasets,IPMD),這類問題需要在不同數(shù)據(jù)集上進行重復計算,且同一數(shù)據(jù)集內待處理數(shù)據(jù)元素的索引與循環(huán)變量不具有線性關系。采用GPU(Graphics Processing Unit)能夠加速IPMD計算,但在算法設計中也面臨著一些挑戰(zhàn),這些挑戰(zhàn)主要來自三個方面:首先,由于數(shù)據(jù)空間局部性較差,數(shù)據(jù)集內難以劃分為獨立子塊;其次,子任務及其組合到GPU計算資源之間不易找到最優(yōu)映射;第三,數(shù)據(jù)訪問地址不規(guī)則導致無法進行合并存取。本文在研究GPU并行算法分析模型的基礎上,針對上述問題分別提出解決方法,并將這些方法應用到LDPC譯碼和鞏膜識別的GPU并行計算中。本文的主要貢獻有:1.在GPU并行算法分析方面,針對GPU部件(CUDA core,SFU和LD/ST)間并行、部件內采用流水線的工作方式,通過源碼分析,利用DAG圖化簡隱藏并行指令,設計了多部件流水線的基本分析模型。采用就緒Warp數(shù)、合并存取、同步、程序分支等九個因子對基本模型進行校準,使分析模型既能夠量化反映硬件約束,又能夠充分體現(xiàn)GPU內兼有指令并行和Warp并行的特性。應用所設計的分析模型,對LDPC譯碼的三種算法進行了分析,得出SPA算法在GPU譯碼中性能最優(yōu)的結論。2.在IPMD并行算法設計方面,提出了多級并行的算法設計方法,該方法的內容主要包括:多數(shù)據(jù)集上的計算并發(fā)執(zhí)行;同一數(shù)據(jù)集中的計算限定在一個Block內;采用同步指令對計算任務進行分塊;在任務塊內進行子任務劃分和循環(huán)邊界確定。分析指出能夠采用多級并行的IPMD問題應滿足兩個條件:多數(shù)據(jù)集應能保存在外存儲器中;單個數(shù)據(jù)集上的計算時間要足夠小。結合鞏膜匹配算法,研究了使IPMD滿足這兩個條件的方法,即設計Y描述符以減少計算量,設計WPL描述符以降低存儲空間占用。3.在任務組塊和映射方面,針對不同的GPU任務需求,設計了三種GPU并行任務組塊和映射模型:任務均衡模型、可同步模型以及合并存取模型,分析了這三種基本模型及其變形的映射方法和適用條件。將這些模型應用到鞏膜匹配的四個階段,通過在每個階段應用不同的組塊映射模型,使鞏膜匹配計算全過程達到了任務均衡,并使訪存和同步開銷降到了最低。4.在提高IPMD訪存速度方面,提出了加速全局存儲器訪問的方法:一是用較少的信息位量化編碼原有信息,實現(xiàn)數(shù)據(jù)壓縮;二是通過多組數(shù)據(jù)并行實現(xiàn)合并存取。其中合并存取的實現(xiàn)主要通過映射一組大小與Warp相等的數(shù)據(jù)集到同一Warp,從而使Warp內原本無序或隨機的訪問地址能夠被有序訪問。設計了校驗似然比的LDPC譯碼算法中,降低了8位定點數(shù)表示更新信息時產(chǎn)生的量化錯誤。以上模型和方法應用到鞏膜匹配和LDPC譯碼后,鞏膜匹配速度由每秒匹配2個提高到每秒匹配1,083個,使得鞏膜識別這一新技術的實時應用成為了可能�；贕PU的LDPC譯碼器吞吐率達到了550Mbps,是目前單塊GPU上譯碼速度最快的LDPC譯碼器。
[Abstract]:Low Density Parity Check (LDPC) can achieve Shannon limit in error correction performance, but its decoding algorithm is computationally expensive and time-consuming. LDPC decoding and sclera matching are irregular problems on multiple datasets (IPMD), which require repeated calculations on different datasets, and the index of data elements to be processed in the same dataset does not have a linear relationship with cyclic variables. Phics Processing Unit (IPMD) can speed up IPMD computing, but it also faces some challenges in algorithm design. These challenges mainly come from three aspects: first, it is difficult to divide the data set into independent sub-blocks because of the poor locality of data space; second, it is difficult to find the optimal mapping between sub-tasks and their combination to GPU computing resources; third, data. Based on the research of GPU parallel algorithm analysis model, this paper proposes solutions to these problems and applies these methods to the parallel computation of LDPC decoding and scleral recognition. The main contributions of this paper are as follows: 1. In the analysis of GPU parallel algorithm, the GPU components (C) UDA core, SFU and LD/ST are parallel, and pipeline is used in components. Through source code analysis, hidden parallel instructions are simplified and hidden by DAG graph, the basic analysis model of multi-component pipeline is designed. The analysis model is applied to analyze the three algorithms of LDPC decoding, and the conclusion that SPA algorithm has the best performance in GPU decoding is drawn. 2. In the aspect of IPMD parallel algorithm design, a multi-level parallel algorithm design method is proposed. The main contents of the method include: concurrent execution of computations on multiple datasets; limited computations within a block in the same dataset; partitioning computational tasks by using synchronous instructions; partitioning sub-tasks and determining cyclic boundaries within the task block. The data set should be stored in external memory, and the computation time on a single data set should be small enough. Combining with scleral matching algorithm, this paper studies the methods to satisfy the two conditions of IPMD, that is, designing Y descriptors to reduce computation, and designing WPL descriptors to reduce storage space occupation. 3. In terms of task block and mapping, different GPU tasks are required. Three GPU parallel task block and mapping models are designed: task balancing model, synchronizable model and merging access model. The mapping methods and applicable conditions of these three basic models and their variants are analyzed. These models are applied to four stages of scleral matching, and different block mapping models are applied in each stage. The whole process of scleral matching computation achieves task balance and minimizes the memory access and synchronization overhead. 4. In order to improve the speed of IPMD memory access, a method of accelerating global memory access is proposed. Firstly, the original information is encoded with fewer information bits to realize data compression, and secondly, multiple sets of data are paralleled to achieve merger access. By mapping a set of data sets with the same size as Warp to the same Warp, the original disordered or random access addresses in Warp can be accessed orderly. A LDPC decoding algorithm for checking likelihood ratio is designed to reduce the quantization error of 8-bit fixed-point representation updating information. When applied to scleral matching and LDPC decoding, the speed of scleral matching is increased from 2 matches per second to 1,083 matches per second, which makes the real-time application of scleral recognition possible.
【學位授予單位】：西安電子科技大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：TN911.22

【相似文獻】

相關期刊論文 前10條

1 孫永軍;蘇昕;易克初;;一種基于球形譯碼的分層空時譯碼算法[J];電路與系統(tǒng)學報;2008年05期

2 許文源;王振宇;朱修祥;;序貫譯碼——在電子計算機上的模擬實驗結果[J];計算機與網(wǎng)絡;1976年04期

3 賈文祥,酆廣增,周月臣;傳真文件的計算機譯碼[J];電信科學;1991年05期

4 石雅盟;李建平;;一種新的聯(lián)合譯碼方案研究[J];中國傳媒大學學報(自然科學版);2013年06期

5 朱宏杰;裴玉奎;陸建華;;一種提高噴泉碼譯碼成功率的算法[J];清華大學學報(自然科學版);2010年04期

6 李慶坤;馬洪光;李正生;王鵬毅;;基于裁減自動球形算法的多符號差分空時譯碼[J];計算機仿真;2010年03期

7 陳仲津;周振虞;;二輸入端多址信道的線性δ-可譯碼[J];南京郵電學院學報;1986年03期

8 賈文祥;周月臣;酆廣增;;傳真文件的計算機譯碼[J];南京郵電學院學報;1991年04期

9 許成謙,林雪紅,陳嘉興;一種加速Turbo碼譯碼實現(xiàn)的改進算法的研究[J];電子學報;2002年08期

10 單永杰;韓家瑋;張洪群;李安;;衛(wèi)星數(shù)據(jù)組合譯碼技術研究與實現(xiàn)[J];微計算機信息;2011年04期

相關會議論文 前6條

1 王名俅;夏樹濤;;LDPC碼的快速量化譯碼[A];中國電子學會第十六屆信息論學術年會論文集[C];2009年

2 于越華;;低誤碼率BCH碼的譯碼糾錯及應用[A];圖像 仿真 信息技術——第二屆聯(lián)合學術會議論文集[C];2002年

3 李云強;王念平;余昭平;;基于遺傳算法的R-M碼快速譯碼[A];開創(chuàng)新世紀的通信技術——第七屆全國青年通信學術會議論文集[C];2001年

4 鞏克現(xiàn);劉世剛;葛臨東;;DVB-RCS中循環(huán)遞歸Turbo碼尾比特譯碼技術[A];2009年通信理論與信號處理學術年會論文集[C];2009年

5 陳卓峰;劉星成;;基于RBF神經(jīng)網(wǎng)絡技術的分組Turbo碼譯碼[A];2005通信理論與技術新進展——第十屆全國青年通信學術會議論文集[C];2005年

6 周丹丹;鄒艷;陸佩忠;;多個可變長信源的聯(lián)合信源—信道卷積碼譯碼[A];2006北京地區(qū)高校研究生學術交流會——通信與信息技術會議論文集（上）[C];2006年

相關博士學位論文 前9條

1 陳正康;LDPC譯碼關鍵技術研究[D];西北工業(yè)大學;2015年

2 藺勇;基于GPU的并行鞏膜識別與LDPC譯碼研究[D];西安電子科技大學;2014年

3 周偉;低密度奇偶校驗碼譯碼研究及其應用[D];北京郵電大學;2007年

4 李暉;級連碼譯碼研究[D];西安電子科技大學;1998年

5 雷菁;低復雜度LDPC碼構造及譯碼研究[D];國防科學技術大學;2009年

6 Nguyen Thi Dieu Linh（阮氏妙玲）;基于和-積算法的LDPC譯碼改進及性能分析[D];哈爾濱工業(yè)大學;2013年

7 楊洋;LDPC碼的編譯碼及代數(shù)構造研究[D];西安電子科技大學;2012年

8 王曉松;下一代無線通信系統(tǒng)中調制與編碼關鍵技術研究[D];東北大學;2009年

9 李璐穎;無線通信中噴泉碼應用關鍵技術研究[D];北京郵電大學;2011年

相關碩士學位論文 前10條

1 郭米娜;Raptor碼編譯碼技術及其在LTE下行鏈路中的仿真研究[D];西南交通大學;2015年

2 李青;BICM-ID性能仿真研究及其定點數(shù)譯碼的實現(xiàn)[D];西南交通大學;2015年

3 朱志風;噴泉碼及其在高鐵通信中的應用[D];蘇州大學;2015年

4 鄧波;基于概率計算的超高速全并行Turbo碼譯碼芯片ASIC實現(xiàn)[D];電子科技大學;2015年

5 郭藝峰;基于LDPC碼的BP譯碼改進算法研究[D];西安電子科技大學;2014年

6 趙雯;基于Turbo同步的聯(lián)合解調譯碼技術研究[D];西安電子科技大學;2014年

7 張洋;基于GPU的Turbo譯碼實現(xiàn)技術的研究[D];國防科學技術大學;2013年

8 王莉;飛行器遙測MSD和TPC技術研究與實現(xiàn)[D];國防科學技術大學;2013年

9 張浩;合并譯碼結構及應用研究[D];西安電子科技大學;2012年

10 陳誠;基于圖像知識的預測譯碼結構研究[D];西安電子科技大學;2013年

，

本文編號：2233171