Saeed Ur

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders

Keywords: Config, 3 Non-Shuffled Butterfly 16 YES Config, 4 Non-Shuffled Butterfly Config, 5 Non-Shuffled Butterfly

We live in the era of high data rate wireless applications (smart-phones, net-books, digital television, mobile broadband devices…) in which advanced technologies are included such as OFDM, MIMO and advanced error correction techniques to reliably transfer data at high rates on wireless networks. Turbo and LDPC codes are two families of codes that are extensively used in current communication standards due to their excellent error correction capabilities. For high throughput performance, decoders are implemented on parallel architectures in which more than one processing elements decode the received data. However, parallel architectures suffer from memory conflict problem. It increases latency of memory accesses due to the presence of conflict management mechanisms in communication network and unfortunately decreases system throughput while augmenting system cost.

To tackle memory conflict problem, three different types of approaches are used in literature. In first type of approaches, "architecture friendly" codes are constructed with good error correction capabilities in order to reduce hardware cost. However, these codes originate problem at the channel interleaver. In the second type of approaches, flexible and scalable interconnection network are introduced to handle memory conflicts at run time. However, flexible networks suffer from large silicon area and increased latency. The third type of approaches are design time memory mapping approaches in which the resultant architectures consist of ROM blocks used to store configuration bits. The use of ROM blocks may be sufficient to design parallel architecture that supports single codeword or single application.

However, to design hardware architecture that supports complete standard or different applications, ROM based approaches result in huge hardware cost. To reduce hardware cost, optimizations are required to use as less ROMs as possible to support different applications.

In this thesis, we aim to design optimized parallel architectures. For this purpose, we have proposed two different categories of approaches. In the first category, we have proposed two optimized design time off-chip approaches that aim to limit the cost of final decoder architecture targeting the customization of the network and the use of in-place memory architecture.

In the second category, we have introduced a new method in which both runtime and design time approaches are merged to design flexible decoder architecture. For this purpose, we have embedded memory mapping algorithms on-chip in order to execute them at runtime to solve conflict problem. The on-chip implementation replaces the multiple ROM blocks Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

2.Dedicated approach to explore design space of turbo decoder architecture 2.1.Turbo decoder architecture - -----------------------------------------------35 2.2.Proposed design flow - ------------------------------------------------------36 2.2.1.Shuffled decoding memory issues - ------------------------------------------ ---------------------------------------------------38 2.3.Case study: Turbo decoder for LTE - ------------------------------------39 3.Memory mapping approach based on network customization 3.1.Proposed Approach ---------------------------------------------------------43

2.2.2.Solving memory conflicts -

3.1.1.Memory Mapping with Network Relaxation ------------------------------43 3.1.2.Pedagogical Example --------------------------------------------------------46

3.2.Experiments and Results ---------------------------------------------------48 -------------------------------------------------------60 3.Design Flow 62 3.1.Graph construction - ---------------------------------------------------------63 3.2.Bipartite test - ----------------------------------------------------------------- -----------------------------------------------------------66 3.4.Vizing theorem for edge coloring - ----------------------------------------67 3.4.1.Pedagogical Example --------------------------------------------------------73 3.5.In-place memory mapping for multigraphs - -----------------------------78 3.5.1. Modeling -----------------------------------------------------------------------79 3. 5 Graph ----------------------------------------------------------------------------------------------------- --------------------------------------------------------84 4.Experiments and results 87 4.1.Case study-1: Shuffled turbo decoders for LTE - -----------------------87 4.2.Case study-2: Non-Binary LDPC codes ---------------------------------88 ------------------------------------------------------------------------ -----------------------------------------------------98 2.2.Generation of data access order - ------------------------------------------99 2.3.Execution of memory mapping approach - -----------------------------104 2.4. Routing Algorithm --------------------------------------------------------106 2. 4 Algorithm ------------------------------------------ The channel encoder and decoder are responsible for the reliable transfer of data for which forward error correction (FEC) codes are widely used. FEC codes are among the significant parts of the whole system. FEC codes are described in the next section.

3.2.1.Case study for HSPA ---------------------------------------------------------49 3.2.2.Case study for LTE ----------------------------------------------------------

.2.Transformation of bipartite graph into Transportation Matrix ---------------------------------------------------------------------------------------------------81 3.5.3.Algorithm to find semi 2-factors in Turbo Bipartite

4.2.1.Vizing theorem for non-binary LDPC codes -----------------------------90 4.2.2.Results -

.1.Example for Routing

List of Tables

Forward Error Correction (FEC) Coding

We are now moving through the 4 th generation of wireless communication systems which are expected to achieve high data rates and reliable data transfer. Since error correction is one of the complex and power consuming part of whole transceiver design, therefore extensive research was carried out in the field of channel coding especially Forward Error Correction (FEC). Research in the field of FEC codes is aimed to find the best possible error correcting codes allowing high throughput decoding and their efficient VLSI implementation in term of area, speed and power consumption. In block codes, original information sequence is first divided into different blocks and then each block is independently encoded to generate code-word bits. The encoder must wait for the whole message block before starting the encoding step. However, in convolutional Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 encoder the code-word is transmitted as soon as encoding is started without any wait to obtain the entire message.

Two main error correcting codes families are used in current telecommunication standards. One from convolutional codes called Turbo codes and another from block codes called Low Density Parity Check (LDPC) codes. These two error correcting codes are widely used due to their excellent error correcting capabilities. However, implementation of decoders for these two codes for high data rate applications is a challenging task. In this thesis, we focus on the implementation of both of these codes on parallel architectures.

Introduction to Turbo codes

Due to their excellent error correction capabilities, Turbo codes [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes. 1[END_REF] are part of most of the current telecommunication standards such as [START_REF]Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access; Multiplexing and Channel Coding (Release 8)[END_REF] [HSP04] [DVBS08]. They are constructed through the parallel concatenation of two "simple" convolutional codes that share their information during the decoding step. The first convolution encoder encodes the message x in natural (original) order to produce p (1) parity bits, whereas the second one encodes the message in interleaved order (after passing the original message through interleaver) to generate p (2) parity bits. The output turbo codeword c is composed of the original message and parallel concatenation of parity bits.

Interleaver

Code 2 encoder Code 1 encoder

P (2) P (1) x C = x p (1) p (2) Figure 1. 2. Turbo Encoder
The high performances of turbo codes are due to the presence of this pseudo-random interleaver. Interleaving (Π) is a permutation law that scrambles data to break up neighbourhood-relations. It is a key factor for turbo-codes performances, which vary from one standard to another. The low-complexity iterative decoding algorithm for turbo-decoding makes its hardware implementation possible with the current standards. However, in order to achieve high throughput architectures, we will see that this interleaver generates memory access conflicts when parallel architectures are used. The turbo decoder receives input values Y (u) , Y (1) , Y (2) from the channel (resp. for x, p (1) , p (2) ). One complete iteration of turbo decoder is carried out through two half iterations.

Designing

Firstly Code 1 Decoder receives channel values for message bit Y (u) , first parity bit Y (1) and deinterleaved extrinsic value from Code 2 Decoder to generate extrinsic value. Then, during the second half iteration, Code 2 Decoder creates extrinsic value from interleaved message bits, second parity bit Y (2) and interleaved extrinsic value from Code 1 Decoder. The final decision about the message bits is made based on the extrinsic values from the two decoders and channel values for message bits, after a fixed number of decoding iterations. In a LDPC code, codeword constraints (or parity check equations) are often expressed in matrix form as follows:

Introduction to LDPC codes

Low

1 2 3 4 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 c c c c H               =                  
The above H matrix is an M * N binary matrix where each row M i of H corresponds to a parity check equation whereas each column N j associated with codeword bit. A nonzero entry at (i, j) th location means that the j th codeword bit is included in the i th parity check equation. For a codeword x ∈ C to be valid, it must satisfy all parity check equations.

LDPC codes can also be graphically

Memory conflict problem

In order to achieve high throughput performance, parallel hardware architectures are needed. The implementation of a typical parallel architecture is shown in Figure 1. 5. In this architecture, P processing elements (PEs) are used to process data elements which are connected to B memory banks through interconnection network, where P = B.

Unfortunately this kind of parallel architectures generates memory access conflicts as soon as several PEs simultaneously try to access to the same memory bank. This problem is also called "collision problem" [START_REF] Giulietti | Parallel turbo coding interleavers: avoiding collisions in accesses to storage elements[END_REF]. Memory conflict problem is a major source of concern in designing parallel architectures. The memory conflict problem is explained for turbo and LDPC codes in the two following sub-sections.

Memory conflict problem for Turbo Codes

In parallel implementation of turbo codes, different number of processing elements access the data elements from the banks first in the natural order and then in interleaved order.

The memory conflict problem for turbo codes is explained here with a pedagogical example.

Let us consider L = 20, P = B = 4, M =5 and T = 10, where L is the number of data elements, B is the number of memory banks, M= L/B is the size of each memory bank and T is the total number of time accesses. The data elements are accessed first in natural order and then in interleaved order shown in Figure 1. 6.

Memory conflict problem for LDPC Codes

The memory conflict problem for the LDPC codes is different from turbo codes due to the difference in codes construction of these codes. The data access pattern of turbo codes are represented by natural and interleaved order matrices whereas LDPC codes are specified by their H matrices and represented by tanner graphs which shows that how data (variable nodes) must be processed by the processing elements (check nodes) in order to achieve good error correction performances. In order to explain a memory conflict problem in LDPC codes, let us consider L = 6, P = B = 3, M = 2 and T = 6 as shown in data access matrix in Figure 1. respectively. There is no conflict at time instances t 1 but at t 2 more than two processors want to access the same memory bank.

Chapter 3

In this chapter, we present our first approach that aims to limit the cost of final decoder architecture by targeting the customization of the network at the design time (offchip). In the beginning, shuffled and non-shuffled turbo scheduling schemes are explored.

Then, the proposed approach based on network relaxation method is described in details.

Different experiments are performed for different test cases by using the proposed approach.

Chapter 4

In this chapter, our second contribution is presented. This approach is based on inplace memory mapping architectures in order to generate optimized hardware decoders at design time. We propose different algorithms based on Vizing theorem and transportation problem in order to solve memory conflict problem in polynomial time while providing optimized decoders.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Chapter 5

Finally, we present an on-chip approach to support multiple standards/applications in order to generate optimized hardware architecture. In order to avoid multiple ROM blocks needed to store controller information, we propose to embed memory mapping approaches on-chip such that complete multiple standards can be supported.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Chapter 2

STATE OF THE ART

. Introduction ---------------------------------------------------------------------------------17 2.
Avoiding conflicts during the code construction ------------------------------------17 3. Solving conflicts by means of dedicated runtime approaches --------------------21 4. Solving conflicts with dedicated memory mapping approaches -----------------24 4.1. Memory mapping approaches -----------------------------------------------------------25 4.2. Architecture for design time memory mapping approaches ------------------------28 4.2.1. In-place memory mapping architecture -

--------------------------------------------28 4.2.2. MRMW architecture --------------------------------------------------------------------29 5. Conclusion -----------------------------------------------------------------------------------31

Introduction

Forward error correction codes are used for reliable data transfers between transmitters and receivers. In the associated decoders, parallel architectures are used to achieve high throughput performances. However, these kinds of architectures suffer from memory conflict problem. Many approaches are proposed in literature in order to overcome this issue. In this chapter, different approaches are discussed to implement parallel architectures taking into account the conflict problem for Turbo and LDPC decoders. These approaches can be classified in three categories.

In the first family of approaches, conflict free interleaving laws are defined. The goal is to construct codes with good error correction capabilities, reduced hardware cost and that allow avoiding memory conflicts. In the second family of approaches, conflicts are solved at run time by using flexible and scalable interconnection networks with sufficient path diversity (routing mechanism) and/or buffering techniques to handle memory conflicts. The third family of approaches deals with algorithms that assign data in memory in such a manner that all the processing elements can access memory banks concurrently without any conflict.

These approaches which resolve the memory conflict problem at design time are referred as memory mapping approaches.

These families are described in detail in the three following sections.

Avoiding conflicts during the code construction

In

Π(x) = (f 1 x 2 + f 2 x) mod L
where x and Π(x) represents the natural and interleaved address respectively and variables f 1 , f 2 are different for different block lengths as specified in the standard.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

In [START_REF] Takeshita | On maximum contention-free interleavers and permutation polynomials over integer rings[END_REF], QPP interleaver is proved to be contention-free for every window size that is a factor of interleaver length. However, it is not contention-free for other data rates in which high level parallelisms are used in the decoder.In [BOH07], a new interleaver for turbo codes is proposed. The interleaver is described by using four successive distinct laws and can also be defined using simple matrix S of size L x L where L is the size of the frame. This matrix is composed of k circularly right shifted z x z matrices (like in LDPC codes). The amount of shift is denoted by δ(r) and it is located at position P(r) of the matrix. In this approach, first the frame with L = k.z elements is interleaved by z-row m-column permutations. Secondly, each group r (where r = [0, k-1]) of z elements is right shifted by δ(r)

positions. Finally, in the last step the group of z elements is interleaved. . This interleaver has good performance and low-complex hardware implementation for high parallelized turbo decoders as compared to 3GPP-LTE interleaver.

However, this interleaver is not a part of the current telecommunication standards. where each sub-matrix is obtained by permuting rows of the identity matrix as shown in Moreover, it must be observed that the conflict free data access order in the decoder part of the architecture can be different from the data access order coming from the channel as it is the case in QPP interleaver for example. This issue reports hence the conflict problem on the channel interleaver side.

Y 1 Y 2 Y 3 Y 4 CNs 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 VNs Y 1 Y 2 Y 3 Y 4 X 1 X 2 X 3 X 4 X 5 X

Solving conflicts by means of dedicated runtime approaches

The second family of solutions solves memory access conflict problem by storing the data elements in different memory banks in an arbitrary order and then use additional mechanism (buffering/routing) in the interconnection network to manage conflicts at runtime.

These approaches are referred as run time conflict resolution. However, we have referred these approaches as time relaxation methods in this document.

Such approach is presented in [START_REF] Thul | Enabling high-speed turbo decoding through concurrent interleaving[END_REF] in which the data is simply stored in different memory banks without considering conflicting accesses and then additional buffers are used in the interconnection network to manage conflicts at runtime. This approach is based on a LLR distributor which is connected with all the P processing elements on one side and all the memory banks on the other side, as shown in Figure 2.4. The LLR distributor consists of interconnection network, buffers, FIFOs and multiplexers. The total cost and the latency of the architecture increases due to the use of buffers, FIFOs and multiplexers to manage conflict. The Benes network has good path diversity as it provides all possible permutations between inputs and outputs. However, this network avoids conflicts between packets, if all the packets have different destinations, which is not the case in turbo decoding. A modified topology and routing algorithm is proposed in this approach to optimize Benes network for turbo decoding.

Routing algorithm transmits packets which are intended for different router at the same time and registers are used (instead of FIFOs) to store conflicting data. However, pre-processing is required to generate routing information and memory is needed to store router configuration.

A multistage network based on barrel shifter has been recently proposed for 3GPP LTE System for parallel decoder architecture in [START_REF] Wong | Turbo decoder using contentionfree interleaver and parallel architecture[END_REF]. The connection between each memory bank and its corresponding processing element is established by shifting each sub block by a given offset due to the permutation characteristics of QPP interleaver used in LTE. The authors have presented a multistage interconnection network based on barrel shifter as shown in Figure 2.8. This figure shows the parallel architecture with multistage interconnection network for P = 8 with three stages. In the proposed network, 2 i bits are needed for shifting data in the stage (3 -i) where i = 0 ∼ 2 and the amount of shift in the stage (3 -i) is 2 i locations. So, we can compute that one bit is needed for stage 0, two bits are needed for stage 2 and four bits are needed for stage 3. Therefore, the three stages of the modified barrel shifter require driving seven bits for configuration at each access. Similarly, for P = 4, two stages of modified barrel shifter needs three bits. The data between the processor and memory is transferred immediately as the interconnection network has short path delay and simplified network control mechanism.

However, the proposed approach can only be applied to QPP interleaver. This approach is not compliant with any other interleaving law.

The presence of interconnection network and buffer management mechanisms to manage conflicts increases hardware cost and latency of decoders which often restricts the implementation of such architectures for practical systems.

Solving conflicts with dedicated memory mapping approaches

The third family of solutions deal with memory access conflict problem by storing the data elements in different memory banks in such a way that all the processing elements can access to the data without any conflict at each time instance. Different mapping algorithms are proposed in state-of-the-art to perform pre-processing steps in order to determine each data element in the memories. These approach leverage on specific architectures that are presented in the last sub-section.

Memory mapping approaches

In [BEN04], one of the first algorithms based on simulated annealing meta-heuristic to resolve conflict problem for Turbo and LDPC codes is proposed. This algorithm is always able to find conflict free memory mapping, but the time to calculate the solution cannot be computed statically. Therefore, the computational complexity of the problem inhibits the addition of other constraints into the algorithm such as targeting a dedicated interconnection network.

In [JIN10], an approach based on optimized memory address remapping is presented.

In this method certain collision-free exchange rules are defined to complete the simulated annealing procedure much faster than achieved in the traditional method presented in

[BEN04] thanks to a reduced number of iterations to complete the annealing procedure .

However, this method is also based on a meta-heuristic and the time of completion of the algorithm cannot be predicted.

In [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF], a new simplified approach called Static Address Generation Easing (SAGE) is presented. This approach includes additional constraints to determine architecture oriented conflict free memory mapping. In SAGE, two Mapping Matrices (MAP Nat , MAP Int ) are used during algorithm execution to store bank information. These matrices have the same order as the natural and interleaved order matrices as shown in Figure 2.9. ). In the next iteration, the most constrained column (i.e. the column with the greater number of assigned cells) is filled and reported in the same manner. This process continues until all the columns of the mapping matrices are filled with mapping information.

The above mentioned approach is limited to turbo-codes and a more generic approach has been proposed in [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF]. This approach is able to solve memory conflict problem also for LDPC codes. It is based on Multiple Read Multiple Write (MRMW) mechanism in which each data element e i consists of two memory locations: one for read data and the other for write data, as shown in Figure 2.9. For functional correctness, if data is accessed several times, then j th read access of e i must be equal to the (j-1) th write access of e i . The algorithm assigns read and write memory banks to the most constrained column (i.e. the column with high number of data elements already mapped) of the MAP matrix. Then the corresponding entries in the other matrix are filled respecting the targeted interconnection network constraints. This process continues until MAP matrices are fully filled with targeted network constraints. However, recursion is needed when a conflict is detected. This approach innovates a new way to solve computationally complex problem through multiple read and multiple write mechanism. However, it can use backtracking making time to complete the algorithm unknown. In [START_REF] Sani | A methodology based on transportation problem modeling for designing parallel interleaver architectures[END_REF], an approach based on Transportation problem modeling is presented.

