【摘要】：低密度奇偶校驗(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ù)集上進(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ì)上述問題分別提出解決方法,并將這些方法應(yīng)用到LDPC譯碼和鞏膜識(shí)別的GPU并行計(jì)算中。本文的主要貢獻(xiàn)有:1.在GPU并行算法分析方面,針對(duì)GPU部件(CUDA core,SFU和LD/ST)間并行、部件內(nèi)采用流水線的工作方式,通過源碼分析,利用DAG圖化簡隱藏并行指令,設(shè)計(jì)了多部件流水線的基本分析模型。采用就緒Warp數(shù)、合并存取、同步、程序分支等九個(gè)因子對(duì)基本模型進(jìn)行校準(zhǔn),使分析模型既能夠量化反映硬件約束,又能夠充分體現(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)滿足兩個(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)用不同的組塊映射模型,使鞏膜匹配計(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ù)表示更新信息時(shí)產(chǎn)生的量化錯(cuò)誤。以上模型和方法應(yīng)用到鞏膜匹配和LDPC譯碼后,鞏膜匹配速度由每秒匹配2個(gè)提高到每秒匹配1,083個(gè),使得鞏膜識(shí)別這一新技術(shù)的實(shí)時(shí)應(yīng)用成為了可能�；贕PU的LDPC譯碼器吞吐率達(dá)到了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.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2014
【分類號(hào)】：TN911.22

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

2 許文源;王振宇;朱修祥;;序貫譯碼——在電子計(jì)算機(jī)上的模擬實(shí)驗(yàn)結(jié)果[J];計(jì)算機(jī)與網(wǎng)絡(luò);1976年04期

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

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

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

6 李慶坤;馬洪光;李正生;王鵬毅;;基于裁減自動(dòng)球形算法的多符號(hào)差分空時(shí)譯碼[J];計(jì)算機(jī)仿真;2010年03期

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

8 賈文祥;周月臣;酆廣增;;傳真文件的計(jì)算機(jī)譯碼[J];南京郵電學(xué)院學(xué)報(bào);1991年04期

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

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

相關(guān)會(huì)議論文 前6條

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

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

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

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

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

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

相關(guān)博士學(xué)位論文 前9條

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

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

3 周偉;低密度奇偶校驗(yàn)碼譯碼研究及其應(yīng)用[D];北京郵電大學(xué);2007年

4 李暉;級(jí)連碼譯碼研究[D];西安電子科技大學(xué);1998年

5 雷菁;低復(fù)雜度LDPC碼構(gòu)造及譯碼研究[D];國防科學(xué)技術(shù)大學(xué);2009年

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

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

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

9 李璐穎;無線通信中噴泉碼應(yīng)用關(guān)鍵技術(shù)研究[D];北京郵電大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

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

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

3 朱志風(fēng);噴泉碼及其在高鐵通信中的應(yīng)用[D];蘇州大學(xué);2015年

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

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

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

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

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

9 張浩;合并譯碼結(jié)構(gòu)及應(yīng)用研究[D];西安電子科技大學(xué);2012年

10 陳誠;基于圖像知識(shí)的預(yù)測譯碼結(jié)構(gòu)研究[D];西安電子科技大學(xué);2013年

，

本文編號(hào)：2233171