Implementation and Comparison of XY & Improved XY Algorithms for on Chip Routing in Diametrical 2D Mesh NOC

Implementation and Comparison of XY & Improved XY Algorithms for on Chip Routing in Diametrical 2D Mesh NOC

Mallikarjun Gachchannavar

Department of Electronics & Communication Engineering, SDM College of Engineering and Technology,

Dharwad, India

Dr. S. S. Kerur

Assistant Professor

Department of Electronics & Communication Engineering, SDM College of Engineering and Technology

Dharwad, India

Abstract – The design of integrated circuits will change a lot because of shorter time-to-market it is impossible to design all functional blocks from scratch. One proposed solution to this problem is to use Network-On-Chip (NOC) architectures,[18] which are built up from reusable interconnect IP blocks. In NOC 2D mesh is popular due to its simple implementation and scalability of simple XY routing, but due to long network diameter and extra hops makes it energy inefficient as the network grows on the other part Extended diametrical 2D mesh architecture reduces the network diameter up to 50 percent compared to 2D mesh at the cost of few extra links added to the architecture. Router is the main building block in NOC architecture and Router with XY algorithm is well known for its simplicity. In this project XY algorithm is changed to Extended XY algorithm where an extra diametrical link will be used which will reduce the number of hops considerably and helps in performance enhancement.

Keywords: NOC,SOC,MPSOC

1. INTRODUCTION

   As per Moores law statement the transistors on the chip getting double approximately every 18 months and due to this the advancement seen in the CMOS technology is such that million-billion transistors are been place on the single chip and this really increasing the complexity of the chip beyond the human imagination. These type o architectures are named as SOCs (System On Chip) or MPSOCs (Multi Processor System on chip).

   As said above NOC is the better solution for the future coming communication architectures which solves the scalability problem introduced by the traditional shared bus or dedicated bus architectures.

   Choice of correct type of the network routing algorithm is very important aspect since it will affect the main aspects of topology like complexity, power consumed, area, performance, latency etc. Deterministic routing algorithm where source and destination path is fix and is stored is the simple algorithm but introduces more delay and waiting time as well as network recourses utilization is less which can be improved by using adaptive algorithms but adaptive algorithms are live lock and dead lock prone which is the disadvantage of such type of algorithms. Hence the choice of the algorithm between deterministic or adaptive since the

   techniques introduced to overcome the dead lock and live lock free techniques may introduce the errors and also hinder the operation

   There are distinctive sorts of topologies portrayed for NOC engineering. These incorporate work, torus, ring, butterfly, octagon and sporadic interconnection systems. Numerous looks into demonstrated that the 2-D work engineering for NOC is increasingly productive as far as inactivity, control utilization and straightforwardness of execution , as contrasted and others. As showed in Fig. 1.1 The figure demonstrates a NOC interconnection design with a 2D work sort topology, which comprises of a few preparing components (PEs) associated together by same size wires. A hub containing PE can be any segment, for example, a microchip, ASIC square or memory, or a mix of parts associated together. Any information produced by PE is packetized by system interface (NI) at the limit of every PE. This NI is associated with a switch, and it has cushions at its info and yield to acknowledge information bundles from a PE or from different switches associated with it.

   Fig. 1 4×4 2D mesh architecture for NOC

   As said above NOC is the better solution for the future coming communication architectures which is giving solution for the scalability problem introduced by the traditional shared bus or dedicated bus architectures, and in NOC router plays an vital role and hence routing algorithms. To carry out the proposed work the objectives are as follows

   • Detailed study of traditional approaches and its challenges.

   • Literature survey of available methods and algorithms.

   • Comparative analysis of different routing algorithms.

   • Implementation and performance analysis of traditional and proposed algorithm.

