# INTRODUCTION layered architecture called Network on Chip(NoC) [1] has been proposed for global communication in complex SoCs to meet the performance requirements. In NoC each core is connected to switch by a network interface.Cores communication with each other by sending packets via a path consisting of a series of switches and inter switch links. Fig. 1 shows an abstract view of a NOC in this architecture. As shown, each tile is composed of a resource(R) and a switch or router(S). The router is connected to the four neighboring tiles and its local resource via channels. Each channel consists of two directional point-to-point links between two routers or arouter and a local resource [2,3]. The problem of defining communication protocols for these NoCs is not an easy matter since the resources used in traditional networks are not available on-chip. The communication in NoCs takes place via data packets, which are delivered between the communicating components. The paths the packets are routed through the network are determined by the routing algorithm. Communication and performance of the entire system are significantly affected by the routing algorithm [4].The performance of NoC largely depends on the underlying Author ? : Islamic Azad University, Dezful Branch, Dezful, Iran. Email : mehranzadeh@iaud.ac.ir Author ? : Islamic Azad University, Dezful Branch, Dezful, Iran. Email : hoodgar@iaud.ac.ir routing technique, which chooses a path for a packet and decides the routing behavior of the switches. Routing algorithms can be generally classified into two types: deterministic and adaptive. In deterministic routing, the path is completely determined by the source and the destination address. On the other hand, a routing technique is called adaptive if, given a source and a destination address; the path taken by a particular packet depends on dynamic network conditions (e.g. congested links due to traffic variability). One main advantage of using deterministic routing is its simplicity in terms of routers design. Because of the simplified logic, the deterministic routing provides low routing latency. In this paper we present and evaluate a Fault aware routing scheme called FAXY which a packet first traverses along x dimension and then along the y dimension. The proposed routing algorithm is able to route packet even in the case of faulty links or switches in the NoC. Simulation results demonstrate the advantage of FAXY in terms of average packet latency, packet loss rate compared with XY routing algorithm in the presence of permanent faults. FAXY can get much less average packet latency and lead to less than average 15% packet loss rate. # II. # RELATED WORK The idea of NoC is derived from large-scale computer networks and distributed computing. NoC should be reasonably simple [5]. Several previous works have investigated different routing algorithms that are tolerant to permanent and/or temporary errors. In order to ensure successful message transmission through the network, several copies of the same packet may be sent on the network links [7].Similarly, probabilistic flooding algorithms can be employed to flood packets to the entire network, which will finally reach to the destination [8].These techniques increase network load and may create congestion when the network is heavily loaded. Different deterministic routing algorithms have been proposed to detour the faulty link(s) in the case of permanent faults [9]. Recently, a fault tolerant algorithm was proposed to avoid routing on the faulty links [10]. In this paper, we present a fault-aware dynamic routing algorithm for NoC applications. Our algorithm has the ability to locate the faulty links to avoid them in order to increase the overall network throughput and prevent packet losses. # III. # PROPOSED ROUTING ALGORITHM In proposed routing algorithm, a new faultaware routing algorithm based on XY routing, namely fault-aware XY (FAXY), is used as a representative of deterministic routing scheme because of its simplicity and wide popularity. Obviously, XY routing is a minimal path routing algorithm and is free of deadlock and live lock [11]. As shown in Fig. 3, With FAXY routing, a packet first traverses along X dimension and then along the Y dimension. When a packet traverses along the X dimension and a link is masked because permanent fault, its traverses along Y dimension in order to increase the overall network throughput and prevent packet losses. The mask is used in order to increase the overall network throughput and prevent packet losses.Our algorithm incorporates the acknowledgment signal to reroute the packets around faulty links [12]. Fig. 2 : Pseudo code of FA-XY routing algorithm IV. # EXPERIMENTAL RESULTS In order to evaluate the FAXY routing algorithm, we developed a Java based simulator, namely gpNoCsim [13]. We simulate several square mesh networks with XY and FAXY routing algorithms. The efficiency of each type of routing is evaluated through latency, throughput and average packet loss percent curves. Each simulation is run for a warm-up period of 10000 cycles. Thereafter, performance data are collected after 100,000 packets are sent. The network size during simulation is fixed to be 6* 6 tiles. All of the input ports have a FIFO size of 5 flits. Fig. 3 shows the network throughput and Fig. 4 shows switch throughput, respectively. As shown in Fig. 3 and Fig. 4, FAXY routing performs better than XY routing algorithm under different fault percent schemes. The fault percent is the number of faulty switches of network that has one link with permanent fault. The packet injection rate (i.e., the number of packets injected to the network per cycle) is fixed to 150 (packets/cycle). As in previous work [3,6], the performance of the routing scheme is evaluated through latencythroughput curves. For a given packet injection rate, a simulation is conducted to evaluate the average packet latency. It is assumed that the packet latency is the duration from the time when the first flit is created at the source core, to the time when the last flit is delivered to the destination core. For each simulation, the packet latencies are averaged over 50,000 packets. Latencies are not collected for the first 5,000 cycles to allow the network to stabilize. It is assumed that the packets have a fixed length of 5 flits and the buffer size of input channels is 5 flits. As shown in Fig. 5, FAXY routing performs better than XY routing algorithm. FAXY routing algorithm is able to achieve a lower packet latency rate than XY for the same traffic pattern and the injection rate (10%). Fig. 5 : Average packet latency for XY and FAXY routing algorithms Fig. 6, show the average packet loss rate. As shown in Fig. 6, FAXY can achieve average 15% less packet loss rate. Similar to other work in the literature, we assume that the packet loss rate is percent of the packet is created and do not received in the destination node. # CONCLUSION In this paper, we presented a new approach for fault aware routing algorithms on NoC, namely FAXY routing. We investigated the effect of permanent errors, and packet injection rates on the performance of our algorithm.Simulation results demonstrated the advantage of our routing algorithm in terms of packet loss percent and latency compared to XY routing algorithms in the presence of permanent faults. Our algorithm can achieve average 10% less latency and average 15% less packet loss rate. 20111![Fig.1: The typical structure of a 4*4 NoC](image-2.png "A © 2011 Fig. 1 :") 34![Fig.3 : Network throughput for XY and FAXY routing algorithms](image-3.png "Fig. 3 :Fig. 4 :") 6![Fig.6 : Average packet loss rate for XY and FAXY routing algorithms](image-4.png "Fig. 6 :") © 2011 Global Journals Inc. (US) © 2011 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XI Issue XVII Version I October © 2011 Global Journals Inc. (US) FAXY: Fault Aware Routing Algorithm Based On XY Algorithm for Network on Chip * Networks on chips: a new SOC paradigm LBenini GDMicheli IEEE computer 35 Jan 2002 * On-chip networks: A scalable, communication-centric embedded system design paradigm JHenkel WWolf SChakradhar Vlsi Design 2004 India * DyAD -Smart routing for networks-on-chip JHu RMarculescu DAC 2004 * Fully Adaptive Fault-Tolerant Routing Algorithm for Network-on-chip Architectures TSchonwald JZimmermann OBringmann 10 * Methods and Tools DSD 2007 * Packetization and routing analysis of on-chip multiprocessor networks TTYe LBenini GDe Micheli Journal of Systems Architecture 50 2004 * The odd-even turn model for adaptive routing GMChiu IEEE Transactions on Parallel and Distributed Systems 11 2000 * Fault and energyaware communication mapping with guaranteed latency for applications implemented on noc SManolache PEles ZPeng Proceedings of IEEE/ACM Design Automation Conference, DAC IEEE/ACM Design Automation Conference, DAC 2005 * Fault tolerant algorithms for network-on-chip interconnect MPirretti GLink RBrooks NVijaykrishnan MKandemir MIrwin Proceedings of IEEE Computer society Annual Symposium on VLSI IEEE Computer society Annual Symposium on VLSI 2004 * Implications of rent's rule for noc design and its fault-tolerance DGreenfield ABanerjee J.-GLee SMoore Proceedings of International Symposium on Networks-on-Chip International Symposium on Networks-on-Chip 2007 * A fault tolerant mechanism for handling permanent and transient failures in a network on chip MAli MWelzl SHessler Proceedings of International Conference on Information Technology, ITNG International Conference on Information Technology, ITNG 2007 * A survey of wormhole routing techniques in direct networks LMNi PKMckinley IEEE Int, Conference on Computer 26 Feb. 1993 * A Fault-Aware Dynamic Routing Algorithm for on-Chip-Networks AHosseini TRagheb YMassoud 2008 IEEE * GPNocSim-A General Purpose Simulator for Network-onchip HHossain MAhmed AAl-Nayeem 2007 Dhaka, Bangladesh * Global Journal of Computer Science and Technology Volume XI Issue XVII Version I 62