InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Engineering » Electrical and Electronic Engineering » "WIMAX New Developments", book edited by Upena D Dalal and Y P Kosta, ISBN 978-953-7619-53-4, Published: December 1, 2009 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 6

LDPC Decoders for the WiMAX (IEEE 802.16e) Based on Multicore Architectures

By Gabriel Falcao, Vitor Silva, Jose Marinho and Leonel Sousa
DOI: 10.5772/8265

Article top

Overview

Periodicity 
							
								
									
										z
										×
										z
									
								
							
							
						=
							
								
									
										96
										×
										96
									
								
							
							
						for a matrix with n=2304, rate=1/2 and {3, 6} CNs per column.
Figure 1. Periodicity z × z = 96 × 96 for a matrix with n=2304, rate=1/2 and {3, 6} CNs per column.
A 4x8 H matrix and corresponding Tanner graph representation. The example shows messages being exchanged from CNm to BNn. A similar representation applies for messages going in the opposite direction.
Figure 2. A 4x8 H matrix and corresponding Tanner graph representation. The example shows messages being exchanged from CNm to BNn. A similar representation applies for messages going in the opposite direction.
Generic overview of the Cell/B.E. architecture.
Figure 3. Generic overview of the Cell/B.E. architecture.
Parallelization model for an LDPC decoder on the Cell/B.E. architecture.
Figure 4. Parallelization model for an LDPC decoder on the Cell/B.E. architecture.
Illustration of irregular memory accesses for the example shown in figure 2.
Figure 5. Illustration of irregular memory accesses for the example shown in figure 2.
Segment of the SIMD vectorized data structures in memory to represent: a) 
								
									
										
											
												r
												
													mn
												
											
											/
											
												
													Lr
												
												
													mn
												
											
										
									
								
								
							messages associated to BNs; and b) 
								
									
										
											
												q
												
													nm
												
											
											/
											
												
													Lq
												
												
													nm
												
											
										
									
								
								
							messages associated to CNs.
Figure 6. Segment of the SIMD vectorized data structures in memory to represent: a) r mn / Lr mn messages associated to BNs; and b) q nm / Lq nm messages associated to CNs.
Comparing LDPC decoding times for serial and parallel modes, where codes A, B and C represent, respectively, matrices (256, 128), (504, 252) and (1024, 512).
Figure 7. Comparing LDPC decoding times for serial and parallel modes, where codes A, B and C represent, respectively, matrices (256, 128), (504, 252) and (1024, 512).
BER curves for WiMAX codes (576, 288) and (1248, 624), considering both 6- and 8-bit data precision representations.
Figure 8. BER curves for WiMAX codes (576, 288) and (1248, 624), considering both 6- and 8-bit data precision representations.

LDPC Decoders for the WiMAX (IEEE 802.16e)based on Multicore Architectures

Gabriel Falcão1, Vitor Silva1, José Marinho1 and Leonel Sousa1

1. Introduction

The WiMAX is a wireless communications standard (IEEE 802.16e) used in small to medium distances in urban areas, that uses Low-Density Parity-Check (LDPC) codes, which are powerful error correcting codes very demanding from a computational perspective [Gallager, 1962, Mackay & Neal, 1996]. The throughput requirements imposed by the WiMAX standard define a maximum of 75 Mbps [IEEE P802.16e/D12, 2005], which typically demands a high number of arithmetic operations and memory accesses per second. In order to accommodate such requirements hardware-dedicated solutions were investigated and developed to deliver such computational power.

With the number of transistors on a die approximately doubling every 18 months, we have seen in last years processors scaling up to hundreds of millions of gates. To overcome power and memory wall constraints, the industry of processors has introduced a new trend: increasing the number of cores per processor rather than using higher clock speeds. Associated to this new paradigm, new kinds of different homogeneous and heterogeneous multicore architectures have been proposed. Initially developed essentially for rendering purposes in the industry of games, recently we have seen multicores start offering new possibilities to support general purpose computing. Nowadays largely disseminated worldwide and supported by appropriate tools, they can be exploited by convenient parallel programming models delivering unmatched performances. This reality introduced the massive generalization of general purpose processing in these parallel architectures.

So far, dedicated VLSI was the only solution capable of decoding LDPC codes at acceptable rates [Brack et al., 2006, Liu et al., 2008]. In this chapter we present a novel, programmable/flexible and scalable parallel LDPC decoding approach for the WiMAX standard based on multicore accelerators such as the Cell/B.E. architecture from Sony-Toshiba-IBM (STI) [Hofstee, 2005, International Business Machines Corporation, 2007, Falcão et al., 2008]. Moreover, we exploit parallel programming models and present parallel algorithms for this architecture [Falcão et al., 2009a]. We also report experimental results and compare them with state-of-the-art LDPC hardware decoding solutions, based on Application Specific Integrated Circuits (ASIC).