0 1 2 0 6 4 ------------ 3 4 5 8 5 7 ------------ 6 7 8 2 10 1 ------------ 9 10 11 11 3 9 ------------ Time PE 1 PE 2 PE 3 PE 4 t 1 t 2 t 3 t 4 t 5 t 6 (
This method finds conflict free memory mapping for Turbo codes with architecture optimization. The mapping problem for turbo codes is transformed as transportation problem.

The proposed approach is interesting as it is based on a polynomial time algorithm. However, Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

it works for a subset of cases and can be widely improved as demonstrated in the dedicated section of chapter-4.

In [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF], another polynomial time algorithm is presented to reduce the computational complexity to find conflict free mappings. The algorithm is based on two steps.

In the first step, a bipartite graph is constructed based on two data access matrices. Then in the second step, a polynomial time bipartite edge coloring algorithm is used to find conflict free memory mapping. This approach can be used to solve memory conflict problem for both Turbo and LDPC codes.

Finally, in [BRI12] [BRI13a] [BRI13b]
, the authors have presented a memory mapping approach to find conflict-free memory mappings for both Turbo-codes and LDPC codes for any standard respecting targeted interconnection network. This approach is referred as memory relaxation method in this thesis. It is based on the idea of adding registers in the memory architecture (and not in the interconnection network) to deal with conflicting data and to respect the targeted interconnection network. However, the cost of the final architecture is increased due the inclusion of registers and their dedicated additional steering logic as shown in Figure 2.11. In this figure, the four processors are connected to four memory banks through a targeted interconnection network. Additional registers and steering logic are required to support the conflict free memory mapping with the targeted network as shown in Figure 2.11. However, if the targeted interleaving law is strongly incompatible with the targeted interconnection network the additional costs will be high.

Architecture for design time memory mapping approaches

All of the previously mentioned memory mapping approaches are either based on inplace memory mapping or multiple read multiple write (MRMW) memory mapping architecture as shown later in this section. We will describe the two kind of architectures in the two next subsections.

In-place memory mapping architecture

The architecture for turbo-like memory conflict problem is known as in-place memory mapping architecture. In order to explain in-place architecture, consider a set of L data

Mapping problem

We need to store the L data elements in B memory banks in such a way that P processing elements can access B memory banks in parallel for all time instances without any conflict.

For in-place conflict free memory accesses, the two following mapping constraints must be fulfilled:

-All memory banks have to be used only one time at each time instance (conflict free).

-Each data must be mapped in one and only one memory location (in-place).

As an example, a matrix in which each data is accessed twice (in natural and interleaved order), is shown in Figure 2.12.a. The resultant mapping of the considered example is shown in Figure 2.12.b by using memory mapping approach [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] which is based on in-place architecture. In this figure, each data in a column has a mapping cell which shows the memory bank from where a given data is read and written at a given time. It can be seen that every data element is read and written in the same memory bank, e.g. data 0 is read and written back in the same bank b 1 .

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Then this concept is extended in [SANI13] using polynomial time algorithms to find conflict free memory mapping. In MRMW architecture, memory mapping of each data element is done in two memory locations: First location called read mapping represents read access to that data element whereas second location called write mapping expresses write access of that data element. The aim of MRMW architecture is to find memory mapping with optimal number of memory banks.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Mapping problem

Store L data in B memory banks in such a manner that P processing elements can access B memory banks at each time instance in parallel for first reading P data and then

writing back these P data without any conflict.

The MRMW mapping is shown in Figure 2.14.b for the example in Figure 2.14.a by using [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF]. In this figure data-2 at time instance t 2 is read from bank b 2 and written in a different bank b 1 . Hence, it can be noticed that the in-place mapping architecture could lead to reduce the network controller cost as compared to MRMW architecture. The MRMW architecture is more costly in term of area as compared to in-place memory architectures. Memory conflict problems like shuffled turbo (see chapter-3, section 2.2.2) and LDPC codes are solved using [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF], [SAN11], [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] based on MRMW architecture.

PE 1 PE 2 PE 3 t 1 t 2 t 3 t 4 t 5 t 6 0 2 5 4 3 1 1 4 0 5 2 0 2 5 3 1 4 3 PE1 PE2 PE3 0 2 5 4 3 1 b1 b1 b2 b1 b3 b1 b2 b2 b3 b1 b3 b3 1 4 0 5 2 0 b3 b3 b3 b2 b1 b2 b1 b1 b1 b2 b2 b1 2 5 3 1 4 3 b2 b2 b1 b3 b2 b3 b3 b3 b2 b3 b1 b2 t 1 t 2 t 3 t 4 t 5 t 6
So, in order to optimize generated architectures, it could be really interesting if in-place memory mapping architecture could be used to solve these problems.

Conclusion

In this chapter, different approaches to handle memory conflict problem for Turbo and LDPC codes are explained. One solution is to develop an interleaving law taking into account architectural constraints at the time of code construction. However, with this approach the memory mapping problem is only partially solved, and the designers still have to handle conflicts in the final architectures (for some parallelism degrees, block lengths, channel interleaver in telecommunication systems…).

A second technique exists in literature to tackle memory mapping problem at run time.

However, the implementation of such architectures requires large hardware cost and latency due to the addition of conflict management mechanisms which limits its use in practical systems.

The third technique is to develop algorithms at design time that assign data in memory banks in such a manner that all processing elements can access their required data concurrently from memory without any conflict. Some of these techniques solve memory mapping problem for any type of interleaving law but results in costly hardware architecture.

Others are limited to a subset of applications.

In this thesis, we aim to design optimized parallel hardware architectures to solve memory conflict problems. For this purpose, we propose two categories of complementary approaches. In first category, we propose memory mapping approaches that aim to limit the cost of final decoder architectures by customizing interconnection networks (see chapter 3) and by using in-place memory architectures (see chapter 4). In the second category, we propose to merge both runtime and design time approaches to design flexible decoder architectures. For this purpose, we have embedded polynomial time memory mapping algorithm on-chip along with the interconnection network in order to execute it at runtime to solve conflict problem (see chapter 5).

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Chapter 3 --------------------------------------------------------------35 2.2.Proposed design flow - -------------------------------------------------------------------- -----------------------------------------------------------------------43 3.1.1.Memory Mapping with Network Relaxation - ---------------------------------------43 3.1.2.Pedagogical Example - ------------------------------------------------------------------46 3.2.Experiments and Results - -----------------------------------------------------------------48 3.2.1.Case study for HSPA - ------------------------------------------------------------------49 3.2.2.Case study for LTE - ---------------------------------------------------------------------54 4

OPTIMIZED MEMORY MAPPING APPROACH BASED ON NETWORK CUSTOMIZATION

36 2.2.1.Shuffled decoding memory issues ----------------------------------------------------37 2.2.2.Solving memory conflicts --------------------------------------------------------------38 2.3.Case study: Turbo decoder for LTE -----------------------------------------------------

.Conclusion 55

This chapter consists of two parts. First, a dedicated approach to explore the design space for parallel

turbo

Introduction

In this chapter, we first present a dedicated approach to explore design space for hardware architectures of turbo decoders in order to analyze their hardware complexity. The turbo decoder memory issues are explored and state of the art approaches are used to solve the memory access conflicts in case of shuffled and non-shuffled turbo decoders. We have performed different experiments for a case study of turbo decoders for 3GPP-LTE.

The second part of this chapter is about our proposed memory mapping approach based on network customization. The complexity for a given memory mapping problem depends on the memory and network controller. Unfortunately, none of the existing approaches focused on network controller optimization to design conflict free memory mapping. Our proposal is to introduce a new approach based on finding conflict free memory mapping approaches which gives the degree of freedom in the interconnection network in order to reduce the complexity. In this approach, the interconnection network is customized to find a conflict free memory mapping which generates optimized architectures.

Dedicated approach to explore design space of turbo decoder architecture

Parallel turbo architecture can be based on different decoding techniques (shuffled, nonshuffled) and different scheduling like backward-forward, butterfly/butterfly-replica, … (see section 2.3). The impact of these techniques on the hardware complexity and throughput is usually determined at the end of design process after the synthesis process. Thus, the time to market is penalized and the probability of designing an optimized system decreases. In order to tackle this problem, we have introduced a dedicated approach to efficiently explore the design space of parallel turbo decoder architectures. Thanks to this approach, a tradeoff between the hardware complexity can be estimated for the architecture design process. The memory access conflict problem is solved using existing approaches in order to design high throughput architecture for any parallelism and interleaver. However, a penalty in terms of the hardware complexity is expected. This work has been carried out in collaboration with TELECOM Bretagne, Brest-France [START_REF] Sanchez | A dedicated approach to explore design space for hardware architecture of turbo decoders[END_REF]. interconnection network. The controller is also to be designed to address the ROM memories and to generate control signals of the memory blocks. Figure 3. 1(a) shows the architecture for non-shuffled decoding [BER90] in which all the P PEs are first assigned to decode the natural order, and then all of them are assigned to the interleaved order. However, as mentioned in [START_REF] Zhang | Shuffled iterative decoding[END_REF], shuffled decoding can also be applied as shown in Figure 3. 1(b). In this case, P/2

Turbo decoder architecture

PEs are used to decode the natural order, while the remaining P/2 PEs work on the interleaved order. Let L denotes the number of symbols in the received frame. This frame can be divided into Q sub-blocks that can be decoded in parallel. Each sub-block is formed by M = L/Q symbols with Q = P for non-shuffled turbo decoders and Q = P/2 for shuffled turbo decoders.

Proposed design flow

The proposed design flow is detailed in Figure 3 Concurrent access problem occurs in shuffled turbo decoders when the extrinsic information for the same data is accessed in the natural as well as interleaved orders during the same clock cycle i.e. two processors access one data concurrently. In order to find the conflict free memory mapping, additional extrinsic memory locations are used to copy the extrinsic information with concurrent access ensuring that a correct exchange between natural and interleaved order is achieved. However, this kind of memory collision does not appear in non-shuffled architectures, since any information symbol is accessed first in natural order and then in the interleaved order.

The second memory issue for the shuffled decoding is consistency problem. Consistency problem occurs during the decoding process when a reading operation done by a PE in one domain (natural order) is followed by a reading operation performed by the PE in the other domain (interleaved order) in the next operation. This occurs for a writing operation as well.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

As a result the data element can be overwritten as the two PE will write at the same memory location: if only one memory position is used for the extrinsic information, the same extrinsic value is read in both orders and the extrinsic value that has to be produced by one PE decoder is missed due to overwrite. In this case, performance degradation in the correction capabilities of the turbo decoders may occur. So, before finding conflict free memory mapping we need to add extrinsic memory locations as well due to consistency.

Let l denotes the number of additional memory positions used to solve concurrent access to the same extrinsic value and the consistency problems. Memory access description files then enable to carry out conflict free memory mapping which is presented later. Thus, L+l extrinsic values are assigned to B memory banks. From this memory mapping, the controller can be designed and the content of ROM memories can be established.

Solving memory conflicts

In-place memory mapping and multiple read multiple write (also called double) memory mapping are the two types of architectures that exist in literature. Non-Shuffled turbo decoding is similar to in-place memory mapping as data elements are first accessed in natural order and then in interleaved order. On the other hand shuffled turbo decoding presents double memory problem as the data elements are accessed in natural and interlaeaved order simultaneously. In order to find a conflict free memory mapping for these two problems, two approaches are introduced in this section: one is in-place memory mapping approach for nonshuffled decoding and another one is multiple read multiple write memory mapping approach for shuffled decoding in turbo decoders. Both approaches can be applied to find conflict free memory mapping.

Different in-place memory mapping approaches can be used to find conflict free memory mapping. In [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF], a polynomial time algorithm is presented in order to find conflict free mappings for conflict problem in turbo and LDPC codes. In-place architecture is used to solve problem for turbo like problems and MRMW architecture is used to solve memory conflict problem for LDPC like problems. Memory conflicts for non-shuffled turbo decoders is solved using [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] using in-place architecture. Data access order can be illustrated through data access matrices as shown in Figure 3. 3 (a). In this figure, one matrix is related to the natural order access and the other one is related to the interleaved order access. In turbo decoders, As shown in Figure 3. 3 (b), the data access matrices for both natural and interleaved orders are processed concurrently for shuffled turbo decoders. Memory mapping with in-place architecture is not possible using [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF]. Therefore, the approach [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] with MRMW architecture is used to solve memory mapping problem in this case.

Trellis
The detailed description of the approach [SAN13] is given in section-4.1 of chapter-2 for in-place architecture and in section-4.2 of chapter-2 for MRMW architecture.

Case study: Turbo decoder for LTE

We have applied the approach described in the previous section to the 3GPP In the final architecture, the critical path is in the processor of the decoder. However, the critical path of the interconnection network is greater than the critical path of the decoder for some B. Therefore to prevent the critical path to be in the interconnection network, pipelining stages have been introduced. From logic synthesis results we determined that one pipeline stage is enough for B = 32, 64, while two stages are necessary for B = 128. Table 3.1 lists the number of logic gates required to implement the Beneš network for six bit width data after logic synthesis. architectures. In non-shuffled turbo decoder configurations, the use of internal PE memories is convenient since it has a positive impact on the turbo decoder throughput (it reduce the number of reading accesses) and it helps to reduce the hardware complexity of the whole system. However, for the shuffled configurations, the turbo decoder hardware complexity is slightly reduced but the throughput is significantly affected.

Figure 3. 4 Area estimations of the considered configurations Table 3.3. We have not taken in to account the cost of processors as it is considered to be same in all the cases. ). For configuration-5 the cost of network controller is 40% of the total cost and cost of memory controller is 50% of the total cost, whereas for configuration-8 the cost of network controller is 50% of the total cost and cost of memory controller is 37% of the total area. The cost of the interconnection network itself is just 1% of the total area. The analysis of the distribution of the estimated areas for in an in-place architecture is almost same for all configurations with in-place memory mapping (conf. 1 to 5), and the distribution of the cost of the different components in the MRMW architecture is almost same for all other configurations with MRMW memory mapping problem (conf. 6 to 9). Hence, it can be concluded that the network cost is negligible whereas network and memory controller is larger in the total cost. network. However, the cost of these approaches is very high in some cases when the interconnection network is not compatible with the interleaving law due to the additional components (buffers, register, multiplexers) needed to find conflict free access of data. We have proposed a memory mapping approach to design optimized parallel hardware architectures based on network customization which can reduce the network controller cost as network controller in the designed architecture is also among the most costly elements in the architecture. Moreover, the proposed approach is also able to generate a conflict free memory mapping with reduced cost for a targeted interconnection connection as compared to state of the art approaches.

Memory mapping approach based on network customization

The network and memory controller has a larger effect on the total cost as compared to other parts for the approaches used for finding conflict free memory mapping as shown in previous section. The memory relaxation approaches [BR12] [BRI13b] [BRI13a] emphasis on the optimization of memory and network controller. However, State of the art approaches exist which are based on customizing architectures to support the constraint of a particular targeted interconnection network. However, Time relaxation [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF] and memory relaxation [START_REF] Briki | A Conflict-Free Memory Mapping Approach To Design Parallel Hardware Interleaver Architectures With Optimized Network And Controller[END_REF] approaches are based on customizing architectures to support the constraint of a particular targeted interconnection network. In memory relaxation method, if the targeted interleaving law is strongly incompatible with the targeted interconnection network the additional costs are high. However in time relaxation, the final architecture is based on Benes network architecture and requires additional buffers which results in the increase of the total latency of the system. The targeted interconnection network has a large impact on the final cost of the architecture besides solving the parallel interleaving conflict as the set of possible permutations offered by the network can strongly restricts architectural design space exploration. Since this interconnection network has a great impact on the final architecture and it is considerably the cause of the problem which is not taken into account in the state of the art approaches. Since, the cost of the network controller depends on the size of the network (number of control bits is equal to the number of switches in the network) and it is not taken into account in the state of the art approaches. A smart memory mapping approach should focus on this network directly in order to adapt the network constraint to the interleaving law as much as possible. In this way, the optimization of the generated architecture will be more impressive than the existing approaches as it will be seen with proposed approach: we call it network relaxation. This work has been published in [REH14b].

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Proposed Approach

Memory Mapping with Network Relaxation

Our proposed approach aims to take advantage of network relaxation principle. Figure 3. 5 presents an approach by considering the customization of the interconnection network and reducing the cost of the controller architecture. The constraint relaxation is provided by modifying the original network by adding additional multiplexers/switches. The idea is to keep the advantage of memory mapping approaches like [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] or [TAR04] in terms of architectural cost and latency, while proposing an approach that is able to target any application as [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF] or [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF].

First, starting from the description of an interleaving law (number of data, interleaving algorithm, parallelism) and a targeted interconnection network (i.e. NULL, Barrel-Shifter(BS), Butterfly(BF), Benes(BEN), Cross-Bar(CB)), the set of input memory mapping constraints is generated and provided to our memory mapping algorithm. Then, the next step consists in applying a memory mapping algorithm under network constraint. In the network library, all the permutations offered are stored separately for each network. This mapping step aims to fully explore the memory mapping solution space by checking all the permutations of the selected network. If no memory mapping solution exists for this network, then the set of permutations will be extended by addition of a network component, resulting into customized network architecture with enriched set of permutations (see Figure 3. 8). At the end the resulting architecture is generated. By applying this process for all available networks in the library, the designer is able to widely explore the design space and to select the best solution. The proposed algorithm is based on the memory mapping model proposed in [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF].

A formal description of the mapping matrix model is presented here. Let us consider a parallel decoder architecture composed of P processing elements PE={PE 1 ,…PE p } and P= B memory banks B={b 0 ,…b B-1 } to store L data. We need P= B, because it is always possible to find conflict free memory mapping using P= B for any conflict problem [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF][CHA10b] and the increase in the number of banks will result in increase of the size of network which will increase the cost of the network controller. Figure 3 in which each data is associated to two mapping cells which will be filled with the label of a memory bank. An element of the memory mapping matrix is shown in Figure 3. 6(c) in which data e i is read in the memory bank b j , and written in the memory bank b k after having been processed by a PE. In order to guarantee a valid memory mapping, constraints have to be respected for a given parallelism and interleaving law.

