Bertrand Granado

Keywords: adaptive NoC -impact parameter -fault tolerant routing Contents

Chips will be designed with billion of transistors and heterogeneous components integrated to provide full functionality of an current application for embedded system. These applications also require highly parallel and exible communicating architecture through a regular interconnection network. The emerging solution that can fulll this requirement is Network-on-Chips (NoCs).

Designing an ideal NoC with high throughput, low latency, minimum using resources, minimum power consumption and small area size are very time consuming.

Each application required dierent levels of QoS such as minimum level throughput, delay and jitter. In this thesis, rstly, we proposed an evaluation of the impact of design parameters on performance of NoC. We evaluate the impact of NoC design parameters on the performances of an adaptive NoCs. The objective is to evaluate how big the impact of upgrading the value on performances. The result shows the accuracy of choosing and adjusting the network parameters can avoid performance degradation. It can be considered as the control mechanism in an adaptive NoC to avoid the degradation of QoS NoC. The use of deep sub-micron technology in embedded system and its variability process cause Single Event Upsets (SEU) and aging the circuit. SEU and aging of circuit is the major problem that cause the failure on transmitting the packet in a NoC. Implementing fault-tolerant routing techniques in NoC switching instead of adding virtual channel is the best solution to avoid the fault in NoC. Communication performance of a NoC is depends heavily on the routing algorithm. Adaptive routing algorithms such as fault-tolerant has been proposed for deadlock avoidance and load balancing. This thesis proposed a novel adaptive fault-tolerant routing algorithm for 2D mesh called Gradient and for 3D mesh called Diagonal. Both algorithm considers sequences of alternative paths for packets when the main path fails. The proposed algorithm tolerates faults in worst condition trac in NoCs. The number of hops, the number of alternative paths, latency and throughput in faulty network are determined and compared with other 2D mesh routing algorithms. Finally, we implemented Gradient routing algorithm into FPGA.

All these work were validated and characterized through simulation and implemented into FPGA. The results provide the comparison performance between proposed method with existing related method using some scenarios.

List of Figures

Introduction

Microprocessor is the most important component in all electronic equipment. It allow to runs specic application software at the user interface level, to manage appropriately internal hardware and software interface based on its functionality. Current applications for embedded systems are modeled as a large number of communicating tasks with dierent characteristics [START_REF] Kumar | A network on chip architecture and design methodology[END_REF]. Single core processor systems cannot handle anymore the requirement of this highly complex applications and the related real time constrains. Thus, communication architecture is required to support the full functionality of these applications. An embedded system will be designed with billions of transistors and heterogeneous components integrated together in a chip called Multiprocessor System on Chip (MPSoC).

The MPSoC paradigm or the embedded system adopts the architecture of the desktop computers and bus architectures used in PCB by assembling dedicated hardware on a single chip. The current Personal Computer (PC) contains multiple processors, multicore Central Processing Unit (CPU), Digital Signal Processor (DSP), and other application specic-processors (like GPU) to support high computing power, with less power consumption for advanced applications such as multimedia or 3D games. The SoC platform has recently evolved into MPSoC. The interconnection network appeared as the critical bottleneck in MPSoC and the principal important component for highperformance MPSoC. MPSoC has replaced VLSI (very-large-scale integration) or ULSI 2 Introduction (ultra-large-scale integration). MPSoCs are widely used in the equipment systems such as cell phones and portable game devices.

Classically, shared buses and direct point-to-point connections are used for the communications between processing elements on a chip. Both technologies are simple and easy to manage. But, as silicon technology advances further several problems related to buses and point-to-point links has appeared. With a high numbers of interconnected nodes, bus arbitration can become a bottleneck that can increase the delay. While direct point-to-point, each core needs a lot of pins thus becomes messier in terms of wiring.

Buses and point-to-point interconnections are no more possible to support communications between resources on embedded system or System-on-Chip (SoC). To support eciently these communications it is then required using highly parallel and exible regular interconnection networks.

Network-on-Chips (NoCs) has been proposed as a solution for communications infrastructure in SoC. NoC architecture provides the communication infrastructure for the resources on a chip. The adaptivity of this communication paradigm provides dierent Quality of Services (QOS) based on applications need. Moreover, the NoCs can also provide exible infrastructure to overcome performances degradation due to change in environment or application requirements [START_REF] Koch | An adaptive system-on-chip for network applications[END_REF].

A NoC architecture consists of resources or processing elements such as processor or storage units in the network, and switches or router that are connected using channels so that they are able to communicate with each other by sending messages. A generic NoC infrastructure, as presented in Figure 1.1, is the combination of various hardware elements (e.g., processing element, switches, and links) and protocols communication (e.g., routing, switching policies) that determine the communication architecture. The processing elements can be a processor, DSP, Field Programmable Gate Array (FPGA) block or RAM while the switches are in charge to routes and buers messages between resources.

A physical layout that describes how the switches or routers in NoC are connected to each other is dened as the topology. In SoC, the key requirement for the network topology is scalability with low power consumption [START_REF] Zia | 3d {NOC} for many-core processors[END_REF]. Mesh topology is the most used topology for NoC due to its relative simplicity and its high scalability [13]. In generic 2D mesh NoC topology, several tiles of routers and resources are connected in a grid-like fashion (Figure 1.1). It is known as a regular structure and short interswitch wires. From this structure, a variety of 3D topologies can be derived. The 3D topology consists of stacking 2D mesh layers connected by I/O or Through-Silicon-Vias (TSVs). It is the solution of the increasing uses of semiconductor and the scalability in embedded system based on the Moore's Law prediction. 3D architecture are designed to avoid suer from high power dissipation and a large network diameter distance between nodes. It oer better network-on-chips performance compared to the 2D architecture [START_REF] Pavlidis | 3-d topologies for networks-on-chip[END_REF] due to the increasing complexity of chips and limited scope of 2D topologies. In this work, we mainly consider the 2D and 3D mesh topology. We designed a fault tolerant routing algorithm for 2D and 3D mesh topologies. Some applications such as video and audio decoding have specic constraints on communication requirements. For these applications, the trac ow between the pair producer-consumer should need some guarantees on the network performances such as latency or throughput. Latency is the Introduction time needed to send packet from a source to a destination while throughput also known as bit-rate, denes how many bit arrive at destination per second. Traditional packet switching networks which uses packet to communicate with other nodes do not oer guarantees as all packets share the same resources. The quality of service (QoS) refers to a resource reservation mechanism where special packets do not share the resources with other packets. These special packets are called Guaranteed Service (GS) packets while the others are called Best Eort (BE) packets. In worst case scenarios, GS reserve resources to guarantee it services, while BE do not reserve any resources. Designing a NoC is very time consuming. Dierent levels of QoS are required to the users based on application constraint. Minimum threshold level of throughput, delay and jitter are needed to fulll the application requirements. To support a certain QoS for various applications in dynamic condition, an adaptive NoC is mandatory [START_REF] Mak | Adaptive routing in network-onchips using a dynamic programming network[END_REF]. An adaptive NoC should provide a minimum level of performances to support QoS needed by dierent application requirements and support exible communication or dynamic reconguration to react and adapt to the changes of working conditions [START_REF] Pastrnak | Realization of qos management using negotiation algorithms for multiprocessor noc[END_REF]. A designer should consider the QoS requirements of dierent applications to design an adaptive NoC [START_REF] Guo | A framework for providing quality of service in chip multi-processors[END_REF]. A challenge facing designers of SoCs containing NoC is to nd NoC instances that balance the cost (e.g. area) and performance (e.g. latency and throughput) [START_REF] Pestana | Costperformance trade-os in networks on chip: a simulation-based approach[END_REF].

In a NoC based architecture, all nodes are connected and transfers packet through the network via routers. The performances and properties of the adaptive NoCs are dependent on the design of the infrastructure layer, application layer and communication architecture layer as shown on Figure 1.2. In this thesis, routing techniques are designed as a solution towards the dynamic adaptation of NoC. The goal of the routing algorithm is to distribute trac evenly among the paths supplied by the network topology, so as to avoid hotspots and minimize contention, thus improving network latency and throughput.

An adaptive routing algorithm is proposed for deadlock avoidance and load balancing. The main objective is to reduce the overall latency of communications inside the network. Furthermore they can be used to avoid failures that cause deadlocked packet. Adaptive fault-tolerant routing [START_REF] Mak | Adaptive routing in network-onchips using a dynamic programming network[END_REF] is the only solution to reduce the chance of packet entering hot-spots or faulty nodes so that probability of blocking for packets is reduced.

A NoC can be designed in three levels: high level abstraction, medium level and hardware level. A NoC designer can use high-level design to design larger, more complex system and higher performance embedded system using system-level design tools with less eort. The advantages of this method are that it requires less-time to obtain the output performances of the design based on application requirement. Further, NoC designer can also prototype or manufacture their design using high-level synthesis or medium level synthesis. But accuracy of result cannot be guarantee.

Most of existing fault-tolerant routing methods employ virtual channel (VC) in routers to guarantee deadlock-freeness [9]. VCs are known as logical channel which diers from physical wires. It associates multiple queues at each input port in the router so that when a packet is blocked at one port, the other packet can use VC to choose another port. Thus VCs can increase the utilization of physical channel and also the throughput on the network. However, implementation of VCs requires large capacity memory or buers, which in turn increases area overhead and power consumption, thus making it impractical. Hence, adaptive fault-tolerant routing without VC is desirable for NoCs [START_REF] Wu | A fault-tolerant adaptive and minimal routing approach in 3-d meshes[END_REF].

A SoC that is composed by several core processors can be built in a single FPGA.

Impact of design parameters on performances

The introduction of the Quality of Service into a Network-on-Chip requires some kind of end-to-end path reservation in order to guarantee the latency and the throughput of oered packets. The questions addressed for this topic are packet latency, throughput, shared resources and path allocation. The interconnections in NoC have plenty of parameters that aect the performances and the capacity of the interconnection. These parameters can be, for example, the number of data lines, clock frequency, arbitration scheme, the priorities of the blocks, or the maximum time a packet can reserve a shared resource [START_REF] Riihimaki | Parameter optimization tool for enhancing on-chip network performance[END_REF]. Almost all NoC parameters such as topology, processing element (PE) number, application type, trac type, routing algorithm, switching algorithm, packet size, buer size, it size and number of virtual channel have inuence on throughput, latency and power consumption. For this purpose, a NoC designer should ne several parameters (and their values) impacting the network performances. This way, the adaptation of the network has to fulll performance requirements.

Fault-tolerant routing algorithm

The use of deep sub-micron technology in an embedded system increase susceptibility to Single Event Upsets (SEU) that can decrease the reliability of NoC. A SEU occurs when a radiation causes a bit-ip in some latches (1 to 0 or vice versa). This undesired modication may cause the dysfunction of the architecture. Another problem that leads to permanent faults in the circuit is the aging of circuits. Aging of circuits is caused by physical eect in deep-submicron process and cause permanent errors.

The most important adapted strategies criteria requirement for future circuits is the dependability. The dependability has an impact on computation parts of the embedded Objectives and contributions 7 system architecture. If a processor fails, it cannot be used anymore and a dierent task placement has to be computed. In the same way if the error occurs in the NoC, a rerouting of message in the NoC can be enhanced by adding fault tolerance capabilities, thus they can adapt communication ows to follow fault-free paths.

The important requirements of routing are to avoid deadlock and live-lock. A deadlock occurs when a it (an elementary portion of a packet) or a packet waits for a resource that will never be released. The routing can create deadlock if bad decisions are taken. The routing-time of packets is one of the key factors critical to the performance of NoCs. Thus, NoC routing schemes should be enhanced by adding fault tolerance capabilities so that they can adapt the dynamically and exible communication ows to avoid the performance degradation. This leads us to dene a communication infrastructure able to handle faults and manage errors in its resources.

In 2D mesh topology, the classical routing algorithms divide the destination node into several zones, and hence route the packets using one routing criterion. While in 3D mesh NoC, classical routing algorithms divide 3D mesh topology into horizontal and vertical layer which some of them reuse existing 2D mesh routing algorithm for horizontal destination. The algorithms are then not able to handle failures in network if a fault occurs in a router or on a link. It also cannot adapt the route to avoid the use of this resource. Other weaknesses are on how it chooses the sequence of alternative routes when the main routing path fails. Inappropriate selection of alternative path may increase the number of hops of packet to reach its destination, thus degrading the performance of NoC.

1.2

Objectives and contributions

Ob jectives

The main goals of designing a NoC are to get high throughput, low latency, minimum number of resources, minimum power consumption and small area size. In this thesis we rst propose an evaluation of the impact of NoC design parameters on its performance.

Introduction

It shows that the accuracy of choosing and adjusting the network parameters can avoid performance degradation. The results can be considered as a basis for the control mechanism in an adaptive NoC to avoid the degradation of QoS. For these purposes, rst we evaluated the impact of NoC design parameters on the performances of an adaptive

NoCs. The objective of this step is to evaluate how big is the impact of upgrading a value of a given parameter on performances. In a second phase we evaluated the impact of dierent type of parameters on the performances. For this purpose, we identied the most important parameters inuencing the performances of the network. We then adjust network parameters under dierent conditions and hence evaluate their impact on the performance variations. One of the challenges of the study lies in the accuracy in choosing and adjusting the NoC design parameters that can upgrade the performances in minimum QoS condition. The results on latency, throughput and reliability were evaluated using the Noxim simulator and show the impact of the parameters on studied performances.

We designed a novel adaptive fault-tolerant routing algorithm for 2D mesh called Gradient and for 3D mesh called Diagonal. Both algorithms consider sequences of alternative paths for packets when the main routing path fails. The proposed algorithm can avoid more faults and tolerates multiple failures in worst condition trac in NoCs.

It has minimum hops, lower latency and higher throughput in worst network conditions when compared to conventional routing algorithms. To evaluate the performance of these networks, scenarios with various link-faults and node failures schemes were created and simulated using Noxim simulator. Hence the number of hops from source to destination nodes, the number of alternative paths, latency and throughput in faulty network are determined and compared with other adaptive routing algorithms. Further, we implemented Gradient into RTL level then simulate the performances using Modelsim and evaluated the hardware cost thanks to Xilinx ISE tool.

Organization of the manuscript Then, the characteristics of NoC parameters and the performances of NoC are dened.

Finally, an existing related work of adaptive fault and NoC simulators are presented.

From Bus to NoC

Nowadays, most electronic equipment use system or application that is embedded in a chip. Multi-core in embedded systems has become the basis blocks of computer systems [START_REF] Peh | On-Chip Networks[END_REF]. Direct point-to-point interconnections shown in Figure 2.1 were the rst communication infrastructure designed for on-chip systems to communicate between cores. The connection is direct and use dedicated wires without any needs of centralized arbitration. The arbitration decides when incoming data can be served by the router.

In terms of bandwidth availability, latency, and power usage, dedicated point-topoint links are optimal as they are designed especially for this purpose. Also, they are simple to design, verify and easy to model. In small systems of low number of cores, this communication structure is viable. But, as the systems grow and the design Classically, buses are used for the communication between processing elements on a chip. In a SoC, buses are advantageous because they provide high performance interconnections while they can still be shared by several communication blocks as shown in Figure 2.2. In most SoC applications, a shared bus interconnection is adopted to communicate between each integrated processing unit due to the low-cost and simple control characteristics. But, as the number of units into the system increase, the communication overhead between cores grows and hence quickly become a communication bottleneck. The increasing number of cores in Multi-Processor Systems-On-Chip (MP-SoCs) causes the unfeasible intercommunication between cores using single shared bus or a hierarchy of buses. This is because their poor scalability with system size and their shared bandwidth between all attached cores [5].

Data communication in a general networks have replaced buses in small systems: as the PCI-Express, a network-on-a board, replacing the PCI board-level bus [START_REF] Peh | On-Chip Networks[END_REF]. In data communications, networks can be classied into packet switching and circuit switching From Bus to NoC In the computer network world, dierent strategy is used. In packet switching network, the packets contain a header packet and payload of packets. Header packet contains routing information needed to route the packet over the network while on the circuit-switching network, an end-to-end circuit (i.e. a physical path) has to be established before any communication can happen. Thus, the routing method is not needed and this is suitable for streaming and guaranteed service trac. While packet switching send the packets through undedicated path. Thus, it needs routing method to route the packet to destination.

Packet switching is suitable for Best Eort (BE), a trac on which there is no guarantee on the performances. The disadvantage of using dedicated end-to-end circuit is that it need an allocator to establish the circuit while in undedicated circuit, the resources can be released automatically. In terms of performance, header packet in packet switching is an overhead while circuit switching have guaranteed throughput and predicted latency. The performances of packet switching are depended on the network condition.

Packet-switched on-chip networks (NoC) as shown on Figure 2.3 were replacing buses and crossbars [START_REF] Kogel | Integrated system-level modeling of network-on-chip enabled multi-processor platforms[END_REF] as communication in many-core chips. This architecture is adopting State of the art -Denitions All network wires can be pipelined that's why the local performance will not degrade when scaling the network size. The similarities and the dierences between NoCs and general computer network are shown in Table 2