Besides the introductory and closure sections, we propose to organize this chapter around five other main sections. The second and third sections introduce, respectively, WiMAX LDPC codes and the algorithms used to perform LDPC decoding. The main characteristics of the Cell/B.E. multicore architecture are presented in section four. The fifth section describes the parallel programming models and the parallel algorithms developed to efficiently implement LDPC decoding. Finally, the experimental results section shows that the obtained throughputs compare fairly against state-of-the-art ASIC LDPC decoders.

2. WiMAX LDPC codes

The WiMAX standard (IEEE 802.16e) works in distances typically below the 10 Km range [Falcão et al., 2008], and uses LDPC codes, whose decoders can be very demanding from a computational perspective. For this reason, they are still implemented using dedicated hardware based on ASIC solutions. LDPCs are linear (n, k) block codes [Lin & Costello, 2004] defined by sparse binary parity-check H matrices of dimension (n-k) x n, and represented by bipartite graphs also called Tanner graphs [Tanner, 1981]. The Tanner graph is formed by Bit Nodes (BNs) and Check Nodes (CNs) linked by bidirectional edges. An example is shown in figure 2.

The Forward Error Correcting (FEC) system of the WiMAX standard is based on a special class of LDPC codes [IEEE P802.16e/D12, 2005] characterized by a sparse binary block parity-check matrix H of the form:

H(nk)×n=[H1H2]=[P0,0P0,1P0,k/z1Pb0I00P1,0P1,1P1,k/z1II0II0Pnk/z2,0Pnk/z2,1Pnk/z2,k/z1IIPnk/z1,0Pnk/z1,1Pnk/z1,k/z1Pbnk/z100I]
(1)

where H1 is sparse and adopted special periodicity constraints introduced in the pseudo random design of the matrix [IEEE P802.16e/D12, 2005; Brack et al., 2006] and H2 is a sparse lower triangular block matrix with a staircase profile. The periodic nature of these codes defines H1 based on permutation sub-matrices Pi,j , which are: (1) quasi-random circularly shifted right identity sub-matrices (I) (as depicted in figure 1), with dimensions z×z ranging from 24×24 to 96×96 and incremental granularity of 4 (table 1); or (2) z×z null sub-matrices. The periodic nature of such codes allowed simplifying the architecture of the system and storage requirements without code performance loss [IEEE P802.16e/D12, 2005]. Also, the right sub-matrix H2 is formed by identity: (1) I sub-matrices of dimension z×z ; or (2) null sub-matrices of dimension z×z

Therefore, the LDPC codes adopted by the WiMAX standard (IEEE 802.16e) support 19 different codeword sizes with 4 distinct code rates (rate=k/n) and 6 different class codes (distinct distributions of the number of BNs per column or CNs per row). They are depicted in table 1. Class 2/3A defines codes having {2, 3, 6} BNs per row and {10} CNs per column, while class 2/3B codes have {2, 3, 4} BNs and {10, 11} CNs. Also, class 3/4A has {2, 3, 4} BNs and {14, 15} CNs, and class 3/4B has {2, 3, 6} BNs per row and {14, 15} CNs per column.

CodeCodeword bits ( n ) z×z factorInformation bits ( k )
(rate)( rate )( rate )( rate )
1/2 2/3 3/4 5/6
1576 24×24 288384432480
2672 28×28 336448504560
3768 32×32 384512576640
4864 36×36 432576648720
5960 40×40 480640720800
61056 44×44 528704792880
71152 48×48 576768864960
81248 52×52 6248329361040
91344 56×56 67289610081120
101440 60×60 72096010801200
111536 64×64 768102411521280
121632 68×68 816108812241360
131728 72×72 864115212961440
141824 76×76 912121613681520
151920 80×80 960128014401600
162016 84×84 1008134415121680
172112 88×88 1056140815841760
182208 92×92 1104147216561840
192304 96×96 1152153617281920

Table 1.

Properties of LDPC codes used in the WiMAX IEEE 802.16e standard.

To illustrate the periodic nature introduced in the design of the H matrix, the generic structure of a sample parity-check matrix used in WiMAX, with n=2304 and rate=1/2, is depicted in figure 1.

3. Algorithms for LDPC decoding (SPA and MSA)

Computationally intensive message-passing algorithms can be used for LDPC decoding, varying from the well known belief propagation, or Sum-Product algorithm (SPA) [Falcão et al., 2009a] to the more efficient but yet still intensive Min-Sum algorithm (MSA) [Falcão et al., 2008]. The intensive message passing procedure is illustrated in figure 2. We will discuss the parallelization of the SPA and MSA, and show how data dependencies can be manipulated in order to allow the implementation of parallel decoders.

