Reliable and Error-free Router Arbitration Design for Circuit-switched NOC

Reliable and Error-free Router Arbitration Design for Circuit-switched NOC

Dr.K.R.Kashwan, Ph.D 1, G.Selvaraj M.E, Research Scholar 2

ABSTRACT

1. Prof & HOD/Dean PG,ECE Department, Sona College Of Technology, Salem(TN), INDIA,

2. HOD/ECE, Bhaktavatsalam Polytechnic College, Kanchipuram (TN), INDIA

decouple computation from communication concerns, simplify

In this paper we designed a reliable and error free transmission of router arbitration for circuit-switched NOC router. Circuit switched NOC has guaranteed throughput, and high performance for large size packets. Arbiter has been used in NOC router when many inputs want to go out through same out put port at the same time, then round robin arbiter handles the situation to assign priorities to incoming inputs based on round robin arbiter algorithm used in the router, in which priorities are assigned in clockwise the request was just served should have the lowest priority on the next round of arbitration. The simulation result reveals that the round robin arbiter in circuit switched NOC router has low overhead of consuming less power, is around 1.446W and occupies less area, is around 1119slices (29%). This paper also applies the hamming code to get error free transmission from input port to output port of the router.

Keywords:

Arbiter, Hamming- code, Network-on-Chip, Router.

1. INTRODUCTION

   More and more processor cores and large reusable components have been integrated on a single silicon die, which has become known under the label System-on-Chip (SoC).Buses and point-to- point connections were the main means to connect the components. But as silicon technology advances further, problems related to buses have appeared First buses do not scale as the number of communication partners connected become higher. Second, long and global wires and buses become undesirable due to their low and unpredictable performance, high power consumption and noise phenomenon. Third, due to the unpredictability of the communication performance, designing and verifying a large bus based communication networks is very hard. Fourth, every system has a different communication structure, making its reuse difficult. So researches in systematic approaches to the design of the communication part of SoC are needed at all levels from the physical to architectural to the operating system and the application level. So Network- on-Chip(NoC) is used mostly in a very broad meaning, encompassing the hardware communication infrastructure, the middleware, operating system communication services, the design methodology and tools to map application onto a NoC. All these together can be called a NoC platform. Platform based design methods accelerate time-to-market through extensive reuse of an architectural platform. Such design methods

   problems.

   The basic idea is to interconnect various IP cores using on chip networks as compared to traditional shared bus approach. The interconnection is achieved by means of routers. The information is transferred using packet switching mechanism. NoC present a host of advantages like IP reuse, scalable and modular architecture. Area is at an important Constraint of FPGA, when programming a good system will utilize Less Memory and therefore communication network system should be as small as possible to meet the Less Area. Hence router which is the central component of any NoC must also be a very small [1].

   In this paper we present a light-weight router for NoC implemented on FPGAs, which can support five parallel connections simultaneously. The router uses store and forward type of flow control and XY deterministic routing. Reducing the size of the Finite state Machine (FSM) for XY routing and performing a simple logical OR of the Select/Gnt lines, significantly reduces the number of slices. The area savings has significant impact on the performance and power consumption. NoC has advantages on architecture, performance, reusability and scalability than traditional bus- based system-on-chip. Among these basic modules, the data flow control of virtual channel play an important role to alleviate the package congestion. The architecture and dataflow control will affect the design of arbiter of NOC significantly. The arbitration should guaranteed the fairness in scheduling, avoid starvation, and provide high throughput [2]. The NoC's switches should provide high speed and cost- effective contention resolution scheme when multiple packets from different input ports compete for the same output port. Fast arbiter is one of the most dominant factors for high performance NoC switches [3].

2. ROUTER ARCHITECTURE

   In this work we have designed a Parallel router which is having Low Area as shown in the figure-1. The motivation is to reduce the area which also reduces the power consumed. We choose one of the popular methods of buffering called store and forward. The motivation behind choosing such a scheme is to have the simplest possible decoding logic, thereby, reducing both area and power. Establishment of connections is made automatically without any complex decoding logic.

   Figure-1:Block Diagram of Router architecture in the Network-on-chip