Topologies

The most important parameter of a NoC is the network topology. It gives signicant eects on NoC performances due to the fact that it determines the distances between connected node. The two most common topologies for NoCs are mesh and torus as presented in Figure 2.5-a and 2.5-b. These both topologies can be described as k-ary n-cubes, where k is the number of nodes along each dimension while n is the number of dimensions [8]. For 2-D mesh, the value of n is 2 while for 3-D the value of n is 3. For State of the art -Denitions than the nodes in the center of the network. A torus is also edge-symmetric [START_REF] Towles | Worst-case trac for oblivious routing functions[END_REF], this property helps the torus network to balance trac across channels. In this thesis we consider mainly 2-D mesh topology due to the wide usage of this topology that has been implemented in the SoC domain. Further, this topology has been used by most researchers to design novel routing algorithm in NoC.

In Ring topology (Figure 2.5-c), all the nodes are connected to each-other in a closed loop. Each node is connected to two other nodes on either side, and can communicate with these two adjacent neighbors. The trac ows in one direction use a token. This topology does not need central point or server to control the connectivity between nodes.

Each node has equal access to resources. The main drawback of this topology is that when one node is faulty, the entire network is aected. such as removing certain links from a mesh or mixing dierent topologies [8]. In irregular topology, user may specify dierent router architectures (i.e. number of input and output port, buer size, routing, etc.) with other router in network. The goals are to reduce the number of ports, switches or channels that can reduce signicantly power and area. With irregular topology, some blocks in network can direct be connected without need of switch, or some router need only two input/output ports instead of complete input/output ports.

Switching

The main component of the interconnection architecture in NoC is the switch. Inside a switch, a data is transferred from an input port to any of its output ports. The data may need to be buered before going out through the output port. The switch control may consist of arbitration, ow control and routing algorithm that govern where and when the data are forwarded. The arbitration decides when incoming data are served by the The time gap between data enters the input port and the time when the data leaves the switch through an output port is called switch-delay [START_REF] Gebali | Networks-on-Chips: Theory and Practice[END_REF].

Store-and-Forward (SAF) technique is the rst switching technique proposed in NoC.

SAF switching techniques convert every packet into its. The rst it of a packet is the header it and the last it is the tail. SAF technique forward the header its to the next switch if only all body its of a packet are received. Compared to other switching technique, the SAF switching is not suitable with the requirement of NoCs because it have large latency because all body its of packet have to be received before forwarding it to the next switch. Moreover, it requires large buer sizes to accommodate all the its resulting in a large area needed [START_REF] Gebali | Networks-on-Chips: Theory and Practice[END_REF]. The advantage of this technique is no deadlock can occurs.

Wormhole switching technique is similar to SAF switching technique. Both implement packet-based operation with simple control mechanism between routers. In wormhole switching technique, the header its of packet is forwarded to the next switch before the next it of packet arrives. Thus, the channel buer at every router can be as small as a single it. Moreover, wormhole switching have better latency than SAF because the header it is processed without waiting the arrival of the next its or entire packet [START_REF] Gebali | Networks-on-Chips: Theory and Practice[END_REF]. The movement of wormhole switching technique looks like a worm. The tail it follow the same routing path as the header it. The main drawback of wormhole State of the art -Denitions switching is the performance degradation due to a chain of packet blocks [START_REF] Gebali | Networks-on-Chips: Theory and Practice[END_REF] and risks of deadlocks.

Flow control

Flow control is a technique used in network to control the transmission of data to avoid congestion in a busy network. It is designed to avoid the over usage of the queue that causes congestion and collisions in the network. In NoC, ow control governs the allocation of buers and links in every router. It determines when buers and links are assigned to messages, the granularity at which they are allocated, and how these resources are shared among the messages using the network [START_REF] Peh | On-Chip Networks[END_REF]. The implementation of complex ow control protocol in NoC router requires complex wiring that increases router micro-architecture area and power consumption.

The main ow control techniques used are handshaking and credit based. Handshaking control ow is used to avoid the overload of the receiver buer. It governs the process before the communication between two nodes. The sender start sending the packet only if it receive the acknowledge messages from the destination. The acknowledge messages from destination node can be ready or not-ready to receive the packet.

Credit based communication is the extension of the handshake. It transmits data after receiving return signal from neighbor node that has sucient free space to store the data. Credit based control how use the concept of buer management [START_REF] Kranich | Noc switch with credit based guaranteed service support qualied for gals systems[END_REF]. The its are transmitted when the buer space in destination router sucient. The its in current input-buer of router become arbitration for the output-port of neighbour and routers. The current buers decrement the credit count when it departs from the current router.

Routing

In term of networks, routing has been classied in several ways: as source routing or distributed routing, and as deterministic, oblivious or adaptive routing. In source rout-Network-on-Chips architecture 21 ing, the source node decides the path on which the sending packet will be propagated, while in distributed routing the current node in the networks decides the next hop of the packet. With these schemes, a distributed routing can adapt the route based on network condition while source routing cannot. Routing algorithms are also classied as deterministic, oblivious or adaptive. In a deterministic routing algorithm, all packets take the same path from a source node to the destination [START_REF] Gebali | Networks-on-Chips: Theory and Practice[END_REF]. In oblivious routing, the decision of the routing path are xed or not considering the state of the network condition while in adaptive routing the packets are routed depending on local decisions that considering the state of the network. The main goal of adaptive routing is to avoid congested areas.

Most of routing algorithms in NoC are based on the wormhole switching technique due to its simplicity and its deadlock-free [START_REF] Verbeek | On necessary and sucient conditions for deadlock-free routing in wormhole networks[END_REF]. In this technique, the tail its follow the same path as header it. XY routing algorithm [START_REF] Glass | The turn model for adaptive routing[END_REF] is one of the example of a deterministic routing algorithm. It is the most widely used routing strategy for 2-D mesh due to its deterministic, simple, easy and deadlock-free algorithm. In this algorithm a packet rst traverses along the X dimension and then along the Y dimension to the destination. XY algorithm is deadlock-free in normal condition but does not support adaptivity. This algorithm is then not able to handle failures in the network. If a fault occurs in a router or on a link, the XY algorithm cannot adapt the route to avoid the use of this resource.

The deterministic routing may cause potential hot-spots if particular router receives more requests than it can serve at a time [START_REF] Peh | On-Chip Networks[END_REF]. Thus it resulting large delay in communication. The solution for this deterministic routing problem is by using Virtual Channel, but this solution comes with a huge hardware overhead.

The main inuences factors of routing performances are number of path hop and path distribution. Based on the hops views, routing algorithms can be classied into minimal and non-minimal routing [START_REF] Peh | On-Chip Networks[END_REF]. A minimal routing algorithm use minimal paths pair from source to destination while non-minimal can take both minimal and nonminimal paths. The adaptive routing allows alternative paths between the same pair of source and destination nodes. This property provides fault tolerance, because it usually enables the routing algorithm to select a path that avoids faulty network components.

The turn model [START_REF] Glass | The turn model for adaptive routing[END_REF] routing algorithm is an example of adaptive routing. It travel data using a deterministic algorithm, but when the router or the channel fail or is already used for a communication, then the data turn on another direction. Thus, the data reach the destination through an alternative path. The weakness of this algorithm happens when the only path to reach the destination is on the forbidden turn as shown in Figure 2.9. The Odd-Even turn model [12] is designed as a solution of the weakness on previous turn model. This algorithm improves the network performance due to the forbidden turn are more evenly distributed in the network. However, this algorithm doesn't have alternative selection path which is not suitable in faulty network.

3-D NoC Technologies

Performances, power consumption and the size of chip area are the main consideration in designing a NoC. Existing NoC topologies employ routers with a small number of ports (low-radix) to avoid the increasing power and latency [START_REF] Zia | 3d {NOC} for many-core processors[END_REF]. But, with the need of high NoC performances on current application, it pushes the use of more processing 3-D NoC Technologies 23 element inside same system that can increase the interconnection requirements between PE. As the network scale, topologies with high-radix (scalable) routers become more feasible than low-radix topologies in terms of both power dissipation and latency caused by large average minimum distance between PE [START_REF] Zia | 3d {NOC} for many-core processors[END_REF].

The conventional 2-D integrated circuit (IC) has limited oor-planning choices, and consequently, it limits the performance enhancements arising out of interconnection architectures [START_REF] Pavlidis | 3-d topologies for networks-on-chip[END_REF]. Fat-tree topology has been used to support increasing number of PE and avoid large distances between nodes. But, with a the large number of PE, fat-tree need routers with high number of ports and consequently more wires increasing latency of forwarding packet [START_REF] Ngo | Analyzing the performance of mesh and fat-tree topologies for network on chip design[END_REF]. A 3-D topology with wafer-to-wafer bonding that consist of multiple stacked connected by Through Silicon Via (TSV) is proposed in [START_REF] Topol | Three-dimensional integrated circuits[END_REF].

Most of new design topologies interconnection uses vertical integration to face the 3D challenge. This concept is similar with vertical-building like hotel or apartment which is a number of rooms closely connected by using elevator or stairs. This is the idea of TSV for vertical chip interconnection, leads to shortest distance between two layers, and the bulk capacitance of a wire is also smaller [START_REF] Topol | Three-dimensional integrated circuits[END_REF].

The main objectives of 3-D NoC technology are scalability and power dissipation.

Three-dimensional ICs is capable of achieving better performances, functionalities, and packaging density. The 3-D architecture also oer better interconnection performances compared to the 2-D architecture [START_REF] Pavlidis | 3-d topologies for networks-on-chip[END_REF]. Feero and Pande in [START_REF] Feero | Networks-on-chip in a three-dimensional environment: A performance evaluation[END_REF]. Other 3-D architecture which consists of multiple network layers connected via crossbar switches called XNoTs is proposed in [START_REF] Matsutani | Tightly-coupled multi-layer topologies for 3-d nocs[END_REF].

The most widely used static routing algorithm for 3-D mesh is XYZ. It is a deterministic, simple, easy and deadlock-free algorithm. As its counterpart in 2D, packet rst traverses along the X dimension, then Y dimension, and nally along the Z dimension.

XYZ algorithm is deadlock-free in normal condition but does not provide adaptivity in faults condition thus it cannot handle failures in the network. If a fault occurs in a router or on a link, the XYZ algorithm cannot adapt the route to avoid the use of this resource.

Performances, parameters and dependencies

The main goals of NoC design are to get high throughput, low latency, minimum resources requirement, minimum power consumption and small area size. But, the most important consideration on designing a SoC is the trade-o between network perfor-State of the art -Denitions mances, energy consumption, and silicon area requirements after mapping. Generally, the system performance consists of two parts: computation and communication performance. In NoC, the quality can be measured from its energy consumption, area size and network performance.

Several xed design NoC architectures such as topology, routing and switching schemes has been proposed to get high performances in certain application, however it may reduce performances in other applications. Thus, NoC designer must consider the impact of each parameter on the result performances.

NoC parameters consist of hardware architecture (i.e router micro-architecture, link architecture and topology), and communication architecture (i.e application, security, trac, transport protocol, packet size, header size, routing, ow control, switching, it size, and buer size). While NoC performances can be classied into latency, throughput and reliability.

Latency is dened as the time spent to transfer one packet from a source node to a destination node [START_REF] Jantsch | Networks on chip[END_REF]. In term of NoC, latency is dened as the time elapsed between the moment the PE source sends the rst bit of a data and the moment the PE destination receives the last bit of data. Throughput sometimes known as data rate, represents how many bits arrives at destination node per second. In network, it corresponds to the rate at which packets are delivered by the network and presented in percentage from total network capacity.

Reliability is the reliable communication which provide notications to the sender of the the delivery of transmitted data [START_REF] Jantsch | Networks on chip[END_REF]. In terms of OSI model, reliability depends on the transport protocol layer. Transport protocol ascertains whether the packet arrived at the destination correctly. Complex transport protocol increases the latency of packet.

Error control and ow control is a part of control mechanism in transport protocol. Error control and error detection combined with retransmission further can increases the NoC congestion.

In chapter 3, we propose a method to evaluate the impact of design parameters on the performances of NoC. The result of this work will help NoC system designers in esti-Fault-tolerant and deadlock-free techniques 27 mating the system performance, associated overheads and dening the best parameters to adapt its system condition.

Fault-tolerant and deadlock-free techniques

An error in the networks can be caused by the faulty in the circuit. There are two type of faulty circuit: permanent faults and temporary fault. Permanent faults can be caused by dielectric breakdown, poor fabrications and irreversible wear-out damage [START_REF] Wang | System-on-Chip Test Architectures: Nanometer Design for Testability[END_REF] while temporary fault are caused by the operating conditions process such as voltage and temperature uctuations.

If an error caused by temporary fault, the operation needs to be retried or corrected [START_REF] Rusu | Adaptive inter-layer message routing in 3d networks-on-chip[END_REF]. But if an error is caused by permanent fault, it needs some form of redundancy in time, space, or information due to retrying an operation will not solve the problem [START_REF] Pasricha | A low overhead fault tolerant routing scheme for 3d networks-on-chip[END_REF].

In that case, sucient redundancy or spare units are required to continue error-free operation.

The failed element must be remove from the communication system or the faulty chip region must be shuttled down if the permanent fault are caused by poor fabrication yield or lifetime failure [START_REF] Wang | System-on-Chip Test Architectures: Nanometer Design for Testability[END_REF]. Other solution is by re-routing the packet avoiding faulty area, thus fault-tolerant design is needed. Fault tolerance is the ability of a system to continue operating in the presence of unexpected faults. This property of NoC not only aect fault-tolerance routing strategy, but as simple ow control strategy called Dimensional Bubble Flow Control (DBFC) in [START_REF] Wang | A fault tolerant adaptive routing algorithm in 2d mesh network on chip[END_REF] has been proposed to avoid fault in network by routing the packet based on its buer state.

Problems of non-fault tolerant routing

A major problem on oblivious routing typically arises when the network starts to block trac. The only solution is then to wait for a reduction of the trac amount and to try again. Deadlock, livelock and starvation are potential problems on both oblivious and adaptive routing.

State of the art -Denitions

Deadlock occurs in a network when a group of packets are unable to progress because they are waiting on another one to release resources (buer, link, etc.). If a sequence of packets forms a cycle in the network [START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF], then the network is deadlocked. In network communication, a deadlock is dangerous because when few resources are occupied by deadlocked packets, other packets will block on these resources thus completely paralyzing the network. Moreover the network would remain in this state until an external intervention occurs. For example, in minimal adaptive routing algorithm that always routes packets along the shortest path. The algorithm is eective when more than one minimal or as short as possible route between sender and receiver exist. The main drawback is when the minimal path is faulty, the packet is blocked due to in fact that it route only on minimal path (i.e. entering a faulty region).

Closely related network pathology is livelock. In livelocks, packets continue on moving inside the network but without making progress toward their destinations. This becomes a concern for example when packets are allowed to take non minimal paths through the network. Livelock occurs when a packet keeps spinning around its destination without ever reaching it. This problem exists in non-minimal routing algorithms.

Livelock should be cut out to guarantee packet's throughput. There are a couple of resorts to avoid the livelock.

Other problems of non-fault tolerant routing are contention and starvation. Contentions are dened as delays imposed to a packet in order to wait for a resource to be available. Contentions are not problematic like deadlocks and livelocks because the network recovers from contention without any external intervention. It recovers as soon as previous communication nishes or as soon as another path is found. Starvation can be avoided using a fair routing algorithm or reserving some bandwidth for low-priority packets.

Fault tolerant and deadlock freeness

Designing a fault-tolerant routing algorithm is mandatory to achieve design of reliable NoCs. Fault-tolerant routing algorithms can use alternative routes when the main Many fault-tolerant routing algorithms have been designed to avoid the faulty resources in network. The rst's proposal was based on the adaptation of turn model such as west-rst, north-last, negative-rst [START_REF] Glass | The turn model for adaptive routing[END_REF], and odd-even [START_REF] Wu | A fault-tolerant and deadlock-free routing protocol in 2d meshes based on odd-even turn model[END_REF]. These techniques were proposed to avoid packet deadlock, lower hardware costs compared to more sophisticated algorithm. But they are not deadlock free routing algorithm and have lows performance due to the fact that they have less adaptivity than fully adaptive routing algorithms in avoiding the fault [START_REF] Valinataj | A fault-aware, recongurable and adaptive routing algorithm for noc applications[END_REF].

Turn model routing algorithms divide 2-D coordinates into four destination zones, based on vertical and horizontal lines. Some of them use only one route and are qualied as deterministic. We found three deadlock in the West-rst routing algorithm as presented in Figure 2.12-a. Almost all deadlock in West-rst routing algorithm occurs when there is a destination node in westbound part of the current node and there is a fault in the west port of current node. For North-last routing algorithm, the deadlock are presented in Figure 2.12-b. It occurs if there is a fault on the south port of the destination node in the northbound of current node. In Negative-rst routing algorithm, the deadlock condition are presented in Figure 2.12-c. The deadlock occurs when the fault in the west port of current node for destination node in northwest and southeast from current node. While in Fully-adaptive routing [START_REF] Palesi | Noxim -the NoC Simulator -User Guide[END_REF] algorithm, the deadlock will occurs only if there are at least two faults between the current node and the destination node as presented in Figure 2.12-d.