0 1 2 0 6 4 ------------ 3 4 5 8 5 7 ------------ 6 7 8 2 10 1 ------------ 9 10 11 11 3 9 ------------ Time PE 1 PE 2 PE 3 PE 4 t 1 t 2 t 3 t 4 t 5 t 6 (
Memory constraints:

1-Data processed at the same cycle (i.e. data that are read or written concurrently at time instance) have to be stored in different memory banks.

2-The i th read access to a given data must be performed in the same memory bank such that its (i-1) th write access i.e. a data must be read in the same memory location it has been written.

Network objective:

The memory mapping has to respect the set of supported permutations (i.e. this set is initialized with permutations of user-defined network constraint topology). The proposed memory mapping algorithm (cf. Figure 3. 7), first selects the most constrained column (i.e. the column with high number of data elements already mapped) in the memory mapping matrix (all the matrices are initially empty, so the mapping algorithm starts from the first column). Then the algorithm generates the subset of valid permutations for this column from the set of supported permutations in the targeted interconnection network. If this subset is not empty (i.e. conflict free memory mapping solution could be obtained for the selected column, with respect to the set of possible permutations) then each possible permutation from this subset is explored one by one, until a final conflict-free memory mapping is generated by our recursive algorithm. If no such valid memory mapping can be found with the targeted network then the set of possible permutations must be extended As shown in Figure 3. 8(a), the algorithm starts by finding conflict free memory mapping with one switch and if the mapping is not possible another switch is added to the network (see Figure 3. 8(b)). Afterwards, the algorithm adds another switch to the network if the mapping is not possible with previous network and tries to find conflict free memory mapping using permutation resulted by this network (see Figure 3. 8). This process continuous (see Figure 3. 8(d) to (f)) until a fully connected network is established which can always give a conflict free memory mapping according to [TAR04]. However, during this process from Figure 3. 8(a) to (e), if the algorithm succeeded to find conflict free memory mapping then the network at that stage will be the optimized resultant network.

The architecture generated with network relaxation is composed of a classical interconnection network (i.e. Barrel-Shifter, Butterfly…) or NULL network along with additional network component(s) named customized network. Then, since the source of the memory conflicts is relaxed, it is possible to find an optimized conflict free architecture compared to [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF] or [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF].

Pedagogical Example

In order to fully elaborate the proposed approach, the data access pattern example shown in Figure 3. 6(a) is considered. Firstly, a Barrel-Shifter BS is considered as input network constraint for this example. Hence, the set of permutations offered by a BS (see Figure 3. 9(b)) is selected from the library. The general architecture targeting BS is shown in Figure 3. 9(a). The mapping is started from the 1st column and the column is filled according to the permutation supported by the BS (σ1 of Figure 3. 9(b)). This column is then reported in the mapping matrix accordingly as shown in Figure 3.10(a). It can be seen that after one iterations of our algorithm, the partial memory mapping described in Figure 3.10(b) is achieved. At this step, when the second column is filled according to the permutations of BS and when this column is reported, the permutation at the last column is not supported by BS permutations as shown in If no network constraint is defined by the designer, the algorithm starts from scratch considering no network constraints, i.e. start mapping with NULL network (each PE is directly connected to a single memory bank through a wire). The algorithm will add new network components to the network when needed, until a valid memory mapping is achieved.

As a result a fully customized network is developed. The complete mapping for the considered example using network relaxation can be seen in Figure 3. 12. The algorithm will find the conflict free memory mapping for all the possible combination of the available permutations (i-e 1 st column is filled with σ1 and if the mapping is not valid, then σ2 is tried and so on).

Experiments and Results

Currently turbo codes are used in different standards. However, interleavers used in these standards are not conflict free for every type of parallelism. The proposed approach is able to find conflict free memory mapping for any type of interleaver and for any type of parallelism. This section presents the different experiments we performed to show the interest of the proposed approach. All the results in this thesis are given in NAND-gate equivalent

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 area using 90nm technology from STMicroelectronics. These estimations are based on synthesized and pre-characterized components (Registers, multiplexers, …). The number of the different components is provided by the mapping tool and as a result the estimations for the architecture are generated. We performed experiments for two test cases: HSPA and LTE.

In all these results we have considered the network controller cost which is 50% of the total architecture (recall section 2.3).

Case study for HSPA

For experimental purpose, we implemented interleavers from the most widely used are considered. The area of the network controller for proposed customized network is compared with the area of the network controller for approaches which uses fully connected (Benes network). Figure 3. 13 shows comparison of area in logarithmical (base10) scale. Our proposed approach has 50% (average) lesser area as compared to [TAR04] and 18% (average) lesser area as compared to [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF]. Figure 3. 14 shows latency comparison in term of cycles. The latency show the number of cycles needed to access all the data elements. Our proposed approach has equivalent latency as compared to [TAR04] and 56% (average) lesser latency as compared to [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF] (as [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF] approach uses FIFOs for conflicting data which is routed in next iteration and as a result the number of cycles increases which increases the latency). Therefore, the proposed approach significantly reduces the cost as compared to [TAR04] with the same latency. On the other hand as compared to [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF],

our proposed approach reaches small reduction in terms of area, but without any additional latency (i.e. our architecture will achieve higher throughput) leading to a better performance/area tradeoff. Moreover, we compared our proposed approach with existing approaches [CHA10a],

[TAR04] and [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF]. These experiments was performed for all block length from HSPA and for parallelism P=4 and P=8. Since the area for the memory banks is the same for each test case, it is not taken into account in these results. Figure 3. 15 and Figure 3. 16 show typical results obtained in this case for 2240 and 800 data and a unique Barrel Shifter BS network constraint. Here, [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] and [TAR04] are not able to find conflict free memory mapping: architectural constraints are not supported in [TAR04] and it is not possible to find a conflict free memory mapping with a BS as network objective for [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] . However, [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] is able to find the solution with the use of additional registers along with BS. As shown in these figures our proposed approach can find an optimized solution with an area divided by about 66 as compared to [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] for the example considered in Figure 3. 15 and by about 20 as compared to [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] for example considered Figure 3. 16. The latency for all the approaches based on memory mapping solutions [TAR04], [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF], [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] and the proposed approach is same as no additional buffer elements are needed in the interconnection network. In Figure 3. 17 and Figure 3. 18, the best results for each approach are presented. In this case, the interconnection could be different for each approach, for example [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] and

[TAR04] are not able to find a solution with a Barrel Shifter interconnection network so

[TAR04] gives solution only with a fully connected network like Benes and [CHA10a] is able to find a solution with a Butterfly BF network, for L=2240 and P=4. Whereas for the second example with L=800 and P=8 in Figure 3. 18, the minimum cost is achieved with Benes network for [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF][TAR04] . The cost of the [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] is very high due to the addition of buffers and multiplexers to solve the conflicts. Our approach (based on customized network) is able to find the conflict free memory mapping for all the considered examples with an area reduction of 34% in average for Figure 3. 17 and 50% in average in Figure 3. 18.

Block Length

[14]

[20] proposed Nand Gate eq. area (Log.)

1 [TAR04] 1 [BRI12]
Nand Gate eq. area (Log.) Block lengths In order to further explore our approach we have considered different block lengths from HSPA with P=4 and P=8. The results for P=4 is shown in Figure 3. 19 and for P=8 in Figure 3. 20. Like in the previous experiments, these figures show the best result for each approach.

The results clearly show that our proposed network relaxation method always gives lower cost solution as compared to existing approaches. For P=4, our solution reduces the total area 21 times in average for all the experiments. Compared to [TAR04] the area is divided by 1.8 in average and compared to [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] the area is divided by 41 in average. For P=8, network relaxation reduces the total area 40 times in average for all the experiments. Compared to

[TAR04] the area is divided by 2.6 in average and compared to [START_REF] Briki | A Design Approach Dedicated to Network-Based and Conflict-Free Parallel Interleavers[END_REF] the area is divided by 76 in average. As it has been said, the latency is same for all the considered approaches [TAR04][BRI12] [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] and are compared to our proposed approach. On the contrary, in [START_REF] When | SOC-Network for Interleaving in wireless Communications[END_REF] the latency of the architecture is impacted as compared, then this solution is not considered in the final results.

Case study for LTE

We also performed experiments for interleaver used in LTE. In [START_REF] Cheng | Reconfigurable Turbo Decoder With Parallel Architecture for 3GPP LTE System[END_REF], LTE with parallel architecture is presented. They have presented a multistage interconnection network based on barrel shifter. Figure 3. 21 shows the parallel architecture with multistage interconnection network with P = 8 (2 i ) with three stage. Configuration bits (bits needed to control the network) for P = 8 can be calculated by considering a stage (3 -i), in which i = 0 to 2, we need one bit for 2 i inputs in that stage (like in first stage we will need 2 0 i-e 1 bit). So, one bit is needed for stage 0, two bits are needed for stage 2 and four bits are needed for stage 3.Therefore, three stages of modified BS need seven bits for configuration at each access.

Similarly, for P=4, two stages of modified barrel shifter needs three bits. We have applied our proposed approach for the above mentioned case study. The proposed approach is able to optimize the network as some block lengths can support standard BS. Table 3.5 shows LTE block lengths that support BS network. As a result, the cost of the architecture can be reduced as shown in Figure 3. 22. In this figure, the area comparison between [WON11b] and our approach is given for different block lengths. The proposed approach can save up to 35% of the network area as shown in Figure 3.

22.

Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art approache and Network Relaxation approach for different block lengths (P=4)

Conclusion

In this chapter, a dedicated approach to explore the design space for parallel turbo decoder architectures is presented in which different configurations based on shuffled and non-shuffled schemes are considered in order to analyze the hardware complexity of the decoder architecture. A novel architecture to decode turbo codes using shuffled scheduling is also proposed in which we have studied and solved different memory issues for shuffled decoding technique. The analysis of the cost estimation gave us the distribution of cost for different parts of the architecture like network controller, memory controller, extrinsic memory. We have seen that network controller is up to 60% of the total cost for some test cases; unfortunately state of art approaches are not able to directly optimize this part.

Therefore, we proposed a new approach for conflict free memory mapping based on network customization to generate optimized architectures. This approach also respects targeted network architecture by modifying it with additional network components if needed. Proposed approach is compared through industrial test-cases with the state of the art approaches.

Results show that optimized architectures can be obtained by applying proposed network relaxation approach even when particular network is targeted with significant area reduction and without any reduction in terms of throughput (as the latency of the proposed approach remains the same as state of art memory mapping approaches).

The proposed network relaxation approach provides in-place mapping for conflict problem which can be solved with P banks, and provides MRMW mapping for conflict problems which cannot be solved with in-place mapping. However, due to the customized network solution the proposed approach is able to generate optimize solution in both the cases. As mentioned in chapter-2, MRMW architecture is more costly in term of area as compared to in-place memory architectures. Therefore, a second option must also be explored in order to optimize the final architecture in term of area: to use in-place memory mapping architecture for other memory conflict problems. This solution is presented in the next chapter.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Chapter 4 ---------------------------------------------------------------------60 3.Design Flow 62 3.1. Graph construction ------------------------------------------------------------------------63 3.2.Bipartite test - ------------------------------------------------------------------------------- --------------------------------------------------------------------------66 3.4.Vizing theorem for edge coloring - ------------------------------------------------------ ------------------------------------------------------------------73 3.5.In-place memory mapping for multigraphs 78 3.5.1. Modeling ----------------------------------------------------------------------------------79 3.5.2.Transformation of bipartite graph into Transportation Matrix --------------------81 3.5.3.Algorithm to find semi 2-factors in Turbo Bipartite Graph -----------------------82 3.5.4.Pedagogical Example ------------------------------------------------------------------- --------------------------------------87 4.2.Case study-2: Non-Binary LDPC codes - ----------------------------------------------- ---------------------------------------90 4.2.2. Results------------------------------------------------------------------------------------- -----------------------------------92

IN-PLACE MEMORY MAPPING FOR OPTIMIZED ARCHITECTURE

5.Conclusion 93

In this chapter, we present an optimized parallel hardware architecture using in-place memory mapping. In-place memory mapping architecture and multiple read multiple write (MRMW) architectures are currently used in the state of the art approaches to solve a memory mapping problem. However, the controller MRMW architectures are more costly as compared to in-place architecture. In this chapter, we show that some of the memory mapping problems which are currently solved using MRMW architectures can be solved by using in-place memory mapping architectures. We also present polynomial time algorithms to solve these problems with in-place architecture. As a result the complexity in term of area of the decoder can be reduced.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Introduction

In (as explained in chapter 2). However, for in-place architecture the network configuration of a read cycle is also reused for the write cycle. As a result, the network controller is reduced for in-place architecture as compared to MRMW architecture.

In this chapter, we introduce that every conflict problem with two accesses (each data element is accessed two times e-g natural order access and interleaved order access) which are currently solved with MRMW memory mapping architecture can be solved using in-place architecture. It allows us to reduce the network controller which results in an optimized decoder architecture. Our proposed work addresses the memory mapping problems in which each data is accessed exactly two times.

Two access memory mapping problem

In this section we describe memory conflict problems in which each data is accessed exactly two times. These problems include memory mapping problems of turbo decoders in LTE and HSPA interleaver with shuffled as well as non-shuffled decoding schemes [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes. 1[END_REF].

The memory conflict problem in non-binary LDPC is also with two accesses [DAV].In order to find conflict free memory mapping using classical design time approaches, these problems can be categorized as shown in Figure 4 In this work, we propose that all of these two access memory conflict problems can be solved by using in-place memory mapping architecture and associated memory mapping algorithms are proposed.

Problem formulation

Approaches based on in-place memory mapping includes [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] which can solve the given problem in polynomial time using bipartite edge coloring algorithm. Using in-place mapping solution, this approach can only target turbo like problems (e-g non-shuffled HSPA/LTE) in which data is first accessed in natural order and then in interleaved order because of their bipartite nature. However, we can show that it is also possible to use the approach [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] for problems which are not of bipartite nature i-e data elements accessed randomly and not accessed in natural order and interleaved order pattern (like in shuffled LTE). This can be done by performing a test which can determine the bipartiteness. This test will be referred as bipartite test. After applying the bipartite test if the conflict problem results in bipartite graph then we can apply the bipartite edge coloring algorithm to find inplace conflict free memory mapping [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF]. Bipartite graph can be defined as below.

Definition Bipartite Graph Bipartite Graph is a graph whose nodes can be divided into two independent sets, T x and

T y such that every edge (t x , t y ) connects a node t x from T x to a node t y from T y . Moreover, there is no edge that connects nodes of same set.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

So the bipartiteness of a graph can be determined by the bipartite test which can show whether the graph is bipartite graph or not. Hence, the graph for two access problem can be categorized in bipartite graph and non-bipartite graphs as shown in Figure 4.2. We can find conflict free memory mapping using in-place architecture by applying bipartite edge coloring algorithm in case of bipartite graphs. On the other hand, memory mapping problems in nonbinary LDPC codes and shuffled decoding of HSPA interleaver result in a non-bipartite graphs. For these graphs, approaches based on MRMW mapping architecture are needed as currently state of the art approaches are not able to find conflict free memory mapping using in-place architecture.

Memory conflict problem with two accesses

Bipartite Graph Non-bipartite graphs In this work, we propose to solve mapping problem using in-place memory mapping architecture even for non-bipartite graphs. We can find memory mapping using Vizing theorem [VIZ64] which can find conflict free memory mapping for any given problem using P+1 banks. So, thanks to this approach, in-place mapping architecture can be achieved by adding only one additional bank. However, Vizing theorem is true only for simple graphs. We will define simple and multi-graph before introducing Vizing theorem.

Definition Simple Graph A simple graph is a graph which has no loops (edges connected at both ends to the same node) and no parallel edges (two nodes are connected with only and only one edge).

A simple graph is shown in Figure 4.3 in which no loops and no parallel edges exist.

Definition Multi-Graph A multi-graph is a graph which has loops (edges connected at both ends to the same node) and/or parallel edges (two nodes are connected with only and only one edge).

A multi-graph is shown in Figure 4.4 in which a loop exists at node t 4 and parallel edges exist between t 1 and t 3 , and between t 6 and t 3.

Definition Vizing Theorem

A simple graph of degree P (largest number of edges connected to a node in the graph) can be edge-colored with at most P+1 colors where P is the maximum degree in a graph

[VIZ64].
Hence, non-bipartite graph for memory mapping problem can be edge colored with P+1 colors which results in conflict free memory mapping with P+1 banks using Vizing theorem.

We will perform a test (simple graph test) before applying Vizing theorem. For multi-graphs a dedicated approach is used to find conflict free memory mapping.

Finally, if a non-bipartite graph is also a multigraph, then a dedicated approach proposed in this thesis can be used. This proposed approach is based on approach used for transportation problem which can find conflict free memory mapping for any given problem.

The above mentioned proposed work can be formalized by the design flow described in the next section.

Design Flow

This entire process is presented in a proposed design flow presented in Figure 4.5. For a given mapping problem first a graph is constructed. Then bipartite test is performed to determine whether the given problem can be solved using P banks. If the graph is not bipartite then more than P memory banks are needed. Hence, simple graph test is performed to check whether Vizing theorem can be applied which can provide conflict free memory mapping

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 using upto P+1 banks. Finally, for multi-graphs, a dedicated approach is applied which can find conflict free memory mapping using upto (3/2)*P banks.

Mapping problem

Mapping using P Banks

Graph construction

The first step of the design flow is to construct a graph based on the memory access matrix. First an initial graph G' = (T ∪ L, E) is constructed according to the data access matrix in which set of nodes T represents all the time instances whereas set of nodes L represents all the data elements of the access matrix. An edge (t i ,l j ) is incident to the data node l j and to the time node t i if l j is processed at t i (i.e. data l j will be read and next written at time t i ) where t i ∈ T. Then the graph G' is converted into a graph G = (T, E).

The two access memory mapping problems have the following two distinct properties:

Property 1

The number of parallel accesses to data the elements P (i. The graph G is needed to be edge colored in order to find conflict free memory mapping. However, for approach proposed in [SAN13] a bipartite graph is required for edge coloring. Therefore, the bipartiteness of the graph is checked by bipartite test as described in next section.

Bipartite test

Bipartiteness of a graph can be tested by using breadth first search algorithm (BFS).

The BFS begins at a source (starting) node and inspects all its neighboring nodes. Then for each of those neighboring nodes (one after another), their own neighbor nodes which have not been visited before are traversed, and so on. We start the search at any node and assign it to alternating sets i-e assign the starting node to set-1 and assign its entire connected neighbor nodes to set-2, further assign to set-1the nodes connected to the all neighbors of the neighbors and so on. The graph is not bipartite if at any step a node has connected neighbors assigned Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

with the same set. In the end, the graph is bipartite, if the search ends without having two connected neighbors assigned to the same set.

As shown in Figure 4.8, the algorithm uses a queue data structure to store intermediate results as it traverses the graph. A queue is a collection in which the entities are kept in order as same as First-In-First-Out (FIFO). The addition of entities is made to the rear terminal position, known as en-queue, and removal of entities is made from the front terminal position, known as de-queue. The whole process is shown in the following steps.

1) The first step is to enqueue the source node as shown in Figure 4.9(b) in which t 1 is considered as the source node in the graph shown in Figure 4.9(a).

2) Dequeue a node and assign to a set. 3a). If two adjacent node are assigned to same set then the graph is not a Bipartite graph then the algorithm is completed 3b). Otherwise enqueue the neighbor nodes (the direct child node) which are not yet assigned.

As it is shown in Figure 4.9(b), t 1 is dequeued and assign it to set-1. Then all the neighbours nodes t 2 and t 5 are enqueued.

4) If the queue is empty, every node on the graph has been assigned then the algorithm is completed, else repeat previous step by assigning alternate sets to the neighbors.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

t 1 Set-1= t 2 t 5
Step-1)

Step-2)

Step-3b)

Set-1=

(a) (b) Figure 4.9 Birpartite test example As a result, the bipartiteness of a graph can be decided for a conflict problem, so bipartite edge coloring approach can be used to find conflict free memory mapping [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF].

However, for non-bipartite graph we can apply the Vizing theorem in case of simple graphs (see Figure 4.5). The simple graph test is described below.

Simple graph test

Simple graph has two properties: no loops and no parallel edges. The access of one data element twice at a time instance always results in a graph for memory mapping problem with loops which is never the case for memory access problems. Therefore, we can easily perform a test to determine whether a graph is a simple graph or not by checking the existence of parallel edges in the graph by modifying the breadth first algorithm. 2) Dequeue a node and check all its neighbours (see Figure 4.11). 3a) If there exist a parallel edge between the neighbor and the dequeued node.

No parallel edges detected

Step-1)

Step-2)

Step-3b) We start traversing the graph by checking whether there exists a parallel edge. As soon as a parallel edge is detected, we stop traversing the graph and conclude that the graph is a multigraph and we cannot apply Vizing theorem. On the other hand if no parallel edges are detected in the entire graph, then it is a simple graph and we can apply Vizing theorem which can resolve the memory conflict problem by using P+1 banks.

Vizing theorem for edge coloring

The process of edge coloring using Vizing theorem is shown in Figure 4.12 in which first a node is selected to color. Then vizing fan (defined later in this section) is constructed and if same colors are not available at both nodes of the edge. The fan is ended in two possible cases: 1) without any repetition of missing colors (the un-used colors) at the nodes of the fan, 2) with repetition of missing colors at the nodes of the fan. In the second case, first path is traced and then existence of the loop in the path is detected. So a path is selected based on the loop detection. Finally, the colors are exchanged and the final coloring is assigned to the graph. As a result, the desired edge is colored. This whole process is described below in details and an example is provided in the next sub-section. We have to color the edges of graph G by using at most P+1 colors. Let us consider a graph G having j+1 time nodes with a maximum degree P. Edges of G are e 1 , e 2 …e j . We will start from an empty graph G 0 with j+1 time nodes without any edge. This graph is then extended to the graph G 1 in which one edge (e 1 ) is considered. We keep on adding edges to color them until the whole the graph is completed. Mathematically, in each iteration we extend the graph coloring of G i-1 to colour G i = G i-1 U {e i }, For i = 1 to j.

