Low density parity check code decoding acceleration technology based on GPU

doi:10.11772/j.issn.1001-9081.2021101726

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (12): 3841-3846.DOI: 10.11772/j.issn.1001-9081.2021101726

• Advanced computing • Previous Articles

Low density parity check code decoding acceleration technology based on GPU

Qidi XU, Zhenghong LIU(), Lin ZHENG

Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing （Guilin University of Electronic Technology），Guilin Guangxi 541004，China

Received:2021-10-09 Revised:2021-12-26 Accepted:2022-01-05 Online:2022-01-24 Published:2022-12-10
Contact: Zhenghong LIU
About author:XU Qidi， born in 1997， M. S. candidate. His research interests include Graphics Processing Unit （GPU） parallel computing， software radio applications.
ZHENG Lin， born in 1973， Ph. D.， professor. His research interests include wireless communication signal processing， incoherent Multiple-Input Multiple-Output （MIMO）， Ultra Wideband （UWB） communication， radar-communication integration.
Supported by:
Natural Science Foundation of Guangxi(2020GXNSFAA159067);Fund for Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing(GXKL06160112);Fund for Key Laboratory of Cognitive Radio(CRKL200102)

基于GPU的低密度奇偶校验码译码加速技术

徐启迪, 刘争红(), 郑霖

广西无线宽带通信与信号处理重点实验室（桂林电子科技大学），广西桂林 541004

通讯作者: 刘争红
作者简介:徐启迪（1997—），男，广东汕尾人，硕士研究生，主要研究方向：图形处理器（GPU）并行运算、软件无线电应用
郑霖（1973—），男，安徽祁门人，教授，博士，主要研究方向：无线通信信号处理、非相干多进多出（MIMO）、超宽带（UWB）通信、雷达通信一体化。
基金资助:
广西自然科学基金资助项目(2020GXNSFAA159067);无线宽带通信与信号处理重点实验室基金资助项目(GXKL06160112);认知无线电重点实验室项目(CRKL200102)

Abstract

Abstract:

With the development of communication technology， communication terminals gradually adopt software to be compatible with multiple communication modes and protocols. As in the traditional software radio architecture with a Central Processing Unit （CPU） of computer as an arithmetic unit， the wideband data throughput of high-speed wireless communication systems such as Multiple-Input Multiple-Output （MIMO） is not be satisfied， an acceleration method of Low Density Parity Check （LDPC） code decoder based on Graphics Processing Unit （GPU） was proposed. Firstly， according to the theoretical analysis of the acceleration performance of GPU parallelly accelerated heterogeneous computing in GNU Radio 4G/5G physical layer signal processing module， a more parallelly efficient Layered Normalized Min-Sum （LNMS） algorithm was adopted. Then， the decoding delay of the decoder was reduced by using the methods such as global synchronization strategy， reasonably allocation of GPU memory space and stream parallelism mechanism. At the same time， the LDPC code decoding process was optimized in parallel with the multi-threaded parallel technology in GPU. Finally， the GPU accelerated decoder was implemented and verified on the software radio platform， and the bit error rate performance and acceleration performance bottlenecks of the parallel decoder were analyzed. Experimental results show that compared with the traditional CPU serial code processing method， CPU+GPU heterogeneous platform has the decoding rate for LDPC codes increased to about 200 times， and the throughput of decoder can reach more than 1 Gb/s， especially in the case of large-scale data， the decoding performance is greatly improved compared with traditional decoder.

Key words: Graphic Processing Unit (GPU), Compute Unified Device Architecture (CUDA), Low Density Parity Check (LDPC) code, parallel computing, channel decoding

摘要：

随着通信技术的发展，通信终端逐渐采用软件的方式来兼容多种通信制式和协议。针对以计算机中央处理器（CPU）作为运算单元的传统软件无线电架构，无法满足高速无线通信系统如多进多出（MIMO）等宽带数据的吞吐率要求问题，提出了一种基于图形处理器（GPU）的低密度奇偶校验（LDPC）码译码器的加速方法。首先，根据GPU并行加速异构计算在GNU Radio 4G/5G物理层信号处理模块中的加速表现的理论分析，采用了并行效率更高的分层归一化最小和（LNMS）算法；其次，通过使用全局同步策略、合理分配GPU内存空间以及流并行机制等方法减少了译码器的译码时延，同时配合GPU多线程并行技术对LDPC码的译码流程进行了并行优化；最后，在软件无线电平台上对提出的GPU加速译码器进行了实现与验证，并分析了该并行译码器的误码率性能和加速性能的瓶颈。实验结果表明，与传统的CPU串行码处理方式相比，CPU+GPU异构平台对LDPC码的译码速率可提升至原来的200倍左右，译码器的吞吐量可以达到1 Gb/s以上，特别是在大规模数据的情况下对传统译码器的译码性有着较大的提升。

