Research And Implementation Of Fault Tolerant Routing Algorithm For Network On Chip

Network on chip(NoC) is a new paradigm to solve the communication problemof multiprocessor systems. In NoC, two different process elements communicate witheach other by sending packets, thus some problems that SoC are facing such as globalsynchronization and long time delay can be solved. Furthermore, between two nodeson a network, there are maybe many available paths, therefore the network may havehigher bandwidth and can support multiple concurrent communications.However, current VLSI technology allows the integration of thousands of coreson a single NoC. Such massive multicore system is very easy affected by failures, sofault tolerance techniques should be implemented. Among these fault tolerancetechniques fault tolerant routing algorithm is a common and key technology.Fault blocks are often used in fault tolerant routing algorithms for2D Mesh. If amessage encounters a fault block during routing, it is routed around the fault blockalong its boundary. To form a rectangle or convex fault blocks, some nonfaulty nodesare sacrificed. It is these sacrificed nodes and faulty nodes that form fault blocks. Allof the sacrificed nodes can not send or receive messages just as faulty nodes.However, paths consisting of those sacrificed nodes possibly exist in fault blockswhich can be used to route messages normally. But those paths in fault blocks areignored by those fault tolerant roting algorithms.To address this problem, we propose a fault tolerant routing algorithm to use thepaths consisting of sacrificed nodes in fault blocks to route messages. Messages usingthose paths no longer need to travel around fault blocks. Thus, the transmission pathof messages can be shortened. This can directly reduce the total latency of the mesh.In addition, the usage of such paths is conditional. Only under some special condition,a message can use such a path, so that some turns can be prohibited and deadlock isavoided. The proposed routing algorithms is deadlock free without using virtualchannels.Then, we use a cycle-accurate NoC simulator based on SystemC to evaluate theperformance of our routing algorithm. We devised the simulator elaborately so thatit is quite simple to to configure NoC’s parameters, such as network size, routingalgorithm, the injection rate and the rounds to run simulation. The proposed routingalgorithm is simulated under different fault patterns and injection rates. Thesimulation results show that the proposed algorithm can gain much lower averagelatency and higher throughput compared with the traditional routing algorithm usingfault blocks.