media/image34.png

Figure 1.

Periodicity z×z = 96×96 for a matrix with n=2304, rate=1/2 and {3, 6} CNs per column.

3.1. The Sum-Product Algorithm (SPA)

The SPA is a very efficient algorithm [Lin & Costello, 2004] used for LDPC decoding and it is based on the belief propagation between adjacent nodes connected as indicated by the Tanner graph edges (figure 2). As proposed by Gallager, the SPA operates on probabilities [Gallager, 1962, Mackay & Neal, 1996, Lin & Costello, 2004]. Given a (n, k) LDPC code, we assume Binary-Phase Shift Keying (BPSK) modulation which maps a codeword c = (c1, c2,..., cn) into the sequence x = (x1, x2,..., xn), according to xi = (-1)c i. Then, x is transmitted through an additive white Gaussian noise (AWGN) channel originating the received sequence y = (y1, y2,..., yn) on the decoder side, with yi = xi + ni, where ni is a random variable with zero mean and variance σ2.

The SPA is depicted from (2) to (8) [Lin & Costello, 2004]. It is mainly described by two horizontal and vertical intensive processing blocks, respectively defined by equations (3), (4) and (5), (6). The first two calculate messages moving from each CNm to BNn, considering accesses to H on a row basis. It indicates the probability of BNn being 0 or 1. Figure 2 exemplifies, for a particular 4 x 8 H matrix, BN0, BN1 and BN2 being updated by CN0, then BN3, BN4 and BN5 updated by CN1 and finally BN0, BN3, BN6 by CN2. Similarly, the vertical processing block computes messages sent from BNn to CNm, assuming accesses on a column basis. The iterative procedure is stopped if the decoded word ĉ verifies all parity-check equations of the code c^.HT=0 , or a maximum number of iterations I is reached, in which case no codeword is detected.

media/image37.png

Figure 2.

A 4x8 H matrix and corresponding Tanner graph representation. The example shows messages being exchanged from CNm to BNn. A similar representation applies for messages going in the opposite direction.

qnm(0)(0)=1pn; qnm(0)(1)=pn;pn=11+e2ynσ2; EbN0=N2Kσ2{Initialization}
(2)
while ( c.HT0iI) ) { c -decoded word; I-max. number of iterations.}do

{For each node pair (BNn, CNm), corresponding to Hmn= 1 in the parity-check matrix H of the code do:}

{1. Horizontal Processing (kernel 1) – Compute messages sent from CNm to BNn, that indicate the probability of BNn being 0 or 1:}

rmn(i)(0)=12+12n'N(m)\n(12qn'm(i1)(1))
(3)
rmn(i)(1)=1rmn(i)(0)
(4)