We explain how to color G i using at most P+1 colors. Inductively, we suppose that we have already colored the edges of G i-1 using at most P+1colors.

Now G i = G i-1 U {e i }
where e i = (t 0, t 1 ) be the next edge to color (conflict edge) as shown in

G i = G i-1 U {e i }, For i = 1 to j.
As shown in Figure 4.13 at most P -1 edges containing t 0 or t 1 are colored. If the missing color at t 0 is same as missing color at t 1 then color the edge (t 0, t 1 ) with that missing color. Otherwise if the missing color at t 0 is not the same as missing color at t 1 i-e color c 0 is missing at t 0 and one color c 1 is missing at t 1, then we have no simple solution to color the conflict edge.

In order to find solution to color the conflict edge we will first construct a sequence known as Vizing fan. We have represented each node notation t i (c i ) in which t i is the time node and c i is the missing color available for coloring at that code.

Vizing fan

A fan is an ordered sequence of edges at a node t 0 such that the other connected node t x has a missing color c x which is the color of the next edge in the sequence of connected nodes with t 0 .

t 0 (C 0 ) t 1 (C 1 ) t 3 (C 3 ) t 2 (C 2 ) t j-1 (C j-1 ) t j (C j ) C j-1
t 0 (C 0 , C j ) C j-1 t 1 (C 1 ) t 3 (C 3 ) t 2 (C 2 ) t j-1 (C j-1 ) t j (C j ) (a) (b) (c) (d)
Figure 4.14 Vizing theorem Case-1

Case-2

In case-2, the construction of the sequence is completed in such a way that there exists one color in all the edges of the sequence which is similar to the missing color of the last node. Mathematically, we can say that there exist a color c j = c k-1 , for some 2 ≤ k < j, such that the edge (t 0 , t k ) is colored with c j as shown in Figure 4.15(a).

In this case, first of all we have to shift the conflict edge from (t 0 , t 1 ) to (t 0 , t k ) i-e to shift color (t 0 , t i ) with c i for 1 ≤ i ≤ k-1. The edge (t 0 , t k ) becomes the conflict edge and c j is missing at both t k and t j as shown in Figure 4.15(b). In order to color the conflict edge, we have two further sub-cases which have different conditions based on the nodes t 0 , t k , t j as they can be connected to each other or disconnected.

So we check these cases in order to color the conflict edge.The two sub-cases are:

Case-2a

In this case, t 0 and t k are in different connected components (see Figure 4.16(a)) as the path from t 0 is not ending at t k . So the conflict edge can be colored as follows.

