An Efficient Implementation of 4×4 King Mesh Topology using Routing Technique

An Efficient Implementation of 4×4 King Mesh Topology using Routing Technique

T. Madhubala

PG Scholar Dept. of Electronics &

Communication Engineering PSNA College of Engineering & Technology

P. Karthika

PG Scholar Dept. of Electronics &

Communication Engineering PSNA College of Engineering & Technology

1. Sobana

   Assistant Professor Dept. of Electronics and

   Communication Engineering PSNA College of Engineering & Technology

   Dindigul, Tamil Nadu, India Dindigul, Tamil Nadu, India Dindigul, Tamil Nadu, India

   Abstract-In Network on Chip (NoC), the quantity of cores get increases step by step within the past few decades. This have an effect on the performance of the mesh and this ends up in evolution of new topological concept. The king topology provides the high grade evolution of the humanistic mesh and torus topologies. This network exhibits a variety of attention- grabbing characteristics that helps to achieve, reduced execution time of parallel processing applications. However, the long distance traffic might suffer from high transmission latency in mesh. The main aim of the proposed work is to reduce the quantity of hop counts by using XY routing and Weight based Path Selection (WPS) routing technique. That the speed of the system get improved and therefore the utilization of space and power consumption get reduced.

   Keywords- Topology, Routing Algorithm, Communication Network and Switching, Digital Subsystem.

   1. INTRODUCTION

      In System on Chip (SoC) the number of blocks in the IP modules getting rised in which the bus based architecture this reduce the performance of the system. Thus in cooperative communication bus design does not attain the desired bandwidth and other parameter measures. To enhance this, the usage of embedded shift network is meant and results in the evolution of Network on Chip (NoC). The most benefits of NoC architecture is scalability and suppleness.

      In NoC, topology of the network is extremely necessary to inter-connect the modules within the chip. There are various types of topological architectures are used to provide communication between subsystems. In network, the information are processed in the form of flits and packets. Where every single packet consist of header part and payload part. The payload portion of the packet consist of the original data and the header portion consist of sender address, destination address and control logic function. Network flow control is used to find the path how the individual packets are processed inside the network.

      The major principle of NoC architecture is the interconnection between the blocks. But the packet transmission is based on the routing technique. This techniques are used to identify the path of the data to process. This helps to work out the performance of the system. The main aim of the routing algorithms are to

      decrease the usage of in between switches and to reduce the latency. This additionally helps to balance the processing load of the channel. Performance of the network depends on the sort of topology and algorithms used to process.

      1. Topology

         Topological architecture play a major role in Network on Chip (NoC). This proceed with the physical layout and interconnection of the nodes and links in the network. The topology has a specialized impact on the processing performance and cost of the architectural design. Based on this routers are used as a switches are nodes to transfer the information. Those nodes are connected either by half duplex or full duplex link to communicate with their neighboring nodes.

         Fig. 1. A 4×4 mesh topological network

         The switches in between the sender node and receiver node is consider as the hops. Based on the number of hop counts, latency of the system get rise or fall. The number of switch hops is typically captured by the average hop counts. Various type of topological architectures have different path diversity. This provides the best opportunities for balancing the traffic loads across the multiple paths. NoC consist of various type of topologies such as Mesh, Torus, Star, Spin and Octagon. Most commonly used topological architecture in the integrated circuit design is mesh topology.

      2. Routing Algorithms

      By using the routing technique the datas are transmitted between sender and receiver. There are different type of routing techniques are present in designing process based on the rules of the algorithm. The broad classification of routing algorithms are Oblivious, Deterministic and Adaptive algorithms.

      Oblivious routing algorithms does not bother about the traffic conditions in the network where adaptive routing technique gives a wide description of congestion and traffic load conditions. Every deterministic algorithms are a type of oblivious algorithms. The merit of the deterministic algorithm is simple to use and easy to implement because the packets are arrive in order.

   2. RELATED WORKS

      1. Source routing

         Vaishali V. Ingle and Mahendra A. Gaikwad has proposed a source routing based mesh topology. They consider this topology because of its simplicity. Based on the protocol of the routing algorithm the process of the architecture is proceeded [16]. In this paper they discussed about different algorithms namely XY routing algorithm and OE routing Algorithm. Here the two major portion of NoC platform is discussed in terms of topology and routing algorithm and the performance is estimated. The performance metrics include latency, power/throughput ratio and power consumption for different algorithms.

      2. Radix Router

         Xinyu Wang and et al deals with the DMesh based routing algorithm. The difference between the mesh and DMesh is the crossing lines between the routers. This leads to high radix router architecture in which the path diversity get increased. In DMesh the overall performance of get improved based on the routing algorithm. The DXY algorithm reduces the deadlock and livelock in the network. Beyond this they use virtual cut through and wormhole as a switched network. Here two routing algorithms are compared namely DXY and RDXY [15]. On comparing this algorithms they concluded that RDXY provide a good balance enhancement in DMesh and this provides an efficient utilization of high path diversity and it can be used for large parallel architectures.

      3. Concentrated Mesh

         Akash Punhani and et al deals with the objective, if the number of cores in the system get increased then it affect the performance of the basic topologies. This leads to the evolution of new topology with concentric mesh at the center portion. They introduced a new algorithm to improve the efficient time and performance. In this they identify the hot spot based on the routing process. The new algorithm is the combination of two algorithms namely hybrid XY routing and CMM routing this improves the quality of service [17]. This algorithm is found better than odd-even routing technique. This topological implementation reduces the area and power of the system. So the extra memory usage get reduced.

      4. XY Routing Torus

         Priyanka N. Chopkar and Mahendra A. Gaikwad deals with the network in congestion, the package transportation will leads to produce more delay [2]. So maintaining an appropriate routing technique to get the equity between the time delay and throughput rate becomes the major problem. In this paper they tried to solve that problem using torus topology with our modified XY routing algorithm with the help of 3*3 network the Constant Bit Rate (CBR) is usd in traffic estimation. It is identified that if packet rate get boosted then latency/packet and throughput get increases but latency decreases. By using the routing technique shortest path can be easily found. In this algorithm the average latency is reduced and throughput get increased. Due to this process the performance of the system get in improved.

      5. Input and Output Selection Technique

      Ebrahim Behrouzian and et al deals with the improvement of both output selection and input selection technique. They presented an efficient routing algorithm namely BIOS, this combines the merits of deterministic routing and adaptive routing techniques. The network congestion conditions are discussed based on the routing algorithms. Performance is estimated based on the three traffic conditions namely Uniform, Transpose and hot spot [5]. This result gives a better performance of new routing algorithm compared to adaptive and deterministic algorithms.

   3. EXISTING METHOD

      1. King Topological Architecture

         The combination of three various topologies such as mesh, torus and diagonal leads to king topology. Where king network is broadly classified into two types as King Mesh topology and King Torus topology. The king topology are a higher degree progression of traditional mesh and torus topological network. In king topology data can be transported in orthogonal and diagonal migration similar to the king on a chess board. This topology has some effective properties such as bisectional bandwidth and path diversity. The folding scheme increases the efficiency of the network structure. Thus the centred nodes in king network has eight degrees structure in it. Based on the routing technique the processing of the information is proceeded. By using various routing algorithm leads to a various result in the performance. The main goal is to decrease the number of hop switch counts during the transmission process.

         1. 8 Port Node (b) Orthogonal (c) Oblique Fig. 2.Behaviour of node during transmitting

      The architecture analysis reveals the processing by duplicating the link number so that it doubles the bisectional bandwidth. The major reason for extra links, reduces the average length by 33 percent. Beyond this king mesh and king torus can be easily partitioned and this helps for a proper uniform distributions of switches. This is similar to specialized processing units or memory controllers. Based on the routing techniques the proper use of the path diversity is achieved this topological architecture is mainly described for large parallel processing applications. The suitable routing technique improves the performance of the system and efficiently transfer the packet to its destination by selecting the proper path in the local traffic conditions.

   4. PROPOSED METHOD

      A. 4X4 KING MESH TOPOLOGY

      King topological network architecture reveals a various attractive characteristics that helps to decrease the processing time of the parallel application based systems. By using the Dimension Ordered Routing (DOR) algorithm the topology is not effectively used because it force the data to process the routing record in single dimension before processing to the next. Due to this technique the counts of hop in between source and destination get raised so the area utilized and power consumed get raised. So that a Weight based Path Selection routing technique (WPS) is used to decrease the hop counts. It is a type of oblivious routing algorithm, this doesnt bother about traffic and load conditions in the network.

      In this method initially the transmitting way is chosen based on the weight assigned to the path 00, 01, 10,

      1. The shortest path is chosen among this and the packet is transmitted from the source node to destination node. Here the use of packet switching technique is used to transfer the data in the form of packets. So the shortest path can be easily identified. Eventually the speed of the process get increased.

         Fig. 3. Structure of 4×4 king mesh network using XY Routing Technique

         A 4×4 king mesh topology using XY routing based architecture is shown in Fig. 3 is designed by using node to node information transfer by using routing process.

         This architecture also reduces the internal connectivity level so that utilization area get decreased and power consumption also get reduced. Here two different algorithms are used to determine the performance of the system namely XY routing algorithm and path selection randomized routing algorithm. In XY routing technique the count of hops between the sender and receiver is high when compared to the path selection process. So the utilization of the flip-flops, registers and LUT count get reduced and automatically the area get minimized and speed get increased.

   5. EXPERIMENTAL RESULT

      The result shows the efficient performance of king mesh topology based on the routing techniques. This is estimated by using VHDL coding. The input data is in the form of binary values of 4 bytes. By using XY routing algorithm the data is transferred initially in X axis and it is followed by Y axis as shown in Fig 4. So the number of hop counts used to transmit the data get raised.

      Fig. 4. Data transmitted by XY routing technique Here the path selection technique is used for

      transmitting the data in the least weight based path, in which weight is assigned in the form of 00,01,10,11. Based on the assigned value of the path the shortest way is easily identified.

      Fig. 5.Data transmitted by path selection technique

      In the proposed method, 4×4 king mesh topological architecture is simulated and synthesized by using Xilinx 14.2. Thus compared to XY routing algorithm WPS technique has reduced number of hops between sender and receiver as shown in Fig. 5. Hence the time taken to process and power consumption for transmitting get minimized. The experimental results are listed below.

   6. PERFORMANCE ESTIMATED

      The device utilization summary reports has the area utilization and latency time for transferring the packet from source to destination node by routing algorithm. The power is estimated based on routing technique by using power analyzer.

      TABLE. I. COMPARISON BETWEEN XY ROUTING ALGORITHM AND WEIGHT BASED PATH SELECTION ROUTING TECHNIQUE.

      PARAMETERS	XY routing	WPS routing
      Number of slice LUTs	235	155
      Number of slice Registers	582	388
      Number of fully used LUT-FF pairs	231	152
      Number of Hop counts	5	2
      Power	1.488W	1.484W

      NUMBER OF HOPS

      The proposed technique effectively decreases the area and the number of hop counts utilized between sender and receiver by using WPS algorithm rather than using XY routing algorithm. The parameters estimated are listed in the above table I.

      HOP COUNTS BETWEEN XY

      & WPS

      6

      4

      2

      0

      XY

      WPS

      ALGORITHMS

      Fig. 6. Comparison of hop counts utilized between routing algorithms (XY & WPS).

   7. CONCLUSION