{where N(m)\n represents BNs connected to CNm excluding BNn.

{2. Vertical Processing (kernel 2) – Compute messages sent from BNn to CNm:}

qnm(i)(0)=Knm(1pn)m'M(n)\mrm'n(i)(0)
(5)
qnm(i)(1)=Knmpnm'M(n)\mrm'n(i)(1)
(6)

{where knm are chosen to ensure qnm(i)(0)+qnm(i)(1)=1 , and M(n)\m is the set of CNs connected to BNn excluding CNm.}

{3. Compute a posteriori pseudo-probabilities:}

Qn(i)(0)=Kn(1pn)mM(n)rmn(i)(0)Qn(i)(1)=KnpnmM(n)rmn(i)(1)
(7)

{where kn are chosen to guarantee Qn(i)(0)+Qn(i)(1)=1 .}

{Perform hard decoding} n ,

c^n(i)={1Qn(i)(1)0.50Qn(i)(1)0.5
(8)
end while

3.2. The Min-Sum Algorithm (MSA)

The MSA [Guilloud et al., 2003] is a simplification of the well-known SPA in the logarithmic domain. It is also based on the intensive belief propagation between nodes connected as indicated by the Tanner graph edges, but that uses only comparison and addition operations. Being one of the most efficient algorithms used for LDPC decoding [Liu et al., 2008, Seo et al., 2007], even so, the MSA still requires intensive processing.

Let us denote the log-likelihood ratio LLR of a random variable as L(x) = ln (p(x = 0)/p(x = 1)). Also, considering the message propagation from nodes CNm to BNn and vice-versa, the set of bits that participate in check equation m with bit n excluded is represented by N(m)\n and, similarly, the set of check equations in which bit n participates with check m excluded is M(n)\m. LPn designates the a priori LLR of BNn, derived from the values received from the channel, and Lrmn the message that is sent from CNm to BNn, computed based on all received messages from BNs N(m)\n. Also, Lqnm is the LLR of BNn, which is sent to CNm and calculated based on all received messages from CNs M(n)\m and the channel information LPn. For each node pair (BNn, CNm) we initialize Lqnm with the a priori log-likelihood ratio (LLR) information received from the channel, LPn. Then, we proceed to the iterative body of the algorithm by calculating (9) and (10), respectively, where Lrmn denotes the message sent from CNm to BNn, and Lqnm the message sent from BNn to CNm.

{1. Horizontal Processing (kernel 1) – Compute messages sent from CNm to BNn:}

Lrmn(i)=n'N(m)\nsign(Lqn'm(i1))minn'N(m)\n|Lqn'm(i1)|
(9)

{2. Vertical Processing (kernel 2) – Compute messages sent from BNn to CNm:}

Lqnm(i)=LPn+m'M(n)\mLrm'n(i).
(10)

{3. Finally, we calculate the a posteriori pseudo-probabilities and perform hard decoding: }

LQn(i)=LPn+m'M(n)Lrm'n(i).
(11)

4. The Cell/B.E. multicore architecture

The required computational power and the irregular memory access patterns for LDPC decoding define hard challenges that we propose to tackle for the heterogeneous Cell/B.E. multicore [Hofstee, 2005] shown in figure 3. The Cell/B.E. processor provides a set of cores that include one main 64-bit PowerPC Processor Element (PPE) and eight Synergistic Processor Elements (SPEs) under a vectorized 128-bit wide Single Instruction Multiple Data (SIMD) oriented architecture [Sony Computer Entertainment Incorporated, 2005]. Data transfers between the main memory and each SPE’s local memory (256KByte) are performed by using efficient Direct Memory Access (DMA) mechanisms that offload the processors from the expensive task of moving data. Each SPE, by its turn, exploits quite efficiently a dual pipeline mechanism executing independently: one supports arithmetic operations; while the other performs load and store memory operations.

The memory in the CELL/B.E. is organized as a distributed memory system. Data is loaded from the main memory into the SPE’s local storage and vice-versa, allowing each processor to exploit data locality individually. As in opposition to architectures based on shared memory models, here the programmer is free from having to deal with strategies to avoid memory access conflicts.

media/image56.png

Figure 3.

Generic overview of the Cell/B.E. architecture.

5. The parallel programming model and parallel algorithms for LDPC decoding on multicores

The Single Program Multiple Data (SPMD) and the SIMD programming models are adopted to exploit data parallelism and to develop the parallel methods and algorithms for LDPC decoding on the Cell/B.E. A vectorized SIMD-based multicore approach that exploits data locality and fast data-block transfers associated to a powerful dual pipeline mechanism, allowed us to efficiently implement the concept of simultaneous multicodeword LDPC decoding on the Cell/B.E. Each SPE decodes several complete codewords and a total of 24 to 96 codewords, depending if we use 32- or 8-bit data precision, are decoded in parallel and at the same time in all the 6 SPEs available on the PlayStation 3 platform used in this work.

media/image57.png

Figure 4.

Parallelization model for an LDPC decoder on the Cell/B.E. architecture.

The parallel LDPC decoder exploits SIMD data-parallelism by applying the same algorithm to different codewords on each SPE. As the Tanner graph is common to all codewords under decoding, these data structures can be shared allowing multicodeword decoding simultaneously in all SPEs. These features are illustrated in figure 4.

The irregular memory access patterns common in LDPC decoding represent a challenge to the efficiency of the algorithm as illustrated in figure 5 for the example shown in figure 2. The access to different nodes in the Tanner graph is defined by the H matrix and should favor randomization in order to allow good coding gains. For that reason, the data structures developed and represented in figure 6 try to minimize that effect, by grouping contiguously in memory associated data computed in the same kernel. A global irregular access pattern is translated into several partial regular access patterns. Moreover, only non-null elements of the H matrix are stored which represents savings in terms of memory usage.

media/image58.png

Figure 5.

Illustration of irregular memory accesses for the example shown in figure 2.

5.1. The parallel algorithm on the Cell/B.E.

The parallelization approach proposed for developing an LDPC decoder is explained in the context of the Cell/B.E. architecture. The data structures that define the Tanner graph and the program as well are loaded into the local storage on the SPEs where the processing is performed. The LDPC decoder processes on an iterative basis. The PPE reads information yn from the input channel and produces the probabilities pn as indicated in (2). The PPE controls the main tasks, offloading the intensive processing to the SPEs, where the processing is then distributed over several threads. Each SPE runs independently of the other SPEs. After receiving the pn values associated to the corresponding codewords, each SPE performs two steps: (i) computes kernel 1 and kernel 2 alternately using SIMD instructions; and (ii) sends the final results back to the PPE, which concludes the computation of the current codewords and starts new ones by replacing data to be sent to the SPEs.

media/image59.png

Figure 6.

Segment of the SIMD vectorized data structures in memory to represent: a) rmn/Lrmn messages associated to BNs; and b) qnm/Lqnm messages associated to CNs.

