How GPUs can outperform ASICs for fast LDPC decoding

ABSTRACT

Due to huge computational requirements, powerful Low-Density Parity-Check (LDPC) error correcting codes, discovered in the early 1960s, have only recently been adopted by emerging communication standards. LDPC decoders are supported by VLSI technology, which delivers good parallel computational power with excellent throughputs, but at the expense of significant costs.

In this work, we propose an alternative flexible LDPC decoder that exploits data-parallelism for simultaneous multicodeword decoding, supported by multithreading on CUDA-based graphics processing units (GPUs). The ratio of arithmetic operations per memory access is low for the efficient min-sum LDPC decoding algorithm proposed, which causes a bottleneck due to memory latency and data collisions. We propose runtime data realignment to allow coalesced parallel memory accesses to be performed by distinct threads inside the same warp. The memory access patterns of LDPC codes are random, which does not admit the simultaneous use of coalescence in both read and write operations of the decoding process. To overcome this problem we have developed a data mapping transformation which allows new addresses to be contiguously accessed for one of the mentioned memory access types. Our implementation shows throughputs above 100Mbps and BER curves that compare well with ASIC solutions.

REFERENCES

• 1: R. G. Gallager. Low-density parity-check codes. IRE Transactions on Information Theory, 8(1):21--28, January 1962.
• 2: R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, IT-27(5):533--547, September 1981.
• 3: C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: Turbo-codes (1) In IEEE International Conference on Communications (ICC'93), pages 1064--1070, May 1993.
• 4: D. J. C. Mackay and R. M. Neal. Near Shannon limit performance of low density parity check codes. IEE Electronics Letters, 32(18):1645--1646, August 1996.
• 5: Digital video broadcasting (DVB); second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broad-band satellite applications. EN 302 307 V1. 1.1, European Telecommunications Standards Institute (ETSI), 2005.
• 6: T. Zhang and K. Parhi. Joint (3,k)-regular LDPC code and decoder/encoder design. IEEE Transactions on Signal Processing, 52(4):1065--1079, April 2004.
• 7: F. Kienle, T. Brack, and N. Wehn. A Synthesizable IP Core for WIMAX 802.16E LDPC Code Decoding. In IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, pages 1--5, September, 2006.
• 8: John Dielissen , Andries Hekstra , Vincent Berg, Low cost LDPC decoder for DVB-S2, Proceedings of the conference on Design, automation and test in Europe: Designers' forum, March 06-10, 2006, Munich, Germany
• 9: Li Ping and W. K. Leung. Decoding Low Density Parity Check Codes with Finite Quantization Bits. IEEE Communications Letters, 4(2):62--64, February 2000.
• 10: A. J. Blanksby and C. J. Howland. A 690-mW 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder. IEEE Journal of Solid-State Circuits, 37(3):404--412, March 2002.
• 11: Federico Quaglio , Fabrizio Vacca , Cristiano Castellano , Alberto Tarable , Guido Masera, Interconnection framework for high-throughput, flexible LDPC decoders, Proceedings of the conference on Design, automation and test in Europe: Designers' forum, March 06-10, 2006, Munich, Germany
• 12: Sangwon Seo, Trevor Mudge, Yuming Zhu, and Chaitali Chakrabarti. Design and Analysis of LDPC Decoders for Software Defined Radio. In Proceedings of IEEE Workshop on Signal Processing Systems, pages 210--215, October 2007.
• 13: A. Ghuloum, E. Sprangle, J. Fang, G. Wu, and X. Zhou. Ct: A Flexible Parallel Programming Model for Tera-scale Architectures. Intel, pages 1--21, 2007.
• 14: Wilson W. L. Fung , Ivan Sham , George Yuan , Tor M. Aamodt, Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.407-420, December 01-05, 2007 [doi>10.1109/MICRO.2007.12]
• 15: M. McCool. Scalable Programming Models for Massively Multicore Processors. Proceedings of the IEEE, 96(5):816--831, May 2008.
• 16: Gabriel Falcão , Leonel Sousa , Vitor Silva, Massive parallel LDPC decoding on GPU, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345221]
• 17: G. Falcão, V. Silva, L. Sousa and J. Marinho. High coded data rate and multicodeword WiMAX LDPC decoding on Cell/BE. IET Electronics Letters, 44(24):1415--1417, November 2008.
• 18: S. Chung, G. Forney, T. Richardson and R. Urbanke. On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit. IEEE Communications Letters, 5(2):58--60, 2001.
• 19: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 20: Nolan Goodnight , Rui Wang , Greg Humphreys, Computation on Programmable Graphics Hardware, IEEE Computer Graphics and Applications, v.25 n.5, p.12-15, September 2005 [doi>10.1109/MCG.2005.101]
• 21: Ka-Ling Fok , Tien-Tsin Wong , Man-Leung Wong, Evolutionary Computing on Consumer Graphics Hardware, IEEE Intelligent Systems, v.22 n.2, p.69-78, March 2007 [doi>10.1109/MIS.2007.28]
• 22: Jens Krüger , Rüdiger Westermann, Linear algebra operators for GPU implementation of numerical algorithms, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 23: Shu Lin , Daniel J. Costello, Error Control Coding, Second Edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 2004
• 24: F. Guilloud, E. Boutillon, and J.-L. Danger. λ-min decoding algorithm of regular and irregular LDPC codes. In Proc. 3rd Int. Symp. Turbo Codes Relat. Topics, pages 1--4, September 2003.
• 25: C.-H. Liu, S.-W. Yen, C.-L. Chen, H.-C. Chang, C.-Y. Lee, Y.-S. Hsu, and S.-J. Jou. An LDPC Decoder Chip Based on Self-Routing Network for IEEE 802.16e Applications. IEEE Journal of Solid-State Circuits, 43(3):684--694, 2008.
• 26: Xin-Yu Shih, Cheng-Zhou Zhan, Cheng-Hung Lin, and An-Yeu Wu. An 8.29 mm 2 52 mW Multi-Mode LDPC Decoder Design for Mobile WiMAX System in 0.13 μm CMOS Process. IEEE Journal of Solid-State Circuits, 43(3):672--683, 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing

General Terms:
Algorithms, Design, Performance

Keywords:
graphics processing units, low-density parity-check codes, memory coalescence, multithreading, parallel processing