关键词: 图形处理器, 计算统一设备架构, 低密度奇偶校验码, 并行计算, 信道译码

CLC Number:

TN764

Qidi XU, Zhenghong LIU, Lin ZHENG. Low density parity check code decoding acceleration technology based on GPU[J]. Journal of Computer Applications, 2022, 42(12): 3841-3846.

徐启迪, 刘争红, 郑霖. 基于GPU的低密度奇偶校验码译码加速技术[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3841-3846.

Figures/Tables 7

Fig. 1 Performance comparison of LDPC decoding algorithms

Fig. 2 Flow chart of LNMS decoding algorithm

Fig. 3 Parallel strategy

Fig. 4 Synchronization implementation method

Fig. 5 Speedup performance under multi-codeword parallelism

Fig. 6 Comparison of throughput performance under multi-codeword parallelism

Tab.1 Comparison of different decoders

模型	LDPC码型	GPU型号	迭代次数	时延/ $μ s$	吞吐量/（Mb·s^-1）
文献［16］模型	（2 304，1 152）	GTX 580	5	Non	710
文献［17］模型	（2 304，1 152）	GTX TITAN	10	1 266/50	304.16
文献［18］模型	（1 944，972）	TITA NX	5	2.13	913
文献［19］模型	（2 160，1 056）	RTX 2080Ti	10	Non	506
本文模型	（2 304，1 152）	RTX 5000	10	2.10	1 084

Tab.1 Comparison of different decoders

模型	LDPC码型	GPU型号	迭代次数	时延/ $μ s$	吞吐量/（Mb·s^-1）
文献［16］模型	（2 304，1 152）	GTX 580	5	Non	710
文献［17］模型	（2 304，1 152）	GTX TITAN	10	1 266/50	304.16
文献［18］模型	（1 944，972）	TITA NX	5	2.13	913
文献［19］模型	（2 160，1 056）	RTX 2080Ti	10	Non	506
本文模型	（2 304，1 152）	RTX 5000	10	2.10	1 084

References 19

1	GALLAGER R. Low-density parity-check codes［J］. IRE Transactions on Information Theory， 1962， 8（1）： 21-28. 10.1109/tit.1962.1057683
2	TANNER R. A recursive approach to low complexity codes［J］. IEEE Transactions on Information Theory， 1981， 27（5）： 533-547. 10.1109/tit.1981.1056404
3	MacKAY D J C， NEAL R M. Near Shannon limit performance of low density parity check codes［J］. Electronics Letters， 1996， 32（18）： 1645-1646. 10.1049/el:19961141
4	CHEN J H， FOSSORIER M P C. Density evolution for two improved BP-based decoding algorithm of LDPC codes［J］. IEEE Communications Letters， 2002， 6（5）： 208-210. 10.1109/4234.1001666
5	IYENGAR A R， PAPALEO M， SIEGEL P H， et al. Windowed decoding of protograph-based LDPC convolutional codes over erasure channels［J］. IEEE Transactions on Information Theory， 2012， 58（4）：2303-2320. 10.1109/tit.2011.2177439
6	MITCHEL D G M， LENTMAIER M， COSTELLO D J. Spatially coupled LDPC codes constructed from protographs［J］. IEEE Transactions on Information Theory， 2015， 61（9）：4866-4889. 10.1109/tit.2015.2453267
7	WANG Q F， CAI S H， LIN W C， et al. Spatially coupled LDPC codes via partial superposition［C］// Proceeding of the 2019 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2019： 2614-2618. 10.1109/isit.2019.8849384
8	WANG Q F， CAI S H， LIN W C， et al. Spatially coupled LDPC codes via partial superposition and their application to HARQ［J］. IEEE Transactions on Vehicular Technology， 2021， 70（4）： 3493-3504. 10.1109/tvt.2021.3065052
9	PHAM T X， LEE H. High-efficient nonbinary LDPC decoder with early layer decoding schedule［C］// Proceeding of the 2021 IEEE International Symposium on Circuits and Systems. Piscataway： IEEE， 2021： 1-4. 10.1109/iscas51556.2021.9401072
10	WIJEKOON V B， VITERBO E， HONG Y. Decoding of NB-LDPC codes over subfields［J］. IEEE Transactions on Communications， 2021， 69（2）： 716-727.
11	SHAN B W， FANG Y. GPU accelerated parallel algorithm of sliding-window belief propagation for LDPC codes［J］. International Journal of Parallel Programming， 2020， 48（3）： 566-579. 10.1007/s10766-019-00632-3
12	YUAN J Y， SHA J. 4.7-Gb/s LDPC decoder on GPU［J］. IEEE Communications Letters， 2018， 22（3）： 478-481.
13	LIU Z X， LIU R K， ZHAO L. GPU-based non-binary LDPC decoder with weighted bit-reliability based algorithm［J］. China Communications， 2020， 17（5）： 78-88. 10.23919/jcc.2020.05.008
14	任计林，车书玲，郑征. 规则LDPC码在GPU上的加速译码［J］. 西安电子科技大学学报， 2017， 44（3）：25-30. 10.3969/j.issn.1001-2400.2017.03.005
	REN J L， CHE S L， ZHENG Z. Decoding of regular LDPC codes accelerated by the GPU［J］. Journal of Xidian University， 2017， 44（3）：25-30. 10.3969/j.issn.1001-2400.2017.03.005
15	孔飞跃，蒋学芹，万雪芬，等. 基于GPU的LDPC增强准最大似然译码器并行实现［J］. 计算机工程， 2020， 46（5）：207-215. 10.19678/j.issn.1000-3428.0056226
	KONG F Y， JIANG X Q， WAN X F， et al. Parallel implementation of GPU-based LDPC enhanced quasi-maximum likelihood decoder［J］. Computer Engineering， 2020， 46（5）：207-215. 10.19678/j.issn.1000-3428.0056226
16	LI R C， DOU Y， ZOU D， et al. Efficient graphics processing unit based layered decoders for quasicyclic low-density parity-check codes［J］. Concurrency and Computation： Practice and Experience， 2015， 27（1）： 29-46. 10.1002/cpe.3193
17	WANG G H， WU M， YIN B， et al. High throughput low latency LDPC decoding on GPU for SDR systems［C］// Proceeding of the 2013 IEEE Global Conference on Signal and Information Processing. Piscataway： IEEE， 2013：1258-1261. 10.1109/globalsip.2013.6737137
18	KESKIN S， KOCAK T. GPU-based gigabit LDPC decoder［J］. IEEE Communications Letters， 2017， 21（8）： 1703-1706. 10.1109/lcomm.2017.2704113
19	LI R C， ZHOU X， PAN H Y， et al. A high-throughput LDPC decoder based on GPUs for 5G new radio［C］// Proceeding of the 2020 IEEE Symposium on Computers and Communications. Piscataway： IEEE， 2020： 1-7. 10.1109/iscc50000.2020.9219558

[1]	Jingwen CAI, Yongzhuang WEI, Zhenghong LIU. GPU-based method for evaluating algebraic properties of cryptographic S-boxes [J]. Journal of Computer Applications, 2022, 42(9): 2750-2756.
[2]	Xinyuan QIU, Zecong YE, Xiaolong CUI, Zhiqiang GAO. Survey of communication overhead of federated learning [J]. Journal of Computer Applications, 2022, 42(2): 333-342.
[3]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[4]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[5]	CHEN Fatang, ZHANG Youshou, DU Zheng. Low complexity offset min-sum algorithm for 5G low density parity check codes [J]. Journal of Computer Applications, 2020, 40(7): 2028-2032.
[6]	Zhiyang ZENG, Yan CHEN, Ke WANG. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[7]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[8]	HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system [J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.
[9]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.
[10]	WANG Peng, ZHOU Yan. MPI big data processing for high performance applications [J]. Journal of Computer Applications, 2018, 38(12): 3496-3499.
[11]	HAN Litao, LIU Hailong, KONG Qiaoli, YANG Fanlin. Parallel algorithm for hillshading under multi-core computing environment [J]. Journal of Computer Applications, 2017, 37(7): 1911-1915.
[12]	JIAO Jiafeng, LI Yun. Review of typical machine learning platforms for big data [J]. Journal of Computer Applications, 2017, 37(11): 3039-3047.
[13]	JI Lina, CHEN Qingkui, CHEN Yuanjing, ZHAO Deyu, FANG Yuling, ZHAO Yongtao. Real-time crowd counting method from video stream based on GPU [J]. Journal of Computer Applications, 2017, 37(1): 145-152.
[14]	ZHAO Yongtao, CHEN Qingkui, FANG Yuling, ZHAO Deyu, JI Lina. Early warning method for driving safety based on CUDA [J]. Journal of Computer Applications, 2017, 37(1): 134-137.
[15]	XUE Jun, DUAN Fajie, JIANG Jiajia, LI Yanchao, YUAN Jianfu, WANG Xianquan. Parallel cyclic redundancy check Verilog program generating method based on Matlab [J]. Journal of Computer Applications, 2016, 36(9): 2503-2507.

Low density parity check code decoding acceleration technology based on GPU

基于GPU的低密度奇偶校验码译码加速技术

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 19

Related Articles 15

Recommended Articles

Metrics