The parallel LDPC decoder explores data-parallelism by applying the same algorithm to several codewords simultaneously on each SPE (as shown in figure 4). Data is represented as 32-bit precision floating-point or 8-bit integer elements, depending on the algorithm used – SPA or MSA. The proposed LDPC decoder suits scalability and for that reason it can be easily adopted by future generations of the architecture with a higher number of SPEs. In that case, it will be able of decoding more codewords simultaneously, increasing the efficiency and aggregate throughput of the decoder.

Processing a complete iteration inside the SPE is performed in two phases: (i) kernel 1 computes data according to (3) and (4) for the SPA or (9) for the MSA, where the horizontal processing (row-major order) is performed. The data structure designed to represent rmn/Lrmn in order to perform this task is depicted in figure 6 a). It can be seen in this figure that data related to BNs common to a CN equation is stored in contiguous memory positions to optimize processing; and (ii) kernel 2 processes data according to (5) and (6) for the SPA or (10) for the MSA, performing the vertical processing (column-major order). The qnm/Lqnm data structure used in this case is depicted in figure 6 b). The SPE accesses data in a row- or column-major order, depending on the kernel that is being processed at the time. Also, the parallel algorithm implemented exploits the double buffering technique by overlapping processing and data accesses in memory.

Kernel 1 performs the horizontal processing according to the Tanner graph, and the rmn(i)/Lrmn(i) data is updated for iteration i. The data is initially transferred to the local storage of the SPE by performing a DMA transaction, and its access organization maximizes data reuse, because a CN updating BNs reads common information from several BNs that share data among them. Figure 6 b) shows the data structures that hold the qnm/Lqnm values to be read and also the corresponding indexes of the rmn/Lrmn elements in figure 6 a) that they are going to update. As depicted in figure 6, BNs and CNs associated with the same rmn/Lrmn or qnm/Lqnm equation are represented in contiguous blocks of memory.

In kernel 2 data is processed in a column-major order. According to the Tanner graph, each BN updates all the CNs connected to it and holds the addresses necessary to complete the update of all qnm(i)/Lqnm(i) data for iteration i. Once again, maximum data reuse is achieved, but this time among data belonging to the same column of the H matrix, as depicted in figures 2 and 6 b).

The computation is performed in the SPE for a predefined number of iterations. One of the purposes of this work is to assess the performance of the proposed solutions in terms of throughput. Pursuing this goal, we decided to develop a solution where the number of iterations is fixed to allow a fair comparison between different approaches, where the processing workload is known a priori and the same for all environments. This is why, at the end of an iteration, we don't check if the decoder produces a valid codeword, which could cause the decoding process to stop. Nevertheless, this operation represents a negligible overhead. The iterative updating mechanism applied to BNs and CNs is performed in a sequence of pairs (BN, CN) and tested for a number of iterations ranging from 10 to 100. When all the BNs and CNs are updated after the final iteration, the SPE activates a DMA transaction and sends data back to the main memory, signalizing the PPE to conclude the processing. As the DMA finishes transferring data, synchronization points are introduced to allow data buffers reuse.

Algorithm 1 PPE side of the algorithm
for th_ctr=1 to NSPEs: do    Create th_ctrt hreadendforrepeat    Receive yn from the channel and calculate pn probabilities    Send msg NEW_WORD to MASTER SPEEnsure: Wait until mail is received (SPE[i].mailboxcount0) from MASTER SPE    msg=SPE[i].mailbox(received msg END_DECODE from MASTER SPE)until true

Table 2.

Synchronization between the PPE and the SPEs is performed using mailboxes. This approach tries to exploit data-parallelism and data locality by performing the partitioning and mapping of the algorithm and data structures over the multiple cores, while at the same time minimizes delays caused by latency and synchronization.

5.2. Processing on the PPE

The part of the algorithm that executes on the PPE side is presented in Algorithm 1. We force the PPE to communicate with only one SPE, called MASTER SPE, which performs the control over the remaining SPEs. This is more efficient than putting the PPE controlling all the SPEs.

Algorithm 2 MASTER SPE side of the algorithm
repeatEnsure: Read mailbox (waiting a NEW_WORD mail from PPE)    Broadcast msg NEW_WORD to all other SPEs    Get pn probabilities    for i=1 to N_Iter: do        Compute rmn/Lrmn        Compute qnm/Lqnm    endfor    Put final Qn values on the PPEEnsure: Read mailbox (waiting an END_DECODE mail from all other SPEs)    Send msg END_DECODE to PPEuntil true

Table 3.

