© The Institution of Engineering and Technology
Low-density parity check (LDPC) codes can achieve performances close to the Shannon limit and they have been widely adopted for various communication standards. However, the irregular message exchange pattern of LDPC codes is a major challenge for decoder design. Additionally, there is a great demand for integrating diverse applications onto a single system where a flexible, scalable and efficient implementation of LDPC decoding is highly preferable. With the enormous computing power provided by integrating many processors on a single chip in advanced process technology, a multiprocessor platform is regarded as a promising solution to tackle these design challenges. In this work, we devised a parallelisation scheme to implement LDPC decoding on a multiprocessor platform. By using a distributed and cooperative way for LDPC decoding, the memory bottleneck, commonly seen in LDPC decoder design, is eliminated. Moreover, we used a graph spectra-based mapping algorithm to reduce heavy message exchanges among processors during the decoding process. Compared to the sequential mapping strategy, our approach has successfully decreased the amount of inter-processor communication by up to 48%/45%/40% for 16/32/64-processor platforms, respectively. Cycle-accurate simulation results from various LDPC codes demonstrate that desirable scalability and speedups are obtained by our approach.
References
-
-
1)
-
H. Lütkepohl
.
(1996)
Handbook of matrices.
-
2)
-
M.R. Anderberg
.
(1973)
Cluster analysis for applications.
-
3)
-
Vacca, F., Masera, G., Moussa, H., Baghdadi, A., Jezequel, M.: `Flexible architectures for LDPC decoders based on network on chip paradigm', 12thEuromicro Conf. on Digital System Design, Architectures, Methods and Tools, 2009.
-
4)
-
A.J. Blanksby
.
A 690 mW 1 Gb/s 1024-b, rate-1/2 low-density parity-check code decoder.
IEEE J. Solid-State Circuits
,
404 -
412
-
5)
-
Neeb, C., Thul, M., Wehn, N.: `Network-on-chip-centric approach to interleaving in high throughput channel decoders', IEEE Int. Symp. on Circuits and Systems, 2005, p. 1766–1769.
-
6)
-
Wagner, D., Wagner, F.: `Between min cut and graph bisection', Proc. 18th Int. Symp. on Mathematical Foundations of Computer Science, 1993, p. 744–750.
-
7)
-
Moussa, H., Baghdadi, A., Jezequel, M.: `Binary de bruijn on-chip network for a flexible multiprocessor LDPC decoder', Proc. Design Automation Conf., 2008, p. 429–434.
-
8)
-
Yeo, E., Nikolic, B., Anantharam, V.: `Architectures and implementations of low-density parity check decoding algorithms', Proc. IEEE Midwest Symp. on Circuits and Systems, 2002.
-
9)
-
G.H. Golub ,
C.F. Van Loan
.
(1989)
Matrix computations.
-
10)
-
M. Fiedler
.
Algebraic connectivity of graphs.
Czechoslovak Math. J.
,
298 -
305
-
11)
-
Lee, S.E., Bahn, J.H., Yang, Y.S., Bagherzadeh, N.: `A generic network interface architecture for an NoC based multiprocessor SoC', Int. Symp. on Architecture of Computing System, February 2008, (LNCS, 4934), p. 247–260.
-
12)
-
A. Pothen ,
H.D. Simon ,
K.P. Liou
.
Partitioning sparse matrices with eigenvectors of graphs.
SIAM J. Matrix Anal. Appl.
,
430 -
452
-
13)
-
Hu, W.H., Bahn, J.H., Bagherzadeh, N.: `Parallel LDPC decoding on a network-on-chip based multiprocessor platform', Proc. Int. Symp. on Computer Architecture and High Performance Computing, 2009.
-
14)
-
Falcao, G., Sousa, L., Silva, V.: `Massive parallel LDPC decoding on GPU', Proc. 13th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2008, p. 83–90.
-
15)
-
Brack, T., Alles, M., Lehnigk-Emden, T.: `Low complexity LDPC code decoders for next generation standards', Proc. Conf. on Design, Automation and Test in Europe, 2007, p. 331–336.
-
16)
-
J.H. Bahn ,
S.E. Lee ,
Y.S. Yang ,
J.S. Yang ,
N. Bagherzadeh
.
On design and application mapping of a network-on-chip architecture.
Parallel Process. Lett.
,
2 ,
239 -
255
-
17)
-
U.V. Luxburg
.
A tutorial on spectral clustering.
Stat. Comput.
,
395 -
416
-
18)
-
R. Gallager
.
Low-density parity-check codes.
IRE Trans. Inf. Theory
,
21 -
28
-
19)
-
R.M. Neal
.
Software for low density parity check codes.
-
20)
-
Falcao, G., Sousa, L., Silva, V., Marinho, J.: `Parallel LDPC decoding on the cell/BE processor', Proc. Fourth Int. Conf. on High Performance Embedded Architectures and Compilers, 2008, p. 389–403.
-
21)
-
M.P.C. Fossorier ,
M. Mihaljevic ,
H. Imai
.
Reduced complexity iterative decoding of low density parity check codes based on belief propagation.
IEEE Trans. Commun.
,
5 ,
673 -
680
-
22)
-
Dally, W.J., Towles, B.: `Route packets, not wires: on-chip interconnection networks', Proc. Design Automation Conf., 2001, p. 684–689.
-
23)
-
G. Masera ,
F. Quaglio ,
F. Vacca
.
Implementation of a flexible LDPC decoder.
IEEE Trans. Circuits Syst. II: Express Briefs
,
542 -
546
-
24)
-
Matus, E., Tavares, M.B.S., Bimberg, M., Fettweis, G.P.: `Towards a GBit/s programmable decoder for LDPC convolutional codes', Proc. IEEE Int. Symp. on Circuits and Systems, 2007.
-
25)
-
Bimberg, M., Tavares, M.B.S., Matus, E., Fettweis, G.P.: `A high-throughput programmable decoder for LDPC convolutional codes', Proc. IEEE Int. Conf. on Application-Specific Systems, Architectures and Processors, 2007, p. 239–246.
-
26)
-
Theocharides, T., Link, G., Vijaykrishnan, N., Irwin, M.: `Implementing LDPC decoding on network-on-chip', 18thInt. Conf. on VLSI Design, 2005, p. 134–137.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2010.0177
Related content
content/journals/10.1049/iet-cdt.2010.0177
pub_keyword,iet_inspecKeyword,pub_concept
6
6