The Dyad routing scheme algorithm [START_REF] Hu | Dyad -smart routing for networks-on-chip[END_REF] combines deterministic and adaptive tech- The algorithm does not care although the route is not the shortest path between sender and receiver. It may select a non-minimal path allowing uniform distribution of trac but may result in deadlock. C-routing algorithm in [START_REF] Puthal | C-routing: An adaptive hierarchical noc routing methodology[END_REF] is partially adaptive and prevents live-lock and deadlock without use of virtual channel. It combines XY routing and partially adaptive routing depending on the location of source and destination nodes.

All these algorithms were designed for latency optimization and do not take into account faults arising in the network. The RAFT [START_REF] Valinataj | A fault-aware, recongurable and adaptive routing algorithm for noc applications[END_REF] tolerant routing algorithm handles a basic one-faulty-link and can be considered as a fault-tolerant version of DyXY [START_REF] Li | Dyxy -a proximity congestion-aware deadlockfree dynamic routing method for network on chip[END_REF].

In [START_REF] Daneshtalab | A systematic reordering mechanism for on-chip networks using ecient congestion-aware method[END_REF], the authors proposed a load balancing method to reduce the network congestion using an adaptive scheduler in network interfaces based on the Global Load Balancing (GLB) information metric for arbitration in routers.

A fault-tolerant routing algorithm in [START_REF] Zhang | A recongurable routing algorithm for a fault-tolerant 2d-mesh network-on-chip[END_REF] propose a method that if there are faultyrouter, the algorithm route the packet through a cycle free contour surrounding the faulty router. However this algorithm has more number of hops when it avoids a faulty router to reach the destination In [10,11], the authors proposed a fault-tolerant deadlock-free routing algorithm that guarantee message delivery from any source to any destination node, as long as a path exists, for 2-D mesh interconnects of any size. This algorithm will serve as comparison basis for our work.

NoCs simulator

NoC simulator is a software simulation tool used to simulate the NoC design before its implementation. It used to know the characteristics, the process and the performances results of the NoC design. By the simulation we know which design meets constraint to be implemented. Simulation can give the detail level result that is not experimentally measurable with the current level of technology. Simulation is the cheapest way to design, build, test, redesign, rebuild and retest the design. Despite the advantages of simulation, the fact that a simulation is not real, the results can be far from reality due to the use of models.

Generally, NoC simulator can be classify into high level abstraction and low level environment. High-level simulators work well at the behavioral and architectural levels, but they are useful only in determining the functional correctness of a system. But when the aim is to evaluate the performance or power consumption, low level simulators are needed. OMNet++ [4], NS2 [2] and GpNoCsim [START_REF] Hossain | Gpnocsim -a general purpose simulator for network-on-chip[END_REF] can be dened as high-level simulators due to the use of java language. While Noxim [START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF], Nirgam [3] and Nostrum [START_REF] Lu | Nnse: Nostrum network-on-chip simulation environment[END_REF] can be classify in low level environment due to the systemC language usage that can models hardware module. The NoC designer can also directly design a NoC in hardware level or RTL (Register Transfer Level) by writing the logical gates code in VHDL such as ATLAS [1].

In terms of output performance evaluation (i.e. throughput, delay, reliability, power and area), no one of NoC simulator can provide all NoC performance in the same time.

State of the art -Denitions

For example Orion [START_REF] Kahng | Orion 2.0: A fast and accurate noc power and area model for early-stage design space exploration[END_REF], is designed only to provide power performance at the micro architectural-level but do not provide latency or throughput. While most high-level simulators such as NS-2 and OmNet++ can only supports latency, throughput, and reliability estimation but not power or area size gures.

Due to the similarities between NoCs and networks, Network Simulator-2 (NS-2) [2] and OmNet++ [4] is very common used tool to simulate and observe the behavior of a

NoC at a high level of abstraction. Both provide many varieties of protocols of general computer network such as transport layer, network layer, MAC layer and also physical layer of OSI model. The main drawback is that it is not possible to obtain a structural and physical design view of real NoC such as logic gates canal and RTL logic design.

These simulators also cannot model and measure the energy consumption.

There are some open source simulator such as NS-2 or Noxim [START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF] that enable the users to customize or modify the communication protocol and router architecture. Customizing the communication protocol means that user can change or modify the routing algorithm, ow control, error control, trac pattern, packet size and topology. While customizing the router architecture enable the modication of the arbitration, routing algorithm, number of port, crossbar, buer and switch control part of routers. Thus, user can create their router with their own topology or communication architecture.

Due to its relative simplicity and its high scalability, majority NoC simulator provide mesh topology in their router library architecture such as Noxim [START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF], GpNoCsim [START_REF] Hossain | Gpnocsim -a general purpose simulator for network-on-chip[END_REF],

Nirgam [3], and BookSim [START_REF] Becker | Booksim 2.0 user guide[END_REF].

Noxim [START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF] is the Network-on-Chip Simulator developed using SystemC under GPL license terms. The logic element in modern FPGA device has increased signicantly to fulll the requirement of complex system design. A SoC composed by several core processors can be built in a single FPGA. FPGA has been chosen by NoC designer to prototype their design due to their fast and low cost of implementation. Further, it requires less-time to obtain the output performances of the design based on application requirement. A designer can also uses system-level design tools to design larger, more complex system and higher performance embedded system with less eort. The topology choice for NoC implementation on FPGA is more exible than on ASIC due to the over-provisioned routing resource on FPGA [START_REF] Lu | The impact of global routing on the performance of nocs in fpgas[END_REF].

A BIST controller for fault detection. Virtex-5 has also used by the author in [START_REF] Kia | A new fault-tolerant and congestion-aware adaptive routing algorithm for regular networks-on-chip[END_REF] to implemented a fault-tolerant and congestion-aware adaptive routing algorithm. In term of topology, the work in [START_REF] Elhajji | Feronoc: Flexible and extensible router implementation for diagonal mesh topology[END_REF] has also used Virtex-5 FPGA to implement a diagonal mesh topology called FeRoNoC.

Conclusions

Embedded system in a chip are used as the basis block in most electronic equipment such as mobile phone, digital video camera etc. A single processor in an embedded system cannot handle anymore the requirement of current application on electronic equipment that require parallel and real time constrain. Thus, embedded system is designed with many processors together with other heterogeneous component integrated in a chip called MPSoC.

Point-to-point and shared bus are classically used to communicate between the processing element in MPSoC due to their simplicity, low-cost and high performance interconnections. But, when the number of processing elements increase, point-to-point and shared bus are no more possible to support the communication in MPSoC. NoCs communication architecture has been proposed as a solution to overcome their limitation. Adding virtual channel into a network can be seen as adding input port and the corresponding input buer to each router. Virtual channel are proposed not only as a solution for deadlock avoidance but also to skirt around blocking in ow control, thus improving throughput. In case of an heavy load on the network, virtual channel port and buer can handle and store packets from congestion. Increasing virtual channel in the network will increase the throughput and decrease the latency. In case of congestion in a path, the virtual channel can be a solution for alternative path so that packet can be sent without passing through congested path. But increasing virtual channel numbers has a large impact on resources, area of router and power consumption.

In NoC, a packet is converted into its. The size of the it will inuence the queue in the buer and the processing time on the router. In heavy networks, when the it size is bigger than buer, the it is queued outside the buer or transmitted using another channel.

The routing algorithm and switching are used to decide what path a message will take through the network to reach its destination. The goal of the routing algorithm is to distribute trac evenly among the paths supplied by the network topology, so as to avoid hotspots and minimize contention, thus improving network latency and throughput.

While energy overhead of routing circuitry is typically low, the specic route chosen aects hop count directly and thus substantially aects energy consumption and latency. comes more congested. In other hand, if the channel capacity is bigger than the network load, increasing injection rate will increase the throughput. On contrary if the channel capacity is lower than the network load, increasing injection rate will degrade the throughput. Table 3.1 shows several parameters of NoC that have inuence to the performance of NoC. Almost all parameters have inuence to throughput and latency.

The more resources are used the more power consumption increase. The hardware of channel between resources have inuenced to area size of chip.

Existing work on evaluate of the impact of parameters on performances

There are a number of methods that can be used to evaluate the impact of design parameters on the performance of NoC for providing QoS. A typical way to approach this task is by manual method, which often implies trial-and-error design phases [START_REF] Riihimaki | Parameter optimization tool for enhancing on-chip network performance[END_REF].

Obviously this method tends to be cumbersome, error-prone and even tedious. However, there are analytical methods but often these mathematical methods use far too abstract models and therefore the achieved results dier from real implementations [START_REF] Foroutan | An analytical method for evaluating network-on-chip performance[END_REF][START_REF] Umit | An analytical approach for network-on-chip performance analysis[END_REF].

These methods also make too many assumptions about the network and trac to get accurate values for a real system.

Various techniques based on simulation are already used to identify the impact of NoC parameters on performance. Narasimhan et. al. [START_REF] Narasimhan | An investigation of the impact of network parameters on performance of network-on-chips[END_REF] investigates the impact of dierent NoC topologies and trac types on dierent applications using OPNET simulator. Gehlot et. al. [START_REF] Gehlot | Performance evaluation of network on chip architectures[END_REF] investigates the performance of NoC topologies such as CLICHE, Folded Torus, BFT, SPIN and octagon using NS-2 simulator. An evaluation in terms of cost and performance by sweeping over dierent parameters (e.g. network topology, network interface queue depth) using a XML is proposed in [START_REF] Pestana | Costperformance trade-os in networks on chip: a simulation-based approach[END_REF]. A simulation framework for CMP system based on virtutech Simics [START_REF] Magnusson | Simics: A full system simulation platform[END_REF] and GEMS [START_REF] Milo | Multifacet's general execution-driven multiprocessor simulator (gems) toolset[END_REF] tool-set is used to evaluate the choice of key network parameters (topology, it size) on the behavior and performance of applications running on top of dierent network congurations

Impacts of NoC Design Parameters on Transmission Performance

presented in [START_REF] Villanueva | A performance evaluation of 2d-mesh, ring, and crossbar interconnects for chip multiprocessors[END_REF]. Bagherzadeh et. al [6] evaluates the performance impact of the communication protocol depending on the task structure. Some works made evaluation in terms of cost and performance by sweeping over dierent parameters (e.g. network topology, network interface queue depth) using XML, for example in [START_REF] Pestana | Costperformance trade-os in networks on chip: a simulation-based approach[END_REF] and [6]. The main drawbacks of these previous works rely to the level of abstraction which leads to inaccurate evaluation, or cannot provide information on hardware implementation costs.

In the proposed work we evaluate the impact of NoC design parameters on performance using systemC based simulator. We used a systemC based simulator because designing hardware for each NoC in the design space is unrealistic, and systemC utilize low-level hardware modeling combined with C++ for implementing the network characteristic and evaluating the network performances. The purpose is to obtain sufcient accuracy in choosing and adjusting the design parameters that can upgrade the performances in minimum QoS condition. For this purpose, we dene scenarios that represent network condition with minimum QoS and hence we adjust the value of each network parameter. The resulting performances such as latency, throughput, reliability and power consumption are evaluated using Noxim simulator.

In Noxim, power is estimated by total power consumption of router and each incoming and forwarding packet in router during simulation time. Noxim has dened the power value of each NoC parameter such as buer, packet size, routing type and selection path strategy. Thus, the power consumption in simulation is dependent on the number of transferred packet, parameters used and simulation time. Mapping method has inuences on area-size, power consumption and resource-use.

The eciency of using resources is inuenced by design of communication architecture.

Table 3.2 presents the main parameters that have an impact on the performances of NoC. We can note that NoC hardware micro-architecture have an impact on area and power because each resource needs power and space. Thus, increasing the resources scale or hardware micro-architecture in Figure 3.1 give impact on increasing the area size and power consumption.

Adding resources based on task placement in NoC system also cause the path of packet farther to reach destination, hence increasing latency performance. Total energy consumption is a result of multiplying the power with duration time. The increasing of latency causes the increasing in resources activity time thus increasing energy consumption. The mapping method in Figure 3.1 means topology mapping and task mapping.

Topology mapping is assigning each PE resource inside a network and task mapping is assigning a task to a PE. A bad mapping method uses more resources, need more area-size and increase power consumption.

Simple communication architecture uses only few numbers of resources and area thus power, area and use of resources are minimized. Conversely, complex communication architecture uses more resources thus causing an increase on power consumption and area size. Increasing injection rate in the network cause heavy trac. Network becomes more congested thus increasing latency. In other hands, if the channel capacity is bigger than the network load, increasing injection rate will increase the throughput.

Conversely, if the channel capacity is lower than the network load, increasing injection rate will degrade the throughput.

Latency (L) is one of the performances required to provide QoS [START_REF] Sheibanyrad | 3D Integration for NoC-based SoC Architectures[END_REF]. We have evaluated that latency is the most important performance of network. On limited perfor- A.size = Area Size, R.use = Resource use Color green = give impact, color red = not give impact mances of network, latency may represent other NoC performances such as throughput, reliability and power. Several NoC parameters which have inuence on the latency will automatically have inuence on throughput, reliability and power. Throughput depends on time because it is calculated by the number of arriving bit per time [START_REF] Sheibanyrad | 3D Integration for NoC-based SoC Architectures[END_REF].

On overloaded network when latency increase, the packets are queued and increase the arriving time of the packet, thus decreasing throughput. When latency increase, the network cannot guarantee that a packet will arrive at destination in a reliable time thus impacting reliability. The increasing of energy consumption is linear to duration time of active resources. When latency increases, it will increase the duration time of active Impacts of NoC Design Parameters on Transmission Performance resource thus increasing power consumption. That is why latency is the most important NoC performance indicator because it inuences three NoC performances.

Methodology and Experimental Result

This section presents the methodology and the experimental results of our work. We dene three scenarios in order to evaluate the impact of each parameter on the NoC performances. Firstly we evaluated the impact of parameters that causes network saturation. In this scenario we want to nd the combination of parameter that cause performance saturation and also evaluate the saturation point. By knowing these information, we then avoid the use of these combinations and the value after saturation in next scenario which evaluate the impact of parameter on performance.

We implemented the scenarios into Noxim simulator then evaluate the result of each scenario. Noxim provides several type of network parameters (i.e. routing algorithm, trac distribution, selection path strategy and arbitration) and network performance (i.e. average delay, throughput and power) needed in simulating the NoC design. Further, Noxim is customizable and modiable due to its open source code. User can customize the router architecture such as number of port, buer size or adding control mechanism in the router.

In terms of output result, Noxim simulator provides output performances such as latency, throughput, reliability and power. Latency is dened as the time spent to transfer one packet from a source node to a destination node while throughput is the network connection rate or channel capacity and is evaluated as a number of it per cycles. Reliability guarantees the delivery of packet arrived at destination in a tolerable time. In the simulation, we measured the reliability by dividing the number of received packets with the number of sent packets during simulation time. To get the percentage of the reliability, we multiply the results by 100. Power dissipation denotes the energy per time required to operate an embedded system. Total power dissipation is calculated as the sum of energy for switch, buer, wires and link. In the simulation, power calculated by the total of incoming its, outgoing its, active router and standby router. Each router has dierent power consumption depending on the use of routing algorithms and selection path type.

Worst condition scenarios

In real-life application, worst condition happens when the performances degrade over the threshold limit of QoS. Thus the system must adapt this condition by adjusting the parameters that have signicant impact on increasing performance. Worst condition is chosen because in normal condition the performances of network are maximum, thus the upgrading of parameters cannot give signicant impact on the upgrading performance or saturated network. In normal condition, we cannot dene which parameter can give more impact on performance.

We dene the worst condition by combining eight parameters: number of hotspot node, buer size, packet size, packet injection rate, routing type, selection path strategy and a number of resources. The challenges on determining worst network condition where the performance start to increase is to dene the parameter values. We have evaluated some combination of parameters hence dened a minimum or maximum value of parameter that causing worst condition as presented in Table 3.3. In the scenario to evaluate the impact of parameter on performance (chapter 3.4.3), we used 2D mesh dimension from 3x3 to 6x6. Thus in this scenario we have evaluated

Impacts of NoC Design Parameters on Transmission Performance

3x3 to 6x6 2D mesh dimension by increasing some parameters value. We found that, to degrade the performance of 3x3 mesh dimension, it must be at minimum one faulty node with a failure percentage minimum 0.5%, buer size of maximum one it and packet size composed by a minimum of 6 its as presented in Table 3.3.

Logically, larger packet size can decrease the overhead of data which then increase throughput. But in the network, the limitation of buer, retransmission and transmission delay aect degradation of throughput. Thus, to set worst condition, we degrade the performance by using big packet size. In this scenarios we used a packet size of minimum 6 its.

Increasing packet injection rate will increase throughput but contrarily will degrade the latency when the network is overload. Thus, there is no minimum or maximal value for packet injection rate in determining worst condition.

Network saturation