In this paper, different type of routing algorithms has been discussed related to the mesh topological architecture. Based on the analysis of algorithms, XY routing algorithm and weight based path selection

algorithms are used in 4×4 king mesh topology. XY routing technique is widely used in mesh structure. But according to the king mesh architecture it has been concluded that XY routing algorithm achieves less efficient performance compared to the WPS algorithm. This is due to the high path diversity property of king topology. Where the utilization of hop counts between the sender and receiver is minimzed in the architecture. So the utilization of area and power get reduced in the WPS algorithm.

REFERENCES

1. Abts D., Enright Jerger N.D., Kim J., Gibon D. and Lipasti M.H. (2009), Achieving predictable performance through better memory controller placement in many-core CMPs, ACM SIGARCH Comput. Archit. News, vol. 37, no. 3, pp. 451-461.

2. Akash Punhani., Pardeep Kumar and Nitin N. (2017), Routing for Center Concentrated Mesh, International Journal of Intelligent Engineering and Systems, vol. 10, no. 1.

3. Arpit Jain., Adesh Kumar., Rakesh Dwivedi and Sanjeev Sharma. (Sep. 2016), Network on Chip Router for 2D Mesh Design, International Journal of Computer Science and Information Security, vol. 14, no. 9.

4. Camara J.M., Moreto M., Vallenjo E., Beivide R., Miguel-Alonso J., Martinez C. and J. Navaridas. (Dec. 2010), Twisted torus topologies for enhanced interconnection networks, IEEE Trans. Parallel Distrib. Syst., vol. 21, no. 12, pp. 1765-1778.

