摘要: 低密度奇偶校验码（LDPC，Low-Density Parity-Check）是被当今的通信标准所采用的非常有效的纠错码。LDPC解码器基于置信传播（belief propagation）算法实现，该算法中使用了Tanner图和非常密集的消息传递计算。并且该类解码器的实现通常需要采用基于硬件的专门的解决方案。随着图形处理单元（GPU，graphics processing unit）计算能力的指数级增长，在GPU上开发通用计算应用已为解决上述问题带来了新的机遇。
最近几年，多核体系结构已经从双核或四核发展到T级（tera-scale）系统，能支持多线程，可以采用有效的技术来掩盖访存延迟，并且能提供更强大的单指令流多数据流（SIMD，Single Instruction Multiple Data）的向量处理能力。通过在基于流的模型（stream-based model）下编写程序，当前的GPU作为多核架构也可以用于通用处理（GPGPU，general purpose processing），这使得商用产品也可以产生较高的计算性能。文献中所包含的GPGPU相关应用包括i）数值计算，如稠密矩阵和稀疏矩阵乘法，ii）计算机图形算法，如光线跟踪方面的算法，iii）运用于物理学方面的仿真，如流体力学求解器，及iv）数据库和数据挖掘操作。
在程序设计级别，目前已经实现了对C语言的扩展，降低了在GPU上编写通用计算程序的难度。这种扩展支持数据并行结构，并能使GPU作为流协处理器使用。尽管如此，要将GPU用于通用处理，还需要对GPU的操作进行管理和控制。针对GPGPU所开发的编程工具和开发环境有，由NVIDIA开发的CUDA（Compute Unified Device Architecture），及Caravela平台。虽然CUDA是提高GPU编程效率的一种有效的特定解决方案，但是它仅支持基于Tesla的NVIDIA GPU。而Caravela工具则是一种通用的编程接口，它基于基于流的计算模型，可以将任何GPU作为协处理器使用。Caravela不直接与GPU硬件进行交互，而是通过与GPU驱动进行通信，使自身成为一个能够独立于操作系统和GPU生产厂商的通用并且强大的编程接口工具。实现Caravela的主要目的是为了支持在GPU上进行并行算法的开发和测试，而不是在性能方面与商用并经过优化的编程工具，比如CUDA，进行竞争。
本文基于计算密集的和积译码算法（SPA, Sum-Product Algorithm）提出一种新的方法，用于实现基于流的LDPC解码。该方法通过基于流的计算模型来发掘LDPC解码中的数据并行性。基于该方法，本文开发了一种在GPU上进行LDPC解码的高效并行算法，并采用Caravela编程接口和工具实现了该算法。在这种新的基于流的方法中，提出了采用压缩数据结构的方法来表示Tanner图。可以看出，由于拥有非规则的访存模式、存储带宽和递归流控制的限制，这样一种面向流计算的，具有挑战性的应用能够在GPU上得到高效的实现。本文采用Caravela平台——一种不受限于GPU厂商和操作系统，用于管理内核执行的通用接口工具，通过在GPU上编程实现LDPC解码器，对上面提出的方法进行了实验评估。而且，为了对所得到的结果进行相对评估，本文还在通用处理器上采用流SIMD扩展（Streaming SIMD Extension）指令实现了LDPC解码器。
本文首次在GPU上实现了一种高效的并行LDPC解码器，文章的主要的贡献是：i）开发了一种用于LDPC解码的新的数据结构，该数据结构能支持基于流的计算；这种新方法采用了不同的压缩数据结构，这些数据结构来自传统的压缩行存储格式和压缩列存储格式。凭借该数据结构，Tanner图中节点间的连接关系可以通过循环寻址的方式来表示，以满足SPA处理中所需的对不同数据单元的循环访问；ii) 介绍了多码字解码（GPU的并行体系结构允许同时对多个码字进行解码）概念；iii) 提出一种体系结构，该结构描述了一种可编程的解决方案。这种解决方案有别于采用VLSI的专用LDPC解码器（新的趋势表明，处理器核心数量不断增加，其计算性能在后续若干年中也将得到提高）；iv) 使用了只有32位数据精度（单精度）的浮点计算。基于VLSI的解决方案所能达到的最高水平是5-6位的数据精度。与其相比，本文的方法能产生更低的位错误率（BER, Bit Error Rate）。
实验结果表明，本文提出的算法在GPU上的运行速度远远快于在现代通用处理器上的运行速度。本文开发了一种高效的解决方案，用于将LDPC解码器在CPU上的执行情况和在GPU上通过同时解码多个码字以发挥基于流的体系结构的并行性的新方法进行比较。报告结果表明，本文提出的解决方案可以同时高效解码多个码字，将处理时间降低一个数量级。