基于GPU的并行巩膜识别与LDPC译码研究

发布时间：2018-09-09 18:10

【摘要】：低密度奇偶校验码(Low Density Parity Check,LDPC)的纠错性能能够达到Shannon极限,但其译码算法计算量大,计算时间长。巩膜识别是新兴的生物识别技术,在可见光条件下的识别性能优于虹膜识别,但因其匹配算法计算密度大、耗时长,从而难以应用在实时环境中。LDPC译码和巩膜匹配都属于多数据集上的非规则问题(Irregular Problem on Massive Datasets,IPMD),这类问题需要在不同数据集上进行重复计算,且同一数据集内待处理数据元素的索引与循环变量不具有线性关系。采用GPU(Graphics Processing Unit)能够加速IPMD计算,但在算法设计中也面临着一些挑战,这些挑战主要来自三个方面:首先,由于数据空间局部性较差,数据集内难以划分为独立子块;其次,子任务及其组合到GPU计算资源之间不易找到最优映射;第三,数据访问地址不规则导致无法进行合并存取。本文在研究GPU并行算法分析模型的基础上,针对上述问题分别提出解决方法,并将这些方法应用到LDPC译码和巩膜识别的GPU并行计算中。本文的主要贡献有:1.在GPU并行算法分析方面,针对GPU部件(CUDA core,SFU和LD/ST)间并行、部件内采用流水线的工作方式,通过源码分析,利用DAG图化简隐藏并行指令,设计了多部件流水线的基本分析模型。采用就绪Warp数、合并存取、同步、程序分支等九个因子对基本模型进行校准,使分析模型既能够量化反映硬件约束,又能够充分体现GPU内兼有指令并行和Warp并行的特性。应用所设计的分析模型,对LDPC译码的三种算法进行了分析,得出SPA算法在GPU译码中性能最优的结论。2.在IPMD并行算法设计方面,提出了多级并行的算法设计方法,该方法的内容主要包括:多数据集上的计算并发执行;同一数据集中的计算限定在一个Block内;采用同步指令对计算任务进行分块;在任务块内进行子任务划分和循环边界确定。分析指出能够采用多级并行的IPMD问题应满足两个条件:多数据集应能保存在外存储器中;单个数据集上的计算时间要足够小。结合巩膜匹配算法,研究了使IPMD满足这两个条件的方法,即设计Y描述符以减少计算量,设计WPL描述符以降低存储空间占用。3.在任务组块和映射方面,针对不同的GPU任务需求,设计了三种GPU并行任务组块和映射模型:任务均衡模型、可同步模型以及合并存取模型,分析了这三种基本模型及其变形的映射方法和适用条件。将这些模型应用到巩膜匹配的四个阶段,通过在每个阶段应用不同的组块映射模型,使巩膜匹配计算全过程达到了任务均衡,并使访存和同步开销降到了最低。4.在提高IPMD访存速度方面,提出了加速全局存储器访问的方法:一是用较少的信息位量化编码原有信息,实现数据压缩;二是通过多组数据并行实现合并存取。其中合并存取的实现主要通过映射一组大小与Warp相等的数据集到同一Warp,从而使Warp内原本无序或随机的访问地址能够被有序访问。设计了校验似然比的LDPC译码算法中,降低了8位定点数表示更新信息时产生的量化错误。以上模型和方法应用到巩膜匹配和LDPC译码后,巩膜匹配速度由每秒匹配2个提高到每秒匹配1,083个,使得巩膜识别这一新技术的实时应用成为了可能。基于GPU的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

【相似文献】