The PPE receives the yn information from the channel and calculates probabilities pn, after which it sends a NEW_WORD message to the MASTER SPE. Then, it waits for the download of all pn probabilities to the SPEs and for the processing to be completed in each one of them.

Algorithm 3 SLAVE SPE side of the algorithm
repeatEnsure: Read mailbox (waiting a NEW_WORD mail from MASTER SPE)    Get pn probabilities    for i=1 to N_Iter: do        Compute rmn/Lrmn        Compute qnm/Lqnm    endfor    Put final Qn values on the PPE    Send msg END_DECODE to MASTER SPEuntil true

Table 4.

Finally, when all the iterations are completed, the MASTER SPE sends an END_DECODE message to the PPE to conclude the current decoding process and get ready to start processing a new set of codewords.

5.3. Processing on the SPE

The SPEs are used in the intensive task of updating all BNs and CNs by executing kernels 1 and 2 (either for the SPA or for the MSA), in each decoding iteration. Each thread running on the SPEs accesses data in the main memory by using DMA and computes data according to the Tanner graph, as defined in the H matrix (figure 2). The MASTER SPE side of the procedure is described in Algorithm 2. The Get operation is adopted to represent a communication PPE SPE, while the Put operation is used for communications in the opposite direction.

We initialize the process and start an infinite loop, waiting for communications to arrive from the PPE (in the case of the MASTER SPE), or from the MASTER SPE (for all remaining SPEs). In the MASTER SPE, the only kind of message expected from the PPE is a NEW_WORD message. When a NEW_WORD message is received, the MASTER SPE broadcasts a NEW_WORD message to all other SPEs and loads corresponding pn probabilities. After receiving these messages, each one of the other SPEs gets its own pn values.

The processing starts and terminates when the number of iterations is reached and an END_DECODE mail is sent by all SPEs to the MASTER SPE, which immediately notifies the PPE with an END_DECODE message, as described in Algorithms 2 and 3.

The intensive part of the computation in LDPC decoding on the Cell/B.E. architecture takes advantage of the processing power and SIMD instruction set available on the SPEs, which means that several codewords are decoded in parallel.

6. Experimental evaluation

To evaluate the performance of the proposed LDPC decoder, the Cell/B.E. was programmed using: (i) the PPE alone which is denoted by serial mode in figure 7; and (ii) the complete set of PPE and 6 SPE processors denoted by parallel mode in the same figure. The Cell/B.E. under test is included in a PlayStation 3 (PS3) platform, which restricts the number of available SPEs to 6, from a total of 8. The experimental setup of the PS3 platform is presented in table 2.

Serial modeParallel m ode
PlatformPPESTI Cell/B.E.
LanguageCC
OSLinux (Fedora) kernel 2.6.16
PPESPE
Clock frequency3.2GHz3.2GHz3.2GHz
Memory256MB256MB256KB

Table 5.

Experimental setup.

6.1. Serial versus parallel execution modes

The serial mode depicted in figure 7 uses a dual thread approach and exploits SIMD instructions. It should be noted that by performing the comparison based on the time per bit decoded, the serial solution that uses only the PPE is slower than the execution on a single SPE, because the PPE accesses slow main memory, while the SPE accesses faster local storage memory.

Code (n, k)EdgesOccupancy of data structures on the local storage of a SPE (Bytes)
(504, 252)151270560
(1024, 512)3072143360

Table 6.

Size of data structures used in each SPE in parallel decoding mode.

On the parallel approach the experimental results were also obtained using SIMD instructions on the SPEs, which are responsible for executing the intensive decoding part of the algorithm. In this case the PPE orchestrates the execution on the SPEs as explained before, while inside each SPE several codewords are being simultaneously decoded in parallel. All the processing times were measured for a number of iterations ranging from 10 to 100. In literature, the average number of iterations considered for WiMAX LDPC decoders to work under realistic conditions is typically below 20 iterations [Brack et al., 2006, Seo et al., 2007, Liu et al., 2008].

media/image73.png

Figure 7.

Comparing LDPC decoding times for serial and parallel modes, where codes A, B and C represent, respectively, matrices (256, 128), (504, 252) and (1024, 512).

Table 3 shows the dimensions of two regular LDPC codes with rate=1/2, the corresponding number of edges and the size of data structures used to represent the Tanner graph. The local memory of the SPE is limited to 256 KByte. It should be taken in consideration that the SPE’s local memory should hold both data structures and also the program.

6.2. LDPC decoding using the SPA

