NoC Linked List based Router for Packet Classification Application

NoC Linked List based Router for Packet Classification Application

Kavya K1

1. Tech, Dept of ECE BMSCE Bangalore

   Sujatha K2

   Associate Professor, Dept of ECE BMSCE Bangalore

   AbstractNowadays minimizing the area and power has become the most significant part of the advanced technologies. One such technology is System on Chip where all the electronic components are placed in one integrated circuit. System on Chip uses more on-chip communication systems. These communication systems are un-suitable for most complex systems. To achieve higher performance in SoCs, a new approach was introduced. Network on chip (NoC) is one such advance where communication between processors is transferred by using packets. NoC includes virtual channels to improve the performance of the NoC System. When there are multiple transactions, they share the same physical layer and each virtual channel needs a first-in, first-out (FIFO) and every virtual channel is not used every time, so there is no effective utilization. This leads to complexity in software. Hence in this study, an NoC linked list based router for packet classification application is introduced where the transactions needs to be restored within the time frame. The functionality of the design is verified and simulated by writing Verilog codes in ModelSim- Altera 10.1b (Quartus 2 12.1).

   Keywords Network on Chip (NoC);router;virtual channel; linked list; verilog

   1. INTRODUCTION

      A billion transistors, gates, and circuits on a single silicon chip pose many challenges to silicon chip designers. The silicon chip designers overcome all the challenges to supply accurately and present a good functionality of the silicon chip. Reducing cost became a major concern so a new design technique called System-on-Chip (SoC) was introduced to overcome such complicated designs. The System on Chip technology is where all the electronic components are placed into the smallest possible space. Its architectural approach involves design reuse and increase in cost and time to market problems. It faced many challenges which paved way for Network on chip (NoC). NoC is one such technology which provides solutions to the on-chip communication problems. It uses packets which contain information to route from starting to the ending component, by switches (routers). In NoC wormhole switching is used for communication mechanism. Here the information is arranged as umpteen packets. A single packet consists of a different flow of data and packet information. The header flit contains information as where the packet has to reach. Until all the information is passed through the routers, the route path is restrained. The information is held temporarily in the buffer of the input or output ports. For dynamic data flow each port utilizes virtual channels and virtual channels share the same physical layer by usage of many packets in NoC systems. A router is the main constituent of NoC. Fig. 1. shows a Framework of Five port router.

      Fig. 1. Framework of five port router.

      It is made of five input ports which are north, east, south, west, local and output ports, a crossbar, an arbiter. Virtual channels have data flow mechanisms which are static and dynamic mechanisms. Static mechanism includes FIFOs or buffers which are used to transmit information. Dynamic allocates dynamically.

   2. DATA FLOW MECHANISMS IN VIRTUAL CHANNELS

      1. Static Mechanism

         In static mechanism, the buffer channels are fixed. The virtual channels have the same single channel to communicate and for each virtual channel there are IDs and FIFOs or buffer slots is where the information is stored as shown in Fig. 2. The read and write pointer points to different virtual channels in the FIFOs where the information is read or written.

         Fig. 2. Static Mechanism

      2. Dynamic Mechanism

      In Dynamic mechanism, buffers are allocated dynamically. Linked list based dynamic mechanism is employed as a single buffer maintains many virtual channels and in Fig.3. The link list tables are shown where the data flow is directed. Arbiter shows which ports are free and are ready to communicate. Based on the priority we set the data and where the data has to be placed to avoid congestion and data loss.

      Fig. 3. Dynamic Mechanism

   3. PROPOSED ARCHITECTURE

      Network on Chip has an important feature called as virtual channels. There are packets to be routed so each channel is divided into two, providing two paths. Virtual channels are used for reducing the delay, power reduction and manufacturing cost of NoC. In static flow of mechanism there are multiple transactions using the same physical link and there is no effective utilization of FIFO. Hence the dynamic flow of mechanism is used. Linked list based router for packet classification is introduced where different virtual channels are used and occupies less space.

      1. Linked list based Router

         Here a single buffer is used to maintain multiple virtual channels. In NoC, buffer or FIFO is used interchangeably and this linked list based router replaces FIFO as it is very complex with multiple virtual channels. It consists of Static random access memory, a decoder, slot-state, linked list tables, these linked list tables have five inputs and five outputs as shown in Fig. 4.

         Fig.4 . Linked list based Router

         The five input signals are:

         • VC-ID

         • VC-ID local

         • Read and Write pointer

         • Credit-in signal

         • Grant

           The credit-in signal is turned on and the data is stored in the memory slot and the write signal is pointed. There are five look up tables in the linked list based router:

         • VC-state

         • Slot-state tables

         • Header-List

         • Tail-List

         • Link list table

           In fig. 5. The address of the next port of each packet is seen in the link list tables and the address of the data of all the virtual channels is linked in a First-in, First-out manner. A slot state tables has either zero or one in one slot and identifies if one slot is empty or full. The tail-list has the address of the required slot which points to the data present in tails.

           Fig. 5. Linked list based router with n-VC and n-Slot lookup tables.

      2. Linked list based router communication

         The communication between the starting and receiving end of routers is by handshaking credit-based signals. Asynchronous communication is used between the routers and

         sinks. Fig.6. shows the communication inside a linked list based router.

         Fig. 6. Communication inside a linked list based router.

         In Fig.6. credit-in signal is given when number of instructions sends a packet. In destination source the data is stored in buffer. Hence these signals are identified and updated in the tables. If the buffer slot is full signals are sent to the destination to stop sending the packets.

      3. Slot-State Process

         The procedure of storing the states in a slot-state table is shown in Fig. 7. This table has the record of the slots already occupied in the SRAM by maintaining a Boolean signal for each slot. When a data occupies a slot in the static random access memory the same slot is set. The decoder decodes the data of the slot state table to induce the write-pointer. The write address port is linked to the write pointer as shown in Fig.8.

         Fig. 7. Updating of linklist tables in the slot state process.

         Fig. 8. Updating of linklist tables in the slot state process.

      4. Packet entry and leaving process

         The entry and leavingof the packet are identified by the credit-in and grant signals. If a data arrives, the corresponding virtual channel is set and indicates this slot is occupied and the data is stored in the five lookup tables and then in the slot write pointer is pointed.

      5. VC Selection module and Buffer-full

      The VC selection module has VC-block and VC-ava signals and the VC-block signal is inversed and AND operation is done with the corresponding bit in the VC-state. The VC-ava signal will select based on priority. The buffer- full signal shows the state of the linked list based router which is the input port. Fig.9 shows this signal is functioned to stop the operation in the input port when the linked list based router buffer is full all the slots are high.

      Fig. 9. VC selection module and buffer-full.

   4. PACKET CLASSIFICATION APPLICATION Packet classification is a very important task to transfer

      the packets within the given specified time. A packet is processed according to the priority given. The network processors face pressure due to the increased number of tasks that need to be valued. The important task is to get the transactions within the specified time frame because once the time is expired the transactions will get out of the router fast. Hence the priority counter is required. This will send the packets based on the priority given to each packet.

   5. EXPERIMENTAL RESULTS

      A Verilog code is written for the following five port router and linked list based router for packet classification application and is simulated using ModelSim-Altera 10.1b (Quartus 2 12.1). Fig. 10. Shows the simulation results of five port architecture using FIFO as input port. Here each virtual channel will be allotted with a dedicated FIFO and data will be stored in corresponding FIFO. The disadvantage of this

      technique is many fifo for each virtual channel and hence space required will be more.

      Fig. 10. Simulation result of five port architecture using FIFO as input

      port.

      Fig. 11. Shows the Simulation result of five port architecture using linked list as input port. In linked list router, the linked list is formed between the same virtual channel elements.

      Fig. 11. Simulation result of linked list router as input port.

      Fig. 12. Shows the Simulation result of five port architecture using linked list as input port for packet classification. Here the packet classification is priority with zero value and non-zero value as shown in Figs. 13 and 14. In linked list router, the linked list is formed between the same virtual channel elements. Since this approach contains only one storage fifo area will be less.

      Fig. 12. Simulation result of linked list router with priority zero value.

      Fig. 13. Simulation result of five port with priority non-zero value.

      TABLE 1. POWER OUTPUT

      The power and area report is generated as shown in Table 1 and Table 2.

      TABLE 2. AREA REPORT

   6. CONCLUSION