Each designed network communication has a limit of connection performances known as bandwidth limit. In this sub-section, some scenarios are dened to evaluate the network saturation condition where throughput is maximum. We have combined some NoC parameters and adjusted the value of each parameter to upgrade the throughput until saturation.

Firstly, we dene the range value for each parameter as presented in Table 3.4. Secondly, we dene four scenarios (Table 3.5) to evaluate the maximum throughput when the system adapt the degradation of performance. The objectives of these scenarios are

to nd what combination of parameters causes performance saturation and then dene the starting point of the saturation. We will then avoid the use of these parameters value in evaluating the impact of parameters on performances (chapter 3.4.3). For examples, for faulty percentage 0%, the throughput is not saturated while for faulty percentage 0.2, the throughput reach maximum value on 0.12 its/cycle. In this condition, the upgrading parameter value to adapt the degradation of the performance can upgrade the throughput maximum 0.12 its/cycle.

For faulty percentage 0.6 and 0.8, the maximum throughput are 0.08 its/cycle while for faulty percentage 0.6 the maximum throughput 0.1 0.08 its/cycle. In previous evaluation, we have evaluated the combination of parameters that may give impact on network saturation. The result shows that all combination of evaluated In adapting the worst network condition caused by degrading the reliability performances, decreasing packet size gives more eect on increasing reliability than adjusting other parameters value as shown in Figure 3.5. While to adapt the increasing power consumption in the system, decreasing number of active resources or shut down inactive resources is the best decision due to in fact that each resources consume energy as shown in Figure 3.6.

Best parameters type on performances

Each NoC parameters such as routing algorithm and selection path strategy has their own technique (Table 3.9). Each technique has dierent output performance. In this subsection we simulate each technique then evaluate the best technique based on the output performance. We compared the performances of six routing algorithm and three selection path strategy provided in Noxim simulator.

Table 3.9: The dierent technique of parameters to evaluate the impact on performance NoC is to nd NoC instances that balance the costs (e.g. area) and performances (e.g. latency and throughput). In this chapter, the worst condition scenarios, the evaluation of saturation network and the evaluation of the impact of NoC parameters design parameters on the performance have been presented. Worst condition is used as the rst state of network before adjusting the parameters. While the combination of parameters that causing network saturation is avoided in the evaluation of impact parameter on performance. Some scenarios have been presented to see how big the impact of upgrading parameters to the performances was dened.

The evaluation shows that latency is the most inuencing indicator of NoC performance to provide QoS over the other network performance. In simulation, to adapt the degradation of QoS caused by increasing latency, decreasing packet injection rate and decreasing packet size has biggest impact than increasing buer size or decreasing num- ber of resources as presented in Table 3.10. In worst case scenario, the Fully adaptive routing algorithm and NoP selection path strategy has the lowest latency than their counterparts.

In term of impact of parameter on the throughput performance, as presented in Table 3.10, increasing packet size have biggest impact on increasing throughput performance then followed by increasing injection rate. While increasing buer size and number of resources not give big impact on throughput performance. For other parameter such as routing algorithm, Fully adaptive routing algorithm can adapt the decrease of throughput in worst condition.

In reliability performances, as presented in Table 3.10, decreasing injection rate can increase reliability performances compared to increasing injection rate or increasing buer size. While Fully-adaptive routing algorithm and NoP selection path strategy can adapt the worst condition that cause decreasing reliability.

In term of power consumption, the fastest way to adapt the increasing power consumption is by decreasing the number of resources as presented in Table 3.10. Almost all routing algorithm type and selection path strategy have almost the same power consumption.

The results of this work can be used by NoC system designer as a guideline to estimate the system performance, related parameters and associated overhead in designing an adaptive NoC. In real-life application, all parameters we used in simulation (i.e.

packet size, buer size, routing algorithm and packet rate) are determined in a NoC router. Thus, recongurable router is needed to adapt the condition of network and the To evaluate the performance of the proposed algorithm, scenarios with various linkfaults and node failures schemes were created. Hence the number of hops to destination nodes and the number of alternative paths in faulty network are determined and compared with other 2D mesh routing algorithms. Further, we implemented Gradient in the Noxim simulator to evaluate its latency and throughput performances. the destination node is supposed to be in north-east of the current node. The Gradient algorithm then classies this destination node in Zone-2. In proposed algorithm the main route is north, while for the other algorithms (north-last, and fault-tolerant [11])

the main route is east. In case of dierent fault scenarios shown in Figure 4.3, the dierent decision on the main-route will aects the number of hops to reach the destination.

Moreover, in case of link-faults on north and east port of current node, the alternative route of our algorithm is west but other algorithms will choose the south. This is the second advantage of Gradient decision because the packet chooses the correct direction to avoid the faulty-link. As we can see, the packet with Gradient has always the shortest distance path to reach destination node. This is due to the increased number of alternative paths available when there are problems on the main route. This in turn oers a more precise localization of destination and faults. We can show the same behavior on dierent zone, such as in the case of the destination node is on the south-west of current node as shown in The objective of adaptive routing is to tolerate the faults that may cause packet deadlock and hence degrade the performance in NoC. But we also need to sustain network performance such as bandwidth and latency of communications. We then evaluate four measures of performance for the dierent routing algorithms: i) number of hops, which reect the length of the route and penalty due to faulty link, ii) number of alternative We have evaluated eight dierent routing algorithms, namely XY, West First, North Last, Negative First, Odd Even and Fully Adaptive that are implemented and supported by the Noxim simulator [START_REF] Palesi | Noxim -the NoC Simulator -User Guide[END_REF], the Fault Tolerant algorithm presented in [11] and Gradient. All these algorithms were evaluated under twenty dierent scenarios described in Figure 4.5.

These scenarios are designed to represents all fault position possibility and all destination node direction possibility in 2-D mesh topology. For example scenarios 1 to 4 in Figure 4.5, the destination nodes are in the west, east, north and south from the source node, thus they represents horizontal and vertical direction with a faulty link between them. Thus, these scenarios also represent horizontal and vertical possibility of fault position. In scenarios 5 to 20, the destination nodes are in west-north, east-north, west-south, and east-south of current node. Thus, its represents all possible positions in addition to vertical and horizontal direction.

As described in Figure 4.5, Scenarios 1 to 12 has only one faulty-link between current node and destination while scenarios 13 to 20 presents at least two faults on link or node on the route between the current node and the destination one. Thus the evaluation result of number of hops and the number of alternative paths of each routing algorithm is validated.

In chapter 2 has been stated that each routing algorithm has their own weakness in deciding the direction of packet to neighbour node. For example north-last algorithm, has no alternative route when the destination is in the north side of current node and there is a faulty link in between. A deadlock packet also occurs in west-rst routing algorithm if the destination node is in the west side of current node with a fault in between. The objectives of these scenarios are to shows the comparison of dierent path due to dierent routing decision.

Evaluation result

Table 4.1 summarizes the evaluation result of number of hops of each routing algorithm for scenario 1 to 12 as presented in Figure 4.5. In scenarios 1 to 12, we design one faulty link between source node and destination node in dierent direction. The result in Table 4.1 shows that west-rst algorithm is deadlock for scenario 1, north-last for scenario 3, negative rst and odd-even for scenario 4. While fully adaptive [START_REF] Palesi | Noxim -the NoC Simulator -User Guide[END_REF], fault tolerant [11] and Gradient routing algorithm have 3 numbers of minimum hops without deadlock in scenarios 1 to 4.

Classically, conventional routing algorithms divide 2D mesh topology into 4 zones: northeast, northwest, southwest and southeast, while our algorithm divides 2D mesh topology into 8 zones. In scenarios 5 to 12, we evaluated the path of packets for a destination node in the north-west, north-east, south-west, and south-east from the current node, with a link fault in horizontal and vertical line.

In scenario-1, algorithm North Last, Odd Even, Fully Adaptive, Fault Tolerant and Gradient has a minimum number of hops of 3 nodes, but algorithm XY, West First and Negative First cannot avoid the faulty link on the west side of the current node, thus causing packet deadlock and hence degradation of NoC performance. As expected, the deterministic algorithm fails in adapting the path depending on the position of the fault. Thus, it leads to deadlocks even with only one fault in the NoC. The results in color blue also show that, in scenarios 1 to 12, adaptive routing algorithms (fullyadaptive, fault-tolerant and Gradient) can avoid all faults (no deadlock) and have the same number of minimum hops.

We can see that in these scenarios there are three routing algorithms that have the same minimum number of hops. We then evaluate the number of alternative routes supported. We evaluate this metric only for adaptive routing, since the rst algorithms are deterministic and oer only one path from a source to a destination. Table 4.2 shows that in scenarios 1 to 12, all adaptive routing algorithms have the same number of hops (same results than previously analyzed) and the same number of alternative paths. In presence of only one fault the algorithms are equivalent. However in scenarios 13 to 20, which correspond to two simultaneous faults in the network, the fully adaptive routing algorithms cannot avoid deadlock and then blocked communications appears. In scenarios 13, 15, 17 and 19, the Gradient algorithm has more alternative paths than the fault tolerant routing algorithm, however both of them have the same number of minimum hops. This shows that Gradient has more possibilities to tolerate faults than its counterpart. Gradient also has lower number of hops in scenario 14, 16, 18 and 20. Thus, Gradient algorithm has smallest number of hops and more alternative routes compared to other existing fault-tolerant routing algorithms. In the next chapter, the methodology, the simulation scenarios and the experimental result of Gradient routing algorithm are also presented. Further, the implementation of Gradient routing algorithm into on FPGA is also presented.

For network performances evaluation, we modied the Noxim simulator to support failures as representative of worst-case scenarios. By this method, we were able to evaluate and compare the performance metrics of latency and throughput of the studied algorithms.

4.2 Diagonal: Fault-tolerant routing algorithm for 3D mesh topology

The conventional 2D integrated circuit (IC) has limited oorplanning choices, and consequently, it limits the performance enhancements arising out of NoC architectures.

Three-dimensional (3D) ICs are capable of achieving better performance, functionality, and packaging density compared to more traditional planar ICs [START_REF] Sheibanyrad | 3D Integration for NoC-based SoC Architectures[END_REF].

In this work we propose an adaptive fault-tolerant routing algorithm for 3D mesh NoC. The novel feature of this algorithm is on how the algorithm chooses the sequence of alternative paths when the packet faces a faulty link or node in the 3D mesh NoCs.

Diagonal: Fault-tolerant routing algorithm for 3D mesh topology 79 Some works address the routing problem for 3D mesh networks other than using the basic dimension order routing approach. Most of the existing 3D mesh routing algorithms dene the destination into horizontal and vertical layer. Some of them reuse existing 2D mesh routing algorithm for horizontal destination such as XY or YX. For example [START_REF] Rose | Fpga implementation of low latency routing algorithm for 3d network on chip[END_REF], proposed a deterministic routing scheme for choosing the 3D layer and it uses the XY routing within the 2D layers. The RPM routing algorithm [START_REF] Ramanujam | Near-optimal oblivious routing on three-dimensional mesh networks[END_REF] uses Z as vertical dimension and XY as horizontal dimensions. It rst routes a packet in the minimal direction to a random intermediate Z position then routes the packet on the XY plane using either minimal XY or YX routing.

1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 3 3 2 3 2 3 2 3 4 3 2 3 2 3 2 3 5 2 1 2 1 2 1 2 6 2 1 2 1 2 1 2 7 2 1 2 1 2 1 2 8 2 1 2 1 2 1 2 9 2 1 2 1 2 1 2 10 2 1 2 1 2 1 2 11 2 1 2 1 2 1 2 12 2 1 2 1 2 1
On 3D NoCs, [START_REF] Sunkam Ramanujam | A layer-multiplexed 3d on-chip network architecture[END_REF] proposed a load balancing routing scheme in which a packet is sent to a random layer then use XY algorithm to reach horizontal destination and nally traverse vertical direction to nal destination. An architecture called XNOTs [START_REF] Matsutani | Tightly-coupled multi-layer topologies for 3-d nocs[END_REF] proposed an algorithm which is based on the idea of vertical switching. However, it requires large area switches, which are costly since crossbar area grows quadratically with the number of ports. In router, a 4NP-First routing scheme in [START_REF] Pasricha | A low overhead fault tolerant routing scheme for 3d networks-on-chip[END_REF] extend the 2D west-rst, negative-rst and north-last turn models into 2 negative-rst (2N-rst), 3

negative-rst (3N-rst), and 4 negative-rst (4N-rst) turn models in 3D. A Quadrant-XYZ dimension order routing algorithm [START_REF] Khan | Quadrant-based xyz dimension order routing algorithm for 3-d asymmetric torus routing chip (atrc)[END_REF] partitions the geometrical space of torus 3D NoC topology into quadrants and selects the nearest wrap-around edge to connect the destination node. A recongurable inter-layer routing mechanism (RILM) for 3D

NoCs has been proposed in [START_REF] Rusu | Rilm: Recongurable inter-layer routing mechanism for 3d multi-layer networks-on-chip[END_REF]. It can tolerate high number of vertical link failures by moving the message rstly inside the current layer to reach other vertical link near destination. An Elevator-First distributed routing algorithm [START_REF] Dubois | Elevator-rst: A deadlock-free distributed routing algorithm for vertically partially connected 3dnocs[END_REF] proposed a deadlock and live-lock free algorithm by using two virtual channels (one for ascending and the other for descending packets) for the case of deterministic and deadlock-free planar Diagonal: Fault-tolerant routing algorithm for 3D mesh topology 81 routing schemes. The author in [START_REF] Wu | A fault-tolerant adaptive and minimal routing approach in 3-d meshes[END_REF][START_REF] Wu | A simple fault-tolerant adaptive and minimal routing approach in 3-d meshes[END_REF] proposed a fault-tolerant routing algorithm by dividing the 3-D mesh into eight sub-networks.

A fully adaptive routing algorithm for 3D NoCs named DyXYZ [START_REF] Ebrahimi | Dyxyz: Fully adaptive routing algorithm for 3d nocs[END_REF] has been proposed as a solution of the degradation in performance in deterministic routing algorithm.

This routing algorithm is similar to our proposed 3D routing algorithm called Adap-tiveXYZ. In this work we also designed a simple adaptive routing algorithm for 3D mesh called adaptive-XYZ. This algorithm is the adaptive version of static dimension order routing algorithm XYZ to tolerate faulty network condition.

In adaptive-XYZ routing algorithm, a packet rst traverses along the X dimension, then Y dimension and last in Z dimension. If the X dimension is faulty, the packet continues to Y then continue traverse X dimension again. If the X and Y dimension fail, the packet continue to Z dimension as shown on Figure 4.8-b. We use adaptive-XYZ algorithm and elevator rst algorithm as comparisons to our proposed algorithm. We used AdaptiveXYZ routing algorithm in the scenario to compare the output performance with Diagonal routing algorithm.

In this work we propose a routing method to tolerate both faulty links and faulty routers for 3D mesh NoC. This method is based on distances and directions of destination node positioning in the 3D mesh NoC. It divides destination node position into 48 zones. The novel feature of this method is on how it classies the destination node and the sequence decision of alternatives routes when the main route fails. The accuracy in selecting the alternative route can avoid increasing the required number of hops.

Therefore, proposed routing algorithm has minimum hops compared to other existing 3D mesh routing algorithm. For this purpose, we extend Noxim [START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF] to support 3D mesh topology and then implement the proposed algorithm. We then evaluate and compare the latency performance using worst-case scenario condition. The results presented in this part take into account the performances of fault-tolerant routing algorithm. The latency performance is also evaluated based on simulation and is compared to adaptive XYZ routing algorithm, a modied algorithm developed for comparison purpose. results also show that, in scenarios 3, adaptive-XYZ routing algorithms cannot avoid the fault that leads to deadlock while Vertical rst have 6 hops and Diagonal only 5. Thus, Diagonal algorithm has smallest number of hops than adaptive-XYZ and Elevator-rst [START_REF] Dubois | Elevator-rst: A deadlock-free distributed routing algorithm for vertically partially connected 3dnocs[END_REF] fault-tolerant routing algorithms. Table 4.4 summarizes the evaluation results of number of hops for each routing algorithm. Diagonal has lower number of hops in these four scenarios.

For network performances evaluation, we modied the router in Noxim simulator from 2D router to 3D router and support failures as representative of worst-case scenarios. By this method, we were able to evaluate and compare the performance metrics of latency and throughput of the studied algorithms. The methodology, the simulation scenarios and the experimental result of Diagonal routing algorithm are presented in the next chapter. In the rst experiment, we evaluate the latency performance in a faulty network by increasing the packet injection rate. We considered in this evaluation a 6x6 mesh topology with two nodes failures in the center of the network (Figure 5.1a) and four nodes failures near the border of the network (Figure 5.1b). We used at least 6x6 mesh dimension scales in order to obtain a signicant dierent of performance result between our proposed algorithm with its counterpart. The failure on the center of network permit to evaluate the performance of metrics packet sends from center side to border side and vice versa. While the faulty in border network is to evaluate the performance of metric packet send from border side to other border side. These scenarios are chosen as representative of other location failure.

