摘要
提出了一种基于图形处理单元（graphic processing unit，GPU）的5G软件无线电准循环低密度奇偶校验（low density parity check, LDPC）码译码器，为了节省片上和片下带宽，采用码字缩短和打孔技术、两级量化和数据打包方案，以提升数据带宽的利用率。实验基于Nvidia RTX 2080Ti GPU平台实现了高码率情况下的最小和近似译码算法的并行译码，通过分析GPU上的最优线程设置，将码率为5/6的（2080，1760） LDPC算法的译码吞吐率提升至1.38 Gbit/s，译码吞吐率性能优于现有其他基于GPU的LDPC译码器。
Abstract
A GPU(graphic processing unit) based 5G software radio quasi cyclic LDPC (low-density parity check) code decoder was proposed. In order to save on chip and off chip bandwidth, code word shortening and punching techniques, two-stage quantization, and data packaging schemes were adopted to improve the utilization of data bandwidth. The experiment was based on the Nvidia RTX 2080Ti GPU platform to achieve parallel decoding of minimum and approximate decoding algorithms under high bit rates. By analyzing the optimal thread settings on the GPU, the decoding throughput of the 5/6 (2080, 1760) LDPC algorithm is improved to 1.38 Gbit/s, and the decoding throughput performance is better than other GPU based LDPC decoders.
Keywords
低密度奇偶校验（low density parity check，LDPC）码[1]是一类前向纠错（forward error correction， FEC）码。LDPC码由于接近最佳性能，已经被WiFi、DVB-S2和WiMAX等通信系统所采用。LDPC码也被纳入5G标准，成为第五代新无线电的信道编码方案。目前，高吞吐率的LDPC译码器取得了一定的进展 [2–5]，但基于5G无线电的LDPC译码器工作目前并不多。首先，按照第三代合作伙伴计划（3rd generation partnership project， 3GPP）交付的标准描述，5G无线系统的速度将达到20 Gbit/s[6]。编码和译码的吞吐率必须足够高，才能满足高速数据传输的需求。因此，LDPC译码器需要提高译码吞吐率。在应用5G无线电时，需要更高吞吐率的LDPC译码器来实现高速信号传输。其次，5G新型无线电（new radio，NR）标准要求支持更广泛的码率和码长，利用一些新的结构特点，如码型设计和译码技术来实现更好的性能。
基于专用硬件平台（如ASIC和FPGA）的译码吞吐率可以非常高[7-11]。传统FPGA方案可以采用脉动阵列等方式来实现流水并行，提高译码吞吐率，降低译码延迟。同时其功耗较低，被广泛用于各种无线通信系统中。目前，图形处理单元（graphic processing unit， GPU）由于其强大的并行计算能力和灵活的编程形式，被广泛应用于各种科学计算、智能计算中。基于GPU的无线通信译码器也不断涌现，其吞吐率较高，甚至在某些情况下可以超越FGPA[12]。GPU译码器的优势之一是良好的灵活性，利用基于GPU的译码器，可以通过软件实现多标准、多模式的通信系统。基于GPU的译码器可以轻松实现对LDPC译码的不同码率和码长的支持，从而可以快速实现软件定义无线电平台。此外，开发时间短也使得基于GPU的译码器非常有吸引力。
WiFi和WiMAX系统采用准循环LDPC（quasi cyclic-LDPC， QC-LDPC）码，它是编码和译码复杂度较低的结构化LDPC码。5G无线电标准设计了新的QC-LDPC码。目前已有的基于GPU的QC-LDPC译码器都是特定码长的实现，如IEEE802.16e（2 304，1 152）的LDPC码[13]，IEEE802.11n（1 944，972）的LDPC码[13]。但是其缺少支持5G无线电所需更长码长和更高码率的高吞吐率QC-LDPC译码器。
本文提出了一种基于GPU的5G新型无线电高通量QC-LDPC译码器。为了提高译码吞吐率，利用GPU实现了并行MSA算法。在消息更新过程中的最小值和符号计算在GPU上实现了并行计算。此外，实现了对数似然比（log-likelihood ratio，LLR）和中间值的量化，以合理的性能损失来节省片上和片下带宽。同时，还利用数据打包方法来降低GPU和中央处理器（central processing unit，CPU）之间数据传输的开销。在Nvidia RTX 2080Ti上测量了不同码长和码率的吞吐率。最终实验显示，基于GPU的译码器取得了较高的吞吐率和峰值性能利用率。最后，提出了一种评估方法来计算GPU上并行译码的最优线程设置。
1 用于5G无线电的QC-LDPC码
1.1 QC-LDPC码奇偶校验矩阵
LDPC码由M×N奇偶校验矩阵（parity check matrix，PCM）H构造，其中M代表校验节点（check node，CN）的数量，N代表变量节点（variable node，VN）的数量。将K表示为信息位的长度，K=N-M。PCM中的每一行代表一个奇偶校验方程，如式（1）所示。
(1)
式中，表示模2加，c1，c2，···，ck是行中的非零位。CN和VN之间的关系也可以用Tanner图[14]来描述。Tanner图中CNi和VNj之间的边对应于PCM中的非零条目，这意味着H（ij）=1，其中，i=1，2，···，M；j=1，2，···，N。
QC-LDPC码的PCM可以根据基础矩阵Hb来构造，Hb是一个mb×nb矩阵，由Z×Z右移标识和零矩阵组成。3GPP为NR定义了两个速率兼容的基础矩阵，即BG1和BG2。BG1的目标是编码长度较大（500≤K≤8 448）、码率较高（1/3≤r≤8/9）；BG2的目标是编码长度较小（40≤K≤2 560）、码率较低（1/5≤r≤2/3）。Z是右移大小，代表右移单位矩阵的大小。3GPP对基本图使用8组右移尺度，值为Z=2j×a，其中a∈{2，3，5，7，9，11，13，15}，j∈{0，1，2，3，4，5，6，7}。表1显示了不同a和j变化情况下Z的大小变化及数值集合，Z最大为384。
表15G新型无线电协议中的右移系数
Tab.1 Right shift coefficient in 5G new radio
假设偏移值
(2)
式中，1≤ib≤mb，1≤jb≤nb。
PCM通过使用该映射对Hb进行扩充和单位矩阵的右移来得到。
(3)
其中：Is是一个Z×Z单位矩阵，经过了s次的循环右移；0是Z×Z零矩阵。H的大小为（mb×Z）×（nb×Z）。对于BG1，mb=46，nb=68，信息列数量kb=nb-mb=22。在5G新型无线电中，mb和nb可以调整以适应码率。以下步骤描述了码率r和待编码的码长W条件下QC-LDPC的PCM构造过程。
步骤1：求满足以下条件的缩短长度Ns。
(4)
式中，kb为每行的非零条目，nb为校验矩阵宽度，Ns为缩短长度，d为最大码率偏差。按照上述构造方法，目标码率可能无法完全满足要求，因此允许最终码率与目标码率有微小的偏差。
步骤2：通过消除最右边的Ns列[15]来缩短基图，缩短后基图的大小为（mb-Ns）×（nb-Ns）。
步骤3：通过选择表1中的最小Z值来确定Z，使kb×Z≥K。
步骤4：根据修改后的基图，由右移的单位矩阵和零矩阵构成PCM，如式（3）所述。
5G新型无线电LDPC码的基图如图1所示。在5G新型无线电QC-LDPC码中，为了获得所需的信息块长度和高码率，对基图进行了缩短，剔除的列是扩展奇偶校验部分。
图15G新型无线电LDPC码的基图
Fig.1Base graph of LDPC code for 5G new radio
1.2 5G NR标准QC-LDPC编码
给定H，LDPC编码的目标是求解奇偶性方程
(5)
式中，c是编码后的码字，由信息位和奇偶校验位组成。QC-LDPC的编码方法包括高斯消除法、Richardson等[16]提出的RU方法以及Nguyen等[17]提出的为5G无线电设计的高效编码方法。一旦PCM被确定，生成矩阵G可以从H中得到。
(6)
式中，u是要编码的信息位数组。在5G无线电中，编码的LDPC码字在传输前会被打孔。前2×Z位总是被打孔，而不是传输[18]。
2 QC-LDPC的译码算法
LDPC码可以采用置信传播的方法进行译码，其基本译码算法为和积算法[19]（sum-product algorithm，SPA）。SPA的近似算法是缩放最小和算法（min-sum algorithm，MSA）。由于MSA的复杂度比SPA低，所以更适合于实际实现。yj为接收值，vj为码字的第j位。对于1≤i≤M和1≤j≤N，假设变量节点VNj到校验节点CNi（VN to CN，VTC）消息为Lij，校验节点CNi到变量节点VNj（CN to VN，CTV）消息为Rij。译码过程从1迭代到M层。根据每层的Z元素行来更新R和L。l为消息矩阵的层索引，l=1，···，mb。由于Is是一个单位矩阵，每层内VNj和其他CN之间只有一个联系，为了简化计算，Llij用Llj代替。Llj的初始值为VNj的后验概率（a posteriori probability，APP）比。译码的步骤描述如下。
步骤1：初始化APP比和CTV消息。
(7)
(8)
步骤2：按层计算Llj和Rij。首先，更新来自第i行所有VN的Llj值
(9)
其次，更新Rij
(10)
式中：1≤i≤M；k∈N（i）\{j}代表CNi的VN邻居集，不包括VNj；α是比例因子。最后，更新Llj
(11)
步骤3：在计算了所有层的CN和所有1≤l≤mb和1≤j≤N的VN后，信息位由最后一层的结果决定，其中，l=mb，
(12)
最终得到译码结果v。
3 基于GPU的高吞吐率LDPC译码技术
在本节中，描述了几种用于5G新型无线电的高吞吐率译码技术。重点介绍使用BG1构建的QC-LDPC码的并行译码过程。译码算法MSA是一种分层译码算法，可以在GPU上进行并行高效译码。为了实现高吞吐率译码，有必要进一步优化译码过程。此外，高码率和大码长对GPU的内存带宽提出了挑战。一般来说，内存访问的开销会影响译码速度。在5G新型无线电中，PCM的大小显著增加，对GPU的内存资源需求也相应增加。在译码时，合理分配GPU上的资源至关重要。
3.1 压缩数据结构
H是一个稀疏矩阵。一般来说，利用压缩结构，而不是将整个PCM传输到GPU。定位H中非零项的常用方法是在译码前生成一个查找表，可以在每一行中存储非零条目的位置。然而，H中每一行的非零条目数量并不完全相同。如果大多数行中的非零条目很少，那么执行相同次数的迭代会造成时间浪费。因此，不仅要记录每行非零位的位置，还要记录非零项的数量。
将Pik表示为H中第i行中第k个非零条目的指数。因为在H中每行最多有kb个非零条目，那么1≤k≤kb。设Ci为第i行的非零条目数，则CN和VN之间的联系可由Pik和Ci决定。压缩H的结构可以节省内存空间和访问时间。而且，压缩在GPU上很容易实现。
除了压缩H外，CTV消息R也可以被压缩。如上所述，VN和CN之间的连接在译码前是已知的。如果VNj和CNi之间存在连接的话，则只需要在第i行中保存VN的消息值。R的大小可以从（mb×Z）×（nb×Z）压缩到（mb×Z）×kb。注意到R的压缩也是GPU上内存凝聚的一种优化方法。CTV消息是译码过程的中间结果。将R压缩到连续空间有助于减少GPU上线程束内的块冲突。
3.2 并行层译码
本文采用的LDPC译码算法是MSA算法，MSA算法适合在GPU上进行并行译码。PCM是使用右移单位矩阵构建的，对于H中的每个Z×Z块，所有非零条目都来自不同的列。当计算CTV和VTC消息从i×Z到（i+1）×Z层时，不存在依赖性，其中i=0，1，···，mb-1。所以可以通过固定的线程分配来实现译码计算。本文为MSA的分层译码分配Z线程。对于5G新型无线电来说，最大的Z为384，不超过GPU上每个块的最大线程数。
如上所述，Rij和Llj是由式（10）和式（11）更新的。计算的复杂度为O（d2i），其中di是第i行的非零元素数。本文采用文献[3]中提出的一种线性复杂性方法来计算的最小值；第一个步骤是全局计算，计算出第一个和第二个最小值；第二个步骤是局部计算，根据全局计算中得到的值确定的最小值。
将f，s表示为，k∈N（i）的第一个和第二个的最小值。设f和s的初始值为正最大值。在所有VN中的第一个和第二个最小值fl和sl通过式（13）~（14）计算。
(13)
(14)
那么，可以通过式（15）得到VNj的最小值。
(15)
类似地，可以得到S的全局符号位和。在全局中，通过式（16）计算Sglobal。
(16)
然后通过式（17）得到S。
(17)
因为只有负值才会影响Sglobal的符号，所以只在Lik＜0时更新Sglobal。同时，如果Lik≥0，S=Sglobal。基于此，乘法中的式（10）被式（16）~（17）所取代。这种替换减少了GPU上的计算量。
最终的并行层译码算法如算法1所示。算法的输入是由式（7）计算出的L0j、非零条目的索引矩阵P和每层的非零条目数C，L是中间LLR的向量，f和s是第一和第二最小值的向量。由于在处理（nb×Z）×Z块中的条目消息时没有依赖性，L的计算由译码器中的Z个线程并行处理，层的迭代次数为mb，开始层的迭代次数为lb。在第一次迭代中，所有VN的最小值都是0，在本文实现中，起始层为l=1，以减少译码时间。在并行译码器中，我们实现了两相法，简化了寻找最小值和符号乘积的过程。该方法消除了嵌套循环，大大提高了译码吞吐率。
算法1 并行层译码算法
Alg.1 Parallel layered decoding algorithm
3.3 多块译码
如上所述，每块有Z线程并行译码。但在GPU上，每块最大线程数为1 024或2 048。虽然不建议超过Z的线程数，但最大Z是384，远远没有超过每块线程的最大限制。因此，有可能在同一块内分配更多的线程来译码多个码字。因此，我们实现了多块译码，提高GPU的并行度。让Np作为同一块中被译码的码字数量。那么每个块的线程数为Np×Z。因此，用Nc表示输入码字的数量，为译码内核分配Nc/Np块。有Nc/Np块一起被译码，每个块由Np×Z个线程进行译码。
3.4 存储层次
为了充分利用GPU上的内存资源，经常访问的值被存储在共享内存中。在本文实现中，f、s和L被存储到共享内存中。它们的大小分别是1×Z、1×Z和Z×nb。不建议将R放入共享内存中。因为R的大小是（mb×Z）×kb，BG1中kb=22，最大mb=46。R尺寸过大，以至于把它放在共享内存中可能会限制译码时常驻块的数量，所以本文将R存储在全局内存中。
L的大小只有nb×Z。本文只关心最后的结果，中间的结果会在后几层的迭代中被覆盖。由于译码时经常访问L，所以必须要将L放到离计算单元较近的存储层次中。在5G新型无线电中最大的nb=68，Zmax=384。L的大小小于GPU共享存储的容量。因此将L的值存储到共享内存中，便于GPU的CUDA核心快速访问到L。
3.5 两级量化
以往工作很多都提出了量化方案来提高LDPC的译码吞吐率[20]。在本文实现中，为了更有效地利用带宽，同时减少对性能的损失，提出了一种两级量化方案。
一般来说，GPU支持的内置类型的最小长度为8位。小于8位的量化方案不适合基于GPU的高吞吐率译码。因为较小的长度可能会引入许多类型转换，这些类型转换是为了适应CUDA中原生算术指令支持的最小长度而执行的。与加法和乘法等其他算术运算相比，类型转换在GPU上的吞吐率较低。此外，像AND、XOR以及移位等位元运算吞吐率也很低。
因此，本文在译码过程中使用8位值来节省带宽。虽然小于8位的数据类型的计算效率不高，但通过数据打包可以提高CPU和GPU之间的传输效率。基于此，本文将L0j量化为第一级的4位数。而L和R则在第二级量化为8位数。在两个层次中，第一个位是符号位。
第一级量化、4位L0j方案进一步节省了片外带宽。可以降低CPU和GPU之间的通信延迟。
4位L0j方案避免了计算L时的溢出。如同在式（11）中所描述的，L在每次迭代中与R相加。在多次迭代后，L的数量有可能会溢出。而本文实验结果也证明了，当采用8位数据类型译码时，溢出现象很普遍。因此，我们将L0j量化为4位来限制初始值的范围。这个方案可以避免大部分计算过程中的溢出。
L和R的两级量化可以节省片上带宽。为了实现高吞吐率译码，片上带宽也是需要考虑的重要因素。
两级量化也节省了共享内存和寄存器的空间。驻留块受共享内存占用率的限制。节省共享内存和寄存器有助于实现更多的并行性。与8位方案相比，两级方案的性能损失可以忽略。
3.6 数据打包
数据打包可以减少CPU和GPU之间数据传输造成的译码延迟。译码器的输出是二进制比特位。虽然在GPU上实现比特运算效率不高，但不难发现，我们可以对译码结果进行打包来节省带宽。在本文实现中，每8个译码位在硬性决定后打包成一个8位char值。然后将打包后的数据传输给CPU。
除了对译码位进行打包外，本文还结合量化和数据打包来进一步节省带宽。如上所述，输入的L0j值被量化为4位固定数。因此，每两个L0j的值可以打包成一个8位的char值。一旦打包后的数据被传送到GPU，它们就会被转换为8位的char值，以便进行下一个译码过程。
图2显示了译码器在GPU上的内存层次结构和数据打包策略。在译码前，输入数据被量化为4位值，中间值为8位值。L，f和s存储在共享内存中；R存储在全局存储器中。8个译码后的信息位被打包成一个char类型的值。然后将打包后的数据传送给CPU。
图2内存层次和数据打包
Fig.2Memory hierarchy and data package
4 实验结果
4.1 实验设置
本文在基于图灵架构的Nvidia RTX 2080Ti上实现了QC-LDPC译码器，该译码器拥有4 352个CUDA核心、68个多处理器和11 GB的GDDR6内存，CPU为Inteli7-8700K，CUDA版本为10.2。
在生成编码值时，采用了正交相移键控调制方式，并用加法白高斯噪声作为信道噪声。MSA的尺度因子为0.75，信噪比为3 dB，d=0.15。在测量译码吞吐率时，不采用提前终止法，所以上述参数设置为常用值。
4.2 译码吞吐率
表2描述了不同码率下的基图结构。LDPC基图的码长、码率、右移参数配置会根据码率变化而变化。本文旨在提高由BG1构建的QC-LDPC码的译码吞吐率，基码长度为2 048。如表2所示，右移尺度随着码率的增加而增加。由于Hb的缩短，mb和nb减小。吞吐率T定义为。其中，t为译码时间。
采用不同优化方法的译码器的吞吐率结果如表3所示。采用两级量化的量化方式，吞吐率提升了2.1倍。采用多码块译码方法，吞吐率进一步提升了18.6%。此外，数据打包方案也有很好的效果，与不进行数据打包的方法相比，吞吐率获得了16.9%的提高。
表2不同码率的基图
Tab.2 Base graph under different code ratio
表3不同优化方法下吞吐率性能对比
Tab.3 Comparison of throughput under different optimization methods
本文同时测量了表2中不同码率的译码吞吐率。对于高码率，H会被缩短。如表2所示，mb和nb的大小随着码率的增加而减小。如此，迭代次数在水平和垂直方向上都相应减少，这就造成并行译码器的译码时间减少，而吞吐率显著增加。图3描述了不同码率下的译码吞吐率。多码率译码的吞吐率比普通译码的吞吐率平均提高了40%以上。
图3不同码率下的译码吞吐率
Fig.3Decoding throughput under different code ratio
4.3 线程配置分析
为了最有效地利用GPU上的资源，线程的分配是根据码率来调整的。众所周知，每个线程块和每个多处理器的寄存器和共享内存的数量是有限的。此外，为了避免过载，还要考虑每个流多处理器（streaming multiprocessor，SM）的最大常驻块和线程数。本文将Np、Nr、Nm、Nt表示为每个块的码字数、寄存器数、共享内存数和线程数，并用RSM、MSM、TSM、BSM表示每个SM的最大寄存器、共享内存、常驻线程和常驻块，NSM为GPU上SM的数量，Nb为每个SM上的常驻块。
那么就可以得到相应的线程分配如下
(18)
同时被译码的码块数量可以用以下方法来评估
(19)
在此基础上，评估最合适的线程分配和被并行译码的码字块数量。设最优的线程数配置，译码的最佳码字块数量Ntc=NbNpNSM。对于RTX 2080Ti，实验中参数具体设置如表4所示。Nr由nvcc编译器获得。输出数据Lo=Z×kb，会根据Z 和Nb大小来变化。
表4GPU上资源的占用情况
Tab.4 Resource occupancy on GPU
表5描述了RTX 2080Ti上实现的线程参数配置情况下的吞吐率情况。为了实现更高的吞吐率，本文选择了一个合适的Np参数来实现。
表5最佳线程分配和吞吐率
Tab.5 The Optimal thread allocation and throughput
图4显示了每个SM中的最大常驻块与GPU上的码率的变化关系。M、R、T、B分别代表共享内存、寄存器、常驻线程和每个SM的常驻块。在低码率情况下，Z很小，限制了每个SM的最大常驻块。在高码率情况下，Z较大，Np和Nc受到每个块的最大线程量和最大共享内存量的限制。最终的常驻块是M、R、T、B四个数值的最小值。
图4每个SM中的最大常驻块与r的变化关系
Fig.4Changing relationship between the maximum resident block in each SM and r
4.4 性能比较
目前，基于GPU的5G新型无线电的QC-LDPC译码器很少。在5G新型无线电中，信息列的数量kb较多，达到22个，而 WiMAX中最大的非零条目是7个。表6为本文LDPC译码器和其他LDPC译码器的比较。其中，迭代次数为10次，译码算法为MSA的分层译码，表中的吞吐率用Mbit/s表示。虽然我们在译码时需要处理更多的迭代，但本文提出的译码器在高码率下实现了Gbit/s的吞吐率，超过其他相关工作。另外本文利用吞吐率/峰值性能的比值来衡量同样的峰值性能情况下实现的吞吐率，以此来比较不同的工作对GPU峰值性能的利用率。从最终结果可以看出，本文算法峰值性能利用率也是最高的，证明了本文GPU并行算法及优化方法的优越性。
表6不同GPU的译码器性能比较
Tab.6 Performance comparison of different GPU-based decoder
5 结论
本文提出了一种基于GPU的5G新型无线电的LDPC译码器。同时提出了基于GPU的并行MSA算法。在实现细节上，本文利用多块译码方法实现了码块内的并行译码，提出了两级量化方案，以进一步节省GPU的片上和片下带宽。通过评估目标GPU的最佳线程分配，最终实现了基于GPU的高吞吐率5G新型无线电LDPC译码器。在（2 080，1 760），r=5/6的配置下，本文提出的译码器吞吐率最高可达到1.38 Gbit/s。