The first step traces path and then exchanges colors. We trace the c 0 , c j path from t k i-e to find the other node connected with c 0 and search for c j at that node and then c 0 at the next node and so on as shown in Figure 4.16(a). Then we exchange the color c 0 with c j in the path as shown in Figure 4.16(b) in which c 0 is replaced with c j and c j is replaced with c 0. As a result, c 0 will become missing at both nodes t 0 and t k . Now, we can color (t 0 , t k ) with c 0 (see However, if t 0 and t k are in connected components i-e the path from t 0 is ending at t k as shown in Figure 4.17(a) then by applying the above procedure, the exchange of color c 0 with c j will make c 0 available at t k but it will not be available at t 0 as shown in Figure 4.17(b). So we have no solution in this case. So case-2b will be followed to color the conflict edge.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

(a) (b)
Figure 4.17 Vizing theorem Condition for Case-2b

Case-2b

In this case, t 0 , t j are different connected components as t 0 is not ending at t j, so first the path c 0 and c j is traced at t j as shown in Figure 4.18(a). Then we shift conflict edge from t k to t j such that (t 0 , t j ) will become conflict edge (see Figure 4.18(b)). Then, we exchange colors between c 0 and c j in the t j -path as shown in see Figure 4.18(c). This will make c 0 missing at t 0 and t j . So we can color (t 0 , t j ) with c 0 as shown in

Complexity of the algorithm

The complexity of the algorithm using Vizing theorem can be calculated by considering a graph with m edges to color with n time nodes. At each time node we have P edges. The complexity to draw a fan is O(P 2 ) as we have to examine each edge at the missing color at that edge. O(n) is the complexity to exchange colors for coloring an edge. So overall complexity for the complete graph is O(n m + P 2 m).

Pedagogical Example

We present an example to explain the Vizing theorem. The data access matrix for the considered example is shown in Figure 4.20. The graph is shown in Figure 4.21(a). As P = 4 so we have five colors (4+1) to color this graph. The fan is shown in Figure 4.22(a) in which the color missing at t 16 is c 1 (consider only one) so we choose the next edge of the fan which is colored with c 1 . The other time instance connected to edge with color c 1 is t 3 in which c 2 is missing so the next edge of the fan should be of color c 2 and so on. The fan will end with the following two cases:

C 0 C 0 C 0 C 0 C 1 C 1 C 1 C 1 C 1 C 1 C 1 C 1 C 2 C 2 C 2 C 2 C 3 C 3 C 3 C 3 C 3 C 4 C 4 C 4 C 4 C 4 C 4 C 2 C 2 (
Case-1: when there is no repetition of missing colors at the nodes of the fan.

Case-2: when there is a repetition of missing colors at the node of the fan.

Case-1

The fan will end without any repetition in the missing colors having P edges as shown in Figure 4.22(a) where all the missing colors (c 1 and c 3 at t 16 , c 2 at t 3 , c 3 at t 2 , c 4 at t 17 ) are not repeated at next nodes as missing colors. In this case, there must be a color missing at last node of the fan t 17 is also missing at starting node t 1. The conflict edge can be colored as:

• As the missing color at t 1 is missing at t 17 so shift the dotted line edge to the t 17 as shown in Figure 4.22(b)-(c). The conflict edge is transferred to t 3 , t 2, and then to t 17 .

• Now we can color the conflict edge with c 4 as it is missing at both t 1 and t 17 as shown Figure 4.22(d). 4.22 Vizing theorem Case-1

t 16 (C 1 ,C 3 ) t 2 (C 3 ) t 3 (C 2 ) t 17 (C 4 ) C 2 t 1 (C 0 ,C 4 ) t 16 (C 1 ,C 3 ) t 2 (C 3 ) t 3 (C 2 ) t 17 (C 4 ) C 2 t 1 (C 0 ,C 4 ) (a) (b) t 16 (C 3 ) t 2 (C 2 ) t 3 (C 1 ) t 17 (C 4, C 3 ) C 3 t 1 (C 0 ,C 4 ) t 16 (C 3 ) t 2 (C 2 ) t 3 (C 1 ) C 3 t 1 (C 0 ) t 17 (C 3 ) (c) (d) Figure

Case-2

In case-2 we start constructing the fan and the construction of the fan is ended as soon as a repetition of the missing colors is detected in the fan as shown in Figure 4.23(a). If there is any remaining edge(s) connected to t 1 we will not consider it in the fan. Afterwards, transfer the conflict edge to the edge colored c 1 (color which has repetition). Now at t 3, trace the path of c 0 (missing color at t 1 ) and c 1 (color of repetition) as shown in Figure 4.23(b). At this stage, there could be further two sub-cases:

Case-2a: t 3 is not making a loop with t 1.

Case-2b: t 3 is making a loop with t 1.

Case-2a

First of all we will check if the node t 3 not making a loop with the node t 1. If it is the case then first we trace the c 1 , c 0 path and then exhange the color c 1 and c 0 with each other in the traced path. As a result c 0 will become missing at t 3 as shown in Figure 4.

23(c). Now color

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 the conflict edge with c 0 as it is aviable at both of the nodes t 1 and t 3 as shown in Figure 4.23(d).

t 16 (C 1 ,C 3 ) t 2 (C 3 ) t 3 (C 2 ) t 17 (C 1 ) C 2 t 1 (C 0 ,C 4 ) t 16 (C 3 ) t 2 (C 3 ) t 3 (C 1 ,C 2 ) t 17 (C 1 ) C 2 t 1 (C 0 ,C 4 ) (a) (b) t 16 (C 3 ) t 2 (C 3 ) t 3 (C 0 ,C 2 ) t 17 (C 1 ) C 2 t 1 (C 0 ,C 4 ) C 1 t 16 (C 3 ) t 2 (C 3 ) t 3 (C 2 ) t 17 (C 1 ) C 2 t 1 (C 4 ) C 1 (c) (d)

Case-2b

If the node t 3 is making a loop with t 1 then by exchanging colors c 0 will become missing at t 3 but c 0 will not be a missing color at node t 1 so the conflict edge cannot be colored with c 0 as shown in the Figure 4.24(a) and (b). Therefore, in this case we will not exchange colors at node t 3.

If the node t 3 is making a loop with t 1 then the node t 17 will never make a loop with t 1 .

Therefore, first of all we will transfer the conflict edge to the t 17 (time instance with repetition of c 1 ) and trace the path of c 0 and c 1 as shown in Figure 4.24(c) in which there is only one c 0 edge in this path.

Then we will exhange c 1 and c 0 with each other which will make c 0 avialable at t 1 and t 17 so we can color the conflict edge with c 0 as shown in Figure 4.24(d).

t 16 (C 3 ) t 2 (C 3 ) t 3 (C 1 ,C 2 ) t 17 (C 1 ) C 2 t 1 (C 0 ,C 4 ) C 0 t 16 (C 3 ) t 2 (C 3 ) t 3 (C 0 ,C 2 ) t 17 (C 1 ) C 2 t 1 (C 1 ,C 4 ) C 1 (a) (b) t 16 (C 3 ) t 2 (C 3 ) t 3 (C 1 ) t 17 (C 1, C 3 ) C 3 t 1 (C 0 ,C 4 ) C 0 C 0 t 16 (C 3 ) t 2 (C 3 ) t 3 (C 1 ) C 3 t 1 (C 4 ) C 0 C 1 t 17 (C 3 ) (c) (d)

In-place memory mapping for multigraphs

In the previous section, we have shown that Vizing theorem can be applied only for simple graphs as shown in Figure 4.5. The proposed approach for multi-graphs is described here in details A dedicated approach based on transportation problem for non-bipartite graphs which are also multigraphs, can be used to solve conflict problems with in-place architectures. For example, the data access matrix (Figure 4.26(a)) for shuffled decoding in the HSPA interleaver results in a multi-graph after applying simple graph test: as shown in Figure 4.26(b), as t 1 and t 3 , t 2 and t 5 , t 4 and t 5 have two parallel edges between them.

Theorem Bound for edge coloring multigraphs

Every multigraph with maximum degree P requires atmost (3/2)*P colors in any proper edge coloring [START_REF] Shannon | A theorem on coloring the lines of a network[END_REF]. Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Modeling

In this section, we model our mapping problem as transportation problem (the modeling is same as shown in section 3.1). This transformation is carried out in two steps. In the first step, mapping problem is modeled as bipartite graph and different proves are provided in order to explain that it is always possible to divide this bipartite graph into different subgraphs of equal sizes (see [START_REF] Sani | A methodology based on transportation problem modeling for designing parallel interleaver architectures[END_REF]). Afterwards, this bipartite graph is transformed into transportation matrix. A transportation problem algorithm is applied using this matrix to find memory mapping.

The first step is to construct a bipartite graph G t = (T∪ L, E) in which vertex set T represents all the time instances and vertex set L represents all the data elements used in the computation. An edge e = (t, l)εE is incident to the data element vertex l and to the time instance vertex t if d needs to be processed at t (i.e. data l will be read and next written at time t). This bipartite graph has the same two properties described in section 3.1.

The bipartite graph for the data access matrix of In order to clearly explain how transportation problem is able to find conflict free memory mapping we introduce some definitions, theorems and corollaries.

Definition 2-matching and 2-Factor of Graph

2-matching H of a graph G = (T ∪ L, E) is a subset of E such that every node of G is incident with at most two edges of H. The 2-matching H of G is called 2-factor if every node of G is incident with exactly two edges of H [HAR06].

The proposed approach is based on finding semi 2-factor (defined below) to find conflict free memory mapping so we have introduced the following two theorems [GRO03] which define the necessary and sufficient condition for the graph to contain 2-factor.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Theorem4.1 Every 2k-regular graph contains a 2-factor, where k is integer.

Theorem4.2

Every 2-edge-connected (2k + 1)-regular graph contains a 2-factor.

These theorems result into the following two corollaries [GRO03]:

Corollary4.1 Every 2k-regular graph contains k 2-factors.

Corollary4.2 Every (2k + 1)-regular graph contains k 2-factors and one 1-factor.

Definition Semi 2-factor in Bipartite Graph A semi 2-factor in bipartite graph G is defined as a 2-regular sub-graph in G with 2Y vertices where every node is incident with exactly two edges and where Y = Min (|T|, |L|).

Corollary4.3

Every Bipartite Graph with f t = 2k or f t = 2k + 1, where k is an integer, contains k disjoint semi 2-factors.

Proof: we first join the two edges connected with each data node and then remove all the data nodes to form regular graph G 1 = (T, E 1 ) as shown in Edges of every even cycle can be assigned with two colors which implies that edges in c i and every 2-factor in G 1 can be colored with two colors [START_REF] Soifer | The Mathematical Coloring Book[END_REF]. This results in the following lemma.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 kept empty. After construction of transportation matrix, any algorithm to solve transportation problem can be used to find semi-2 factor.

Algorithm to find semi 2-factors in Turbo Bipartite Graph

In this section, algorithm to solve memory mapping problem is presented. This algorithm is same as [START_REF] Sani | An approach based on edge coloring of tripartite graph for designing parallel ldpc interleaver architecture[END_REF] with some modification. [START_REF] Sani | An approach based on edge coloring of tripartite graph for designing parallel ldpc interleaver architecture[END_REF] is only able to tackle conflict problem for turbo codes (only non-shuffled) whereas our modified version of The algorithm starts by first calculating the number of semi 2-factors i-e k by using the degree of each time node f t of bipartite graph as explained in corollary 4.3. After that, it starts constructing the cycle (path) c 1 of current semi 2-factor sf cur by choosing a first route l i1 connected with consumer t 1 (see Figure 4.31(a)). The selection of the route l i1 decreases the demand of t 1 and the supply of d i to one. Simultaneously, the selected route is assigned with bank b a where index a represent the next un-assigned bank (a = 0 for c 1 ). Algorithm then selects the route connected with t 1 choosing any route l k1 and assigns it with bank next bank b a+1 .

The selection of l k1 completes the demand of t 1 , so all the producers connected with t 1 are completely removed from sf cur because now they are unable to provide two items in sf cur or they cannot work at their full capacity. The other route l km connected with d k is assigned the same bank b a+1 to reach to the consumer t m . This completes the supply of d k . Algorithm repeats the same process by selecting the route, decreasing the supply of producer and demand of consumer and alternately assigns banks to the route until c 1 is completed i.e., no producer with supply of one and no consumer with demand of one remains in the transportation matrix.

The final step is to check for the odd cycle for which a third bank b a+2 can be assigned.

The odd cycle can be detected if the starting and ending route or routes are assigned with alternate banks which results in a conflict as two different banks cannot be assigned to same data. In this case the third bank b a+2 is assign to the starting and ending route of the cycle.

Furthermore, the algorithm tests whether all the consumers fulfill their demands. If not, the algorithm starts constructing another cycle c 2 . For this, our algorithm selects consumer whose demand is still unfulfilled and which has at least one deleted route. Using this deleted route, the algorithm selects the route and assigns a bank b a to this route. After the assignment of b a , the algorithm repeats the same process used for the construction of c 1 to complete c 2 .

When the algorithm finds that demands of all the consumers are fulfilled then it declares that sf cur is constructed. In that case, the algorithm tests whether k semi 2-factors are constructed.

If not, the algorithm removes sf cur from transportation matrix, initializes all consumers with demand of 2 and starts constructing sf next from remaining matrix using the process described above until k semi 2-factors are constructed. Partitioning algorithm is explained through a pedagogical example in the next section. In [START_REF] Sani | A methodology based on transportation problem modeling for designing parallel interleaver architectures[END_REF], the author proposed an approach for finding semi 2-factor but their algorithm is not able to find cycles as explained with the help of an example shown in Figure 4.29. In this example, the transportation matrix is constructed first as shown in Figure 4.29(b).

Then, the algorithm is applied on this matrix as explained for constructing cycle c 1 . The algorithm is based on depth first algorithm without any recursion in which the cycle is started at a node and the next node is selected randomly. But it can be seen that there is a problem at t 6 in the cycle. Two edges are deleted at t 6 instead of deleting one edge which is wrong solution for finding cycles. So, we have no solution in this case using approach [START_REF] Sani | A methodology based on transportation problem modeling for designing parallel interleaver architectures[END_REF]. In this thesis, we have proposed another memory mapping approach based on transportation problem using breadth first algorithm with recursion. In the proposed approach, the cycle is started from a node and all the nodes are recorded at that node. Then, one node is selected and the cycle is completed using the selected node. However, if the cycle is not completed or the cycle results in the deletion of additional rows then other recorded nodes can be explored one by one in the tree (breadth first algorithm) to construct a cycle until the cycle is completed. As in Figure 4.29 the cycle is not completed due to a problem at t 5 so we have selected another node at t 1 and assigned b 1 to data 8 instead of data 4. In this case, the cycle is completed without any problem as shown in Figure 4.30.

t
t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 1 b 0 b 0 2 1 1(1) 1(1) 2 2 1(1) 1(1) 2 3 1(1) 1(1) 2 4 1(1) 1(1) 2 5 b 1 b 1 2 6 b 1 b 1 2 7 1(1) 1(1) 2 8 b 1 b 1 2 9 b 0 b 0 2 11 b 0 b 0 2 11 1(1) 1(1) 2 2 2 2 2 2 2 2 2

Figure 4.30 Resulting cycle obtained with proposed cycle construction approach

Complexity of the algorithm

Algorithm needs to traverse f t edges at each time instance to select two accesses that can be included in sf cur . However we need to use breadth first algorithm to explore all the option, so its complexity is O (f t + |T|) where |T| is the number of time nodes. To construct a partition sf cur , algorithm needs to select a couple of accesses for each time nodes So, the number edges to be traversed for one partition is in the worst case (f t + |T|) * |T|. Since there are k = f t /2 semi-2 factors (see definition), in order to construct all the partitions, the overall complexity of the partitioning algorithm is O (f t /2 * |T| * (f t + |T|).

Pedagogical Example

We present an example based on data access matrix depicted in reduces the supply and demand to 1 in the matrix as shown in Figure 4.31(b). The algorithm then fulfills the demand of t 1 by choosing a data elements in t 1 . The algorithm selects a route l 31 (data d 3 connected with time node t 1 ) and assigns another memory bank b 1 . Now the demand of t 1 is completely fulfilled and the remaining producers connected with t 1 (d 5 and d 7 in this case) are completely removed because these producers are unable to work at their full capacity (see Figure 4.31(c)).. The second route connected with producer d 3 (l 34 ), is also assigned the same bank b 1 . The algorithm fulfils the supply and demand of producers and consumers respectively in the same manner until the cycle c 1 is completed (cycle is completed when we will reach at l 03 ) i.e the algorithm do not contain any producer with supply of 1 and any consumer with demand of 1 in the transportation matrix. This process is presented in The algorithm continues to find cycle c 2 by using the same approach used in construction of c 1 until the cycle c 2 is completed as shown with gray highlighted cells in additional bank used in c 1 can be reused in case of an odd cycle of c 2 (not in case of this example). The demands of all the consumers are fulfilled so the first semi 2-factor is constructed.

X 8 l 84 (b4) l 85 (b4) X 9 X X X X X (a) (b)
The algorithm removes the first semi 2-factor from the transportation matrix. It initializes all consumers with demand of 2 and starts constructing the second semi 2-factor from remaining matrix using the process described for the first semi 2-factor as shown in

Experiments and results

Different experiments have been performed to validate the theoretical work presented in this chapter. Again, all the results in this are given in NAND-gate equivalent area using 90nm technology from STMicroelectronics. These estimations are based on synthesized and precharacterized components (Registers, multiplexers, …). The number of the different components is provided by the mapping tool and as a result the estimations for the architecture are generated.

We have performed experiments for each cases of the proposed approach considering three test cases: shuffled turbo decoders for LTE, non-binary LDPC and shuffled turbo decoders for HSPA.

Case study-1: Shuffled turbo decoders for LTE

In the first part of chapter-3, we have presented a case study for 3GPP-LTE standard turbo decoder for nine different configurations as shown in Table .4.1. In-place memory mapping architecture was used to solve configuration 1 to 5 (non-shuffled architecture) and MRMW memory mapping architecture was used to solve configuration 6 to 7 (shuffled architecture) [START_REF] Sanchez | A dedicated approach to explore design space for hardware architecture of turbo decoders[END_REF] with L = 1024 and P = 16 and 32. We have applied our proposed approach to solve configuration 6 to 7 (shuffled architecture) to use in-place memory mapping architecture. Bipartite test is applied to test the bipartiteness of these configurations as shown in Figure 4.5. Results showed that these configurations are of bipartite nature and now we can apply bipartite edge coloring algorithm using in-place memory mapping architecture [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF]. In [START_REF] Sanchez | A dedicated approach to explore design space for hardware architecture of turbo decoders[END_REF], MRMW mapping architecture was used to solve configuration 6-9 but thanks to our proposed design flow we can solve the conflict problems for these configurations using in- The first step is to prepare data access matrix for the architectures. Data access matrix for partially parallel architecture is shown in Figure 4.36 where 6 data elements are needed to be accessed in parallel for one check node (12 data are needed for two check nodes). To find conflict free memory mapping, all data should be stored in memory bank in such a manner that there is no conflict in accessing them in each cycle.

Vizing theorem for non-binary LDPC codes

To solve memory conflict problem for NB-LDPC codes, MRMW architecture has been used in [START_REF] Sani | Bipartite edge coloring approach for designing parallel hardware interleaver architecture[END_REF]. However, the approach we propose in this chapter can solve memory mapping problem for non-binary LDPC using in-place mapping architecture. Girth is an important parameter for LDPC codes, which is strongly related to code performance. Girth can be defined as the size of the smallest cycle of the bipartite graph. then more than one data elements is common between two time nodes (check nodes) which will result in parallel edges. So, for better performance LDPC codes are designed with g > 4.

Discussion

Therefore, the data access matrix will always have only one data element common between two time nodes as it can be seen in the example shown in Figure 4.20 with g > 4. In this example, the data access matrix have only one data element common between two time nodes. This property will make the resultant graph into a simple graph because only one edge will be possible between two nodes (due to one same data). Therefore, Vizing theorem can be applied to solve the memory conflict problem for non-binary LDPC codes.

Results

We have performed experiments for NB-LDPC with different block lengths and parallelisms. In-place memory mapping solutions in the state of art approaches like [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] are not able to find conflict free memory mapping for NB-LDPC conflict problem. Therefore

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

we compared our proposed work with [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF] and [START_REF] Briki | A Conflict-Free Memory Mapping Approach To Design Parallel Hardware Interleaver Architectures With Optimized Network And Controller[END_REF]. The result for [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] are not shown as they are same as [CHA13b] because mapping solution with [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] for these experiments are also based on MRMW architecture so the cost of the architecture will be same for [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] and [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF]. The approach proposed in [START_REF] Briki | A Conflict-Free Memory Mapping Approach To Design Parallel Hardware Interleaver Architectures With Optimized Network And Controller[END_REF] is also to generate optimize hardware architecture so we have compared our results with [START_REF] Briki | A Conflict-Free Memory Mapping Approach To Design Parallel Hardware Interleaver Architectures With Optimized Network And Controller[END_REF]. Block Length [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF] [BRI13a] Proposed The approach [START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF] optimizes the architecture up to 15% whereas our proposed approach can optimize the architecture up to 40% as compared to approaches without optimization [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF]. We have discussed the shuffled decoding for turbo decoding in chapter-2 in details. We have also explored the memory conflict problem for LTE in section 4.1 of this chapter. The turbo decoder architecture given in chapter-2 is same for LTE and HSPA interleaver.

However, the memory conflict problem is different in both the cases.

We have applied our proposed approach for shuffled turbo decoding in HSPA interleaver to solve the memory conflict problem. According to the design flow shown in section-3, first we have applied the bipartite test. The resultant graph in this case was not a bipartite graph.

Then, we have applied the simple graph test and we have observed that Vizing theorem cannot be applied as the resultant graph is a multigraph. Therefore, the approach based on transportation problem is used to solve the memory conflict problem for this test case as the resultant graph.

In Figure 4.39, we show first results based on our approach. We have considered the worst case scenario for these results as our transportation problem based memory mapping approach uses 3/2*P memory banks each time. In fact, these are the worst case results as less than 3/2*P could also be used for a given test case, but the current software version of the proposed design flow is not fully optimized. However, even in worst cases, in place memory mapping can reduce the cost up to 37% as compared with [START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF] as shown in Figure 4.39. The proposed approach needs up to six banks instead of four memory banks (in case of [START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF]) to find conflict free memory mapping. However, due to the in-place architecture the final cost is still reduced. As [START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF] is an optimization of the approach [CHA10b] so we have compared our results with [START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF] only for the block lengths in which the current software of [START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF] provides optimized results than [START_REF] Chavet | A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses[END_REF].

Conclusion

In this chapter, we have shown that all conflict problems with two accesses can be solved using in-place architecture. We have proposed algorithms to find conflict free memory mapping for two accesses conflict problem by using in-place architecture as state of art approaches needs MRMW architecture for some of these memory mapping problems. Hence, the total area of the decoder can be reduced by using in-place architecture for memory mapping problems. We have proposed Vizing theorem for solving memory conflict problem using in-place architecture. Moreover, we have introduced a dedicated approach based on transportation problem to solve memory conflict problems using in-place architecture. These proposed algorithms are able to find conflict free memory mapping in polynomial time.

In future, we can further optimize the decoder architecture by merging our two proposed optimization concepts: the network customization and in-place memory architecture. We could further optimize the solutions by using the customized network approach using in-place --------------------------------------------------------------------98 2.2.Generation of data access order- ---------------------------------------------------------99 2.3.Execution of memory mapping approach - -------------------------------------------104 2.4.Routing Algorithm -----------------------------------------------------------------------106 2.4.1.Example for Routing Algorithm ----------------------------------------------------108 3.Experiments 109

4.Conclusion 112

In The proposed approach is based on the design flow introduced below.

Proposed Design flow

The proposed design flow is shown Figure 5.3. In the first step, the data access order is generated based on the input parameters like interleaving law, block length sizes, level of parallelism and scheduling. The second step is the execution of the memory mapping approach using the data access order from the previous step. As a result a conflict free Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 memory mapping is generated which contains the memory address information. The final step is to generate the routing information for the interconnection network. We will define each of these steps in details.

Generation of Interleaved order

Generation of data access order

The first step of the design flow is to generate data access order based on the input parameter like interleaving law, block length size and parallelism. To illustrate, we have considered two interleavers: LTE and HSPA. Here we will describe in detail how to generate the interleaved order for both of these interleavers.

a. HSPA Interleaver

Series of specification have been released from time to time for high speed packet access (HSPA) after the release of initial draft by 3GPP-WCDMA. To obtain high throughput, it is necessary to perform turbo decoding on parallel architecture. However, the interleaver used in HSPA+ is not conflict free to support parallel implementation of turbo decoder. Also it is necessary to design interleaver architecture that support wide range of block sizes used in HSPA+ i.e. from 40 to 5114. • Write the input bit sequence into the rectangular matrix row by row and if R*C > L, the dummy bits are padded to fill the matrix.

K R if K or K if K ≤ ≤     = ≤ ≤ ≤ ≤     =   • Determine
C = p -1; if ( L ≤ R * (p-1) ) C = p; if ( R*(p-1) < N ≤ R * p) ) C = p + 1; if ( R*p < N )
• Construct the base sequence S(j) for intra-row permutation as: S(j) = [ v * S(j-1) ] % p; where j = 1,2, ……., p-2

• Determine the least prime integer sequence q(i) for i = 1, 2, ……., R-1 , by assigning q(0) = 1, such that gcd(q(i), p-1) = 1 and q(i) > 6 and q(i) > q(i-1).

• Permute the sequence q(i) to construct the sequence r(i) such that r T(i) = q(i) where i = 0, 1, …., R-1 and T(i) is the inter-row permutation defined in the standard.

• Perform the intra row permutation U i (j), such that for i = 0, 1,….., R-1 and j = 0,1, ……, p-2;

If ( C = p) then U i (j) = S[ (j*r(i) ) mod (p-1)] and U i (p-1) = 0; If ( C = p+1) then U i (j) = S[ (j*r(i) ) mod (p-1)] and U i (p-1) = 0 and U i (p) = p and if (L = R*C) then exchange U R-1 (p) with U R-1 (0) if ( C = p-1) then U i (j) = S[ (j*r(i) ) mod (p-1)] -1
• Perform the inter row permutation of the matrix based on the pattern T(i) where T(i) is the original row position of the i-th permuted row and defined in the standard.

• Read the bits column by column from the rectangular matrix by deleting the dummy bits padded to the input bits sequence.

Example for HSPA Interleaver

The algorithm can be explained best through a small example of L = 44. Different parameters obtained from the specifications explained previously are:

R = 5, C = 10, p = 11, v = 2
Next step is to put 44 data into matrix of order 5*10 (R*W) starting from row 0. Since there are 50 cells in the matrix, so the last 6 cells are filled with dummy bits represented by -1 in the last row as shown in Figure 5.4. In the last step, inter-row permutation is performed on rectangular matrix using the permutation pattern defined in the standard. Inter-row permutation pattern for this example is:

T = 4, 3, 2, 1, 0
where number of values in T is R = 5

The matrix after inter-row permutation is shown in Figure 5.6.

Π(x) = (f 1 x+ f 2 x 2 ) mod L … (1)
Where f 1 is odd and relatively prime to L, f 2 is a multiple of an arbitrary selected prime factor of L, x and Π(x) represents the original and interleaved address respectively and integers f 1 , f 2 are different for different block lengths defined in the standard as shown in However, the equation (1) includes multiplication and square function to be implemented which is hard to embed online. So, the on-line calculation approach [SUN11] rewrites (1) into the following recursive form:

f i L 1 f 2 f i L 1 f 2 f i L 1 f 2 f 1 40
Π(x+1) = f 1 (x+1) + f 2 (x+1) 2 mod L … (2) = Π(x) + g(x) mod L … (3)
where g(x) = f 1 + f 2 + 2f 2 x which can also be computed recursively through: The second step generates the conflict free memory mapping by executing memory mapping approach which is explained below.

g(x+1) = g(x) + 2 f 2 mod L … (4)

Execution of memory mapping approach

The second step of the design flow is the execution of the memory mapping approach.

The proposed work in chapter-4 is not considered here as that is our recent work (completed in last year of my thesis work) which is not published yet. So, the proposed approaches of chapter-4 are included in the future perspectives of this work. We have embedded on-chip the polynomial time algorithm presented in [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF]. This approach is described briefly. After constructing bipartite graph, the next step is to apply bipartite edge coloring algorithm to color the edges of that graph in polynomial time. For this purpose, we find an Euler partitioning by taking every other edge to obtain two (k/2)-regular subgraphs. In this way the problem is reduced to two (k/2)-regular graphs. However, to find euler partitioning, it is necessary that k is even to divide a regular graph into two regular subgaphs of equal degree. Afterwards, addressing and network control logic are generated based on this mapping and stored in the memory. So, if we change the interleaving law then we get a new mapping that is different from the previous one using memory mapping approach. For example, new interleaved order and memory mapping are:

Interleaved order = 2, 7, 10, 8, 9, 6, 1, 5, 11, 3, 4, 0.

Bank b 0 ={0, 1, 2, 3} Bank b 1 ={4, 5, 6, 11}, Bank b 2 ={7,8 9,10}

Routing Algorithm

The third step of the design flow of our proposed approach is the execution of the routing algorithm to generate the routing information for the targeted interconnection network. We have considered two fully connected networks: Crossbar and Benes network.

Crossbar is a non-blocking network in which connection of a processing element to a memory bank does not interfere the connection of any other processor to any other memory bank. It is feasible for online approaches to use crossbar network due to its high speed as they can be configured automatically. But, their use is normally limited to low level of parallelism, due to high complexity and cost. Hardware constraints such as the number of available pins and the available wiring area limits the number of physical connections of a switch. These Benes network needs a routing algorithm to generate routing information. For this purpose, we define a simplified routing algorithm for Benes network that can be executed onchip along with the mapping algorithm. The Control Algorithm for the (B x B) Benes Network, B = 2 n is described as follow:

1. The B numbers of the destination permutation in the binary representation are the input to the network.

2. For SN1, perform 2 i CRP's on the 2 i CRS's(mod 2 (n-i) ), formed by bits b i …b (n-1) for E i stage of SNI to get 2 (i+ l) CRS's(mod 2 (n-i-1) ) using bits b (i+l) …b (n -1) for 0 <=i<= (n -2). Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

For

Example for Routing Algorithm

Let us consider an 8x8 Benes network with a permutation [0 4 2 6 1 5 3 7] to be routed using the above defined algorithm.

The network is divided in SN1 and SN2 as shown in The complete control mechanism is shown in Figure 5.12. The control mechanism for the last three stages of SN2 are based on bit control as shown in the figure. In SN2, the first stage is controlled by C 0 , the second stage is controlled by C 1 and the third stage is SN2 is controlled by C 2. In SN, the switch is set straight if the inputs to the switch are (0,0) or (0,1) and the switch is set cross if the inputs to the switch are (1,0) or (1,1).

Figure 5.12 Example with complete routing tags

Experiments

In this section, different experiments are presented. These experiments are performed by using different embedded processors to measure the computational complexity of memory mapping approaches based on block size and parallelism. Moreover, the memory required to store command words both in case of on chip and off chip execution of memory mapping approaches is also compared. For experimental purpose, one hard processor PowerPC time for [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] is achieved as compared to [TAR04] [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] for all block lengths. For L = 5120 with P = 32, using PowerPC the execution time in case of [TAR04] is same as [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] which is about 2 hours whereas by using the approach [SAN13] the execution time is reduced significantly to only 127ms. Furthermore, the results for [SAN13] also include the delay introduced by routing information generation process whereas the routing information is automatically generated as crossbar is considered for [TAR04] and [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF]. For experimental purpose, we have considered crossbar for [TAR04] and [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] for which the time to generate routing information is very simple and automatic so we considered it negligible. An additional delay of 0.2ms (not included in the results shown in Figure 5.13 and 5.14) is required in order to generate routing information in case of [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] for complete block length of size L=256 with P=32, which increases to 4ms for L=5120 with same P.

However, for the same block length the delay in command word generation remains almost the same for different level of parallelism as explained in previous section. Furthermore, we performed experiments with P=4, 8, 16 and 32 for L=5120 as shown in Figure 5.14. From these experiments, significant reduction in execution time for [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] can be seen as compared to [TAR04] and [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF]. Furthermore, the execution time for [START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] has no significant change with increase in parallelism whereas execution time for

[TAR04] and [START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF] increases almost 25 times with the increase in parallelism from P =4 to P =32. From architecture perspectives, cost of our architecture always remains constant for different parallelisms supporting several block lengths for each processor. However, for offline memory mapping approaches, high memory cost is required to support several block lengths. Figure 5.15 shows the comparison between the memory required to store command words with P=4, 8, 16 and 32. Same memory is reused to store command words as soon as the parallelism is changed in order to support this parallelism in case of proposed approach whereas off-chip approaches require additional memory to store new set of command words with each type of parallelism. For P=32, size of memory required in case of off-chip approach to store command words is 64-Mbits to implement all the block sizes used in 3GPP-WCDMA. Thanks to the extensive reuse of RAM only 128Kbits of memory is required in case of on-chip execution of mapping algorithms. However, we need an embedded processor for the proposed approach.

Normalized runtime

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

On-chip implementation of memory mapping algorithms to support flexible decoder architectur -112 -

Conclusion

In this chapter, we have proposed to embed memory mapping approaches on-chip to solve memory conflict problem in parallel hardware decoders. Dedicated architecture composed of an embedded processor and RAM blocks to store command words is proposed.

We have embedded on-chip a polynomial time memory mapping approach and routing algorithm based on Benes network to solve memory conflict problem in parallel hardware decoders. Different experiments have been performed by using existing memory mapping approaches executed on several embedded processors. Results showed that the on-chip implementation of polynomial time memory mapping approaches allows to reduce significantly the execution time and reduction in hardware cost by the use of RAM blocks instead of multiple ROM blocks (though we need an embedded processor for proposed approach).

Future perspective of this work is to further improve the execution time by using ASIPs or ASICs to target real time flexible decoder architectures and to include cache like mechanism to speed up the switch from one configuration to another one. Another future perspective is to embed the polynomial time approaches proposed in this thesis (in-place memory mapping architecture approaches) to support flexible hardware architecture to support multiple block lengths and/or multiple applications.

CONCLUSION AND FUTURE

PERSPECTIVES

Turbo and LDPC codes are two families of codes that are extensively used in current communication standards due to their excellent error correction capabilities. For high throughput performance, decoders are implemented on parallel architectures in which more than one processing elements decode the received data. However, parallel architecture suffers from memory conflict problem. It increases latency of memory accesses due to the presence of conflict management mechanisms in communication network and unfortunately decreases system throughput while augmenting system cost.

To tackle memory conflict problem, three different types of approaches exist in literature. In first type of approaches, codes are constructed with good error correction capabilities without any conflicts. Also, these interleavers often simplify the parallel decoder architectures. However, these are conflict free only for particular types or degrees of parallelism used in turbo decoding or for a subset of block lengths. A second class of solution to deal with memory access conflict problem is to simply assign data in different memory locations without considering concurrent access issue and then use additional buffers in the interconnection network to manage memory conflicts. These kinds of approaches can greatly increase the cost of the system due to presence of interconnection network and buffer management mechanism to manage conflicts. The total latency of the system is also impacted since each conflicting data access must travel buffers before being stored in the memory banks which in turn decreases the throughput. Third type of approaches are design time memory mapping approaches. The resultant architectures consist of ROM blocks used to store configuration bits. The use of ROM blocks may be sufficient to design parallel architecture that supports single codeword or single application. However, to design hardware architecture that supports complete standard or different applications, ROM based approach results in huge hardware cost and area.

In this thesis, we aimed to design optimized parallel interleaver architecture. For this purpose, we have proposed two different categories of approaches. In first category, we have proposed optimized design time off-chip approaches that aim to limit the cost of final decoder architecture targeting the customization of the network and the use of in-place memory architecture.

In the second category, we have introduced a new method in which both runtime and design time approaches can be merged to design flexible decoder. For this purpose, we have embedded memory mapping algorithms on-chip in order to execute them at runtime to solve conflict problem. The on-chip implementation replaces the ROM blocks with a single RAM block to support multiple block lengths and/or to support multiple applications. Different experiments are performed by executing memory mapping approaches on several embedded processors.

Future Perspectives

A lot of scope for future enhancement of proposed contributions is possible. In future, we can further optimize the decoder architecture by merging the two design time approaches proposed in this thesis: the network customization and in-place architecture. We can take advantage of using the customized network approach along with in-place memory mapping architecture in order to generate strongly optimized architectures. Another future perspective is to embed proposed polynomial time approaches (in-place memory mapping architecture approaches) to support flexible hardware architecture for different block lengths with in a standard or to support different standards.

In the on-chip approach, memory mapping approaches are also executed on several embedded processors. The results showed that the proposed approach allows to greatly improve timing performances and to reduce memory footprint. Future perspective of this work is to further improve the execution time by using ASIP or ASICs to target real time flexible decoder architectures and to include cache like mechanism to speed up the switch from one configuration to another one.

Furthermore, the memory mapping approaches can be used to solve memory mapping like problems from other signal processing and telecommunication domains. Implementation of different algorithms on parallel processing becomes an active domain of research after the development of high data rate applications. In all of these implementations, multiple accesses cause memory conflict problem. In future, current algorithms could be used to solve the mapping problem of other applications used in signal processing domain.

  64 3.3.Simple graph test -

  82 3.5.4.Pedagogical Example -

  90 4.3.Case study-3: Shuffled turbo decoding for HSPA --------------------chip implementation of memory mapping algorithms 97 2.1.Proposed Design flow -

Figure 2 .

 2 Figure 1. 1 A generic digital communication system .............................................................................. Figure 1. 2. Turbo encoder ...................................................................................................................... Figure 1. 3. Turbo decoder ...................................................................................................................... Figure 1. 4. Taner graph representation of H matrix ............................................................................... Figure 1. 5. Typical Parallel Architecture ............................................................................................. Figure 1. 6. Data access matrices for turbo codes ................................................................................. Figure 1. 7. Memory Conflict Problem in Parallel Turbo Decoder ....................................................... Figure 1. 8. Memory Conflict Problem in Partially Parallel LDPC Decoder ........................................Figure 2. 1. Interleaver construction......................................................................................................Figure 2. 2. Interleaver matrix ............................................................................................................... Figure 2. 3. Tanner graph formalization of an LDPC H-matrix ............................................................ Figure 2. 4. Structured LDPC codes ...................................................................................................... Figure 2. 5. Architecture based on LLR Distributor.............................................................................. Figure 2. 6. Architecture based on Double buffer ................................................................................. Figure 2. 7. Architecture based on NoC ................................................................................................ Figure 2. 8. Parallel architecture with multistage network .................................................................... Figure 2. 9. Matrices used in SAGE ......................................................................................................Figure 2. 10. Multiple Read Multiple write (MRMW) approach .......................................................... Figure 2.11. Me Resulting architecture with additional registers and steering logic for Memory relaxation based approach ..................................................................................................................... Figure 2.12. In-place mapping .............................................................................................................. Figure 2.13. Resultant In-place mapping architecture ........................................................................... Figure 2.14. MRMW mapping .............................................................................................................. Figure 2.15. MRMW architecture ......................................................................................................... Figure 3. 1 Decoding Architecture for Turbo Decoders ........................................................................ Figure 3. 2 Integrated design flow for Turbo decoder architectures exploration .................................. Figure 3. 3 Scheduling for Turbo Decoding .......................................................................................... Figure 3. 4 Area estimations of the considered configurations ............................................................. Figure 3. 5. Proposed Memory Mapping Exploration Flow for Network Relaxation Approach .......... Figure 3. 6. Memory Mapping model ................................................................................................... Figure 3. 7. Mapping algorithm with network relaxation ...................................................................... Figure 3. 8. Network customization ...................................................................................................... Figure 3. 9 Barrel shifter ....................................................................................................................... Figure 3. 10 Mapping with BS .............................................................................................................. Figure 3. 11 Network relaxation with BS .............................................................................................. Figure 3. 12 Network relaxation without any NW constraint ............................................................... Figure 3. 13 Comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach ........................................................................................................ Figure 3. 14 Comparison of HSPA Network Controllers latencies obtained with state of art approaches and Network Relaxation approach ........................................................................................................ Figure 3. 15. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, Targeted network: Barrel Shifter) .... Figure 3. 16 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, Targeted network: Barrel Shifter) .......

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure 4 .

 4 Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................ Figure 4.4 Multi-graph ..........................................................................................................................Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................Figure 4.7 General Graph for edge coloring .........................................................................................Figure 4.8 Bipartite test .........................................................................................................................Figure 4.9 Birpartite test example .........................................................................................................Figure 4.10 Simple Graph test ...............................................................................................................Figure 4.11 Simple graph test example .................................................................................................Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors) ..........................................Figure 4.13 Vizing fan ...........................................................................................................................Figure 4.14 Vizing theorem Case-1 .......................................................................................................Figure 4.15 Vizing theorem Case-2 .......................................................................................................Figure 4.16 Vizing theorem Case-2a .....................................................................................................Figure 4.17 Vizing theorem Condition for Case-2b ..............................................................................Figure 4.18 Vizing theorem Case-2b .....................................................................................................Figure 4.19 Vizing theorem Case-2b final ............................................................................................ Figure 4.20 Example for Vizing theorem .............................................................................................. Figure 4.21 Graph for Figure 4.6 ..........................................................................................................Figure 4.22 Vizing theorem Case-1 .......................................................................................................Figure 4.23 Vizing theorem Case-2a .....................................................................................................Figure 4.24 Vizing theorem Case-2b .....................................................................................................Figure 4.25 Resultant in-place architecture ...........................................................................................Figure 4.26 Example resulting a multigraph .........................................................................................Figure 4.27 Bipartite Graph for example of Figure 4.26 .......................................................................Figure 4.28 Partitioning algorithm ........................................................................................................Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm .........................................Figure 4.30 Resulting cycle obtained with proposed cycle construction approach ...............................Figure 4.31 Approach based on transportation problem (part-1) ..........................................................Figure 4.32 Approach based on transportation problem (part-2) ..........................................................Figure 4.33 Mapping based on transportation problem ......................................................................... Figure 4.34 Area comparison for shuffled turbo decoders with P=16 ..................................................Figure 4.35 Architecture for NB-LDPC ................................................................................................Figure 4.36 Data Access Matrix for L = 192 and dc = 6 .......................................................................