5. Ebrahim Behrouzian Nezjad., Ahmad Khadem Zadeh., Amin Javadi Nasab., Ehsan Behrouzian Nezjad and Ali Shanesh Sazan. (Nov. 2007), A New Efficient Routing Algorithm for Network- on-Chip with Best Inout and Outpu Selection Techniques, Proceeding of the 9th WSEAS Int. Conference on Data Networks, Communications, Computers, Trinidad and Tobago.

6. Flahive M. and Bose B. (Aug. 2010), The topology of Gaussian and Einsten-stein-Jacobi interconnection networks, IEEE Trans. Parallel Distrib. Syst., vol. 21, no. 8, pp. 1132-1142.

7. C. Hilton and B. Nelson, PNoC: A flexible circuit-switched noC for FPGA-based systems, 2006.

8. Hu W.H., Lee S.E. and Bagherzadeh N. (2008), DMesh: A Diagonally- Linked Mesh Network-on-Chip Architecture, Int. Workshop NoC Archit. MICRO-41.

9. F. Karim, A. Nguyen, and S. Dey, An interconnect architecture for networking systems on chips, Sep 2002.

10. Kim J., Dally W.J., Scott S. and Abts D. (2008), Technology- driven, highly-scalable dragonfly topology, in Proc. Int. Symp. Comput. Archit., p. 77.