2. LITERATURE SURVEY

   System on Chip (NOC) is another worldview to make the interconnections inside a Framework on Chip (SOC). By the advancements accomplished in incorporated circuits (IC) producing there have been endeavours to plan tremendous measures of system on the chips so as to accomplish progressively proficient and improved chips. A superior steering calculation can upgrade the execution of NOC.

   XY directing calculation is a dispersed deterministic calculation. Odd-Even (OE) directing calculation is conveyed versatile steering calculation with stop free capacity. Each NOC caught to fulfil some execution prerequisites like low dormancy, high throughput and low system power [1]. Here we exhibited the effect of traffic load minor departure from normal inertness, normal throughput and all out system control for two steering calculations XY and OE on a 3×3 2- dimensional work topology. The reproductions have been performed on NIRGAM No C test system adaptation 2.1 for consistent piece rate (CBR) traffic condition. The recreation results contains in general normal inertness (clock cycles per parcel), normal throughput (in GBPS) and all out system control (in mW). Execution measurements (P) is determined for both steering calculations and compared.[2][3].A quick advancement in Extremely Vast Scale Reconciliation (VLSI) in the past ongoing years has brought about the manufacture of a great many transistors on a solitary silicon chip. This progression in the smaller scale hardware prompts the reconciliation of different segments of a figuring framework or some other electronic framework on a solitary Incorporated Circuit (IC) to execute a total framework on a chip. Along these lines a worldview called Framework on Chip (SoC) appeared that alludes to the framework made up of interconnected centers or Protected innovation (IP) hinders on a solitary chip. So a successful correspondence framework is required between the IP squares of SoC [11]. These days direct interconnections and for the most part shared transports are utilized for on chip correspondence. The issue with direct interconnections is that they are not adaptable and turned out to be wasteful with an expansion in the quantity of centers [12]. Shared transports don't give palatable outcomes when scaled past 8 to 10 centres. Dispute for the transport and mediation likewise backs off the information development. They are useful for the frameworks with less number of associations. So System on Chip (SOC) is being considered as the most reasonable contender for executing interconnections in center put together framework with respect to chip (SOC) plan. In NOC worldview, centers are associated with one another through a system of switches and they convey among themselves through parcel exchanged correspondence [12][1]. A SOC with NOC framework is appeared in Fig 2.1.

   Fig 2.Soc with NOC architecture

3. METHODOLOGY

   Network On Chip (NOC) brings a notable improvement over conventional BUS and Crossbar interconnection. Bus based system offers large capacitive loads to bus drivers which ntroduces large delay and huge power consumption. On chip bus allows only one communication at a time hence this makes the bus based architecture inherently non scalable for a complex system.

   NOC architecture is similar to internet. The network consists of wires and routers. Data communication between segments of chip are packetized and transferred through the network. A high level of parallism can be achieved in NOC architecture compared to bus based architecture because NOC can operate simultaneously on different data packets and provides enhanced performance.

   • Extended 2D diametrical mesh can be considered as collection of four sub networks where opposite corners of the each sub networks is connected by diametrical links.

   • Added extra links helps to reduce the diameter in 2D mesh when 2D mesh is expanded by a large number of IP cores.

   • 4 x 4 diametrical 2D mesh is as shown below in Fig.4a. Network on Chip (NOC) brings a notable improvement over conventional BUS and Crossbar interconnection. Bus based system offers large capacitive loads to bus drivers which introduces large delay and huge power consumption. On chip bus allows only one communication at a time hence this makes the bus based architecture inherently non scalable for a complex system.

     NOC architecture is similar to internet. The network consists of wires and routers. Data communication between segments of chip are packetized and transferred through the network. A high level of parallism can be achieved in NOC architecture compared to bus based architecture because NOC can operate simultaneously on different data packets and provides enhanced performance.

   • Extended 2D diametrical mesh can be considered as collection of four sub networks where opposite corners of the each sub networks is connected by diametrical links.

   • Added extra links helps to reduce the diameter in 2D mesh when 2D mesh is expanded by a large number of IP cores.

   • 4 x 4 diametrical 2D mesh is as shown below in Fig.3.1.

     Fig.3. 4 x 4 diametrical 2D mesh with 8 extra diametrical links

   • If the source and destination nodes are located in same row or same column then normal XY routing is followed

   • Else algorithm will calculate shortest path depending on which either diametrical path or XY path, whichever is shortest is followed.

   • Added extra diametrical links in extended XY diametrical routing reduces the number of hops by providing shortest possible path.

   The same will be analyzed and the performance metric in terms of speed, throughput and latency will be compared between simple XY,OE and the proposed design to show how the proposed design will be able to bring tradeoff between deterministic and adaptive routing.

4. IMPLEMENTATION

   Fig.4.1: Router architecture

   Fig.4.2: Each port design

   Router consists of 5 ports since one extra port for diametrical arrived data as shown in fig.4.1 above. For each port as shown in fig 4.2 depending on the destination address the shortest path will be calculated using available routing algorithm as explained in section III. When routing path calculation is over request will be raised by each port for getting grant signal by arbiter. Arbiter grants the grant signal depending on priority and highest priority will be given to the diametrical arrived data this grant signal will also be passed to the crossbar switch which sends the data packect out to appropriate port as in fig4.3.

   Fig.4.3: Each port design

5. SIMULATION RESULTS

   A Fig 5.1 shows the Simulation results for router with XY algorithm.

   Fig.5.1: Simulation results for router with XY algoreithm

   A Fig.5.2 shows the Simulation results for router with Improved XY algorithm.

   Fig.5.2: Simulation results for router with Extended XY algorithm.