Figure

  Figure 4.37 Comparison of NB_LDPC decoder areas obtained with state of art approaches and Vizing coloring for different block length (P = 6) ............................................................................................ Figure 4.38 Comparison of NB_LDPC decoder areas obtained with state of art approaches and Vizing coloring for different block length (P = 12) ..........................................................................................Figure 4.39 Area comparison for different block length for HSPA P = 16 (best results) ..................... Figure 5.1 Parallel decoder architecture ................................................................................................ Figure 5.2 Parallel decoder architecture to embed memory mapping algorithms on chip .................... Figure 5.3 Embedded conflict free memory mapping flow ................................................................... Figure 5.4 Arrangement of L = 44 data into 5*10 matrix ................................................................... Figure 5.5 Matrix after Intra-row Permutation .................................................................................... Figure 5.6 Matrix after Inter-row Permutation .................................................................................... Figure 5.7 Data access matrix ............................................................................................................. Figure 5.8 Bipartite Edge Coloring Algorithm .................................................................................... Figure 5.9 SN1 and SN2 for the routing algorithm ............................................................................. Figure 5.10 A Complete Residue Partition Tree (CRPT) .................................................................... Figure 5.11 Routing example .............................................................................................................. Figure 5.12 Example with complete routing tags ................................................................................ Figure 5.13 Normalized Run time Values for different embedded processors with PE = 32 ............. Figure 5.14 Normalized Run time Values of for different types of parallelism with L=5120 ............ Figure 5.15 Area Comparison of on-chip and off-chip implementation for different P......................

Figure 1

 1 Figure 1. 1 A generic digital communication system A generic digital communication system is shown in Figure 1. 1. The block diagram consists of building blocks each performing a certain well-defined operation on data. The transmitter transforms the signals from information source to the channel. The transmitter consists of blocks namely Digital to analog converter, Source Encoder, Channel Encoder and Digital modulator. Digital to analog converter converts the input information source intobinary digits (bits), groups them together to form digital messages. Source Encoder tries to increase the information content of source symbols by removing the redundant information and encoding the source data using fewer bits than uncoded information. Channel encoding can reduce the errors rates at the expense of decoder complexity. Starting from K bits the channel encoder provides a codeword c of length N by adding N -K redundant bits. By means of introduced redundancy, the channel decoder is able to identify errors introduced by channel and correct some of them. Digital Modulator is a block that facilitates the transfer of information over a passband channel. In digital modulation, an analog carrier is modulated by a digital bit stream. Based on a particular application and channel condition, different

FEC

  codes can be classified into two categories: Block codes and Convolutional codes. Convolutional codes are increasingly used in different telecommunication standards due to their simple and efficiently implementable structures. Currently, convolutional codes are part of standards for mobile communication (HSPA [HSP04], LTE [LTE08]) and digital broadcasting (DVB-SH [DVBS08]). Convolutional codes work as a finite state machine which converts continuous stream of bits into continuous stream of coded bits.

  Figure 1. 3. Turbo Decoder

  density parity check Codes (LDPC) are another class of very high performances error correction codes. They are members of the class of Block codes that are used to transmit information reliably through noisy communication channels. Many types of block codes are used in different applications such as Reed-Solomon [AHA], Golay codes [GOL61] or Hamming codes [HAM50]. LDPC codes have already been included in several wireless communication standards such as DVB-S2 and DVB-T2 [DVB08], WiFi (IEEE 802.11n) [WIF08] or WiMAX (IEEE 802.16e) [WIM06]. The code is represented with parity check equations. As a pedagogical example, consider a codeword: C = [c 1 c 2 c 3 c 4 ] which satisfies the following three parity check equations.

Figure 1

 1 Figure 1. 4. Tanner Graph representation of H

  Figure 1. 5. Typical Parallel Architecture

Figure 1 . 6 .

 16 Figure 1. 6. Data access matrices for turbo codes

8

  .a. The data elements stored in bank b 0 , bank b 1 and bank b 2 are (1,4), (2,5) and (3,6)

Figure 2

 2 Figure 2. 2. Interleaver matrix

Figure 2 . 3 .

 23 Figure 2.3. The check node processors access the vectors nodes data elements in parallel by using simple interconnection network like barrel shifter thanks to the structure of identity matrix in each sub-block.

Figure 2

 2 Figure 2. 4. Structured LDPC codes

Figure 2

 2 Figure 2. 8. Parallel architecture with multistage network

  Figure 2. 10. Multiple Read Multiple write (MRMW) approach

Figure 2 .

 2 Figure 2.11. Resulting architecture with additional registers and steering logic for Memory relaxation based approach

Figure 2 .Figure 2

 22 Figure 2.12. In-place mapping

  Figure 2.14. MRMW mapping

Figure 2

 2 Figure 2.15. MRMW architecture

39 3 .

 3 Memory mapping approach based on network customization 42 3.1.Proposed Approach -

Figure 3 .

 3 Figure 3. 1 shows the turbo decoder architecture. Through an interconnection network the processing elements (PEs) have access to a set of B memory blocks (single port RAM), allocated to keep the extrinsic information. The controller part consists of Read Only Memories which are used to address each memory block and control signals of the

  Figure 3. 1 Decoding Architecture for Turbo Decoders Let T denotes the number of clock cycles where each PE performs writing or reading memory access in order to execute one iteration (for a non-shuffled turbo decoder), or a half iteration (for a shuffled turbo decoder). Let M represents the size of each memory block. The size of each addressing ROM is T*⌈log 2 (M)⌉. Note that iteration in a shuffled and nonshuffled turbo decoder takes the same time if both turbo decoders have the same sub-block size M.

  .2. Inputs include description of the interleaver law (π), the SISO decoder architecture (shuffled/non-shuffled), parallelism P and interconnection network delay (critical path of the interconnection network). The first step in the design flow is the generation of the data access description files based on the input information. These files contain the sequence of extrinsic information values that are read or written by each PE decoder at each clock cycle. This step also tackles memory issues in case of shuffled decoding (discussed later in details). The first step generates data access description file in which information about block length, parallelism and data access patterns are mentioned. In the second step, memory access description files are used to find conflict Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 free memory mapping using appropriate approaches. Thus, extrinsic values are assigned to B memory banks positions without any conflict. From this memory mapping, the controller can be designed and the content of ROM memories can be established. Finally, estimations of the turbo decoder throughput and hardware complexity are done.

Figure 3 . 2

 32 Figure 3. 2 Integrated design flow for Turbo decoder architectures exploration

Figure 3 . 3

 33 Figure 3. 3 Scheduling for Turbo Decoding

  Figure 3. 6. Memory Mapping model The data access matrix in then modeled to a mapping matrix as shown in Figure 3. 6(b)

  Figure 3. 8. Network customization

  Figure 3. 9 Barrel shifter

  Figure 3. 10 Mapping with BS Table 3.4 Permutations after adding network component with BS σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8 b0 b3 b2 b1 b0 b3 b2 b1 b1 b0 b3 b2 b1 b0 b3 b2 b2 b1 b0 b3 b3 b2 b1 b0 b3 b2 b1 b0 b2 b1 b0 b3

Figure 3 .

 3 Figure 3. 11 Network relaxation with BS Then, the memory mapping process is done with this new set of permutations. The entire matrix can be filled according to this new set of permutations as shown in Figure 3. 11(b). The resultant architecture based on customized network is shown in Figure 3. 11(a) which consists of BS network and one additional network component (a swicth).

Figure 3 .

 3 Figure 3. 12 Network relaxation without any NW constraint

Figure 3 .Figure 3

 33 Figure 3. 13 Comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach

Figure 3 .Figure 3

 33 Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4)

Figure 3

 3 Figure 3. 21. Parallel architecture with multistage network

  64 3.3.Simple graph test-

  67 3.4.1.Pedagogical Example -

  Case study-1: Shuffled turbo decoders for LTE -

  88 4.2.1.Vizing theorem for non-binary LDPC codes -

  90 4.3.Case study-3: Shuffled turbo decoding for HSPA -

Figure 4 . 1

 41 Figure 4.1 Solution for memory conflict problems

Figure 4 . 2

 42 Figure 4.2 Categories in two access problem

Figure 4 . 3

 43 Figure 4.3 Simple graph

  Figure 4.4 Multi-graph

  Figure 4.5 Design flow

Figure 4 . 7

 47 Figure 4.7 General Graph for edge coloring

Figure 4 . 8

 48 Figure 4.8 Bipartite test

Figure 4 .

 4 Figure 4.10 Simple Graph test

  3b) Otherwise enqueue the neighbor nodes (the direct child node) which are not yet traversed as shown in Figure 4.11. 4) If the queue is empty, every node on the graph has been visited then the algorithm is completed, else repeat previous step.

Figure 4 .

 4 Figure 4.11 Simple graph test example

Figure 4

 4 Figure 4.12 Edge coloring flow based Vizing theorem (up to P+1 colors)

Figure 4 .

 4 Figure 4.13. Mathematically, in each iteration we extend the graph coloring of G i-1 to colour

Figure 4 .

 4 Figure 4.13 Vizing fan

  Figure 4.15 Vizing theorem Case-2

Figure 4 .Figure 4 .

 44 Figure 4.16(c)). Hence, the conflict edge is colored.

  Figure 4.18 Vizing theorem Case-2b

Figure 4 .

 4 Figure 4.19. Hence, the conflict edge is colored.

Figure 4 .

 4 Figure 4.19 Vizing theorem Case-2b final

Figure 4 .

 4 Figure 4.20 Example for Vizing theorem

Figure 4 .

 4 Figure 4.21(b) shows that we have already partially colored the edges of G i-1 using P+1colors. The five colors shown in the figures are c 0 , c 1 , c 2 , c 3 , and c 4 for this example. The dotted line represents conflict edge e i to be colored. Colors c 0 and c 4 are missing at t 1 and c 1 and c 3 are missing at t 16 (see Figure 4.21(b)).

  Figure 4.21 Graph for Figure 4.6

Figure 4 .

 4 Figure 4.23 Vizing theorem Case-2a

Figure 4 .

 4 Figure 4.24 Vizing theorem Case-2b

Figure 4 .

 4 Figure 4.25 Resultant in-place architecture

Figure 4 .

 4 Figure 4.26 Example resulting a multigraph According to theorem presented above, a multigraph for a given memory mapping problem can be edge colored with atmost (3/2)*P colors which results in finding conflict free memory mapping using upto (3/2)*P banks. In order to edge color a multi-graph, we have proposed a simple polynomial time algorithm based on approach used for transportation problem using (3/2)*P banks which respects the bound introduced in [SHA49].

  Figure 4.26(a) is shown in Figure 4.27(a).

Figure 4 .

 4 Figure 4.27 Bipartite Graph for example of Figure 4.26

  Figure 4.27(b). In this graph, |E 1 | = |L| i.e., each edge in G 1 corresponds to two edges or a data node in G t . Since G 1 is regular, 2-factor always exists in G 1 which implies that semi 2-factor of 2Y nodes where |T| = Y always exists in G t . Every 2-factor is a collection of cycles that spans all nodes of the graph going from 1 cycle with 2Y nodes up to Y/2 cycles of 4 vertices. Additionally, each cycle c i in G 1 can be even or odd which means c i contains even or odd number of edges or time nodes.

[ SAN11b ]

 SAN11b Figure 4.28.

Figure 4 .

 4 Figure 4.28 Partitioning algorithm

Figure 4 .

 4 Figure 4.29 Cycle construction problem for [SAN11a] coloring algorithm

  Figure 4.26. The first step is to constructs the bipartite graph which is shown in Figure 4.27(a). This semi regular bipartite graph has time nodes with degree ft = 4. There are two semi 2-factors using corollary 4.3. The second step first transforms the bipartite graph into matrix model of the transportation problem which is depicted in Figure 4.31(a). The algorithm starts constructing the cycle c 1 from the first route l 01 (data d 0 connected with time node t 1 ) and assigns the memory bank b 0 . Since one route is occupied, the algorithm Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Figure 4 .

 4 Figure 4.31(c). However, as shown in this figure that producer d 0 is assigned with different memory banks b 0 and b 1 which is in-valid for mapping as one data could not be mapped in two banks. Therefore, an additional bank is needed for d 0 so we will assign b 2 for d 0 both at t1 and t3 as shown in Figure 4.31(d).

Figure 4 .

 4 Figure 4.31 Approach based on transportation problem (part-1)

Figure 4 .

 4 Figure 4.32(a). We need only one additional bank for all cycles in a semi 2-factor as

Figure 4 .

 4 Figure 4.32 Approach based on transportation problem (part-2)

  Figure 4.32(b) in which there are shown two cycles c 1 and c2 (in Figure 4.32(b) c 1 is shown in plane and c 2 is shown in gray cells). c 2 is also odd cycle so we also need an extra bank to map it. The final mapping is shown in Figure 4.33(a) in which six ((3/2)*P) banks are used to find conflict free memory mapping. The Figure 4.33(b) gives the final architecture along with the memory mapping for the considered example.

  Figure 4.33 Mapping based on transportation problem

Figure 4 .Figure 4 .

 44 Figure 4.34 Area comparison for shuffled turbo decoders with P=16

Girth g <= 4

 4 are normally considered as short cycles in LDPC codes. Short cycles are avoided in LDPC codes as it degrades the performance of the decoder [XIO05]. If g <= 4

Figure 4 .

 4 Figure 4.37 Comparison of NB_LDPC decoder areas obtained with state of art approaches and Vizing coloring for different block length (P = 6)

Figure 4 .

 4 Figure 4.38 Comparison of NB_LDPC decoder areas obtained with state of art approaches and Vizing coloring for different block length (P = 12)