The first parallel approach mentioned in 6.1 uses the SPA. Data elements have 32-bit floating-point precision, and 4 floating-point elements are packed and operated on a single instruction, making it possible to decode 4 codewords in parallel on each SPE. Then, with 6 SPEs available, the global architecture can decode 24 codewords in simultaneous. We assessed the results for regular codes, which typically execute faster than irregular ones. The average throughput obtained is presented in table 4, and it ranges from 69.1 to 69.5 Mbps, when decoding regular codes (504, 252) and (1024, 512) in 10 iterations. It should be noticed that the decoding time per bit and per iteration remains approximately constant. Although real-life performances demand throughputs which can be typically in the order of 40 Mbps per channel, the theoretical maximum required by the WiMAX standard can go up to approximately 75 Mbps per channel. The throughputs reported in table 4 are inferior to 70 Mbps and do not guarantee such requirements. Also, adapting the algorithm to support the necessary irregular codes used in the WiMAX would produce even worst results, because in that case accesses to memory depend on a variable number of edges per row/column. Therefore, optimizing the LDPC decoding algorithm to make it execute in a shorter period of time became mandatory. One possible solution consisted of exploiting the computationally less demanding MSA described in section 3.2.

Code ( n, k )r ate10 iter.25 iter.50 iter.
(504, 252)1/269.128.314.2
(1024, 512)1/269.528.414.3

Table 7.

Throughput (Mbps) obtained in the parallel mode for the SPA.

6.3. LDPC decoding using the MSA

To increase the efficiency of the LDPC decoder we implemented the MSA on the Cell/B.E. It requires less computation, based essentially in addition and comparison operations [Falcão et al., 2009b]. Additionally, we also adopted the Forward-and-Backward simplification of the algorithm [Mackay, 1999] that avoids redundant computation and eliminates repeated accesses to memory. In the MSA data elements have 8-bit integer precision, which allows packing 16 data elements per 128-bit memory access. This increases the arithmetic intensity of the algorithm, here defined as the number of arithmetic operations per memory access, which favors the global performance of the LDPC decoder. The instruction set of the Cell/B.E. architecture supports intrinsic instructions to deal efficiently with these parallel 128-bit data types. Moreover, because there are 6 SPEs available, the algorithm now supports the simultaneous decoding of 96 codewords in parallel. However, the set of 8-bit integer intrinsic parallel instructions of the Cell/B.E. is more limited than those of the 32-bit floating-point family of instructions. This explains that the speedup obtained when changing from the SPA to the MSA is lower than we would expect. Table 5 shows the throughputs obtained for some example codes used in the WiMAX IEEE 802.16e standard. For 10 iterations, in some cases they approach quite well while in others they even surpass the 75 Mbps required by the standard to work in (theoretical) worst case conditions.

Code ( n, k )r ate10 iter.25 iter.50 iter.
(576, 288)1/279.832.716.5
(576, 432)3/47 3 . 129. 915.1
(576, 480)5/67 9 . 33 2 . 516.4
(672, 448)2/374.830.615.4
(672, 504)3/472.629.715.0
(672, 560)5/678.532.216.2
(960, 480 )1/279.632.616.4
(960, 640 )2/374.730.615.4
(960, 720 )3/472.629.715.0
(960, 800 )5/678.432.116.2
( 1152 , 576 )1/279.632.616.4
( 1152 , 768 )2/374.630.515.4
( 1152 , 864 )3/472.629.715.0
( 1152 , 960 )5/678.432.116.2
(1248, 624)1/279.632. 616.4
(1248, 832)2/378.532.216.2
(1248, 936)3/472. 729. 715.0
(1248, 1040)5/678. 432. 116.2

Table 8.

Throughput (Mbps) obtained in the parallel mode for the MSA.

For codes with n=576 running 10 iterations, it can be seen that throughputs range from 73.1 to 79.8 Mbps. For codes with n=1248 and for the same number of iterations, they vary from 72.7 to 79.6 Mbps. All codes in table 5 were tested for the MSA and approach quite well the maximum theoretical limit of 75 Mbps. They all show better performances than those obtained with the SPA. Furthermore, if we consider a lower number of iterations, the decoder’s throughput may rise significantly. For example, if we consider an LDPC decoder running 5 iterations, the throughput will approximately double to values above 145Mbps.

6.4. Discussion

In multicore architectures, efficient parallel programming, both in terms of computation and memory accesses, represent a significant challenge. The Cell/B.E. is based on a distributed memory model where the problem of data collisions can decrease when properly handled by the programmer. The reported experimental results allow assessing the performance of LDPC decoders based on multicores. We have shown that for LDPC decoders running the SPA on the Cell/B.E., throughputs can range from 68 to nearly 70 Mbps [Falcão et al., 2009a]. Concerning the MSA, a more efficient solution is achieved producing throughputs that range from 72 to 80 Mbps [Falcão et al., 2008]. Regarding to non-scalable hardware dedicated ASIC solutions, which typically adopt 5 to 6-bit precision arithmetic [Liu, 2008], the parallel programmable architecture here proposed allows using 8-bit data precision or even more, which produces lower Bit Error Rates (BER) and superior coding gains as depicted in figure 8. The adoption of specific parallelization techniques on a low-cost multicore platform allowed us to achieve throughputs that approach well those obtained with ASIC-based solutions for WiMAX [Brack, 2006, Seo, 2007, Liu, 2008]. They also guarantee enough bandwidth for LDPC codes used in the WiMAX standard to work in worst case conditions.