6. COMPARISION TABLE

   The table 6.1 shows the Comparison between router using XY algorithm and router using Extended XY algorithm.

   Src-dst address	Router with XY algorithm	No of hops in XY	Router with Extended XY Algorithm	No of hops in extended XY
   00-22	00-10-20- 21-22	04	00-22	01
   01-23	01-11-21- 22-23	04	01-23	01
   02-20	02-12-22- 21-20	04	02-20	01
   03-21	03-13-23- 22-21	04	03-21	01
   10-32	10-20-30- 31-32	04	10-32	01
   11-33	11-21-31- 32-33	04	11-33	01
   12-30	12-22-32- 31-30	04	12-30	01
   13-31	13-23-33- 32-31	04	13-31	01
   00-12	00-10-11-12	03	00-22-12	02
   33-01	33-23-13- 03-02-01	05	33-11-01	02
   12-20	12-22-21-20	03	12-30-20	02

   Table 6.1 Comparison between router using XY and Extended XY algorithm.

7. CONCLUSION

   In XY routing without diametrical link it takes 4 numbers of hops but in Extended XY routing if diametric path available it takes only one hop to reach destination. As due to the extra links it will increase the wire length but simultaneously it gives rise to reduction in diameter by average fifty present and also number of hops will be reduced because of which overall reduction in power consumption can be seen which in turn increases performance of the network.

8. FUTURE WORK

Since the design is taking diametrical path only if router contains diametrical path it can be further improved by making algorithm more robust by searching nearest diametrical path and hence can reduce number of hops to minimum and hence can add to performance.

REFERENCES

1. Jayant Kumar Singh, Ayas Kanta Swain ,Tetala Neel ,Kamal Reddy Kamala Kanta Mahapatra , Performance Evaluation of Different Routing Algorithms in Network on Chip 2013 IEEE Asia Pacific conference on Postgraduate Research in Microelectronics and Electronics.

2. Yonghui Li, Huaxi Gu , XY-Turn Model for Deadlock Free Routing in Honeycomb Networks-on-Chip, Proceedings of the 15th Asia-Pacific Conference on Communications (APCC 2009)-214.

3. Jyoti Khichar, Sudhanshu Choudhary and Rohit Mahar , Fault Tolerant Dynamic XY-YX Routing Algorithm for Network On-Chip Architecture 2017 International Conference on Intelligent Computing and Control (I2C2).

4. Gaoming Du, Dayi Liang, Yukun Song, Duoli Zhang , A Dynamic and Mixed Routing Algorithm for 2D Mesh NoC, National Nature Science

   Foundation of China (Grant No. 61106020, 61006024) and Doctoral Fund of Ministry of Education of China (Grant No. 20100111120009).

5. Elnaz Alikhah-Asl, Midia Reshadi , XY-Axis and Distance Based NoC Mapping (XY-ADB) 2016 8th International Symposium on Telecommunications (IST'2016) 978-1-5090-3435-2/16.

6. Shu Y. Jiang, Gang Luo, Yue Liu, Shan S. Jiang, and Xiu T. Li , Fault- Tolerant Routing Algorithm Simulation and Hardware Verification of NoC IEEE TRANSACTIONS On Applied Superconductivity, VOL. 24, NO. 5, October 2014 9002805.

7. Masood Dehyadgari, Mohsen Nickray, Ali Afzali-kusha, Zainalabein Navabi , Evaluation of Pseudo Adaptive XY Routing Using an bject Oriented Model for NOC Iran Telecommunication research.Center (ITRC).

8. Nezam Rohbani, Zahra Shirmohammadi, Maryam Zare, and Seyed- Ghassem Miremadi , LAXY: A Location-Based Aging-Resilient Xy- Yx Routing Algorithm for Network on Chip, DOI 10.1109/TCAD.2017.2648817, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.

9. Pan Hao,Hong QiI2,Du Jiaqin,Pan Pan, Comparison of 2D MESH Routing Algorithm in NOC ,978-1-61284-193-9/11/$26.00 ©2011 IEEE.

10. Ruilian Xoe,Jueping Cai and Xin Xin , Simple fault tolerant method to balance load in network on chip,Electronics Letters 12Th may 2016 vol.52 No. 10 pp 814-816.

11. W. Dally and B. Towles, Route packets, not wires: onchip interconnection networks, Proc. Design Automation Conference,Jun.2001, pp. 684689.

12. S.Kumar , A. Jantsch, J. Soininen, M. Forsell, M. Millberg, J. Oberg. Et al, A network on chip architecture and design methodology, Proc.IEEE Computer SoCiety Annual Symposium on VLSI