Figure 4 .

 4 Figure 4.39 Area comparison for different block length for HSPA P = 16 (best results)

Figure 5 . 1 Figure 5 . 2

 5152 Figure 5.1 Parallel decoder architecture

Figure 5 . 3

 53 Figure 5.3 Embedded conflict free memory mapping flow

Figure 5 . 4

 54 Figure 5.4 Arrangement of L = 44 data into 5*10 matrix

  Figure 5.8 Bipartite Edge Coloring Algorithm

  So, if K is odd then the algorithm first finds perfect matching Mp in G, assign one color to the edges of Mp and remove Mp from G. The problem is reduced to even (K-1)-regular graph. The perfect matching algorithm runs in O(kD) time. The complete edge coloring of G' after attaching data vertices in G is shown in Figure 5.8(b). In this figure, three colors of the edges, corresponds to three memory banks, are represented with gray bold, gray narrow and gray dotted lines. Further details on this algorithm can be found in [SAN13]. The resultant memory mapping is: Bank b 0 ={0,2,3,5}, Bank b 1 ={1,7,8,10}, Bank b 2 = {4,6,9,11} Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

  issues prevent the use of crossbar networks for large network sizes [DUA03]. For a Crossbar network, the size of network_RAM= T* (B *log 2 B).

Figure 5 .

 5 Figure 5.9 SN1 and SN2 for the routing algorithmIn a Benes network, many useful permutations, often required in parallel processing environments are found to be self-routable. Lenfant proposed efficient set-up algorithms for some frequently used permuatation as bijections[START_REF] Lenfant | Parallel permutations of data: A Benes network control algorithm for frequently used permutations[END_REF], namely the FUB family. Nassimi and Sahni[START_REF] Nassimi | A self-routing Benes network and parallel permutation algorithms[END_REF] proposed a simpler algorithm for routing the F class of permutations that includes the bit-permute complement (BPC) and inverse omega classes of permutations.

Figure 5 .

 5 Figure 5.10 A Complete Residue Partition Tree (CRPT)

  SN2, the remaining n switching stages are controlled by b (n-l) ,b (n-2) ,…, b 0 used as control bits C o , C l , … , C (n 1) , respectively.

  Figure 5.11(a). SN1 consist of first two stages and SN2 consist of last three stages. For SN1, the division of stages in the CRPT is shown in Figure 5.11(b) in which the permutation is shown in binary form controlled by three digits b 2, b 1 and b 0. In the first stage E O of SN1, CRP is applied on CRS (mod 8) which is divided in two CRS(mod 4) using two bits bits b 1 b 2 i-e (000, 010, 101, 111) and (100, 110, 001, 011) see Figure 5.10. In the second stage E 1 of SN1, CRP is applied on each CRS (mod 4) which divide each of it independently in two further two sets of CRS(mod 2) using one bit b 2 i-e (000, 101), (010, 111), (100, 001), and (110, 011).

  Figure 5.11 Routing example

  embedded in Xilinx FPGA and one soft processor NIOS-II used in Altera FPGAs are considered to execute the approach proposed in[START_REF] Sani | A First Step Toward On-Chip Memory Mapping for Parallel Turbo and LDPC Decoders: A Polynomial Time Mapping Algorithm[END_REF] and the results are compared with other state of the art approaches [TAR04][START_REF] Chavet | Static address generation easing: a design methodology for parallel interleaver architectures[END_REF]. The execution times for these approaches are measured for different processors. Moreover, HSPA interleaver used in 3GPP-WCDMA [HSP04] is implemented on parallel architecture. In this thesis we have mostly chosen HSPA interleaver for our experiments because the number of conflicting data elements in this interleaver is high as compared to other interleavers. To design parallel conflict free architecture for this interleaver, memory mapping approaches are required to generate commands word for network and memory to support all the block sizes with different parallelisms. The first processor we considered for the experiments is PowerPC which is a hard processor embedded in Xilinx Virtex-5 ML507 board. Processor clock frequency of 400MHz and System clock frequency of 100MHz was used to perform experiments. The second processor we considered in our experiments is NIOS II. NIOS II is a soft processor used in Altera FPGAs. NIOS II has been implemented on Cyclone-III NIOS II Embedded Evolution Kit with Processor clock frequency of 195MHz and System clock frequency of 50MHz. Normalized time values (as each embedded processor has different frequency so we have Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 normalized all the values to PowerPc) are used to measure the impact of architecture of embedded processors on execution time. PowerPC execution time is used as a reference for normalized time and execution times of NIOS II is normalized with respect to the PowerPC clock frequencies. The normalized times to execute (only the time needed to execute the memory mapping approach) [TAR04] [CHA10a] and [SAN13] on embedded processors for different L with P =4,8,16 and 32 are studied. The normalized times to execute [TAR04] [CHA10a] and [SAN13] for different L with P =32 are shown in Figure 5.13 for NIOS II and PowerPC. From processor perspective, PowerPC executes the mapping algorithm in the least time as compared to NIOS II. From this figure, it is evident that significant reduction in execution

Figure 5 .

 5 Figure 5.13 Normalized Run time Values for different embedded processors with PE = 32

Figure 5 .

 5 Figure 5.14 Normalized Run time Values of for different types of parallelism with L=5120

Figure 5 .

 5 Figure 5.15 Area Comparison of on-chip and off-chip implementation for different P

108 3.Experiments 109 4.Conclusion 112 Conclusion and Future Perspectives 113 Bibliography 115 Abbreviations 123 List of Figures Figure

  1. 1 A generic digital communication system .............................................................................. Figure 1. 2. Turbo encoder ...................................................................................................................... Figure 1. 3. Turbo decoder ...................................................................................................................... Figure 1. 4. Taner graph representation of H matrix ............................................................................... Figure 1. 5. Typical Parallel Architecture ............................................................................................. Figure 1. 6. Data access matrices for turbo codes ................................................................................. Figure 1. 7. Memory Conflict Problem in Parallel Turbo Decoder ....................................................... Figure 1. 8. Memory Conflict Problem in Partially Parallel LDPC Decoder ........................................ Figure 2. 1. Interleaver construction...................................................................................................... Figure 2. 2. Interleaver matrix ............................................................................................................... Figure 2. 3. Tanner graph formalization of an LDPC H-matrix ............................................................

Figure 2. 4. Structured LDPC codes ...................................................................................................... Figure 2. 5. Architecture based on LLR Distributor..............................................................................

Figure 2. 6. Architecture based on Double buffer ................................................................................. Figure 2. 7. Architecture based on NoC ................................................................................................ Figure 2. 8. Parallel architecture with multistage network .................................................................... Figure 2. 9. Matrices used in SAGE ......................................................................................................

Figure 2. 10. Multiple Read Multiple write (MRMW) approach ..........................................................

Figure 2.11. Me Resulting architecture with additional registers and steering logic for Memory relaxation based approach .....................................................................................................................

  Figure 3. 13 Comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach ........................................................................................................ Figure 3. 14 Comparison of HSPA Network Controllers latencies obtained with state of art approaches and Network Relaxation approach ........................................................................................................Figure 3. 17. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, No targeted network) ......................... Figure 3. 18 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, No targeted network) ........................... Figure 3. 19. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=4) ................................ Figure 3. 20. Comparison of HSPA decoder architecture estimated areas obtained with state of art approaches and Network Relaxation approach for different block lengths (P=8) ................................ Figure 3. 21. Parallel architecture with multistage network .................................................................. Figure 3. 22. Comparison of LTE decoder architecture estimated areas obtained with state of art Approache and Network Relaxation approach for different block lengths (P=4) ................................Figure 4.1 Solution for memory conflict problems ...............................................................................Figure 4.2 Categories in two access problem ........................................................................................Figure 4.3 Simple graph ........................................................................................................................Figure 4.4 Multi-graph ..........................................................................................................................

Figure 3. 15. Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=2240, P=4, Targeted network: Barrel Shifter) .... Figure 3. 16 Detailed comparison of HSPA Network Controllers Areas obtained with state of art approaches and Network Relaxation approach (L=800, P=8, Targeted network: Barrel Shifter) .......

Figure 4.5 Design flow .......................................................................................................................... Figure 4.6 Example of data access matrix with two accesses to each data ...........................................

Figure 4.7 General Graph for edge coloring .........................................................................................

Figure 4.8 Bipartite test .........................................................................................................................

Figure 4.9 Birpartite test example .........................................................................................................

  4.37 Comparison of NB_LDPC decoder areas obtained with state of art approaches and Vizing coloring for different block length (P = 6) ............................................................................................ Figure 4.38 Comparison of NB_LDPC decoder areas obtained with state of art approaches and Vizing coloring for different block length (P = 12) ..........................................................................................Figure 4.39 Area comparison for different block length for HSPA P = 16 (best results) ..................... Figure 5.1 Parallel decoder architecture ................................................................................................ Figure 5.2 Parallel decoder architecture to embed memory mapping algorithms on chip .................... Figure 5.3 Embedded conflict free memory mapping flow ................................................................... Figure 5.4 Arrangement of L = 44 data into 5*10 matrix ................................................................... Figure 5.5 Matrix after Intra-row Permutation .................................................................................... Figure 5.6 Matrix after Inter-row Permutation .................................................................................... Figure 5.7 Data access matrix ............................................................................................................. Figure 5.8 Bipartite Edge Coloring Algorithm .................................................................................... Figure 5.9 SN1 and SN2 for the routing algorithm ............................................................................. Figure 5.10 A Complete Residue Partition Tree (CRPT) ....................................................................

Figure 5.11 Routing example .............................................................................................................. Figure 5.12 Example with complete routing tags ................................................................................ Figure 5.13 Normalized Run time Values for different embedded processors with PE = 32 ............. Figure 5.14 Normalized Run time Values of for different types of parallelism with L=5120 ............ Figure 5.15 Area Comparison of on-chip and off-chip implementation for different P......................

Table 3 .

 3 1. Interconnection network area ..............................................................................................Table 3. 2. Different configuration to explore the design space for turbo decoding ............................... Table 3. 3. Cost calculation ................................................................................................................... Table 3. 4. Permutations after adding network component with BS ..................................................... Table 3. 5. Block lengths supported by BS ........................................................................................... Table 4. 1: Different configuration to explore the design space for turbo decoding ............................. Table 5. 1. List of prime number p and associated primitive root v .................................................... Table 5. 2. Turbo code interleaver parameters ....................................................................................Wireless communication is undoubtedly one of the major research areas in telecommunication today. Broad progress can be observed in this field in the past decade, although it has been a topic of study since 1960s. The ongoing goal of providing enhanced services seamlessly and effectively continues to drive wireless communications. We have seen the outcomes in the form of cellular systems that have experienced exponential growth over the last decade with billions of customers worldwide. Incorporation of multimedia and value added services in telecommunication have dramatically increased data rate requirements.

	1. Introduction
			Transmitter
	Source
	information	Digital to	Source	Channel	Digital
		analog	Encoder	Encoder	Modulator
					Communication channel	Noise
					[Wired/Wireless]
			Transmitter
	Sink
	information	Analog to	Source	Channel	Digital de-
		digital	decoder	decoder	modulator

  Figure 1. 8. Memory Conflict Problem in Partially Parallel LDPC Decoder Several approaches exist in literature in order to tackle the memory conflict problem.

	PE 1 PE 2 PE 3	t 1 1 2 3	t 2 3 5 6	t 3 6 1 4	Time t 4 t 5 5 4 6 3 2 5	t 6	2 1 4	PE 1 PE 2 PE 3	Network	Interconnection	Conflict Problem	1,4 2,5 3,6	Bank b 0 Bank b 1 Bank b 2
		(a) Data access matrix						(b) Conflict at t 2
						Figure 1. 8.b shows the memory conflict for the time
	instance t 2 .

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 However optimization is needed to design high throughput decoder architectures. The main purpose of this thesis is to optimize the design of parallel architectures focusing on the memory conflict problems (interleavers) in order to reduce the cost for high throughput Turbo and LDPC decoders. The rest of the thesis is organized as follow:

Chapter 2

In this chapter, an overview of the state of the art approaches to design parallel hardware architectures for Turbo and LDPC decoders is provided. The state of the art is presented in three different categories. The merits and limitations of each of the approaches are explored.

Table of Contents 1

 of1

  Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 simple due to the use of destination address bits for selecting output port of router at each stage of the network. The routers stores conflicting packets using FIFOs. However, Butterfly network lacks in path diversity as it provides distinctive path between source and destination.

	processors and memory banks. This architecture consists of FIFOs associated with processors,
	circular buffers, multiplexers and bypass units as shown in Figure 2. 6. The conflicting
	accesses are routed into a dedicated circular buffer as soon as a conflict is detected. The
	interest of this approach has been demonstrated by designing an interleaver used in a
	HSPA+/LTE decoder. However, this architecture is configured on the basis of simulation Bank 1 PE 1 router router router
	results analysis in order to handle conflicts. PE 1 Circular buffer FIFO PE 2 router router	MUX router	Bank 1 Bank 2	Address Controller
	PE 2	PE P	FIFO router	Circular buffer Network Controller Controller MUX router router	Bank 2 R/W Bank B	Address Controller
	PE P		Bank B Figure 2. 7. Architecture based on NoC Circular buffer FiFO MUX
	Therefore, complex buffering architecture to manage conflicting packets is required
	which increases cost of the architecture. Benes network is the second multistage network
	R/W studied in [MOU07]. It is constructed by concatenating two Butterfly networks back-to-back. Network Controller
					Controller
	Bank 1 Bank 2 Bank B Figure 2. 6. Architecture based on Double buffer Register Address Controller FIFO MUX MUX Approaches based on Network-on-Chip (NoC) architecture are also proposed to PE P PE 2 PE 1 resolve the conflicts on run time. In [NEE05], approaches based on mesh, torus and cube networks are proposed in which routers are used to contain packets for the destination Interconnection network information. However, these approaches suffer from reduced scalability to construct high
	LLR distributer throughput flexible on-chip communication network. Also, due to complex buffer
	management architecture to store conflicting data, the router complexity increases Network Control Logic R/W significantly with the increase of parallelism.
	Controller Another solution based on NoC oriented architecture is presented in [MOU07]. In this
	Figure 2. 5. Architecture based on LLR Distributor work (see Figure 2.7), the interconnection network can be configured on-the-fly to compete
	with any classical interconnection network such as Butterfly and Benes. Butterfly network has
	In [WAN11], the authors proposed an approach based on Double-Buffer Contention-two main advantages: firstly, the network has huge scalability as a network of size N can be
	Free (DBCF) architecture. The DBCF architecture is built around the interleaver between the constructed from two networks of size N/2. Secondly, the packet routing algorithm is very
	Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

10 11 12 13 14 15 t 1 t 2 t 3 t 4 0 2 4 6 3 1 8 10 7 5 11 9 12 14 15 13 t 5 t 5 t 6 t 7 P1 P2 P3 P4 P1 P2 P3 P4 b 1 b 2 b 3 b 4

	0	1	2	3
	4	5	6	7
	8	9
	(a) Natural order access matrix	(b) Interleaved order access matrix
	P1			P1	b 1		b 2
	P2			P2			b 3
	P3			P3
	P4			P4	b 4
	t 1	t 2	t 3	t 4	t 5	t 5	t 6	t 7
		(c) MAP nat				(d) MAP int
		Figure 2. 9. Matrices used in SAGE
	There are two constraints to be respected during the execution of the SAGE algorithm
	in order to find architecture oriented memory mapping. The first constraint is to allocate
	different memory banks to the cells of each column of the mapping matrices. The second

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 constraint is to respect the targeted interconnection network if supported by the interleaving law. The algorithm is initialized by assigning memory banks to the first column of M Nat (see Figure 2.8.(c)). Then the entries corresponding to the data in M int are updated (reported) with this mapping information (see Figure 2.8.(d)

  elements {d 1 , d 2 ,…, d L } and a set of P processing elements {PE 1 , PE 2 ,…, PE P }. These processors process each of the L data elements two times in T time instances {t 1 , t 2 ,…, t

T } first in natural order and then in interleaved order, where T = 2L/P. In order to store these L data elements and to achieve parallel processing of data for high throughput, a set of B memory banks {b 1 , b 2 ,…, b B } are needed.

Table of Contents 1.Introduction 35 2.Dedicated approach to explore design space of turbo decoder architecture 35

 of

2.1.Turbo decoder architecture -

  the PEs, and T columns for the time instances. Data elements in each row are processed by the same PE. Similarly, the d.P data elements in each column have to be accessed in parallel by P PEs.

					Natural and interleaved order Access
	Natural order Access Interleaved order Access	PE N	1	0 9	1 8	2 7	3 6	4 5
	PE 1	0 1 2 3 4 9 8 7 6 5	PE 1	0 37 14 11 28 13 16 39 2 25	PE N PE N	2 3	10 19 20 29	11 18 21 28	12 17 22 27	13 16 23 26	14 15 24 25
	PE 2 PE 3	10 11 12 13 14 19 18 17 16 15 20 21 22 23 24 29 28 27 26 25	PE 2 PE 3	30 27 4 1 18 3 6 29 32 15 20 17 34 31 8 33 36 19 22 5	PE N PE I 1 4 PE I 2	30 39 0 13 30 3	31 38 37 16 27 6	32 37 14 39 4 29	33 36 11 2 1 32	34 35 28 25 18 15
	PE 4	30 31 32 33 34 39 38 37 36 35 t 1 t 2 t 3 t 4 t 5	PE 4	10 7 24 21 38 23 26 9 12 35 t 6 t 7 t 8 t 9 t 10	PE I 3 PE I 4	20 33 10 23 t 1	17 36 7 26 t 2	34 19 24 9 t 3	31 22 21 12 t 4	8 5 38 35 t 5
		Time		Time					Time
	(a) Scheduling for non-shuffled decoding	(b) Scheduling for shuffled decoding

level parallelism is used [WOO00] which are represented by radix-2 s (s = 1, 2, …) in which d = 2 s rows are processed by each processors in parallel. Hence, each PE accesses d data elements i-e d rows in the matrix. Each matrix has d.P rows for the extrinsic values accessed by

Table 3

 3

		.1 Interconnection network area
	Network size	Pipeline stages Area (Logic gates)
	32x32	1	7.4k
	64x64	1	18.9k
	128x128	2	45.7k

Table 3

 3

	approach described in section 2.2.2 was applied to the 9 configurations shown in Table 3.2,
	for P = 16 and 32. The hardware cost of the resultant architecture was estimated using 90nm
	technology from STMicroelectronics in terms of NAND logic gate.
	Figure 3.4 represents the equivalent number of logic gates for all the configurations with

.2 Different configuration to explore the design space for turbo decoding Nine turbo decoder configurations are selected and then studied for 16 and 32 PEs as shown in Table

3

.2. The first 5 configurations were targeted for non-shuffled turbo decoders using different radix values. The last 4 configurations were defined to analyze the convenience of shuffled turbo decoders with radix-2 and radix-4. PE with and without internal memory were considered. Internal memory is a buffer that temporally stores extrinsic values which avoids a second access to the memory banks for a data element. Moreover, this buffer can alleviate collision problems since less memory accesses are necessary. The respect to the number of clock cycles necessary to decode a frame (directly related to the turbo decoder throughput). Configuration 1, 2 and 3, for 16 and 32 PEs, are Pareto-optimal Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Table 3

 3

			.3 Cost calculation
	NW Cost	NW Controller	Memory Controller	Extrinsic Memory	Total
	Config 5 18.9 k	2.1 M	2.5 M	0.4 M	5.1 M
	Config 8 102.2 k	4.7 M	3.4 M	0.9 M	9.1 M

The approach used in

[START_REF] Briki | A Memory Mapping Approach for Network and Controller Optimization in Parallel Interleaver Architectures[END_REF]

[BRI13b] is focused on memory mapping approach to design optimized parallel hardware architectures and to support a targeted interconnection Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

  .6(a) represents a data access matrix for a parallelism P=4 which is scheduled as a table. Lines match processing elements, i.e. each line represents all the data processed by its associated PE. Columns represent computation instants needed to process L=12 data elements.

	PE 1	0	1	2	0	6	4
	PE 2	3	4	5	8	5	7
	PE 3	6	7	8	2 10 1
	PE 4	9 10 11 11 3	9
		t 1	t 2	t 3	t 4	t 5	t 6
							Time

  new network component (i.e. multiplexer or switch) to the existing network. In that case the memory mapping algorithm restarts from the beginning with this new extended set of permutations. The algorithm keeps on customizing the network by adding switch to the network in each iteration until a fully connected Benes network is constructed (worst case).

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 by adding a

Table 3

 3

		.5 Block lengths supported by BS
	P=4	160,200,240,320,360,480,528,800,880,960,1440, 1600,2240,2880,3520,4160,4480,5760
	P=8	416,480,800,1600,2240,3520,3584,4608,4480

  first part of the previous chapter, we have explored different configurations based on shuffled and non-shuffled turbo decoder architecture using state of the art approaches in order

	to find conflict free memory mapping. Non-shuffled configurations are turbo like problems
	for which memory mapping approaches based on in-place architecture are used. On the other
	hand, shuffled configurations represent LDPC like problems for which approaches based on
	multiple read multiple write (MRMW) memory mapping architecture are needed. So, state of
	the art approaches uses MRMW architecture and in-place memory architecture to find conflict
	free memory mapping. For example, memory conflict problems in non-shuffled decoding of
	LTE [SAC12] and non-shuffled decoding in HSPA [SAN13] are solved using in-place

memory architecture. While conflict problems solved with MRMW architecture includes shuffled decoding in LTE [OSC12], shuffled decoding in HSPA and non-binary LDPC problem [BRI12] [CHA10b]. The MRMW memory mapping architecture requires network configurations for read as well as write operations which double the network controller cost

  conclude that in set of T, each edge t i corresponds to a data node in G i , so the coloring of edges in G actually means coloring of data nodes in G i .

			PE 1 0 0 2 4 1 5
			PE 2 1 2 3 5 3 6
			PE 3 8 4 6 7 7 8
				t 1 t 2 t 3 t 4 t 5 t 6
	Figure 4.6 Example of data access matrix with two accesses to each data
	Consider a simple example of data access matrix (see Figure 4.6) in which size of data
	elements L = 9, parallelism P=3 and number of time instances T = 6. For this data access
	matrix, the graph G i is shown in Figure 4.7(a) in which set of data nodes is L = 9 and set of
	time nodes is T = 6. This graph is then converted into the graph G shown in Figure 4.7(b).
	t 1	0	t 2	2	t 3	t 1	t 2	t 3
	1			3
			t 5	6			t 5
	4	8
	7
	t 4	5	t 6			t 4	t 6
	(a) Graph G i				(b) Graph G
	Property 2
	Each data element is accessed exactly two times. This property implies that all the data
	nodes have the same degree, d l = 2.

e. number of data required to access concurrently) at any time instance is always same. This property implies that in G', each time node has same degree, d t = P.