3. ROUTER DESIGN

   Figure-2:Block Diagram of Router Design in the Network-on-chip

   The router consist of five ports east, west, north, south and local port and a central cross point matrix as shown in the figure-2. Each port has its input channel and output channel. Data packet moves in to the input channel of one port of router by which it is forwarded to the output channel of other port. Each input channel and output channel has its own decoding logic which increases the performance of the router. Buffers are present at all ports to store the data temporarily. The buffering method used here is store and forward. Control logic is present to make arbitration decisions. Thus communication is established between input and output ports. The connection

   or configuration is made between both with the central cross point matrix. According to the destination path of data packet, control bit lines of cross point matrix are set. The movement of data from source to destination is called switching mechanism. The packet switching mechanism is used here, in which the flit size is 8 bits .Thus the packet size varies from 8 bits to 120 bits. The solution consists of an on-chip data- routing network generally Known as Network-on-Chip (NoC) architecture [4][9].

   1. Input channel

      One input channel at each port is found, each running its own control logic as shown in the figure-3. Each input channel has a FIFO of depth 16 and data width of 8 bits and a control logic which has implemented as a Finite State Machine (FSM).The input channel accepts request from other neighboring routers. On receiving the request, if it is free, it will acknowledge the request. The first flit is the header and the following flits constitute the data.

      Figure-3:Block Diagram of Input channel in the Network-on-chip

      It will accept the data as long as the request signal held high. The previous routers output channel ensures that the request line is held high until it empties the packet of data, being accepted by the input channel. The input channel accepts the acknowledgement line is high, as long as there is a transfer taking place (indicated by the request line).The transfer being completed the request and the acknowledgement line go low in sequence. The packet of data received from the previous router is stored locally in the FIFO thereby implementing a store and forard dataflow. Next the control logic reads the header of the packet and using decides which output channel is to be requested for sending out of the router and sends the request to that output channel. It is to be noted that each of the input channel is running an independent FSM and hence can initiate five possible parallel connections at the same time. Once the input channel gets a grant from the requested output channel, the control bits of cross point matrix are set appropriately by the granting output channel.

   2. Working

      The working of input channel is based upon that the input given to the GNTL, the working of input channel is as follows, each and every input from the user is given to the MUX, the operation starts that when there is a data in is given as input such that the value is 00001001, based upon the selection of

      the acknowledgement which is high that corresponding the request (req)

   3. XY routing

      Figure-4: Block Diagram Showing XY routing Algorithm

      At the Input channel, once the FIFO is filled, the X-coordinate of the destination router (say Hx) is compared with locally stored X coordinate of the router first to decide on the horizontal displacement as shown in the figure-3. If Hx>x then the packet is forwarded to the East port of the router, and if Hx<X then the packets goes out through the West port of the router. If Hx is equal to X then the Y coordinate of the Router to be decided on the vertical displacement. If Hy>Y the packet is forwarded to the North port and if Hy<Y the packet is forwarded to the South port. When Hy equals Y it indicates that the packet is at the destination router and so the packet is forwarded to the local port. A packet is forwarded horizontally till the target column is reached and is then forwarded vertically to the destination router in a XY routing. This means that there is no request for the East or West output ports by the North or South ports. This fact is exploited and the FSMs of the mentioned output channels are simplified, as they need not service the mentioned input ports. Translating to significant area saving and reduction in number of clock cycles in servicing requests. This helps the implementation of light weight router, having area overheads at the minimum with acceptable level of performance.

      • XY routing algorithm routes packets first in x- direction (or horizontal direction) to the correct column and then in y- direction (or vertical direction) to the receiver.

      • The routing process is taken like this way. Then the routing operation is done on the basis of the following condition X>Y,X=Y,X<Y

      • One of the advantages of XY routing is that it never runs into deadlock or live lock.

      • In XY routing the addresses of the routers are their XY coordinates and is more suitable for networks using mesh or torus topology.

   4. Crossbar

      Cross bar is a set of multiplexers and demultiplexers having an interconnection allowing all possible connection between the five inputs and output channel, as shown in the figure-5.

      Figure-5: Block Diagram of Crossbar Switch in the Network-on- chip

      The output channel while granting the request of an input channel configures the multiplexers and demultiplexers of the cooperating input and output channel thereby establishing the connection between them for the transfer of the packets. A crossbar switch (also known as cross-point Switch, cross point switch, or matrix switch) is a switch connecting multiple inputs to multiple outputs in a matrix manner. The design of crossbar switch has 5 inputs and 5 outputs. Fig.5 shows Multiplexer based crossbar switch. As we are getting five input packets of 40 bits each from five ports of router, number of 5:1 multiplexers used inside the crossbar are five. All five inputs are given to all the multiplexers. Select line is of Three bits. Out of five select lines which one is selected is depend on the logic of arbiter. Outputs of multiplexers are the output ports of the 5X5 router.

   5. Working

      Depending upon the mux selection the mux is working based upon request from the input channel,and based on the input corresponing output will get from the crossbar.

   6. Output channel

      Figure-6: Block Diagram of Output Channel in the Network-on- chip

      One output channel at each port which has an 8 bit FIFO of depth 16 and a control logic making an arbitration decisions is found. The output channel gets request from the different input channels and grants one and sets the control bit lines of cross point matrix, as shown in the figure-6. It accepts the packet into its FIFO as long as the sending input FIFO is not empty thereby providing a simple decoding logic. When transfer is complete the cross point matrix controls are reset.FSM then initiate the process to send the data into the neighbouring router using handshake mechanism. Empty status of its FIFO triggers the next inter-channel transfer.

   7. Working

   The working of output channel is based upon that the input from the CROSSBAR, the working of output channel is as follows, the output from the arbiter is called upon grant is given to demux block of output channel from the corresponding will enables and the particular output i.e.; 00001001 this output packet will receive from the crossbar switch.

