论文部分内容阅读
低密度奇偶校验码(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译码器。