11. Marshall A., Stansfield T., Kostarnov I., Vuillemin J. and Hutchings B. (1999), A reconfigurable arithmetic array for multimedia applications, in Proc. Int. Symp. Field Programm. Gate Array, pp. 135-143.

12. Navaridas J., Miguel-Alonso J., Pascul J.A. and Ridruejo F.J. (2011), Simulating and evaluating interconnection networks with INSEE, Simul. Modelling Practice Theory, vol. 19, no. 1, pp. 494-515.

13. Priyanka N. Chopkar and Mahendra A. Gaikwad. (Nov.2013), Analysis of latency and Throughput of 2D Torus Topology using Modified XY Routing Algorithm, ACEEE Int J. On Communications, vol. 4, No. 2.

14. Priyanka N. Chopkar and Mahendra A. Gaikwad. (2013), Review of XY Routing Algorithm for 2D Torus Topology of NoC Architecture, International Journal of Computer Application (0975-8887).

15. Stafford E., Bosque J.L., Martinez C., Vallenjo F., Beivide R. and Camarer C. (2010), A first approach to king topologies for on- chip networks, in Euro-Par: Parallel Processing. Berlin, Heidelberg: Springer-Verlag, pp. 428-439.

16. Vaishali V. Ingle and Mahendra A. Gaiwad. (2013), Review of Mesh Topology of NoC Architecture using Source Routing Algorithms, International Journal of Computer Applications (0975-8887).

17. Xinyu Wand., Tingting Han and Haikuo Liu. (2015), Exploiting the Routing Efficiency for DMesh Networks, International Journal of Future Generation Communication and Networking, vol. 8, no. 6, pp. 271-278.

18. D. Wiklund and D. Liu, Design of a system-on-chip switched network and its design support,2002.

19. D. Wiklund and D. Liu, SoCBUS: switched network on chip for hard real time2003.

20. C. A. Zeferino and A. A. Susin, SoCIN: A parametric and scalable network-on-chip 2003.