A Spectral-based partitioning algorithm for parallel LDPC decoding on a multiprocessor platform

Low Density Parity Check (LDPC) code is an error correction code that has near Shannon limit performance and is inherently suitable for parallel implementation. It has been widely used in several communication standards such as DVB-S2, WiMAX, and Wi-Fi. To address the need for supporting various LDPC codes in an era where diverse applications are integrated onto a single system, a multi-processor based implementation of the LDPC decoder was proposed. However, the heavy message exchange among processors limits the expected performance. In this paper, we present a partitioning algorithm based on graph spectral clustering to reduce the data communication during the decoding process. From the experiments, our approach successfully decreased the amount of inter-processor communication by 33% ~ 52%, as compared to the original sequential mapping approach. Together with the more balanced computation load from our algorithm, an improvement of up to 85% in the overall decoding time was observed.