论文部分内容阅读
在计算机技术与数字通信技术突飞猛进的今天,如何保证通信技术的可靠性变得日益重要。针对这一问题,纠错编码技术应运而生。Shannon在1948年提出的有扰信道编码理论,奠定了纠错编码的基石。在纠错编码领域,Gallager于1962年发现了低密度奇偶校验码(Low Density Parity-Check,LDPC),该码以其优异的性能,在数字通信系统中扮演着重要的角色。如何提高LDPC码译码器的吞吐量也就成为了研究的重点。LDPC码的和积译码算法中,同一类节点更新时可以互不干扰,基于这一特点可使用可并行处理的芯片——现场可编程门阵列(Field Programmable Gate Array,FPGA)和可编程芯片图形处理器(Graphic Processing Unit,GPU)设计LDPC码译码器。与FPGA相比,GPU译码器的灵活性和扩展性都更好。尤其随着统一计算架构平台——CUDA(Compute Unified Device Architecture)的推出,GPU编程变得更加简单、方便。本文主要根据LDPC码的译码算法设计了基于GPU的并行译码方案和根据GPU并行特点设计了多码字并行译码器。工作内容主要包括以下几方面:(a)针对LDPC码的译码算法,提出了一种基于GPU的边并行译码算法方案。在此方案中,每个线程处理Tanner图中每条边要传递的信息,并将译码时间与节点并行译码时间进行对比;(b)针对(a)中提出的方案进行了进一步的优化,优化内容包括:通过片上缓存将校验节点和变量节点的更新过程合并为一个kernel函数;使用双流处理译码过程;采用交互算法减少校验矩阵行列重较大码字的计算量;(c)由于准循环低密度奇偶校验(Quasi-Cyclic LDPC,QC-LDPC)码在分层译码算法(Turbo Decoding Message Passing,TDMP)中单个码字的并行加速效果微弱,本文在此基础上采用多码字并行译码方案,并优化外信息存储方式,实现高效利用全局内存空间和高速访问全局内存上的信息;(d)为了实现伪随机LDPC码的多码字并行译码,本文提出了针对伪随机LDPC码的多码字多线程译码方案,在该方案中,每个线程处理一个码字,并优化信息存储方式,使相邻的线程访问的信息可以连续存储和访问,通过实现该方案,GPU一次可并行处理数千个乃至上万个LDPC码字。本文对提出的优化方案都进行了实验仿真:使用边并行译码方案,与CPU相比,获得了73.40~130.47倍的加速效果;合并kernel函数方案,获得了106.91~209.69倍的加速效果;采用双流异步并行,最终实现了135.42~257.42倍的加速效果;而对于高列重的码字采用交互方案后,码字的译码速度相对于未优化的GPU程序提升了371ms和1119ms,相对于CPU,译码速度加速了101.87~154.57倍;本文设计的针对QC-LDPC码译码和伪随机LDPC码译码方案,使基于多码字并行的译码器的译码速度有了显著的提升,与CPU译码时间相比,分别达到了48.93倍和134.58倍的加速效果。