The results in Figure 5.2a shows that in packet injection rate between 5.10 -4 to 2.10 -3 almost all routing algorithm have almost the same value of average delay. Then, after 2.10 -3 the Gradient routing algorithm has lowest average delay.

Evaluation on increasing faulty node in network

We have also evaluated the performance of the dierent routing algorithms by increasing the worst condition of the network. For this purpose, we increased the percentage of node failures, i.e. the fault percentage of router (0%=normal, 100%=totally faulty). In this scenario we use a 5x5 (Figure 5.3a) and a 6x6 (Figure 5.3b) mesh network, with a packet injection rate of 0.005 packets/cycle/IP and a simulation time of 10.000 cycles.

The results in Figure 5.3 show that our algorithm has lowest average delay in all cases and the dierence increase as worst case conditions do.

Conclusion

Three scenarios have been presented to evaluate the performance of Gradient fault tolerant routing algorithm. The result shows that Gradient algorithm has lower delay and higher throughput than its counterparts. The result of lower latency in chapter 5 proof the result in chapter 4, that Gradient has minimum number of hops. While the result that Gradient has higher throughput proof that it have more alternative path. Thus, it is validated that Gradient has better performances than its counterpart and contributes to avoid the degradation of NoC performances in hot-spot and worst trac condition. The number of hops and the number of alternative path of Diagonal routing algorithm have been evaluated in chapter 4. It shows that Diagonal has less number of hops and more alternative path than its counterpart. In this section, we evaluate the latency and throughput performance of Diagonal. For this purpose, we modied Noxim to support 3D mesh NoC and failures nodes. Then, we dene network parameters value used in simulation as shown in Table 5.1.

Experimental Results

Evaluation on increasing faulty in network

As the rst experiment, we evaluate the performance of Diagonal in a faulty network by increasing the packet injection rate. We consider the dimension of the network 3x3x3 with a packet injection rate of 0,004 (packets/cycle) and two faulty nodes in the 3D mesh NoC. We then increase the percentage of the faulty nodes and evaluate the average latency of packet traversal. The result shows that the proposed routing algorithm have lower average delay than DyXYZ [START_REF] Ebrahimi | Dyxyz: Fully adaptive routing algorithm for 3d nocs[END_REF] and routing algorithm as shown on Fig. 5.5-a.

In a second experiment, we used a 4x4x4 dimension size with a packet injection rate of 0,0015 (packets/cycle) and 3 faulty nodes in the network. Further we modify the behavior of the network by increasing the packet injection rate on dierent mesh dimension size. In this simulation we dened dierent number of faulty node for each dimension size. We use two faulty nodes for 3x3x3x mesh, three faulty nodes for 4x4x4 mesh, four faulty nodes for 5x5x5 mesh and ve faulty nodes for 6x6x6 mesh. The result on Figure 5.6 shows that the proposed algorithm has lower delay than adaptiveXYZ in all mesh dimension size. As stated in chapter 2, designer can design a NoC system in high level abstraction, middle level or RTL level. In chapter 3, the evaluation of Gradient performance has been done in middle level. In this sub-section, we evaluate the performance of Gradient routing algorithm at the RTL level.

The implementation of Gradient algorithm as switch control in Hermes router is evaluated using Modelsim 6.4 [START_REF]Mentor graphics[END_REF]. The goal is to evaluate the metric performances and to shows that using Modelsim tool, Gradient algorithm also have better performances than its counterpart. The simulation results are then compared to existing algorithm such as west-rst, negative-rst and north-last. In this simulation result, we did not compared the performance of Gradient with other adaptive 2D mesh routing algorithm Gradient and Diagonal routing algorithms are designed to distribute trac evenly among the paths to avoid failure and minimize contention. The scenarios and the methodology to evaluate the performances of Gradient and Diagonal routing algorithm are presented. The experimental results show that both algorithms has lower latency and higher throughput than it counterpart routing algorithm.

The new switch control that implement Gradient routing algorithm has been implemented in Hermes router then implemented into FPGA virtex-5. The synthesis result shows that Gradient use the same resources of slice LUTs as turn model routing algorithm. But, in the evaluation metric performances, Gradient has lower latency. However the XY algorithm has less resource but this algorithm is not adaptive. Thus, our proposed routing algorithm is the best adaptive routing due to its best performances and it use the same resources than other adaptive routing algorithms.

Experimental Results

+D=FJAH $

Conclusions and perspectives

Conclusions

SoCs or the embedded system is widely used in consumer electronics such as cell phone, digital video camera, Global Positioning System (GPS) or portable game devices. Current applications for embedded systems are designed with high number of communicating tasks. To provide these requirements, embedded system will be designed with hundreds or thousands of processing element core or processor inside a chip as predicted by Moore's Law. This requires highly parallel and exible communication architecture between each processing element in an embedded system.

The shared bus communication and direct point-to-point interconnections have been used for the communication between processing elements on a chip, however this communications cannot provide the intercommunication requirement in current and future MPSoCs. When the number of the element cores increase, bus arbitration bottleneck can increase the delay, while using direct point-to-point can become messy in wiring.

Network-on-Chips (NoCs) communication architecture has been proposed as a promising replacement to overcome many limitations of buses and point-to-point communication infrastructure by adopting the communication architecture of general network computer. NoC provides adaptivity and exibility infrastructure to overcome performances degradation due to change in environment and QoS requirements of applications.

104

Conclusions and perspectives

The ideal design of NoC is to get high throughput, minimum latency, minimum using resources, low power consumption and small area size. The quality of NoC can be measured from its network performance (i.e throughput, latency and reliability) and area size. To reach the maximum performance, the design parameters of NoC such as hardware architecture (i.e router micro-architecture, link architecture and topology), and software architecture (i.e application, security, trac, transport protocol, packet size, header size, routing, ow control, switching, it size, and buer size) must be considered.

All NoC parameters have inuence to NoC quality performances, thus the rst objective of this PhD was to evaluate the impact of NoC parameters on its performance To improve the network performances of NoC, routing algorithm is designed to distribute trac evenly among the paths to avoid hotspots and minimize contention.

The major problems of deterministic routing algorithm arise when faulty link or failures node occurs in the networks. Designing a fault-tolerant routing algorithm to avoid link fault and load balancing is mandatory to achieve design of reliable NoCs.

The second objective of this PhD was to propose a fault-tolerant routing algorithm to avoid faults in the network. Gradient and Diagonal routing algorithm has been proposed as fault-tolerant routing algorithm to overcome the deadlock packet. Gradient is proposed for 2D mesh, while Diagonal is designed for 3D mesh topology.

In 2D mesh, compared to existing routing algorithms that divide 2D coordinates The accuracy in selecting the alternative route can avoid increasing the number of hops of packets. Therefore, Gradient and Diagonal routing algorithm has minimum hops compared to existing fault-tolerant routing algorithm for 2D and 3D mesh NoC.

Proposed algorithms contributes to avoid the degradation of NoC performances in hotspot and worst trac conditions.

Finally, the implementation of Gradient routing algorithm into an FPGA has been presented. A new Gradient switch control has been designed and implemented in HER-MES router. The synthesis results shows that however Gradient routing algorithm have better performance than its counterpart, it use the same resources amount of FPGA with other turn model adaptive routing algorithm such as west-rst, negative-rst and north-last.

Perspectives

In chapter 3, the evaluation of the impact of NoC design parameters on the performance as a consideration in designing an adaptive NoC has been presented. In the near future,

Conclusions and perspectives

the researchers can continue this work by making a simple software application as a tool to give an overview of the impact of NoC design parameter on performance.

The concept and the performance of Gradient and Diagonal fault tolerant routing algorithm have been presented. The implementation of Gradient routing algorithm onto FPGA has been done, while Diagonal not. Thus, in the next future, Diagonal routing algorithm should be implemented into FPGA.

The performance evaluation and the implementation onto FPGA of Gradient routing algorithm have been presented in chapter 5. In the next future, we propose to continue this work by designing a dedicated prototype of Gradient router in a 4x4 mesh NoC.

Increasing NoC application that require dierent QoS, make NoC designer consider the network management such as fault detection, fault management, monitoring system or network control architecture. Integrating fault detection module in every NoC router can helps Gradient and Diagonal routing to choose the optimal routing path to destination. It can be local fault detection or global network fault detection. This module then can be used as fault control network that receive and send information or signal to all component in the system. Thus, all components in the network can react and adapt fastly with the current condition of network. Further, a fault management protocol is needed to handle growing number of fault information in network. Fault management protocol will be responsible for detecting, identifying faults in the network then taking corrective actions.

Adding monitoring system module is also part of future work. Thus, all information such as current performance, behavior of each trac application can be monitored then sent to all components in the network. With this monitoring, the information in NoC system can be viewed at transaction level. Thus, the fault detection and error identication fault process can be more quick and easy.

Finally, an intelligent NoC router is proposed as future work to react and adapt the information from fault management and network monitoring module. The intelligent NoC router must be automatically recongurable and user manageable. Les nouveaux systèmes embarqués intègre des milliards de transistors et des composants hétérogènes intégrés ensemble dans une puce appelée système multiprocesseur sur puce (MPSoC). Les bus et les interconnexions point-à-point ne permettent plus de supporter les communications entre toutes ces ressources. Pour soutenir efficacement ces communications, il est alors nécessaire d'implémenter un un réseau d'interconnexion très parallèle régulier et flexible.

Les réseaux sur puce (NoC-pour Network-on-Chip) ont été proposés comme une solution de communication dans les MPSoC. L'architecture NoC fournit l'infrastructure de communication qui est adaptable et offre différente qualité des services (QoS) basée sur les besoins des applications. En outre, les NoC peuvent aussi fournir une infrastructure souple de communications [1].

Une architecture à base de NoC est constituée de ressources de traitement tels que des processeurs, des DSP ou des unités de stockage et des commutateurs, ou routeurs, qui sont connectés par des canaux de sorte qu'ils sont en mesure de communiquer les uns avec les autres en s'envoyant des messages. En outre les routeurs peuvent stocker localement les messages en transit dans des buffers.

La topologie maillée (mesh) est la plus utilisée pour les NoC en raison de sa simplicité et de sa grande évolutivité [2]. Dans un circuit 2D générique les ressources sont connectés dans une grille formant une maille homogène, en 3D le maillage consiste à empiler des mailles 2D. Les architectures 3D offrent de meilleures performances réseau par rapport aux architectures 2D [3] en raison de la complexité croissante des circuits et de la longueur des interconnexions dans les topologies 2D.

L'introduction de la qualité de service dans un réseau sur puce nécessite des mécanismes de réservation afin de garantir le temps de latence et le débit des paquets proposés. Les interconnexions NoC ont beaucoup de paramètres qui influent sur leurs performances. Dans ce sens, un concepteur de NoC doit choisir plusieurs paramètres (et leurs valeurs) qui ont chacun un impact sur les performances du réseau. La précision de ces choix et l'ajustement de la valeur de ces paramètres peuvent éviter la dégradation des performances du réseau. Dans cette thèse nous avons d'abord proposer une évaluation de l'impact des paramètres de conception d'un NoC sur son rendement. Nous avons ensuite fait varier leurs valeurs afin d'évaluer leur impact sur la variation des performances. L'objectif est d'évaluer quelle est l'incidence de la mise à niveau d'une valeur d'un paramètre donné sur les performances. Les résultats obtenus peuvent être considérés comme une base pour la conception de mécanisme de contrôle d'un NoC adaptatif pour éviter la dégradation de la QoS dans des conditions d'opérations changeantes.

L'utilisation des technologies submicroniques profondes dans un système embarqué cause une augmentation de la susceptibilité au "Single Event Upset" (SEU) qui peuvent diminuer la fiabilité des circuits. Un SEU se produit lorsque un rayonnement provoque le changement de valeur d'un bit dans certaines bascules du circuit. Cette modification indésirable peut causer le dysfonctionnement de l'architecture. Un autre problème qui mène à l'apparition de défauts permanents dans le circuit est le " vieillissement ". Dans le cas d'un défaut permanent l'élément fautif doit être éliminé de la communication. Une autre solution est de re-router le paquet en évitant le composant défectueux, ainsi un routage tolérant aux pannes est nécessaire. Nous avons ainsi conçu des algorithmes de routage tolérant aux fautes pour des réseaux mesh en 2D et en 3D. Ces deux algorithmes prennent en compte des séquences de voies alternatives pour les paquets lorsque la voie d'acheminement principale tombe en panne. Les algorithmes proposés permettent d'éviter plus de fautes et tolèrent des défaillances multiples dans le pire état du trafic. destination, cette propriété permet de supporter de la tolérance aux pannes, ou de l'optimisation de performance en évitant des zones du réseau qui seraient surchargée. l'idée de la technologie 3D est de rendre la distance entre les noeud plus près par rapport à une topologie 2D en empilant des circuits les uns sur les autres [3]. Les interconnexions par "Through Silicon Via" (TSV) conduisent à des distances plus courtes entre les deux couches.

Lors de la conception d'un SoC le compromis entre performances du réseau (c.-à latence, débit, charge de la communication ), la consommation d'énergie et le coût silicium est primordial. Ainsi la qualité d'un NoC, peut être mesurée à partir de sa consommation d'énergie, de la taille de ses ressources et de ses performances. Les performances du réseau NoC sont sa latence, son débit et sa fiabilité. Ainsi, le concepteur de NoC doit prendre en compte l'impact de chaque paramètre sur les performances du résultat.

Impacts des paramètres de conception NoC sur les performances de transmission

Le défi à relever pour les concepteurs de SoC contenant un NoC est de trouver l'équilibre entre le coût et les performances (par exemple, la latence et le débit) du réseau. Nous avons dans un premier temps identifié les paramètres importants pour un NoC ainsi que ses performances principales. Nous avons ensuite établis différents scénarios de fonctionnement afin d'évaluer l'impact de la variation de chaque paramètre sur les performances du réseau. Pour évaluer ces scénarios nous avons utilisé le simulateur Noxim basé sur SystemC [7].

Nous avons identifié deux parties pour l'évaluation d'un NoC : la performance du réseau et le coût de mise en oeuvre conformément à la figure 1. Les performances du réseau se composent de la latence, du débit et de la fiabilité tandis que le coût de mise en oeuvre inclus la consommation d'énergie, la surface silicium du réseau et le nombre de ses ressources.

Lors de nos expérimentations nous avons identifié que la latence, le débit, la fiabilité et la consommation d'énergie sont principalement influencés par la capacité des ressources, la capacité du canal, de la topologie et la complexité de la tâche comme indiqué sur la 1. La capacité des ressources indique le maximum d'informations traitées par Processing Element (PE). Il représente la performance du routeur ou du processeur. La capacité du canal indique la quantité maximum d'information de données qui peut être transmis de manière fiable dans un canal. La latence est l'une des performances requise pour permettre une grande qualité de service. Lors de conditions limités d'opérations la latence permet de représenter aussi le débit, la fiabilité et la consommation d'énergie. scénarios de pires conditions En application réelle, les pires conditions se produisent lorsque la performance se dégrade à la limite de QoS. Ainsi, le système doit s'adapter en ajustant les paramètres qui ont un impact significatif sur l'augmentation des performances.

Le pire état arrive lorsque les performances du réseau sont au maximum, donc la mise à niveau des paramètres ne peuvent pas donner d'impact significatif sur la performance ou d'un réseau saturé. En condition normale, nous ne pouvons pas définir quel paramètre peut donner le plus d'impact sur les performances.

Nous avons évalué et définis le pire état en combinant huit paramètres : le nombre de hotspot, la taille de la mémoire tampon, la taille des paquets, le taux d'injection de paquets, le type de routage, la distribution de la circulation, de la stratégie de parcours de sélection et le nombre de ressources. Nous avons évalué les combinaisons de paramètres qui provoque les pires conditions.

Nous avons ainsi pu évaluer l'impact de chaque paramètre sur les performances du réseau. scénarios de saturation réseau Chaque communication de réseau a une limite de performances de connexion connu comme limite de bande passante . Nous avons donc testé le réseau afin de déterminer cet état de saturation. L'objectif dans ce cas est de déterminer les combinaisons de paramètres provoquant la saturation. Dans les conditions testée nous n'avons pas saturé le réseau ce qui permet par la suite de valider les intervalles de valeurs des paramètres testés.

Incidence des paramètres sur les performances

Nous avons dans un deuxième temps évalué l'ampleur de l'impact de l'amélioration de la valeur des paramètres sur les performances du NoC et identifier le meilleur jeu de paramètre à adapter en cas de détérioration des communications. Les résultats montrent que la latence est la performances la plus sensible et un très bon indicateur de la qualité de service du réseau. Il est apparu que la diminution de la taille des paquets et du taux d'injection donne de bon résultat afin de maintenir la latence. L'algorithme de routage a lui aussi un impact important sur cette métrique.

En terme d'impact sur le débit, l'augmentation de la taille des paquets et du taux d'injection ont un grand impact. Ce qui va à contre sens de l'optimisation de la latence. Les autres paramètres n'ont pas un grand impact sur le débit.En ce qui concerne la fiabilité la diminution du taux d'injection permet d'améliorer les choses, mais le paramètre le plus important pour cette performance reste l'algorithme de routage. Finalement la consommation de puissance et les ressources utilisées dépendent grandement de la taille des buffers dans les routeurs, du nombre de ressources et de l'algorithme de routage.

