Optimizing the mapping of low-density parity check codes on parallel decoding architectures

We study the problem of optimizing the mapping of LDPC codes on parallel machines to minimize the communication cost. To reduce the search space, the problem is solved in two stages: clustering, and cluster allocation. We propose a simplified clustering technique based on a modified min-cut algorithm that reduces the search complexity from O(n/sup 2/) to O(n). It was found that most of the locality is exploited by the clustering operation, which results in a 40-52% improvement in the total communication cost over random mapping. For large networks, cluster allocation is much more costly and results in only 1-8% additional improvement in unidirectional and bi-directional torus topologies. We compared the performance of two different approaches for cluster allocation. The first one is bused on min-cut algorithm, and the second one is based on a genetic algorithm. It was found that the min-cut based approach is better for small network sizes. For large network sizes with the number of clusters /spl ges/64, the genetic based approach becomes more attractive.