Design Space Exploration of LDPC Decoders on Programmable and Reconfigurable Architectures

Abstract

Os códigos definidos por matrizes de teste de paridade esparsas (LDPC) são bastante em sistemas de comunicação digital e armazenamento de dados, por operarem quase à capacidade do canal. No entanto, a realização de descodificadores LDPC é um processo desafiante devido à complexidade associada aos códigos LDPC binários e, em particular, aos não-binários. Apesar de a tecnologia de integração em larga escala (VLSI) ter capacidade para a realização de descodificadores LDPC que cumpram a baixa latência e o elevado ritmo de transmissão de dados, os processos de desenvolvimento em circuitos integrados de aplicação específica (ASIC) ou em circuitos lógicos programáveis (FPGA) são morosos, conduzem facilmente a erros e são pautados por detalhes minuciosos ao nível do silício e da micro-arquitectura que elevam os custos não recorrentes de engenharia (NRE). Esta tese aborda estratégias para superar os desafios inerentes ao desenvolvimento de descodificadores binários e não-binários em arquitecturas programáveis e reconfiguráveis. Deste modo, são propostas metodologias que exploram a imensa capacidade computacional de arquitecturas many-core, como processadores gráficos (GPUs), aplicadas a descodificadores binários e não-binários, não só atingindo os elevados ritmos de dados necessários aos sistemas de comunicação actuais, mas também permitindo rápida simulação de Monte Carlo para a caracterização da taxa de erros (BER), essencial para o estudo de novos códigos e algoritmos. A metodologia proposta para arquitecturas programáveis é extendida a arquitecturas reconfiguráveis. Os descodificadores FPGA desenvolvidos tiram partido de síntese de alto-nível (HLS), baseada em modelos dataflow, loop-annotated e wide-pipeline. Através da análise da performance obtida em cada abordagem, propõem-se linhas orientadoras para o desenvolvimento de descodificadores de elevados desempenhos. Finalmente, são propostos métodos ao nível algorítmico e do silício de melhoria da eficiência energética dos descodificadores propostos. As técnicas desenvolvidos utilizam técnicas de gear-shifting e de armazenamento de dados em memórias não-fiáveis, para as quais são introduzidas estratégias de diminuição da degradação de BER.

Low-density parity-check (LDPC) codes are capacity-approaching linear block codes widely employed for digital communication systems and storage. However, the realization of LDPC decoders is a very challenging process due to the numerical complexity associated with binary, and especially, with non-binary LDPC codes. Whereas very large scale integration (VLSI) technology provides the necessary means to allow the realization of efficient LDPC decoders that meet both low latencies and high decoding throughputs, the development process behind application-specific integrated circuit (ASIC) and fieldprogrammable gate array (FPGA) decoders is error-prone, protracted and is an endeavor captured by low-level micro-architecture and silicon details that pose high non-recurring engineering (NRE) costs. In this Thesis, we explore efficient ways to overcome the challenges associated with the development of binary and non-binary LDPC decoders on both programmable and reconfigurable hardware. We propose methodologies that leverage on the immense computational power of multicore graphics processing unit (GPU) architectures applied to binary and non-binary LDPC decoders, not only for achieving the very high data rates required for nowadays communications, but also for very fast Monte Carlo bit error rate (BER) simulation, essential for the study of new LDPC codes. Having exploited the potential of parallel computing on programmable hardware and identified its shortcomings, we extend our proposed methodology to reconfigurable hardware. The developed FPGA-decoders explore different high-level synthesis (HLS) programming models, based on dataflow, loop-annotated and wide-pipeline architectures. From the performance analysis of these accelerators, we identify the key guidelines to the design of efficient LDPC decoders under each approach. Finally, we propose algorithmand silicon-level procedures to boost the LDPC decoders energy efficiency. Namely, we propose gear-shift techniques, and incorporation of unreliable memory storage along with BER degradation mitigation strategies.