A linked list based router for packet classification application is put forward in this paper. The simulation of the modified linked list based router is veried by writing Verilog codes using ModelSim-Altera 10.1b (Quartus 2 12.1) software. This simulation shows that the modified linked list based router for packet classification application exchanges the data at a faster rate.

ACKNOWLEDGMENT

I would like to extend my token of gratitude to Mrs.Sujatha.K, Associate Professor, Department of E.C.E,BMSCE for her immense support and constant

guidance throughout this work and for her valuable suggestions which helped me complete this work.

REFERENCES

1. Masoud Oveis-Gharan and Gul N. Khan, Efficient Dynamic Virtual Channel Organization and Architecture for NoC Systems, IEEE Transactions On Very Large Scale Integration (VLSI) Systems,Vol. 24,NO. 2, February 2016.

2. Somashekhar Malipatil,Rekha S, Design And Analysis Of 10 Port Router For Network On Chip (NoC),International Conference on Pervasive Computing (ICPC),2015.

3. M. Lakshmiswethlana, V. Lavanya, Dr. R.R Ramanareddy, Design and Verification Eight Port Router for Network on Chip, IEEE 2012.

4. H. Zhang, K. Wang, Y. Dai, and L. Liu, A multi-VC dynamically shared buffer with prefetch for network on chip, in Proc. IEEE 7th Int. Conf.Netw., Archit., Storage, Xiamen, China, Jun. 2012, pp. 320327.

5. M. Lai, Z. Wang, L. Gao, H. Lu, and K. Dai, A dynamically-allocated virtual channel architecture with congestion awareness for on-chip routers, in Proc.45th ACM/IEEE DAC, Anaheim, CA, USA, Jun. 2008,pp.630633.

6. M. Evripidou, C. Nicopoulos, V. Soteriou, and J. Kim, Virtualizing virtual channels for increased network-on-chip robustness and upgradeability, in Proc. IEEE Comput. Soc. Annu. Symp. VLSI, Amherst, MA,USA, Aug. 2012, pp. 2126.

7. G. L. Frazier and Y. Tamir, The design and implementation of a multiqueue buffer for VLSI communication switches, in Proc. IEEE ICCD, Cambridge, MA, USA, Oct. , pp. 466471.

8. C. A. Nicopoulos, D. Park, J. Kim, N. Vijaykrishnan, M. S. Yousif,and

   C. R. Das, ViChaR: A dynamic virtual channel regulator for network- on-chip routers 2005,in Proc.39th Annu. IEEE/ACM Int. Symp.Microarchitecture, Orlando, FL, USA, Dec.2006.

9. Y. Tamir and G. L. Frazier, Dynamically-allocated multi-queue buffers for VLSI communication switches, IEEE Trans. Comput., vol. 41, no. 6,pp. 725737, Jun. 2008.

10. M. O. Gharan and G. N. Khan, A novel virtual channel implementation technique for multi-core on-chip communication, in Proc. WAMCA,New York, NY, USA, 2012, pp. 3641.