4 Algorithmes de routage tolérants aux pannes pour réseaux mesh 2D et 3D L'originalité de nos algorithmes de routage vient de la façon dont ils classifie le noeud de destination et comment ils choisissent la séquence de chemins alternatifs.

algorithme de routage Gradient pour mesh 2D

Algorithme

Les algorithmes de routage tolérants aux pannes classiques classent les noeuds destination dans quatre zones, en fonction de lignes verticales et horizontales passant par le noeud courant. Gradient classifie l'adresse de destination en huit zones basées sur la ligne gradient (M ) en coordonnées 2D tel que présenté dans la figure 2. La ligne gradient (M ) est obtenue grâce à l'équation 1

M = D y -C y D x -C x (1)
avec (Dx, Dy) l'adresse de destination et (Cx, Cy) l'adresse du routeur actuel. Nous utilisons alors la ligne de gradient lef t|M right| = 1 pour diviser le réseau en huit zones (Fig. 2). Sur la base de ce positionnement relatif de l'adresse de destination une zone est assignée pour déterminer le saut suivant (c'est à dire le routeur suivant dans la chemin).

Pour chaque zone du noeud de destination pour le paquet courant, l'algorithme Gradient définit un itinéraire principal et trois variantes. La décision du chemin utilisé est alors prise à l'exécution en fonction des conditions du réseau. Par exemple, pour une destination dans la Zone-1, la route principale est Est qui fournit le chemin le plus court vers la destination. Outre le nombre de zone permettant de mieux localiser la destination, la différence repose également sur la séquence de choix de la route alternative. La séquence intégrée dans Gradient permet de minimiser la taille des routes alternatives en cas de fautes sur le chemin principal.

Gradient est indépendant de la méthode de détection de défaut. La position des "hotspots" et des fautes sont définis statiquement dans notre travail. Afin d'éviter une zone de "hotspot" ou un élément défectueux dans le réseau, Gradient choisit la voie alternative la plus courte. le choix de ce chemin plus court permet d'éviter la dégradation de la performance du réseau tels que la latence et le débit.

Evaluation des performances

Nous avons évalué huit algorithmes de routage différents, à savoir XY, West-first, Northlast, Negative-first, Odd-Even, fully-adaptive qui sont mis en place et intégré dans le simulateur Noxim [8], l'algorithme à tolérance de panne présentée dans [9] et Gradient. Tous ces algorithmes ont été évalués selon différents scénarios. ces scénarios sont conçus pour évaluer le nombre de sauts et le nombre de chemins alternatifs de chaque algorithme de routage dans différentes conditions. Le résultat montre que notre algorithme a le plus petit nombre de sauts et le plus grand nombre de routes alternatives par rapport aux autres algorithmes existants.

Nous avons évalué la latence dans un réseau défectueux en augmentant la le taux d'injection de paquets. Nous avons utilisé dans cette évaluation une topologie mesh 6x6 avec deux noeuds fautifs dans le centre du réseau et quatre noeuds fautifs près de la frontière du réseau.

Les résultats montrent que pour des taux d'injection de paquets entre 5, 10 -4 à 2,10 -3 la quasi-totalité des algorithmes de routage ont des performances similaires. A partir d'un taux d'injection de 2, 10 -3 l'algorithme Gradient a le plus faible retard moyen. Nous avons également évalué les performances des différents algorithmes de routage en augmentant le pourcentage de défaillance des noeuds, soit le pourcentage de défauts des routeurs variant de 0 % = normal, à 100 % = totalement défectueux. Dans ce scénario, nous utilisons un réseau mesh de taille 5x5et un autre de taille 6x6, avec un taux d'injection de paquets de 0,005 paquets/cycle/IP. Les résultats montrent que notre algorithme a la plus faible retard moyen dans tous les cas et la différence augmente avec l'aggravation des conditions d'opérations des réseaux. Enfin, nous avons évalué l'évolutivité de l'algorithme en augmentant le nombre de noeuds dans le réseau. Le résultat montre que l'algorithme proposé a un nombre minimum de saut, un plus grand nombre de chemins alternatifs, des latence inférieures et un débit supérieur que les autres algorithmes de routage adaptatifs.

Mise en oeuvre sur FPGA

Algorithme de routage gradient a été mis en oeuvre dans un routeur du réseau HERMES [11]. Ce réseau bien connu a été prototypé avec succès sur Virtex-II FPGA Xilinx [12]. Les éléments de base de ce routeur sont une logique de commande de commutation et cinq ports bi-directionnels (connexion à quatre autres commutateurs et une connexion locale au PE). La logique de commande de commutation est constituée de l'arbitrage et de l'algorithme de routage que nous avons modifié.

Nous avons intégré un réseau mesh de dimension 4x4. La synthèse a été réalisée avec les outils ISE 12.4 [13] pour un FPGA Virtex-5. Les résultats de synthèse (tableau 1) montrent que l'algorithme de routage XY utilise moins de ressources cependant cet algorithme n'est pas adaptatif. Dans les autres cas les algorithmes de routage adaptatif tel que le notre utilisent presque les mêmes ressources du FPGA ciblé. Ainsi, l'algorithme Gradient est préférable car il nécessite les mêmes nombre de ressources, mais a une meilleure performance réseau par rapport aux autres algorithmes. Comme pour Gradient, l'originalité de Diagonal est la façon dont l'algorithme choisit la séquence de chemins alternatifs lorsque le paquet est confronté à un lien en défaut dans les NoC en technologie 3D. L'algorithme proposé considère la distance et la direction du noeud de destination en fonction de la position du noeud courant.

Les distances sont obtenus à partir du rapport entre les valeurs absolus de △X, △Y et △Z. Alors que les directions sont obtenues directement à partir de ces valeurs. L'algorithme choisit la distance la plus longue comme route principale, la seconde distance la plus éloignée comme première alternative et la troisième plus éloignée pour l'alternative-2. Pour l'alternative-3 l'algorithme choisit la route l aplus courte dans le sens opposé à la distance. Sur la base des zones définies, notre algorithme présente un minimum de hop et plus de voie alternative pour atteindre le noeud de destination. Par exemple, si la distance de destination-Xà partir de courant-X (|△X|) est plus loin que |△Y | et |△Y | est plus loin que |△Z|, l'algorithme choisira X comme voie principale, Y comme première alternative, Z comme la seconde variante, -Z pour troisième variante, -Y en quatre et enfin -X en tant que cinquième itinéraire alternatif.

Evaluation des performances

Dans ce paragraphe, nous présente l'évaluation du nombre de sauts pour chaque algorithme de routage. Nous avons évalué trois algorithmes de routage différents, adaptative-XYZ, Elevator-first [10] et Diagonal pour une topologie mesh 3x3x3. Les résultats de l'évaluation du nombre de sauts pour chaque algorithme de routage montre que Diagonal à le plus petit nombre de sauts requis dans tous les scénarios testés. L'évaluation de l'impact des paramètres de conception d'un NoC sur sa performance a été présenté. Les résultats peuvent être utilisés pour concevoir un mécanisme de commande afin d'éviter la dégradation de la qualité de service lorsque les conditions de communications change dans un NoC adaptatif. Dans l'avenir, ce travail sera la base d'une application logicielle permettant l'évaluation au cours de la conception de l'impact des choix du concepteur sur la performance du réseau.

Les algorithmes de routage Gradient et Diagonal ont été proposés comme algorithme de routage à haute disponibilité pour surmonter le blocage de paquets pour des réseaux mesh en technologie 2-D et 3-D. Les séquences de choix d'itinéraires alternatif dans nos algorithmes permettent de choisr le plus court chemin pour éviter des zones de contention ou des éléments fautifs dans le réseau. L'implémentation dans un FPGA a montré que nos algorithmes ne nécessitent pas plus de ressources que les autres algorithmes tout en supportant de meilleure performance dans un environnement avec des éléments fautifs.

xiii 3 . 2

 32 Evaluation of throughput saturation . . . . . . . . . . . . . . . . . . . . 3.3 The impact of upgrading value of injection rate, packet size, buer size and number of resources on upgrading the latency . . . . . . . . . . . . 3.4 The impact of upgrading value of injection rate, packet size, buer size and number of resources on upgrading the throughput . . . . . . . . . . 3.5 The impact of upgrading value of injection rate, packet size and buer size on upgrading the reliability . . . . . . . . . . . . . . . . . . . . . . . 3.6 Energy consumption over dierent values of injection rate, packet size, buer size and number of resources . . . . . . . . . . . . . . . . . . . . . 3.7 The impact of the routing algorithm on latency . . . . . . . . . . . . . . 3.8 Selection-path strategy impact on latency . . . . . . . . . . . . . . . . . 3.9 The impact of the routing algorithm on throughput . . . . . . . . . . . 3.10 Selection-path strategy impact on throughput . . . . . . . . . . . . . . 3.11 The impact of the routing algorithm on reliability . . . . . . . . . . . . 3.12 Selection path strategy impact on reliability . . . . . . . . . . . . . . . 3.13 The impact of the routing algorithm on power consumption . . . . . . . 3.14 Selection path strategy impact on power consumption . . . . . . . . . . 4.1 Gradient concept divide 2D coordinate into eight zones based on gradient line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Sequence decision of Gradient algorithm for a destination in (a) Zone-1, (b) Zone-2, (c) Zone-3, (d) Zone-4, (e) Zone-5, (f) Zone-6, (g) Zone-7, (h) Zone-8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Alternative path of dierent routing algorithms in presence of faults in the network for dierent relative position of the destination node . . . . 4.4 The abstraction of Gradient routing algorithm . . . . . . . . . . . . . . 4.5 Twenty conditions of link-faults and node failures to evaluate the minimum hop and number of alternative path for seven dierent routing algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Addressing the position of node on 3D coordinate . . . . . . . . . . . . xiv List of Figures 4.7 Sequence decision of Diagonal algorithm for destination coordinate on (a) [1,2,3], (b) [3,-2-1], (c) [-2,-3,1] and (d) [-5,-4,-3] . . . . . . . . . . . 84 4.8 Comparison between (a) Diagonal routing algorithm and (b) AdaptiveXYZ routing algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.9 Routing path comparison between Diagonal, AdaptiveXYZ and Elevator rst [16] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.1 Two scenarios used in simulation: (a) 6x6 mesh with 2-nodes failure in the center of network and (b) 6x6 mesh with 4-nodes failure on near border of network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.2 Average delay comparison on increasing packet injection rate for (a) rst scenario and (b) second scenario . . . . . . . . . . . . . . . . . . . . . . 91 5.3 Average delay comparison on increasing faulty percentage with packet injection rate of 0.005 packets/cycle/IP for (a) 5x5 mesh and (b) 6x6 mesh topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.4 (a ) Average delay and (b) average throughput on increasing number of nodes from 3x3 to 10x10 with packet injection rate 0,01 packets/cycle/IP 93 5.5 Average delay comparison on (a) 4x4x4 mesh with packet injection rate 0,004 and (b) 4x4x4 mesh with PIR 0,0015 . . . . . . . . . . . . . . . . 94 5.6 Average delay comparison on increasing packet injection rate from 0,0005 to 0,0035 packets/cycle/IP for (a) 3x3x3, (b) 4x4x4, (c) 5x5x5, (d) 6x6x6 mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.7 Implementing Gradient routing logic inside switch control block of HER-MES NoC router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.8 Average latency comparison of 2D mesh routing algorithm on increasing packet rate and packet size . . . . . . . . . . . . . . . . . . . . . . . . . 101 A.1 Decision path of XY routing algorithm in one fault condition between current and destination node . . . . . . . . . . . . . . . . . . . . . . . . 122 List of Tables 2.1 Similarities and dierences between NoCs and Computer Networks (CN) 2.2 Resources in Xilinx Virtex-5 (xc5vsx50t-1665) FPGA [77] . . . . . . . 3.1 Impact of NoC parameters to performances . . . . . . . . . . . . . . . . 3.2 Impact of design parameters on performance of NoC . . . . . . . . . . . 3.3 Parameter values for worst network condition for dierent size of network 3.4 Parameters range value used in scenarios to evaluate the saturation performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Parameters range value used in scenarios to evaluate the saturation performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Simulation result of latency and starting saturation point . . . . . . . . 3.7 The dened and adjusted parameters used in the scenario . . . . . . . . 3.8 The adjusting parameters to upgrade the performance . . . . . . . . . . 3.9 The dierent technique of parameters to evaluate the impact on performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Summarize the most inuence parameter to NoC performances . . . . . 4.1 Number of hops for each algorithm in the presence of one fault in the network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Comparison of number of minimum hops for the three adaptive routing algorithms and optimal calculation by hand . . . . . . . . . . . . . . . . 4.3 Combination possibilities of (a) distances and (b) directions based . . . 4.4 Number of minimum hops comparison of three adaptive routing algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: General NoC architecture which contains resources (processor, memory, DSP, etc), switch/router and network interface.

Figure 1 . 2 :

 12 Figure 1.2: Proposed novel routing technique as an approaches towards adaptive NoC

FPGA

  has been chosen by NoC designer to prototypes their design due to the fast and Introduction low cost implementation. In our research, we considered the Xilinx Virtex-5 FPGA to implement our proposed fault-tolerant routing algorithm. 1.1 Problem statement (open challenges) 1.1.

9 1. 3

 93 Organization of the manuscript This thesis is organized in six chapters. Chapter 2 provides an overview of the evolution of the NoC, the NoC architecture, the impact of parameters to performances, fault tolerant routing algorithm and NoC simulator. State of the art on communication such as bus and direct point-to-point are explained in the NoC evolution. Main topologies, switching technique, ow control technique, scheduling technique and routing technique of NoC are also presented. The problem of non-fault tolerant routing algorithm faulttolerant routing concept and NoC simulators that are used to evaluate NoC design are also introduced. In chapter 3, the impact of NoC design parameters on the performances of NoC are dened and evaluated. The detail of NoC performances, parameters, and their dependencies are explained. The methodology on how to evaluate the impact of each parameter on each performance is presented. The last section provides the experimental results including evaluation of network saturation condition and the impact of parameters on the NoC performances. Chapter 4 presents the proposed Gradient and Diagonal fault-tolerant routing algorithms for respectively 2D mesh and 3D mesh topologies. Scenarios with various linkfaults and node failures schemes are dened to evaluate the number of hops required to reach a destination nodes and the number of alternative paths. In the presence of faults, the comparison with state of the art algorithm results of minimum hops and alternative path are presented. Chapter 5 presents the experimental results and implementation of proposed faulttolerant routing algorithm. The comparison of network performance between proposed algorithms with other routing algorithm is also presented. In the last section, the synthesis result of Gradient implementation on FPGA and the evaluation of frequency on the performance are presented. Finally, the last chapter concludes this work and proposes the perspectives. +D=FJAH State of the art -Denitions This chapter gives an overview of adaptive NoC architectures and their evolutions. The comparisons between bus interconnection, general network and NoC interconnection are presented. The architectures of NoC such as resources, interconnection, topology and protocol communication are explained. The 3-D NoC technology is also presented.

Figure 2 . 1 :

 21 Figure 2.1: Direct point to point connection infrastructure for SoC[7]

13 Figure 2 . 2 :

 1322 Figure 2.2: Shared bus interconnection infrastructure for SoC

Figure 2 . 3 :

 23 Figure 2.3: Packet switched network communication infrastructure

Figure 2 . 4 :

 24 Figure 2.4: General NoC communication architecture

Figure 2 .

 2 Figure 2.6 present general 2-D meshes router architecture. It has four bidirectional ports (i.e. east, west, north and south) to connect with neighbour routers and a local one to connect to its PE. Each input port has a buer as temporary storage of data before it is served by the router.

Figure 2 . 5 :Figure 2 . 6 :

 2526 Figure 2.5: Regular topologies used in NoC: (a) 2-D mesh, (b) torus, (c) ring and (d) binary tree

Figure 2 . 7 :

 27 Figure 2.7: The example of (a) irregular and (b) mixed topology used in NoC

Figure 2 . 8 :

 28 Figure 2.8: General switching process

  State of the art -Denitions(a) Forbidden turn in West rst (b) Forbidden turn in North last (c) Forbidden turn in Negative rst

Figure 2 . 9 :

 29 Figure 2.9: The forbidden turns (dashed line) in turn model routing algorithm: (a) West rst, (b) North last and (c) Negative rst[START_REF] Park | Generic methodologies for deadlock-free routing[END_REF]

3 -

 3 D topology to make the distance between nodes closer compared to 2-D topology as illustrated in Figure 2.10. It shows that to the connection between node-D and node-M in 2-D topology is farther (Figure 2.10-a) than 3-D topology (Figure 2.10-b). Using

The 3 -Figure 2 . 10 :

 3210 Figure 2.10: The concept of 3-D topology to make the distance between node closer than in 2-D topology

