Research On Buffer Allocation Strategy And Fault-tolerant Routing Algorithm Of Network-on-Chip

With the advances in the semiconductor technology, traditional System-on-Chip (SoC) development is confronted by severe challenges, such as deep submicron effects, global synchrony, on chip communication, productivity gap, etc. Network-on-Chip (NoC) is proposed as a promising solution to address the above problems associated with SoC architecture by employing the packet switching network for chip design.The NoC architecture provides the network infrastructure for internal IP communication. In this dissertation, the key research problems in wormhole-switched NoC design, namely, buffer resources allocation, virtual channel allocation and fault-tolerant routing algorithm, are formulated and solved.Buffers are the integral part of any network router. The traditional uniform and greedy assignment of buffering resources lead to excessive use of the silicon area. Thus, a novel buffer allocation algorithm is proposed. The proposed algorithm first estimates the load on each input channel in different routers by the performance analytical model. Then, it uses genetic algorithm to allocate the resources according to the distribution of the load on all the channels.Virtual channels (VCs) are able to eliminate head of line (HoL) blocking in wormhole-switched NoC, but they also lead to increase of silicon area. Thus, virtual channels should be carefully allocated. The existing algorithms result in a waste of area and significant leakage power. To remedy this situation, a novel algorithm for customizing the VCs is proposed. The algorithm calculates the bandwidth usage at each router based on the traffic characteristics of the target application, and allocates VCs according to the distribution of the bandwidth usage.The fault-tolerant problem of NoC is also investigated in this dissertation. A novel fault-tolerant routing for wormhole-switched NoC is proposed. The algorithm can implement detour routing when there are permanent faults in the network. In addition, the multi-level congestion control mechanism gives the algorithm the ability to distribute the load over the whole network, and avoid network congestion.In order to validate the efficiency of the above algorithms, a NoC performance analysis platform, named NoCSim, is implemented by System C. Simulation results show that the proposed algorithms can significantly improve the performance and resource efficiency.