# Introduction ulti Processor-SoC (MPSoC) and Chip-Multi Processors (CMP) achieve high performance with interconnection networks that give lowlatency, high-bandwidth inter-processor communication [7]. Most of these multi-core system use regular topologies (such as torus, hypercube and mesh) to link their switch components. For packet transmission, many routing schemes have been design to provide an efficient and deadlock free path [1,2,4,5,8,10]. Routing algorithm (RA) decides the path for the packet from source to destination. Two type of RA i.e. distributed and source routing are used for regular and irregular NoC networks [8]. Source routing compute the whole routing path at the source and computed path stored in the packet header, while in distributed routing each router receives a packet; all computations are performed at the switch level, without storing whole path in packet header and decides the output direction to send it. In recent years, several routing schemes have been proposed for application specific networks (i.e. Irregular networks) [6,9,11,12,13,14,15,16]. schemes are able to route packets in different network topologies and achieves livelock and deadlock freedom. To deal with irregular topologies, table based appro-aches were proposed. In this scenario, at each switch that stores a table, for each end-node, the output port that must be used. Using this approach higher adaptivity is achieved and several outputs are stored in each table. The main benefit of this type of routing is that any topology and any routing algorithm can be used; it also supports fault-tolerant routing algorithms. With such routing approaches, the size of routing table increases proportionally with the size of the network at each switch. Hence, the implementation becomes comparatively complex for the communication switch. In this paper a efficient routing algorithm is proposed for irregular networks. The aim is to develop a distributed routing on every switch and remove the tables, the routing decision is made quickly and low latency for packets sending from source to destination. The wormhole switching technique is used in our interconnection networks. The routing algorithm is based on combination of up*/down* and LBDR, and hence called LBDR Up*/Down* (LBDR-UD). [12] up*/down* routing is distributive table-based routing algorithm used in the irregular network and [7] LBDR is a table-less routing implementation technique for regular and irregular networks (generated from the mesh). # II. # Lbdr-ud Routing for Irregular Networks We start the description with the basic mechanism required at every switch to deal with the irregular networks. # a) Methodology In order to enable an efficient routing implementation for irregular networks using minimum logic, an example network for irregular Network-on-Chip with core and channels are placed according to the application condition as shown in Fig. 1. The proposed methodology is based on two assumptions: i. The interconnection network between switches can be modeled by a multigraph G (N, C), where N is the group of switches and C is the group of bidirectional links between the switches. These ii. For each irregular networks, applied routing algorithm must follow some restrictions. These restrictions are as follows: a. Deadlock-freedom The routing algorithm must guarantee that the transmitted messages are received at destination and prevent the deadlock scenarios. b. Connectivity It is essential that the routing algorithm should be capable to offer at least one route between two end nodes. Routing is based on a direction assignment to the operational links, including the ones that do not belong to the tree. In particular, the "up" direction of each link is defined as: 1) A link leading to a parent node in the spanning tree; 2) A link leading to a lower ID, if both are at the same tree level. The "down" direction is along the reverse direction of the "up" direction as shown in Fig. 2. The routing restrictions for the LBDR-UD routing algorithm are shown in Fig. 2. A routing restriction is defined between two successive channels. The LBDR-UD algorithm prohibits messages from taking "downup" transitions. The transitions are allowed in opposite direction by algorithm, thus routing restrictions does not exist for "up" link to "up" and "down" links. Similarly, no routing restrictions are applicable from "down" link to "down" link transitions. # b) Configuration bits Configuration bits are in two sets: connectivity bits and routing bits. Routing bits specify which routing options can be used, whereas connectivity bits specify connectivity with neighbors. # R UU and R UD These bits indicate that the message can take the "up" direction from the current router and from the next router the message can be transmitted in the "up" direction or the "down" direction respectively. # R DD and R DU These bits indicate that the messages can take the "down" direction from the current router and from the next router the message can be transmitted in the "down" direction or the "up" direction respectively. Note that the routing restrictions and routing bits are the opposite to each other. Fig 3(a) shows the restricted turns and allowed turns a message could take according to router 10 and its routing bits. Specifically, bit RUD at router 10 is 1(Set) and shows that a message is routed to the "up" direction first and then to the "down" direction from the next router. Routing decision is taken again at the next corresponding router. Table 1 shows the bits computed for an irregular network using the LBDR-UD routing algorithm (connectivity bits can be seen in Fig. 3(b)). As shown in the figure, bit R DU is set to zero, representing the "down" to "up" routing restrictions which "LBDR-UD" imposes. Bits R UU and R DD are all set except for those cases where the message would be routed out of the network (at the root router and leaf router). R UD is set ("up" to "down" transitions are allowed) except for those cases where the message would be routed out of the network. Finally, based on neighboring routers, connectivity bits are set. Fig. 4 shows the algorithm in pseudo-code for the computation of configuration bits. Function check link shows that whether a link between current router and neighboring router exist or not. Based on the type of restriction the routing bit is set on behalf of its immediate neighbor router. In the LBDR-UD routing only single turn (RDU) is restricted and rest three turns (RUU, RDD and RUD) are allowed. The propose algorithm is flexible, simple and compact routing mechanism for unicast communication that eliminates the requirement for routing tables at every router. The routing logic is separated in two stages. The first stage computes the location of the relative destination router. A general representation of LBDR-UD routing is shown in Fig. 5 and Fig. 6 Initially a comparator module is used, which generates two control signals using three comparators. First comparator (CMP) is used to compare the current_id_level and Dest_id_level, and if the levels are equal then it compares using the Direct Connection CMP otherwise the Ancestor CMP is used. These signals, U1 and D1 indicate the relative direction of the destination in "up" direction and "down" direction respectively. For example, in Fig. 2, if the current router is 7 and our destination is router 6, signal U1 would be set, because it is situated at the lower level in comparison with the current router. With the help of these connectivity (C U ) bits, routing (R UD ) bits and control signals, the LBDR-UD routing generates a set of routing Table 1 : Connectivity bits for an irregular network, Routers are numbered row-wise. (See Fig. 3(b)) The second stage requires two or more logic units and each logic unit will correspond to one output port. Each output port can be implemented with only one inverters, one OR gate and three AND gates. We describe here the logic associated with the up and down output direction, as shown in figure 3.19. Router C 0 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 1 0 1 0 3 1 0 0 0 0 1 0 0 0 0 1 4 0 0 0 0 0 1 0 1 1 0 0 5 0 0 1 1 1 0 1 0 0 1 0 6 1 0 0 0 0 1 0 1 0 0 0 7 0 0 0 0 1 0 1 0 0 0 1 8 0 0 0 0 1 0 0 0 0 1 1 9 0 1 0 0 0 1 0 0 1 0 0 10 0 1 1 1 0 0 0 1 1 0 0 When any of the falling out three conditions is fulfilled, then the incoming packet is headed in "up" output direction for routing. The "up" direction is not considered for routing the packet when none of the following conditions are fulfilled (additionally, the connectivity bit CU is examine in order to filter the up direction). ? The destination is directly connected with destination 1 1 D U × ? The destination is the ancestor of source router and the message can take the up direction at the lower level router through the up direction output port UU R U × 1 . # Results and Analysis In the following, we provide performance evaluation of LBDR-UD and TABLE based (up*/down*) with different network size. Average memory, latency and throughput are calculated on 10 different scenario of each network size (Total 60 scenarios). # a) Effect of Network Size on Memory Distributed Table based routing schemes have also been proposed to deal with irregular topologies and can be used in application-specific systems which facilitates the use of any topology with any routing algorithm. On small systems the hardware cost and power consumption related to the memories used to build routing tables is affordable, but as more and more cores are integrated on the chip, causing the system # Conclusion It is extension of up*/down* routing in irregular networks using LBDR. LBDR-UD minimizes the memory space of the table based routing (up*/down*) in the NoC for irregular networks. On the behalf of simulation evaluation LBDR-UD save the average 64.59% tables and also efficient in terms of network average latency/flit and throughput/packet as compare to TABLE based (up*/down*) routing. In application specific topologies (Irregular networks) LBDR also used for 3D irregular networks and this research will be extended by designing the efficient router architecture for NoC. Year 2014 ![](image-2.png "M") 1![Figure 1 : An example of custom NoC with irregular topology (a) irregular networks (b) corresponding topology graph](image-3.png "Figure 1 :") 2![Figure 2 : Routing restrictions based on LBDR-UD algorithm](image-4.png "Figure 2 :") ![Efficient Routing Implementation for Irregular Networks Global Journal of Computer Science and Technology Volume XIV Issue V Version I](image-5.png "An") 3![Figure 3 : Configuration bits at router 7. LBDR-UD algorithm used A Cy bit defines the connectivity bits for the y th output port. For example, at router 10 if the C 1 bit is set, it implies that there is a neighbor router connected with 1. Fig 3(b) shows all connectivity bits for router 10.Table1shows the bits computed for an irregular network using the LBDR-UD routing algorithm (connectivity bits can be seen in Fig.3(b)). As shown in the figure, bit R DU is set to zero, representing the "down" to "up" routing restrictions which "LBDR-UD" imposes. Bits R UU and R DD are all set except for those cases where the message would be routed out of the network (at the root router and leaf router). R UD is set ("up" to "down" transitions are allowed) except for those cases where the message would be routed out of the network.](image-6.png "Figure 3 :") 4![Figure 4 : Pseudo-code for the computation of configuration bits](image-7.png "Figure 4 :") ![Efficient Routing Implementation for Irregular Networks Global Journal of Computer Science and Technology Volume XIV Issue V Version I Journals Inc. (US)](image-8.png "An") 5![Figure 5 : Comparator module used in the first stage decisions at the next stage. The second stage requires two or more logic units and each logic unit will correspond to one output port. Each output port can be implemented with only one inverters, one OR gate and three AND gates. We describe here the logic associated with the up and down output direction, as shown in figure 3.19.When any of the falling out three conditions is fulfilled, then the incoming packet is headed in "up" output direction for routing. The "up" direction is not considered for routing the packet when none of the following conditions are fulfilled (additionally, the connectivity bit CU is examine in order to filter the up direction).](image-9.png "Figure 5 :") 61![Figure 6 : LBDR-UD implementation, using logic gates. ? The destination is a descendant of source router and the transmitted message can be headed to the up direction at the upper level router via the down direction output port DU R U × 1 . As stated above, this logic provides support for nonminimal and minimal paths of the network, and produces a signal for each output port. When U1 and D1 signals are reset, then the C (Core) signal is set and the message is received at the final destination router. III.](image-10.png "Figure 6 :× 1 .") 7![Figure 7 : Average Memory comparative result between LBDR-3D and Table based (up*/down*) routing with different network size b) Effect of Network Size on Latency Increase the network size also increases the packet transmission delay. Fig. 8 shows the average per flit latency of different network sizes. LBDR-UD performs the bit logic computation for route the message (packets). LBDR-UD and TABLE based (up*/down*) routing generate the approximately same average latency with respect to different network size but compare to Table based, LBDR-UD slight less as shown in fig. 8 Searching time for the corresponding entry in the routing table per router reduces for the LBDR-UD.c) Effect of Network Size on ThroughputFig.9shows the Average Throughput/packet with different network size. LBDR-UD same throughput as compare to TABLE based (up*/down*) routing.](image-11.png "Figure 7 :") 8![Figure 8 : Average Latency/flit comparative result between LBDR-3D and Table based (up*/down*) routing with different network size](image-12.png "Figure 8 :") © 2014 Global Journals Inc. (US) ## Global Journals Inc. (US) Guidelines Handbook 2014 www.GlobalJournals.org * A Comparison of Adaptive Wormhole Routing Algorithms RVBoppana SChalasani Proceeding Intel Symposium on Computer Architecture eeding Intel Symposium on Computer Architecture 1993 * Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors AChien JHKim Journal of ACM 1995 * Principles of on-chip Interconnection Networks NChoudhary 2013 Himanshu Publication * Deadlock-Free Message Routing in Multiprocessor Interconnection Networks WJDally CLSeitz IEEE Trans. on Computers 36 5 1987 * A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks JDuato IEEE Trans. On Parallel and Distributed Systems 4 12 1993 * Logic based distributed routing for NOCs JFlich JDuato IEEE computer architecture letters 7 1 2008 * The Turn Model for Adaptive Routing CJGlass LMNi Proceeding Intel. Symposium on Computer Architecture eeding Intel. Symposium on Computer Architecture 1992 * L-turn routing: an adaptive routing in irregular networks AJouraku AFunahashi HAmano MKoibuchi International Conference on Parallel Processing 2001 * LMNi PKMckinley A Survey of Wormhole Routing Techniques in Direct IEEE on Computers 1993 26 * A new methodology to compute deadlock free routing tables for irregular networks JCSancho ARobles JDuato Proceedings of the CANPC the CANPC 2001 * Autonet: A highspeed self-configuring local area network using point-to-point links MDSchroeder ADBirrell MBurrows HMurray RMNeedham TLRodeheffer EHSatterthwaite CPThacker Journal on Selected Areas in Communications 9 1991 * High-performance routing in networks of workstations with irregular topology FSilla Duato IEEE Transactions on Parallel and Distributed Systems 11 2000 * Efficient adaptive routing in networks of workstations with irregular topology FSilla MPMalumbres ARobles PLopez JDuato Proceedings of the Workshop on Communications and Architectural Support for Network-Based Parallel Computing the Workshop on Communications and Architectural Support for Network-Based Parallel Computing 1997 * An efficient deadlock-free tree-based routing algorithm for irregular wormhole-routed networks based on turn model YMSun CHYang YChung TYHang International Conference on Parallel Processing 2004 1 * Deadlock-free routing in irregular networks using prefix routing JWu LSheng DIMACS Tech. Rep 1999