Fault-tolerant and deadlock-free techniques 29 routing

 29 path fails. The main diculty of these methods is on how to choose the sequence of alternative routes since an inappropriate selection may increase the number of hops of packet to reach its destination, thus degrading the performance of NoCs or causing possible deadlocks or live-locks. Some switching techniques were designed to avoid the deadlock packet in the network. Wormhole and store-and-forward switching technique were proposed for deadlock freeness, however there are no general result that show the adaptivity and deadlock freeness of these techniques.

  State of the art -Denitions(a) Conditions where deadlocks occurs in West-rst routing algorithm (b) Conditions where deadlocks occurs in North-last routing algorithm (c) Conditions where deadlocks occurs in Negative-rst routing algorithm (d) Conditions where Deadlocks in Fulladaptive routing algorithm[START_REF] Palesi | Noxim -the NoC Simulator -User Guide[END_REF]

Figure 2 . 12 :

 212 Figure 2.12: Conditions where deadlocks occur in (a) West-rst, (b) North-last, (c) Negative-rst and (d) Full-adaptive routing algorithm

The 3 -

 3 D technology was proposed to support the need of growing network, communication problem in SoC and as solutions to the limitation performance and oor planning in conventional 2-D architecture. It realizes the stacking of die contouring either processor or memories. A number of 3-D topologies and routing techniques have been presented. 3-D mesh topology is the rst most used topology, while XYZ routing algorithm is the simple, easy and deadlock-free routing mechanism.Conclusions 37The main goal of NoC design is to get high performances. But, the most important consideration is the trade-o between network performances and silicon area requirements after mapping. Thus, NoC designers must consider the impact of NoC parameters on the trade-o between network performances and area size. For this reason, in this thesis (chapter 3) we propose an evaluation on the impact of parameters on performances of NoC as consideration for NoC designer to dene and adjust the parameters that balance the network performances and area.A fault in network may be caused by the behavior of network or by permanent fault caused by poor fabrications yield. If it is not anticipated, it may cause error and deadlock packet then decreasing the NoC performance. Fault tolerance routing is one of the solutions to avoid this problem. Thus, in this thesis we proposed a fault tolerant routing algorithm for 2-D mesh named Gradient and for 3-D mesh called Diagonal. !& State of the art -Denitions +D=FJAH !Impacts of NoC Design Parameters on Transmission PerformanceIn this chapter we evaluate the impact of NoC parameters setting on performances as a consideration in designing an adaptive NoC. We consider two families of NoC performances that are network performances and implementation costs. Network performances consist of latency, throughput, and reliability, whereas the implementation costs consists of power consumption, area size and ecient use of resources. We used eight combinations of NoC parameter values to dene network condition that represents minimum QoS and hence get the resultant performance using systemC based simulator[START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF]. To see the impact on the performances, we adjust the value and change the type of each parameter. The results indicate the impact of parameters on the NoC performances and the tradeo involved among them.

  Communication architecture is used to describe a protocol layer stack. It governs how resources communicate each other and regulates how packets are sent and arrive at destination. Open System Interconnection (OSI) model is successfully employed in general network computer to overcome the problems of buses interconnection. It consists 40 Impacts of NoC Design Parameters on Transmission Performance of the denition of application, transport, network, data-link and physical layers.Application layer provides user-interface to communicate with other applications running on other nodes through a network. The transport layer is responsible for endto-end communication and reliable communication. The network layer denes how a packet is transmitted over the network from an arbitrary sender to an arbitrary receiver directed by the destination network address. It implements the routing algorithm of packets from source to destination and decides the form of packets. This layer is also responsible for the segmentation and reassembly of its, point-to-point routing between switches and contention management.Flow control is part of the data-link layer. It avoids the queue and collision trac by controlling the allocation channel and buer resources in the router. Physical layer is concerned with physical characteristics of the medium used for connecting switches and resources with each other. In the context of SoC, it species voltage levels, length and width of the wires, signal timings and the number of wires connecting two units.3.1.1 NoC router parametersIn a NoC, adding new resources means to add new communication capacity by adding new switches and interconnects. In a bus-based system, adding a new resource has a profound impact on the performance of the rest of the system because the same communication resource is now shared among more resources. This scalability property is a necessary precondition for the arbitrary composability property but it is not sucient to guarantee it. Further, the communication network must be able to guarantee allocated bandwidth and to enforce a decent behavior of the resources to avoid the monopolization of the entire communication bandwidth by a single resource.A topology that denes how the resources are connected in a network is the most important choice in designing a NoC. Topology has big eect on the use of routing strategy and the mapping of core to networks nodes. It also impact on the network latency, throughput, area, fault-tolerance and power consumption. While buer size of routers has inuence to latency and throughput. When a packet arrives in a router, it Main NoC Parameters 41 must go into the buer of input port. When the buer capacity of the output queue is exceeded then the last packet will be delayed, increasing the global latency.

3. 1 . 2

 12 Network parameters A packet may have dierent size, header and type. The header contains routing information. The dierent packet format aects the performance of network especially throughput and latency. Packet size is the total size of packet load and header packet.

3 . 3

 33 Impacts of Design Parameters on PerformanceTo evaluate the impact of NoC parameters to its performances, rst we classied the NoC performances in two part: network performances and implementation costs as shown in Figure3.1. The network performance consist of latency, throughput and reliability while implementation cost consist of power, area size and resource use.

Figure 3 . 1 :

 31 Figure 3.1: NoC performances classication, parameter impact and the major inuence of latency to other NoC performances

Figure 3 . 2 :

 32 Figure 3.2: Evaluation of throughput saturation

Table 3 . 6 :No 3

 363 Simulation result of latency and starting saturation point Impact of adjusting parameters value on performances

Figure 3 . 3 :Figure 3 . 4 :Figure 3 . 5 :Figure 3 . 6 :

 33343536 Figure 3.3: The impact of upgrading value of injection rate, packet size, buer size and number of resources on upgrading the latency

  , Negativerst, Northlast, Oddeven, Fullyadaptive Selection path strategy Random, Buer level, Neighbour on path The evaluation of latency in worst condition shows that Fully-adaptive routing algorithm (Figure 3.7) and Neighbors-on-Path (NoP) of selection path strategy (Figure 3.8) has lower latency than other technique of parameters. The selection of this technique (fully-adaptive and NoP) are suitable to adapt the degradation QoS in worst condition. In worst condition, Fully-adaptive routing (Figure 3.9) and Buer-level selection Methodology and Experimental Result 59 strategy (Figure 3.10) have lower degradation on throughput compared to other parameters, thus these parameters are suitable to adapt the condition of minimum QoS in presence of faults in network. Whereas, Fully-adaptive routing (Figure 3.11) and NoP selection strategy (Figure 3.12) are the best choice to adapt the worst QoS condition caused by degradation reliability. The results show that the best adaptation to the increase of power consumption are by choosing Fully-adaptive routing algorithm (Figure 3.13) and NoP selection strategy (Figure 3.14) while the biggest eect on decreasing the power consumption is by decreasing number of resources as shown in Figure 3.6.

Figure 3 . 7 :Figure 3 . 8 :Figure 3 . 9 : 61 Figure 3 . 10 :Figure 3 . 11 :

 37383961310311 Figure 3.7: The impact of the routing algorithm on latency

Figure 3 . 12 :Figure 3 . 13 : 63 Figure 3 . 14 :

 31231363314 Figure 3.12: Selection path strategy impact on reliability

Conclusions 65 performance 68 Fault

 6568 degradation. In case of changing condition in network caused by fault, for example, the recongurable router can adapt the NoC by adjusting the packet size and packet rate, or change the type of its routing algorithm. $$ Impacts of NoC Design Parameters on Transmission Performance +D=FJAH "Fault tolerant routing algorithm for 2D and 3D mesh network As stated in chapter-1, deadlock packets will occurs when packet waits for resources that will never be released caused by the faulty link or node. Gradient and Diagonal algorithms handle the deadlock packet in the networks by choosing the direction which have more alternative path in avoiding the faults. Further, Gradient and Diagonal router implemented wormhole switching to have better latency and lower buer use due to the header its is forwarded without waiting next it arrives. This chapter presents adaptive fault-tolerant routing algorithms for 2D mesh called Gradient and 3D mesh called Diagonal. Both algorithms are designed to avoid multiple links and node failures that cause deadlock in mesh NoCs. The novel feature of these proposed algorithms is on how they classies the destination node and how they chooses the decision sequence of alternative path while avoiding the faults in both 2D and 3D NoCs. Both Gradient and Diagonal algorithm has been simulated in systemC based Noxim simulator and then compared with existing related routing algorithm. tolerant routing algorithm for 2D and 3D mesh network 4.1 Gradient: Fault-tolerant Routing Algorithm for 2D Mesh Topology Gradient considers sequences of alternative paths for packets when the main path fails. The proposed algorithm tolerates faults in worst condition trac in NoCs. The main dierence with existing 2D mesh routing algorithms relies to the fact that divide 2D coordinates into four destination zone based on vertical and horizontal lines, Gradient algorithm classify the destination address of packets in the network into eight zones based on a gradient line.

4. 1 . 1

 11 Gradient algorithmAn accurate selection of alternative routes can avoid a large number of hops for packet to reach destination. Therefore, the proposed routing algorithm has more alternative routes with minimum hops than other existing fault-tolerant adaptive routing algorithm. Thus, the method proposed is adaptive and fault-tolerant for 2D mesh topology. The algorithm classify the destination address of packets in the network into eight zones based on gradient line (M ) in 2D coordinate as presented in Figure 4.1. Gradient line (M ) is a number that represents the steepness of a straight line and is obtained from the value of destination address (Dx, Dy) and the current router address (Cx, Cy) as shown in equation 4.1 M = D y -C y D x -C x (4.1) We then use the gradient line |M | = 1 to divides the 2D coordinates of network into eight zones as shown in Figure 4.1. Based on this relative positioning the destination address is assigned to a zone to determine the next hop (i.e. the next router in the Gradient: Fault-tolerant Routing Algorithm for 2D Mesh Topology 69 path).For each zone of the destination node for the current packet, the Gradient algorithm denes one main route and three alternatives ones. The decision is then taken at runtime depending on network conditions. For example, for a destination in Zone-1 (Figure4.2-a), the main route is east (No.1) which provide the shortest path to the destination.The rst alternative route is north (No.2) which can also ensure a shortest path to destination and nally south (No.3), if there is no possible hop in the rst paths. The dierent possible decision depending on the zones is shown in Figure4.2.

Figure 4 . 1 :

 41 Figure 4.1: Gradient concept divide 2D coordinate into eight zones based on gradient line

Figure 4 . 2 :

 42 Figure 4.2: Sequence decision of Gradient algorithm for a destination in (a) Zone-1, (b) Zone-2, (c) Zone-3, (d) Zone-4, (e) Zone-5, (f) Zone-6, (g) Zone-7, (h) Zone-8

Figure 4 .

 4 Figure 4.3 shows that dividing the network in eight zones leads Gradient to choose shortest path than turn model and fully adaptive routing algorithms. In Figure 4.3-a,

Figure 4 .

 4 3-b. Here also demonstrate that in worst-case Gradient operate the same than its counterpart.The pseudo code of the proposed algorithm is shown in Figure4.4. According to the current position of the router and the address of the packet destination, it rst divides the zone of destination node into the eight zone based on Gradient line M . The M line is obtained by using equation 4.1. In the algorithm, abs.x is the absolute value of Dx -Cx and abs.y is the absolute value of Dy -Cy. The relation abs.y > abs.x is representative of |M | > 1 and abs.y < abs.x is representative of |M | < 1. Depending on the value of M and the relative position of the destination node, the algorithm then computes the next hop and propose a main route and two associated alternative paths.4.1.2 Evaluation of minimum hops and alternative path

Figure 4 . 3 :

 43 Figure 4.3: Alternative path of dierent routing algorithms in presence of faults in the network for dierent relative position of the destination node

Figure 4 . 4 :

 44 Figure 4.4: The abstraction of Gradient routing algorithm

Figure 4 . 5 : 77 Table 4 . 1 :

 457741 Figure 4.5: Twenty conditions of link-faults and node failures to evaluate the minimum hop and number of alternative path for seven dierent routing algorithms

  , mh : minimum hops, nap: number of alternative path 80 Fault tolerant routing algorithm for 2D and 3D mesh network The decision sequence of Diagonal is based on distances and directions estimation of destination node from the current node. It chooses the farthest destination for the main route or a second alternative and then chooses the shortest distance in opposite direction for third to fth alternative routes.

Table 4 . 3 :Figure 4 . 6 :

 4346 Figure 4.6: Addressing the position of node on 3D coordinate

4 . 3 Figure 4 . 9 :

 4349 Figure 4.9: Routing path comparison between Diagonal, AdaptiveXYZ and Elevator rst[START_REF] Dubois | Elevator-rst: A deadlock-free distributed routing algorithm for vertically partially connected 3dnocs[END_REF]

Gradient:Figure 5 . 1 :Figure 5 . 2 :Figure 5 . 3 :

 515253 Figure 5.1: Two scenarios used in simulation: (a) 6x6 mesh with 2-nodes failure in the center of network and (b) 6x6 mesh with 4-nodes failure on near border of network

  Average delay result in on increasing network size from 2x2 to 10x10 mesh

  Figure 5.4: (a ) Average delay and (b) average throughput on increasing number of nodes from 3x3 to 10x10 with packet injection rate 0,01 packets/cycle/IP

Figure 5 . 5 -Figure 5 . 5 :

 5555 Figure 5.5: Average delay comparison on (a) 4x4x4 mesh with packet injection rate 0,004 and (b) 4x4x4 mesh with PIR 0,0015

Figure 5 . 6 :

 56 Figure 5.6: Average delay comparison on increasing packet injection rate from 0,0005 to 0,0035 packets/cycle/IP for (a) 3x3x3, (b) 4x4x4, (c) 5x5x5, (d) 6x6x6 mesh

Figure 5 . 8 :

 58 Figure 5.8: Average latency comparison of 2D mesh routing algorithm on increasing packet rate and packet size

  as a consideration in designing an adaptive NoC. The combination of NoC parameters values has been used to dene network condition that represents minimum QoS of network. Then, adjusting the values of each parameter is used to see how big the impact of upgrading value on the performances. The Noxim systemC based simulator has been used to evaluate the impact of NoC designed parameter to the performance since it can model hardware characteristics. The results show that the accuracy of choosing and adjusting the network parameters can avoid performance degradation. These results can be used to design control mechanism in an adaptive NoC to avoid the degradation of QoS when trac condition change.

  zones, Gradient divide 2D coordinates into eight zones based on a gradient line. Gradient sequences choose the shortest alternative route to avoid a hot-spot area or a faulty element in the network. Thus, it avoids the degradation of network performances such as latency and throughput. In term of performances, the experimental results show that Gradient algorithm has lower latency and higher throughput than its counterpart.The sequences decision chosen in Diagonal routing is based on the combination of distances and directions of destination node from current node in 3D NoC. It has a main route and four alternative paths. For the main route until second alternative path, the algorithm choose the farthest distance in the same direction, while for the third until ve alternative, it choose the shortest distance in opposite direction. The experimental results show that Diagonal algorithm have smallest number of hops, more alternative possibilities paths to tolerate faults, lower latency and higher throughput than its counterpart.

122Figure A. 2 :Figure A. 4 :Figure A. 6 :Figure C. 3 :

 2463 Figure A.1: Decision path of XY routing algorithm in one fault condition between current and destination node

Figure 1 -

 1 Figure 1 -Classification des performances des NoC et impact des paramètres.

Figure 2 -

 2 Figure 2 -Gradient divise les coordonnées 2D en huit zones

  Afin d'évaluer Diagonal, nous avons modifié Noxim pour intégré les NoC mesh 3D et des noeuds fautifs. Nous avons alors dégradé l'état du réseau en augmentant le nombre de noeuds défectueux et le taux d'injection de paquets sur différentes taille de réseau. Dans un premier lieu, nous prenons un réseau de 3x3x3 avec un taux d'injection de 0004 (paquets/cycle) et deux noeuds défectueux. Nous augmentons ensuite le pourcentage de noeuds fautifs et nous évaluons la latence moyenne des paquets. Le résultat montre que l'algorithme de routage proposé a un délai moyen inférieur que les autres algorithmes de routage comme illustré sur la figure 3.a. Ce résultat reste vrai pour une taille de réseau plus grande, un taux d'injection de 0,0015 (paquets / cycle) et trois noeuds défectueux dans le réseau (Fig. 3.b) montre que l'algorithme proposé ont également délai moyen inférieur comme dans le scénario précédent.

Figure 3 -

 3 Figure 3 -Comparaison moyen de retard sur (a) mesh 3x3x3 avec un taux d'injection de paquets 0004 et (b) mesh 4x4x4 avec PIR 0,0015

  of all routing tables and can stall if the routing table xes (i.e. the table cannot be updated). Our fault tolerant routing algorithms are proposed to overcome the drawback on minimal adaptive and table-based routing algorithm.

