Parallel algorithms and architectures for LDPC Decoding

Abstract

Low-Density Parity-Check (LDPC) codes have recaptured the attention of the scientific community a few years after Turbo codes were invented in the early nineties. Originally proposed in the 1960s at MIT by R. Gallager, LDPC codes represent powerful error correcting codes that allow working very close to the Shannon limit and achieve excellent Bit Error Rate (BER) due to computationally intensive algorithms on the decoder side of the system. Advances in microelectronics introduced small process technologies that allowed developing complex designs incorporating a high number of transistors in Very Large Scale Integration (VLSI) systems. Recently, these processes have been used to develop architectures able of performing LDPC decoding in real-time and delivering considerably high throughputs. Mainly for these reasons and naturally because the patent has expired, they have been adopted by modern communication standards which triggered their popularity, showing how actual they are. Due to the increase of transistor density in VLSI systems, and also to the fact that recently processing speed has risen faster than bandwidth, power and memory walls have created a new paradigm in computer architectures: rather than just increasing the frequency of operation supported by smaller process designs, the introduction of multiple cores on a single chip has become the new trend to provide augmented computational power. This thesis proposes new approaches for these computationally intensive algorithms, by performing parallel LDPC decoding based on ubiquitous multi-core architectures and achieves efficient throughputs that compare well with dedicated VLSI systems. We extensively address the challenges faced in the investigation and development of these programmable solutions, with focus mainly given on flexibility and scalability of the proposed algorithms, throughput and BER performance, and general efficiency of the programmable solutions here presented, that also achieve results more than an order of magnitude superior to those obtained with conventional CPUs. Furthermore, the investigation herein described follows a methodology that analyzes in detail the computational complexity of these decoding algorithms in order to propose strategies to accelerate their processingwhich, if conveniently transposed to other areas of computer science, can demonstrate that in this new multi-core era we may be in the presence of valid alternatives to non-reprogrammable dedicated VLSI hardware that requires non-recurring engineering.

Os códigos LDPC despertaramnovamente a atenção da comunidade científica poucos anos após a invenção dos Turbo códigos na década de 90. Inventados no MIT por R. Gallager no início da década de 60, os códigos LDPC representam sistemas correctores de erros poderosos que permitem trabalhar muito perto do limite de Shannon e obter taxas de bits errados (BER) excelentes, através da exploração apropriada de algoritmos computacionalmente intensivos no lado do descodificador do sistema. Avanços recentes na área da microelectrónica introduziram tecnologias e processos capazes de suportar o desenvolvimento de sistemas complexos que incorporamumnúmero elevado de transístores em sistemas VLSI. Recentemente, essas tecnologias permitiram o desenvolvimento de arquitecturas capazes de processar a descodificação de códigos LDPC em tempo-real, obtendo taxas de débito de saída consideravelmente elevadas. Principalmente por estes motivos, e também devido ao facto do prazo de validade da patente ter expirado, estes códigos têm sido adoptados por normas de comunicações recentes, o que comprova a sua popularidade e actualidade. Devido ao aumento da densidade de transístores emsistemasmicroelectrónicos (VLSI), e uma vez que nos temposmais recentes a velocidade de processamento temsofrido uma evolução mais rápida do que a velocidade de acesso à memória, os problemas associados à dissipação de potência e a tempos de latência elevados criaram um novo paradigma em arquitecturas de computadores: ao invés de apenas se privilegiar o aumento da frequência de operação suportada pelo uso de tecnologias que garantem tempos de comutação do transístor cada vez mais reduzidos, a introdução de múltiplas unidades de processamento (cores) num único sistema microelectrónico (chip) tornou-se a nova tendência, mantendo como objectivo principal o contínuo aumento da capacidade de processamento de dados em sistemas de computação. Esta tese propõe novas abordagens para estes algoritmos de computação intensiva, que permitem realizar o processamento paralelo de descodificadores LDPC de forma eficiente baseada em arquitecturas multi-core, e que conduzemà obtenção de taxas de débito de saída elevadas, comparáveis às obtidas em sistemas microelectrónicos dedicados (VLSI). É feita a análise exaustiva dos desafios que se colocam à investigação deste tipo de soluções programáveis, dando-se especial ênfase à flexibilidade e escalabilidade dos algoritmos propostos, aos níveis da taxa de débito e taxa de erros (BER) alcançados, bem como à eficiência geral das soluções programáveis apresentadas, que alcançam resultados acima de uma ordem de grandeza superiores aos obtidos usando CPUs convencionais. Além do mais, a investigação descrita nesta tese segue uma metodologia que analisa com detalhe a complexidade computacional destes algoritmos de descodificação de modo a propor estratégias de aceleração do processamento que, se adequadamente transpostas para outros domínios das ciências da computação, podemdemonstrar que nesta nova era dos sistemasmulti-core podemos estar na presença de alternativas viáveis em relação a soluções de hardware dedicado (VLSI) não reprogramáveis, cujo desenvolvimento envolve um consumo significativo de recursos não reutilizáveis