According to the property 2, the graph G' can be converted into graph G by first joining two edges at each data node and then removing all the data nodes from G i . Thanks to property 1, G is regular i-e all nodes have same degree with the degree of each time node, d t = P. Now Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 we can Now we can get a conflict free memory mapping by applying edge coloring algorithms where each edge connected to a time instance will have different colors which means that each data accessed at a time instance is placed in different memory banks resulting in a conflict free access to the data.

  No loop in the traced path. t 0 and t k are in different connected components in the graph. Loop in the traced path. t 0 and t j are in different connected components in the graph.

	Case-2.b:

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Case-2.a:

PE 1 0 2 1 18 16 13 4 5 6 21 31 31 12 10 9 23 3 PE 2 1 4 14 19 17 14 11 7 7 22 33 25 26 32 20 24 29 PE 3 2 5 17 20 19 15 12 10 8 8 22 15 27 28 30 25 28 PE 4 3 6 18 21 33 16 13 11 9 23 24 26 32 30 29 0 27 t 1 t 2 t 3 t 4 t 5 t 6 T 7 t 8 t 9 t 10 t 11 t 12 t 13 T 14 t 15 t 16 t 17

0 l 01 (b0) l 03 (b1) X 1 l 12 l 15 2 2 l 23 (b0) l 24 (b0) X 3 l 31 (b1) l 34 (b1)

		t 1	t 2	t 3	t 4	t 5			t 1	t 2	t 3	t 4	t 5
	0	l 01		l 03			2	0	l 01 (b0)		l 03	1
	1		l 12			l 15	2	1		l 12	l 15	2
	2			l 23	l 24		2	2			l 23	l 24	2
	3	l 31			l 34		2	3	l 31		l 34	2
	4				l 44	l 45	2	4			l 44	l 45	2
	5	l 51	l 52				2	5	l 51	l 52	2
	6		l 62	l 63			2	6		l 62	l 63	2
	7	l 71		l 73			2	7	l 71		l 73	2
	8				l 84	l 85	2	8			l 84	l 85	2
	9		l 92			l 95	2	9		l 92	l 95	2
		2	2	2	2	2			1	2	2	2	2
			(a)								(b)
		t 1	t 2	t 3	t 4	t 5			t 1	t 2	t 3	t 4	t 5
							X
	4				l 44	l 45	2
	5	l 51	l 52				2
	6		l 62	l 63			2
	7	l 71		l 73			2
	8				l 84	l 85	2
	9		l 92			l 95	2
		X	2	X	x	2

0 l 01 (b2) l 03 (b2) X 1 l12 l15 2 2 l 23 (b0) l 24 (b0) X 3 l31(b1) l34(b1)

						X
	4				l 44	l 45	2
	5	l51	l52			2
	6		l 62	l 63		2
	7	l 71		l 73		2
	8				l 84	l 85	2
	9		l 92			l 95	2
		X	2	X	x	2
	(c)			(d)

Table 4 .

 4 1 Different configuration to explore the design space for turbo decoding

	Mode	Scheduling	Radix	Internal Memory

Config. 1 Non-Shuffled Butterfly 2 YES Config. 2 Non-Shuffled Butterfly 4 YES Config. 3 Non-Shuffled Butterfly 16 YES Config. 4 Non-Shuffled Butterfly 2 No Config. 5 Non-Shuffled Butterfly 4 No Config. 6

		Shuffled	Replica	2	No
	Config. 7	Shuffled	Replica	2	YES
	Config. 8	Shuffled	Replica	4	No
	Config. 9	Shuffled	Replica	4	YES

  Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 place architecture by applying the proposed bipartite test. The area comparison is presented in Figure4.34 for configuration 6 to 9. The cost of the architecture (excluding processors) can be reduced up to 25% of the total area by using our proposed approach. The reduction in case of P = 32 is almost the same.

	Millions	7 8 9
		6
	Nand gate eq. Area	0 1 2 3 4 5
		Conf.6	Conf.7	Conf.8	Conf.9
		[SAN13]	Proposed

2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 17 t 18 t 19 t 20 t 21 t 22 t 23 t 24 t 25 t 26 t 27 t 28 t 29 t 30 t 31 t 32

  Figure 4.36 Data Access Matrix for L = 192 and d c = 6

	2 10 62 23 59 29 33 26 25 16 17 63 36 21 15 11 18 9 38 34 40 31 3 12 41 32 39 13 30 22 43 60
	3 11 63 24 60 30 34 27 26 17 18 64 37 22 16 12 19 10 39 35 41 32 4 13 42 33 40 14 31 23 44 61
	149 139 159 67 156 97 142 130 115 83 155 65 78 132 181 116 96 174 109 98 106 125 183 91 117 169 123 74 190 189 162 110
	122 123 84 114 133 110 70 119 181 127 109 10 6 184 98 68 96 156 83 85 190 169 78 91 115 81 67 134 108 117 136 167 189
	90 86 126 178 73 191 172 80 153 128 152 176 157 171 107 140 175 99 170 82 161 188 138 173 168 144 95 145 66 75 105 147
	157 179 182 158 124 141 88 148 66 143 75 131 103 126 144 178 105 129 145 138 77 135 128 161 163 118 180 188 152 113 82 99
	48 19 53 42 51 47 46 7 58 28 5 6 1 50 44 35 61 20 56 37 54 14 45 55 8 57 27 49 52 64 4 24
	49 20 54 43 52 48 47 8 59 29 6 7 2 51 45 36 62 21 57 38 55 15 46 56 9 58 28 50 53 1 5 25
	146 104 112 79 113 85 81 84 184 70 167 101 136 108 87 102 119 68 164 154 121 133 71 100 114 120 127 122 72 135 185 94
	100 94 90 154 183 72 164 146 142 159 130 155 139 71 112 174 149 97 116 121 132 102 101 162 74 171 87 79 125 104 65 185
	88 160 137 129 148 177 166 103 89 111 118 93 92 141 131 77 180 134 69 165 179 186 192 143 187 151 163 158 182 76 124 150
	153 177 172 151 89 147 107 168 95 170 86 173 111 175 186 15 69 187 191 80 73 92 165 76 137 93 160 176 140 192 166 120
	t 1 t

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

  :As already shown, Vizing theorem needs P+1 banks for memory conflict problems only with simple graphs. So a memory mapping problem from non-binary LDPC codes can be solved with P+1 banks using Vizing theorem if non-binary LDPC mapping problem results into a simple graph. As simple graph have no parallel edges and there will be no parallel edges in a graph if any two time nodes have only one data common between them. As it can be seen in Figure4.21a(and simpler example in Figure4.7) that the graph is a simple graph as the data access matrix Figure4.20 has only one data element common between two time nodes. Now we have to prove that only one data element is common between two time nodes in non-binary LDPC codes.

	At-most P+1 banks are needed for memory conflict problem in non-binary LDPC codes
	by using Vizing theorem.

  Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

		451
	x 1000	351 401
		301
		251
	Nand gate eq. Area	1 51 101 151 201
		48	96	192	288	384
			Block Length
		[CHA10b]	[BRI13a]	Proposed

  Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

	Millions	1,4 1,6
		1,2
	Nand gate eq. Area	0,4 0,6 0,8 1
		0,2
		0
		300	600	1032	2064
			Block Length
			[BRI13a]	Proposed

  Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014 memory mapping architectures. The second perspective is to extend the proposed in-place approach for other test cases with more than two data accesses.In design time approaches, ROM blocks are used to control interconnection network and generating addresses for different memory banks which may be sufficient to design parallel architecture that supports single code-word or applications. However, to design hardware architecture that supports complete standard and/or different applications, ROM based approach results in huge hardware cost and area. To reduce hardware cost, optimizations are required to use as less ROMs as possible to support different applications. For this purpose, an approach based on on-chip memory mapping mechanism is proposed in the next chapter.

	Chapter 5
	ON-CHIP IMPLEMENTATION OF MEMORY
	MAPPING ALGORITHM TO SUPPORT
	FLEXIBLE DECODER ARCHITECTURE

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

  this chapter, we propose on-chip memory mapping approach in order to reduce the requirement of Design time approaches find memory mappings that provide conflict free concurrent access to all the memory banks. In these approaches, ROM blocks are needed to store the network, memory and other control configurations. However, multiple ROM blocks are needed to support different block lengths within a standard or multiple standards which results in high hardware cost. As shown in Figure5.1, multiple ROM blocks are needed to store address generation logic and network control logic to support multiple block lengths and/or multiple applications. This results in huge hardware cost that is utilized in storing addressing, network and other control logic to design flexible decoder architecture. In order to reduce hardware cost, optimization is required to store addressing and control logic for multiple block lengths or multiple applications. Unfortunately, state of the art memory mapping approaches are unable to optimize memory necessary to store control information for multiple blocks lengths or applications.In order to overcome the hardware overhead problem, we propose a solution to run mapping approaches on chip in order to calculate new mapping information on the fly as soon as new block length needs to be decoded and to update these new generated control information in memory. This work has been published in[REH12] [REH14b].

	1. Introduction
				Controller
		Network Control Logic
			R/W
	PE 2 PE 1 PE 0	Interconnection Network	RAM 0 RAM 1 RAM 2	Address Generation Logic
	PE n-1		RAM b-1
	the multiple ROM blocks. Design time approaches need ROM blocks to store the control
	configurations for memory and network. However, multiple memory elements are required to support
	different block lengths/different standards which results in high complexity(area). In order to
	overcome this problem, we have proposed to embed memory mapping approaches on-chip to solve
	memory conflict problem in parallel hardware decoders. Dedicated architecture composed of an
	embedded processor and RAM to store command words are proposed. We propose to embed on-chip
	the polynomial time memory mapping approach and a routing algorithm based on Benes network to
	solve memory conflict problem in parallel hardware decoders. Different experiments are performed by
	using memory mapping approaches executed on several embedded processors and results are
	presented.

Table 5

 5

	p	v	p	v	p	v	p	v	p	v
	7	9	47	5	101	2	157	5	223	3
	11	2	53	2	103	5	163	2	227	2
	13	2	59	2	107	2	167	5	229	6
	17	3	61	2	109	6	173	2	233	3
	19	2	67	2	113	3	179	2	239	7
	23	5	71	7	127	3	181	2	241	7
	29	2	73	5	131	2	191	19	251	6
	31	3	79	3	137	3	193	5	257	3
	37	2	83	2	139	2	197	2
	41	6	89	3	149	2	199	3
	43	3	97	5	151	6	211	2

. 1. List of prime number p and associated primitive root v

Table 5

 5

	.2.

Table 5

 5

					. 2. Turbo code interleaver parameters
	i	L	f	1	2

  The algorithm is based on two steps. In the first step a bipartite graph is constructed based on two data access matrices. Whereas in the second step a polynomial time bipartite edge coloring algorithm is used to find conflict free memory mapping. In the first step in order to construct a bipartite graph, a tripartite graph G' = (T NAT ∪ T INT ∪ L, E) is constructed based on natural and interleaved data access matrices (as example shown in Figure5.7) in which vertex sets T NAT and T INT represent all the time instances used in natural order access and interleaved order access respectively whereas vertex set L represents all the data elements used in the computation. An edge (t NAT , l) is incident to the data vertex l and to the natural order time vertex t NAT if l needs to be processed at t NAT (i.e. data l will be read and next written at time t NAT ). Similarly, an edge (t INT , l) is incident to the data vertex l and to the interleaved order time vertex t INT if l needs to be processed at t INT . This tripartite graph Figure5.8(a) is converted into bipartite graph G by first joining two edges at each data vertex and then removing all the data vertices from the tripartite graph. G is regular with the degree of each time node, k=P.

	PE 1	0	1	2	3	PE 1	3	7	4	2
	PE 2	4	5	6	7	PE 2	1	0 10 9
	PE 3	8	9 10 11	PE 3	11 6	5	8
		t 1	t 2	t 3	t 4		t 5	t 6	t 7	t 8
			Natural Order			Interleaved Order
			Figure 5.7 Data access matrix

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

, c j and a sequence of edges (t 0, t 1 ), (t 0, t

) , . . . , (t 0, t j ). This sequence can be expressed Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

CRP on CRS(mod 2 n )

CRP on CRS(mod 2 n-1 ) CRP on CRS(mod 2 n-1 ) CRP on CRS(

mathematically as color c i is missing at t i for 0 ≤ i ≤ j and color c i is the color of the edge (t 0 , t i+1 ) for 1 ≤ i ≤ j as shown in Figure 4.13. We can see that color c j is a missing color at t j which is available for coloring. If there exists an edge (t 0 , t j+1 ) colored with c j , where t j+ 1does not belongs to set {t 1 , . . . , t j }, then continue constructing the sequence with the defined c j and t j+1 . Since t 0 has only P neighbors, the construction process completes with one of the following cases:

Case-1: No repetition of missing color at the nodes of the fan. While constructing the sequence of the fan, there exist no edge (t 0 , t i ) colored with c j for 1 ≤ i < j.

Case-2: Repetition of missing color at the nodes of the fan. While constructing the sequence of the fan, there exist a color c j = c k-1 , for some 2 ≤ k < j: such that the edge (t 0 , t k ) is colored with c j .

Case-1

In this case, the construction of the sequence is completed in such a way that the colors of all the edges of the sequence are not similar to the missing color of the last node.

Mathematically, we can say that there exist no edge (t 0 , t i ) colored with c j for 1 ≤ i < j.

In this case, it will always happen that the color missing at the starting node of the conflict edge will be also missing at the last node of the sequence i-e the color c j will be missing at t 0 and t j (see Figure 4.14(a)). In order to color the conflict edge (t 0 , t 1 ), first of all we will shift the conflict edge to the last edge of the sequence. The shifting is done by exchanging colors in a sequence that we keep on exchanging the conflict edge with its neighboring edge until it is transferred to the last desired edge i-e shift colors (t 0 , t i ) with c i for 1 ≤ i ≤ j-1 as shown in Figure 4.14(b-c). In these figures the conflict edge (t 0 , t 1 ) is first exchanged with its neighboring edge (t 0 , t 2 ). As a result, the color of (t 0 , t 1 ) becomes c 1 and the conflict edge is transferred to (t 0 , t 2 ). Now we exchange the conflict edge (t 0 , t 2 ) with its neighboring edge (t 0 , t 3 ). As a result, the color of (t 0 , t 2 ) becomes c 2 and the conflict edge is transferred to (t 0 , t 3 ). We keep on exchanging the conflict edge with its neighboring edge and at last (t 0 , t j ) will become conflict edge (see Figure 4.14(c)). It can be seen that c j is missing at both t 0 and t j so we can color (t 0 , t j ) with c j (see Figure 4.14(c)) and hence the conflict edge is colored.

Designing Optimized parallel interleaver architecture for Turbo and LDPC decoders / Saeed Ur Rehman -2014

Lemma 4.1

All the data nodes in semi 2-factors of bipartite graph with even cycles can be assigned with two memory banks.

Moreover, edges of every odd cycle can be assigned with three colors which implies that edges in c i and every 2-factor in G 1 can be colored with three colors [START_REF] Soifer | The Mathematical Coloring Book[END_REF]. This results in the following lemma.

Lemma 4.2 All the data nodes in semi 2-factors of bipartite graph with odd cycle can be assigned with three memory banks.

As it is unknown that the cycle is odd or even therefore we consider the worst case that each cycle will be odd for every semi 2-factor which means that we will need three memory banks for each semi 2-factor. So k semi 2-factor will result in 3k banks i-e (3/2)*P banks (k =P/2).

Transformation of bipartite graph into Transportation Matrix

Our graph is modeled as transportation matrix based on the properties discussed in the previous section. For this purpose, the bipartite graph is divided into k semi 2-factors and to give colors to the edges of each semi 2-factor. To find semi 2-factor, we transform our mapping problem as transportation problem by considering all the data nodes as producers and all the time nodes as consumers. The route l ij exists between data node d i and time node t j if data d i is accessed at t j . One additional constraint must be considered while modeling our problem as transportation problem: the capacity of each route is fixed in our mapping problem. The reason is that each route represents a connection between processors and memory banks whose size is always fixed. In our case, the capacity x ij of l ij is kept one since only one data can be accessed at a given time instant t j for this route.

In order to find semi 2-factor, we consider : (1) the demand of each consumer is kept to two and (2) each producer either provides two items (i.e. each data is accessed two times) or is not included in the current semi 2-factor (i.e. each producer must work at its full capacity).

The cost o ij of l ij is kept one since the cost is not taken into account in the current work. It will only be used when we will consider the constraint of the network architecture.