. A table-based routing algorithm [21] that can support any NoC topology was also proposed to tolerate faulty links. The main drawback comes with the update

  The user can customize the Noxim router architecture such as number of port, buer size, routing algorithm and selection path strategy. In term of network parameters, Noxim provide some value of packet size and packet injection rate. Noxim

		NoCs prototyping	State of the art -Denitions	33
		transposed. Bit reversal trac distribution only sends the packet to destination address Table 2.2: Resources in Xilinx Virtex-5 (xc5vsx50t-1665) FPGA [77]
		whose is bit reversal of the sender's address. Resources of Virtex-5 Xilinx FPGA Total
		In evaluation of NoC performances, this simulator delivers the throughput, delay Number of Slice Registers 32640
		and power consumption in average and per-communication results. For example: the Number of Slice LUTs 32640
		total number of received packets/its, global average throughput, max/min global delay, Number of fully used LUT-FF pairs 11034
			Number of bonded IOBs	360
			Number of BUFG/BUFGCTRLs	32
	design into physical circuit level before the fabrication process as shown in the Figure
	2.13.
		2.7	NoCs prototyping
	2.7.2	Prototyping NoC into FPGA
		2.7.1	NoC design process

also provide some type of trac time distribution or trac pattern such as random, transpose1, transpose2, bit reversal, buttery and shue. Random trac distribution sends the packet to random destination, while transpose1 and transpose2 only send the packet to destination with address on the upper and lower halves of its own address total energy consumption and per-communications delay/throughput/energy. We have chosen Noxim simulator to evaluate the experimental results in our work due to its possibility to model a structural and physical design view of real NoC such as logic gates and RTL logic design.

The processes of NoC design are classied into three level of abstraction: high level design, RTL level design and logic gate level as described in Figure

2

.13. The NoC designer can preliminary design by model or specify the function of application requirement and the performance such as throughput or power consumption in high level design. In this level, they can specify the interfaces and behavior using high level tools such as C/C++, UML, Java or Matlab. A logic synthesis tool may convert high level design system model into a detailed behavioral and structural RTL.

A designer can also design his system in middle level design known as behavioral modeling. In this level design, a tool such as systemC provides the libraries or packages to model the behavior of each component or subsystem of the NoC. The result performances in middle level design are closer to the real implementation compared to high level.

The lowest level of designing NoC is in RTL level or in logic gate level. In this level, the representation of hardware circuit and the ow of digital signal between hardware register are described. The most common tools used in this level are Verilog and VHDL.

Finally, a place and route tools (i.e. cadance) are needed to synthesis logic gate level

Table 3 .

 3

	2: Impact of design parameters on performance of NoC
	NoC parameters	Impact on network performances Latency Throughput Reliability Power A.size R.use implementation cost
	Hardware micro
	Mapping method
	Topology
	N.resources
	Application type
	Task load
	Injection rate
	Transport protocol
	Packet size
	Routing
	Header size
	Flit size
	Buer size
	Flow control

Table 3 .

 3

	3: Parameter values for worst network condition for dierent size of network
	Parameter	3x3 mesh	4x4 mesh	5x5 mesh	6x6 mesh
	Number of hotspot node min. 1 node min. 2 nodes min. 3 nodes min. 4 nodes
	Failure node percentage	min. 0.5%	min. 0.5%	min. 0.5%	min. 0.5%
	Buer size	max. 1 it	max. 1 it	max. 1 it	max. 1 it
	Packet size	min. 6 its	min. 6 its	min. 6 its	min. 6 its

Table 3 .

 3

		4: Parameters range value used in scenarios to evaluate the saturation perfor-
	mance
		Parameter	Value
		Simulation time	10k -100k cycles
		Faulty percentage of node	0% -100%
		Packet injection rate (Packets/cycle) scale 0,02 -1
		Packet size	2 -14 its
		Buer size	1 -10 its
	Table 3.5: Parameters range value used in scenarios to evaluate the saturation perfor-
	mance
	No Scenarios
	1	Evaluate the network saturation on combination buer size with packet injection rate
	2	Evaluate the network saturation on combination packet injection rate with packet size
	3	Evaluate the network saturation on combination buer size with packet size
	4	Evaluate the network saturation on combination faulty percentage with packet size
	The results of the experiments are shown in Figure 3.2 while the summaries are
	presented in

Table 3

 3

.6. The result of the rst scenario (Figure

3

.2a) shows that however we upgrade the parameters value, the throughput is saturated or reach maximum value (0.22 its/cycle). The saturation point starts after packet injection rate bigger than 0.04 packets/cycle.

Table 3 .

 3 10: Summarize the most inuence parameter to NoC performances

	Performance	Injection rate Packet size Buer size Number of resources
	Latency	1st	2nd	4rd	3rd
	Throughput	2nd	1st	3rd	4rd
	Reliability	2nd	1st	3rd	-
	Power consumption	2nd	3rd	4rd	1st

Table 4 .

 4

	2: Comparison of number of minimum hops for the three adaptive routing
	algorithms and optimal calculation by hand
		Fully	Fault	Gradient Optimum
	Scenario	adaptive	Tolerant			calculated
			[51]	[11]			by hand
		mh	nap	mh	nap	mh	nap	mh	nap

Table 4 .

 4

	4: Number of minimum hops comparison of three adaptive routing algorithms
	scenario Source to	DyXYZ	Elevator	Diagonal
		destination	[17]	rst [16]
	1	000 to 112	6	6	4
	2	202 to 110	6	6	4
	3	220 to 001 deadlock	6	5
	4	200 to 022	8	8	6

Table 5 . 1 :

 51 Parameter use in simulation to evaluate Diagonal routing algorithm

		Parameter	Value
		Trac pattern	Random
		Buer size	4 its
		Packet size	2 -10 its
		Simulation time 10.000 cycles
		Warm-up time 1.000 cycles
	5.2	Diagonal: Fault tolerant routing algorithm

Table 5 .

 5

		6: FPGA resources need for implementing credit based ow control with 2
	virtual channel and round robin scheduling
	Routing	Slice Register Slice LUTs LUT Flip-Flop pairs BUFG/BUFGCTRLs
	XY	25%	89%	25%	5%
	Turn model	25%	89%	25%	5%
	Gradient	25%	89%	25%	5%
	Table 5.7: FPGA resources need for implementing Credit Based ow control with 2
	virtual channel and priority scheduling
	Routing	Slice Register Slice LUTs LUT Flip-Flop pairs BUFG/BUFGCTRLs
	XY	13%	47%	25%	5%
	Turn model	25%	93%	25%	5%
	Gradient	25%	93%	25%	5%
	5.3.2	Gradient performances in RTL level

Table 1 -

 1 Ressources FPGA nécessaires pour mettre en oeuvre le contrôle de flux handshaking sans canal virtuel ni ordonnancement

	Routing	Slice Register Slice LUT LUT Flip-Flop BUFG / BUFGCTRLs
	XY	0,11	0,52	0,21	0,06
	Turn Model	0,11	0,53	0,21	0,06
	Gradient	0,11	0,53	0,21	0,06
	4.2 Algorithme de routage pour réseau mesh 3D
	4.2.1 Algorithme

Fault tolerant routing algorithm for 2D and 3D mesh network

Decision path comparison of 3D mesh topology for 4 fault scenarios Figure C.4: The comparison of decision path of AdaptiveXYZ, Elevator rst and Diagonal routing algorithm for fault scenario-4

Etat de l'ArtL'idée d'une infrastructure de communication de type NoC est de séparer les problèmes d'infrastructure de communication de l'application. Ainsi, un réseau peut être évolutif et configurable. Grâce à cette infrastructure de communication, une ressource matérielle peut se connecter en envoyant des messages à d'autres ressources dans le réseau. Une infrastructure générique de NoC est la combinaison de divers éléments matériels (éléments de traitement, commutateurs, liens) et de protocoles de communication (routage, commutation) qui déterminent l'architecture de communication.L'algorithme de routage décide du chemin sur lequel les données doivent être transmises. Les algorithmes de routage peuvent être classer comme étant déterministe, semi-adaptatif (oblivious) ou adaptatif. Dans un routage déterministe, tout paquet prends le même chemin à partir d'un noeud source vers un noeud destination. Dans le routage semi-adatatif, la décision du chemin de routage est prise localement en fonction de sans prendre en compte l'état du réseau. Le routage adaptatif prends en plus l'état du réseau en compte afin d'éviter des zones encombrées (hot-spots) ou fautives.La plupart des algorithmes de routage sont basés sur la technique de commutation "whormhole" en raison de sa simplicité.La performance d'un algorithme de routage dépend principalement de deux facteurs : i) le nombre de hop entre deux noeuds et ii) la distribution des chemins. Sur la base du nombre de sauts requis (hop-count) les algorithmes de routage peuvent être classés en routage minimal et non-minimal. Un algorithme de routage minimal attribue des chemins minimaux entre des paires source-destination, tandis que l'algorithme de routage non minimal permet de prendre des chemins non-minimaux.L'adaptativité permet d'alterner des chemins entre la même paire de noeuds source et de

$ Personal Publication

head of the Lab Prof. Oliver Sentieys for his kind attitude, generous help and precious suggestions during my PhD thesis. , Dominique HOUZET, Christophe MOY and Achmad AFFANDI who evaluated this work. I wish to thank all the members of the IRISA/CAIRN Lab who make my stay a memorial period. It is a great pride for me completing the PhD thesis in this dynamic Lab.

I am extremely grateful to the Directorate General for Higher Education (DGHE),

Ministry of National Education, The Republic of Indonesia for their nancial support of this thesis. Finally, I would like to thank my wife, my daughters and my parents for their never ending support and encouragement, that has help me to stay concentrated on my thesis.

Impacts of NoC Design Parameters on Transmission Performance

the performance upgrade. We found that, to upgrade the performances of latency, the value of injection rate, packet size and number of resources must be decrease while the value of buer size must be increase as stated in Table 3.8. To upgrade the throughput performances, all evaluated parameters (i.e. injection rate, packet size, buer size and number of resources) must be increase. In vice versa, to decrease the power consumption, all evaluated parameters must be decrease (Table 3.8). For reliability performances, the injection rate and buer size value must be increase while packet size and buer size must be decrease.

In worst condition, the decreasing packet size can increase the performances which are decrease the latency then degrade the throughput. While increasing packet injection rate in overload network condition will degrade the latency hence degrade the performance.

The result in Figure 3.3 shows that decreasing packet injection rate and decreasing packet size give more impact on reducing the latency compared with increasing buer size and decreasing number of resources. Thus, adjusting the packet injection rate is considered as the best decision to adapt the worst condition of network caused by latency degradation.

Fault tolerant routing algorithm for 2D and 3D mesh network The proposed algorithm considers the distances and the directions of destination nodes based on the current node position. Figure 4.6 shows how we dene the distances and the directions of destination-1 (D1) and destination-2 (D2) based on current address (C).

The distances are obtained from the ratio between absolutes value of △X, △Y and △Z.

Based on these distances, Diagonal choose the farthest distance as the rst alternative and shortest distance as the last alternative. While the directions are obtained from the value of △X, △Y and △Z. As an example, if the value of △X, △Y and △Z are positive, the algorithm will chooses X+, Y+, Z+ and vice versa. There are six possibilities to combine the distances of |△X|, |△Y|, |△Z| and eight possibilities to combine the direction of X(+/-), Y(+/-) and Z(+/-) as shown on Table 4.3. We then combine the possibilities of distances and directions into a total of 48 possibilities as shown in Appendix A.

The algorithm chooses the farthest distance for the main route, the second farthest distance for the alternative-1 and third farthest for the alternative-2. In case of a fault on main route, the packet then chooses alternative-1. If the route of alternative-1 also fails, the packet then chooses alternative-2. The novel feature of this algorithm is on how the algorithm chooses the route for alternative-3. When the alternative-2 fails, the algorithm chooses the shortest distance with opposite direction for the alternative-3 as shown in Appendix A. Based on the dened zones, the algorithm has dierent decision sequence of main route and alternatives routes. The goal of this method is to have minimum hops and more alternative route for the packet to reach the destination node.

For example, if the distance of destination-X from current-X (|△X|) is farther than |△Y | and |△Y | is farther than |△Z|, the algorithm will chooses X as the main route, Y as the rst alternative, Z as the second alternative, -Z as the third alternative, -Y as the fourth alternative and nally -X as the fth alternative route.

Fault tolerant routing algorithm for 2D and 3D mesh network The proposed routing algorithm contributes to avoid the degradation performance of 3D mesh topology by tolerating link-fault and hotspot area. We have simulated the proposed algorithm using Noxim to evaluate the performance and compared it with adaptiveXYZ and elevator rst routing algorithms.

Evaluation of minimum hops

This subsection presents the evaluation of number of hops for each routing algorithm.

We have evaluated three dierent routing algorithms, namely adaptive-XYZ, Elevator rst [START_REF] Dubois | Elevator-rst: A deadlock-free distributed routing algorithm for vertically partially connected 3dnocs[END_REF] and Diagonal algorithm in 3x3x3 mesh topology. These algorithms were evaluated under four dierent scenarios described in Figure 4.9. These scenarios are designed to evaluate the number of hops of each routing algorithm regarding dierent faulty condition. On the rst scenario, we want to evaluate the number of hops for destination node in east-north-up direction of current node with dierent distances. Second scenario for direction west-north-down, third scenario for west-south-up and fourth scenario for west-north-up.

In scenario-1 as shows in +D=FJAH #

Experimental Results

The concept of Gradient and Diagonal routing algorithm has been presented in the previous chapter. The manual evaluation of number of hops and number of alternative path has also been presented. In this chapter, the methodology and the scenario used in simulation are also dened. The performances based simulation result of Gradient and Diagonal routing algorithm is presented. Hence, the implementation of Gradient routing algorithm into an FPGA is presented.

Gradient: Fault tolerant routing algorithm

As seen in chapter 2, latency and throughput are the most important network metrics to qualify a NoCs. We design three scenarios to evaluate our proposed fault-tolerant routing algorithms. For the rst scenario, we evaluated Gradient performance using dierent faulty position in the network. The objective is to prove that Gradient has minimum hops in avoiding the faulty. Then, in second scenario, we increase the faulty node to see how big the impact on the performance of each routing algorithm. Finally, we evaluate Gradient algorithm in higher scalability of network by adjust the scalability of network.

Experimental Results

Implementation on FPGA

The implementation of NoC depends on the complexity of routing algorithms, and aects the amount of hardware for the router and/or network interface. In this section we present an evaluation of the implementation of Gradient routing algorithm into a virtex-5 (xc5vsx50t-1665) FPGA. Further, we evaluate the impact of frequency to the performance of Gradient. The synthesis result were obtained using ISE 12.4 [77] tools while the metric performances are evaluated using Modelsim 6.4 [START_REF]Mentor graphics[END_REF].

Synthesis result

We implemented Gradient routing algorithm as a new switch control in HERMES NoC router [1] as shown in Figure 5. We used two metrics in order to evaluate the resources usage and the metric performances: latency and throughput. For the rst experiment, we dene the type of ow control, number of virtual channel and scheduling schemes to evaluate how big is the impact of the dierent routing algorithms schemes: XY, turn model and Gradient to the utilization of resources in targeted FPGA. We then dene four scenarios as representative of dierent combination schemes as shows in Table 5.3. To obtain the synthesis result, we then implement each scenario into Virtex-5 FPGA. The synthesis results of scenario-1 are shown in Table 5.4, scenario-2 in Table 5.5, scenario-3 in Table 5.6 and scenario-4 in Table 5.7. The synthesis results shows that XY routing algorithm use less resources of slice LUTs for scenario-1, scenario-3 and scenario-4 and also use less slice registers for scenario-4. However XY use less resource in FPGA than its counterpart but XY algorithm is not an adaptive routing. In general, all routing algorithm use almost the same resources in the targeted FPGA. Thus, Gradient

Experimental Results

algorithm is better due to it has best network performance compared to its counterpart. Experimental Results

(i.e. odd-even and fully-adaptive routing algorithm) since we implemented Gradient to

Hermes NoC [1] router. Hermes NoC router only provides XY, west-rst, negative-rst and north-last routing algorithm but not on other adaptive routing algorithm.

In this scenario, the network parameters such as frequency, target node, numbers of packet, packet size, trac distribution, packet rate and simulation time are dened as shown in Table 5.8. Further, we adjust the packet rate and the packet size value (Table 5.8) to evaluate the output latency and throughput.

, south (4), north-west (5,6,13,[START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF], north-east (7,8,[START_REF] Daneshtalab | A systematic reordering mechanism for on-chip networks using ecient congestion-aware method[END_REF][START_REF] Dubois | Elevator-rst: A deadlock-free distributed routing algorithm for vertically partially connected 3dnocs[END_REF], south-west (9,10,[START_REF] Ebrahimi | Dyxyz: Fully adaptive routing algorithm for 3d nocs[END_REF][START_REF] Elhajji | Feronoc: Flexible and extensible router implementation for diagonal mesh topology[END_REF] and south-east (11,12,[START_REF] Fazzino | Noxim: Network-on-chip simulator[END_REF][START_REF] Feero | Networks-on-chip in a three-dimensional environment: A performance evaluation[END_REF] from current node.

Path line of routing algorithm in 20 case scenario