Routing Algorithm Implementation And Verification For Network On Chip

Communication modes such as bus and crossbar switch have been unable to meet the higher data throughout requirement between large numbers of IP on a single chip.Technologies originally used for the interconnection of computer networks are ported onto the chip to address the issue of a large number of IP communication on the chip.Routing algorithm is one of most important factor to determine the performance of network on chip.So routing algorithm is selected as the main research direction of the thesis.New adaptive routing algorithm is proposed after studying the adaptive routing algorithm of Duato.The routing for a packet are calculated each cycle until the input virtual channel is assigned to an output virtual channel leading to use the latest output virtual channel congestion information.Packet in escape channel can select adaptive virtual channel as long as adaptive channel is free leading to balanced utilization of virtual channels.According to the analysis,the proposed routing algorithm is not deadlocked.The result of simulation shows that the performance of proposal algorithm is better than classical Duato adaptive routing.Comparing with classical Duato routing,the saturated throughput is increased by 17.8% in uniform and increased by 12.4% in transpose traffic pattern under 2 virtual channel conditions.The saturated throughput is increased by 14.1% in uniform traffic pattern and increased by 0% in transpose traffic pattern under 4virtual channel.The researching approach is as follows.In the research of routing algorithm's literature,many of the papers focus on a particular level abstraction of routing algorithms.Algorithm level,the register transfer level(RTL)and FPGA hardware level is studied.The design of routing algorithm in algorithm level is generally complex.The design of routing algorithm in register transfer level is relatively simple.Both algorithm and RTL level implementation and validation are covered in the thesis.The speed of simulation is fast but the accuracy is slightly poor in algorithm-level modeling.The simulation speed is low in RTL-level.It is hard to implement and test in FPGA-level.The accuracy is very high both in RTL-level and FPGA-level modeling.The respective advantages of different levels is full used in the thesis.The relationship between different factors and performance is analyzed by simulation at the algorithm level.Narrowing the scope of the study,relatively complex routing algorithm is designed at RTL-level and FPGA-hardware after analyzing the result of algorithm-level simulation.Multiple routing algorithms are implemented in algorithm level.The saturation throughput under different size of network,different number of virtual channel and different traffic pattern for different routing algorithms is simulated using Book Sim.After analyzing the performance of different routing algorithm in the various combinations of parameter condition,the result shows that the performance of Duato adaptive routing algorithm is the best.According to the result of algorithm level,Duato adaptive routing algorithm and new proposed adaptive routing algorithm are implemented basing on an open source No C called Netmaker at the RTL-level.Due to the limited capacity of FPGA,a 4x4 mesh-connected No C with 2 virtual channel is implemented on the FPGA.In order to implement it in the FPGA,multiple modules of testbench code are modified to synthesizable style.The performance of 3 different adaptive routing algorithms in FPGA test is the same with the result of RTL-level.