4. ARBITER

   Arbiter is one of the internal components that are used to control the packet switching and from the block diagram arbiter is one of the main components that have ability to use an algorithm and to make switching based upon that algorithm [4].

   Figure-7: Block Diagram of arbiter

   4.1 Round robin arbitration

   Round-robin (RR) is one of the simplest scheduling algorithms for processes in Networks operation as shown in the Table 1.It is generally used to operate the time slices, assigned to each process in equal portions and in circular order, handling all processes without any priority (also known as cyclic executive). Round-robin scheduling is simple, easy to implement, and starving-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks [5][7][8].

   Table 1: without contention and with contention Table

   Sr. No	I/P Port	SA	DA	Select Line	O/P Port Without Contention	O/P Port With Contention
   1)	Port a	000	001	Selb(000)	Port b	Port b
   2)	Port b	001	010	Selc(001)	Port c	Port b
   3)	Port c	010	011	Seld(010)	Port d	Port b
   4)	Port d	011	100	Sele(011)	Port e	Port b
   5)	Port e	100	000	Sela(100)	Port a	Port b

   I/P=Input, SA=Selection Address, DA=Data Address/P=Output

   Figure-8: Screen shot Showing AREA Utilization of Round Robin Arbiter in NOC Router Architecture

   Figure-9: Screen shot Showing Power Utilization of Round Robin Arbiter in NOC Router Architecture

5. HAMMING CODE

   Hamming code is a linear error correcting code .hamming code can detect up to two bit error or correct one bit error .By contrast the simple parity code cannot correct errors. Hamming codes are perfect codes they achieve the highest possible rate for codes. This paper implements hamming distance in order to check the error free arbiter used in router.

   Table 2: Algorithm for hamming cde

   power and occupies smaller area in router architecture. The implantation of Round Robin Arbiter in the router architecture will take an advantage in FPGA that utilization of area, is around 1119 slices-29%, and power consumption is 1.446W. This paper also applies hamming code in order to check the error free data transmission in the circuit switched NOCs router.

   REFERENCES

   1. W. 1. Dally and B. Towles, Route Packets, Not Wires: On-Chip Interconnection Networks, In Proceedings of the 38th Design Automation Conference, p.684 (2001).

   2. Ms. A.S. Kale, Professor. M.A.Gaikwad Design and Analysis of On-Chip Router for Network On Chip

   3. Yun-Lung Lee, Jer Min Jou and Yen-Yu Chen, a High Speed and decentralized arbiter Design for NOC [J], 350-353.

   4. Zhizhou Fu, Xiang Ling The design and implementation of arbiters for Network-on-chips 2010 2nd International Conference on Industrial and Information Systems.

   5. Si Qing Zheng, Senior Member , IEEE , and Mei Yang, Member , IEEE Algorithm-Hardware Code sign of Fast Parallel Round-Robin Arbiters IEEE Transactions on parallel and distributed systems, vol. 18, no. 1, January 2007.

   6. T. Anderson, S.Owicki, J.Saxe, and C.Thacker, High-Speed Switch Scheduling for Local-Area Networks, ACM Transaction on Computer Systems, vol. 1, no. 4, pp. 319-352, 1993

   [7] S.Q. Zheng t, Mei Yang t, John Blsnton t, Prasad Golls t,

   Simplified Simulation Flow for 'Hamming Code'

   Begin Inputs:

   X=1, 2, 3, 4, 5, etc

   Determine:

   Write the bit numbers in binary: 1, 10, 11, 100, 101, etc. All bit positions that are powers of two are parity bits Determine:

   Values of parity bit as 1,2,4,8…

   Change the position for parity bit 1 bit 1, 3, 5, 7, 9, etc.

   Change the position for parity bit 2 bit 3, 6, 7, 10, 11, etc. Repeat:

   Until change of position for the last parity End