media/image74.png

Figure 8.

BER curves for WiMAX codes (576, 288) and (1248, 624), considering both 6- and 8-bit data precision representations.

7. Conclusions

The advent of inexpensive multicore architectures has allowed to develop a novel programmable LDPC decoding solution for the WiMAX standard, with excellent throughputs, on the Cell/B.E. architecture. The LDPC decoder here presented exploits parallelism and data locality and is scalable to future generations of the Cell/B.E. architecture that are expected to have more SPEs, and should therefore improve the performance even further, processing more channels/subcarriers per second. The proposed decoder compares well with non-scalable and hardware-dedicated typical ASIC LDPC decoding solutions, reporting superior BER performances and throughputs above 72 Mbps.

On going additional work related with LDPC decoders running on alternative parallel architectures can be found in [Falcão et al., 2009b; Seo et al., 2007].

References

1 - T. Brack, M. Alles, F. Kienle, N. Wehn, 2006 A Synthesizable IP Core for WIMAX 802.16E LDPC Code Decoding, Proceedings of the IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications, 1 5 , September 2006.
2 - G. Falcão, V. Silva, L. Sousa, J. Marinho, 2008 High coded data rate and multicodeword WiMAX LDPC decoding on the Cell/BE. IET Electronics Letters, 44 24 November 2008, 1415 1417 .
3 - G. Falcão, L. Sousa, V. Silva, J. Marinho, 2009a Parallel LDPC Decoding on the Cell/B.E. Processor, Proceedings of the 4th International Conference on High Performance and Embedded Architectures and Compilers (HiPEAC 2009), 389 403 , Paphos, Cyprus, January 2009, Lecture Notes in Computer Science, Springer, 5409
4 - G. Falcão, V. Silva, L. Sousa, 2009b How GPUs Can Outperform ASICs for Fast LDPC Decoding, Proceedings of the 23rd International Conference on Supercomputing (ICS), New York, USA, June 2009, 390 399
5 - R. Gallager, 1962 Low-Density Parity-Check Codes. IRE Transactions on Information Theory, 8 1 January 1962, 21 28 .
6 - F. Guilloud, E. Boutillon, J. Danger, L. , 2003 λ-min decoding algorithm of regular and irregular LDPC codes. Proceeding of the 3rd Int. Symp. Turbo Codes Relat. Topics, 1 4 , September 2003.
7 - H. Hofstee, 2005 Power Efficient Processor Architecture and the Cell Processor, Proceedings of the 11th International Symposium on High-Performance Computer Architectures (HPCA), 258 262 , San Francisco, CA, USA, February 2005.
8 - IEEE P802.16e/D12 2005 Draft IEEE Standard for Local and Metropolitan Area Networks. Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems, October 2005.
9 - International Business Machines Corporation 2007 Synergistic Processor Unit Instruction Set Architecture, IBM Systems and Technology Group.
10 - S. Lin, D. Costello, 2004 Error Control Coding, Prentice Hall, second edition, ISBN-13 978 0130426727 .
11 - C. H. Liu, S. W. Yen, C. L. Chen, H. C. Chang, C. Y. Lee, Y. S. Hsu, S. J. Jou, 2008 An LDPC Decoder Chip Based on Self-Routing Network for IEEE 802.16e Applications. IEEE Journal of Solid-State Circuits, 43 3 March 2008, 684 694 .
12 - D. Mackay, R. Neal, 1996 Near Shannon Limit Performance of Low Density Parity Check Codes. IEE Electronics Letters, 32 18 August 1996, 1645 1646 .
13 - D. Mackay, 1999 Good Error-Correcting Codes Based on Very Sparse Matrices.. IEEE Transactions on Information Theory, 45 2 March 1999, 399 431 .
14 - S. Seo, T. Mudge, Y. Zhu, C. Chakrabarti, 2007 Design and Analysis of LDPC Decoders for Software Defined Radio, Proceedings of the IEEE Workshop on Signal Processing Systems, 210 215 , October 2007.
15 - Sony Computer Entertainment Incorporated 2005 SPU C/C++ Language Extensions, Sony Corporation.
16 - R. Tanner, 1981 A Recursive Approach to Low Complexity Codes.. IEEE Transactions on Information Theory , 27 5 September 1981, 533 547 .