On task mapping optimization for parallel decoding of low-density parity-check codes on message-passing architectures

In this paper, we investigate the implementation of iterative probabilistic decoding of low-density parity-check codes on programmable message-passing parallel architectures. We present techniques for optimizing the mapping of tasks to processing units so as to minimize the communication cost by localizing communication. Specifically, we present a simplified clustering technique based on a modified mincut algorithm that reduces the search complexity from quadratic to linear. Cluster allocation is optimized with two different approaches for comparison: using a mincut algorithm and using a genetic algorithm. Results show that the majority of communication locality is exploited by within-cluster communication and is achieved by the clustering operation. The proposed mapping techniques result in a reduction of up to 45% in communication cost compared to random mappings.