6. RESULTS

   We use the Xilinx Spartan-3 board, which has an xc3s200 FPGA to functionally verify the standalone router and the NOC system. We use the Xilinx 10.1ISE to synthesize the system and Modelsim 6.3c to simulate the model and generate the activity data of the place and router model.

   Table 3: Simulation result of round robin arbitration

   Arbiter	Area(slices)	Power(w)
   Round Robin	1119	1.446

   W=Watt

7. CONCLUSION

This paper reveals that the implementation of round robin arbitration in router architecture of circuit switched NOCs influences reliable and fault tolerant network, and simulation result shows that the Round Robin Arbiter consumes low

Dominique Verchere A Simple and Fast Parallel Round-Robin Arbiter for High-speed Switch Control and Scheduling.

1. Eung S. Shin, Vincent J. Mooney 111 and George F. Riley Round-robin Arbiter Design and Generation.

2. W. I. Dallv and B. Towels. Route Packets Not Wires: On-Chin L~1 International conference on Networks, Proceedings of IEEE Design@ Automation Conference, 2001, pp. 684-689

First A. Author _ Dr. K. R. Kashwan received his M. Tech. degree in Electronics Design and Technology and Ph.D. in ECE from Tezpur University (A Central University), Tezpur in the years 2001 and 2005 respectively. Dr. Kashwan is a certified Chartered Engineer in ECE. His research areas are VLSI Design, Communication Systems, Circuits and Systems, Embedded Systems, Electronic Nose and

SoC / PSoC. He is currently a Professor and DEAN-PG / HEAD of the Department of Electronics and Communication Engineering, PG, Sona College of Technology, for the last 8 Years. Dr. Kashwan has over 22 years experience in teaching, research and industry. He has taught many courses ECE at post graduate and undergraduate levels. He is currently a director of the Centre for VLSI Design and Embedded SoC. Dr. Kashwan has received many research grants from Government of India. He has published 46 Papers in refereed journals and conferences at international level. Dr. Kashwan has worked on collaborative project on E-Nose. Dr. Kashwans publication citation report on Google search reads 268 as on date. He has guided 4 PhDs and currently guiding another 8. Dr. Kashwan has also guided 72 ME/MTech projects and 5 BE/BTech projects. He has successfully guided many funded research projects such as Automatic Tyre Inflation System, Electronics Senesces for Blind Persons, Microstip Antenna Implementation for PICO Satellite etc. He is currently member of Academic Council, Convener of Research Committee and chairman of Board of Studies in Electronics and Communication Engineering. He has visited many international universities. Dr. Kashwan has presented papers at many international conferences / symposiums and delivered many invited / plenary / expert lectures in India and abroad. He has organized special sessions for IASTED, Calgary, Canada and IACSIT, Singapore. Dr. Kashwan is a Senior Member of IACSIT, Singapore, Member of IASTED, Canada,

Member of IEEE, USA, Life member of ISTE, INDIA and member of Institution of Engineers (INDIA). Dr. Kashwan has conducted 21 seminars/ workshops / conferences and chaired 6 international conference sessions. He is serving as a resource person for faculty development programs since 2005.

Second B. Author SELVARAJ.G, received his degree in Physics(B.Sc) from Madras University(TN) in 1983, degree in Electronics and Telecommunication Engineering(AMIETE) from IETE, New Delhi in 1988, M.E degree in Sathiyabama, University(TN) in 2005 and he is currently pursuing Ph.D in Anna University, Chennai. His area of interest includes Communication, VLSI and Embedded Systems. He

has over 24 years experience in teaching, research and industry. He has taught many subjects in ECE at diploma levels. Mr.G.Selvaraj has conducted 12 seminars / workshops. He has presented papers at National and International Conferences. He is serving as a resource person for Community Development Programs for past 5 years