Multi-fault tolerant deterministic path routing method for large-scale three-dimensional network-on-chip

Abstract

The invention relates to a deterministic path routing method for a large-scale three-dimensional on-chip network that tolerates multiple faults. The method maintains a routing table on each node of the three-dimensional on-chip network, and each node performs online routing based on the routing table. The routing table When a fault is detected, it is dynamically updated, and the update includes: using the Tarjan algorithm to calculate the maximum strongly connected component of the three-dimensional on-chip network to discard nodes that cannot work normally; based on the constructed three-dimensional steering model, the faulty link located at the boundary is processed, Each link cluster has one and only one prohibition pair, and the routing table is updated; the internal faulty link is processed with the preset detour rule, and the routing table is updated. Compared with the prior art, the present invention can not only make the on-chip network bear the influence of various failures, but also can maximize the use of available nodes in the reconstructed on-chip network. In terms of average delay, throughput and energy consumption, the present invention is The inventive performance is superior to existing solutions.

Description

technical field [0001] The invention relates to the technical field of on-chip network reliability design and development, in particular to a deterministic path routing method for a large-scale three-dimensional on-chip network that tolerates multiple faults. Background technique [0002] Network-on-chip is a new communication method between intellectual property cores in a system-on-chip. Large-scale on-chip networks are an important part of supercomputers, which can move a large number of parallel communications between chips to the inside of chips to reduce transmission delays, thereby significantly improving computing performance. At the same time, the use of advanced three-dimensional integration technology can further increase the density of large-scale network processing cores. However, the large-scale on-chip network has the problem of multiple faults, and the immaturity of the current 3D technology has also led to a high failure rate of through-silicon vias, which ...

AI Technical Summary

Problems solved by technology

For example, a local adaptive routing algorithm, which can better tolerate a single point of failure in the on-chip network to avoid deadlocks, but few technologies are developed for multiple faults; another example is a loop routing algorithm, which can reduce the on-chip Congestion and fault tolerance in the center of the network, but the algorithm does not provide a short path for data packet transmission; the routing algorithm using two virtual channels based on the Hamiltonian path can tolerate a single fault on the network on chip and avoid deadlock, FL-RuNS scheme It can tolerate a single failure on a three-dimensional on-chip network and avoid deadlocks, but virtual channels often require huge overhead; the ERFAN algorithm uses a huge table to record the number of hops from each port of the router to each possible destination node, but The effects of multiple failures cannot be fully tolerated; the region defense method can withstand the effects of multiple failures by sacrificing all non-faulty nodes in the unsafe region, and the fault-tolerant minimum routing method further tries to minimize the routing path while tolerating multiple failures, but The excessive sacrifice of fault-free nodes makes these two algorithms unsuitable for large-scale on-chip networks with many faults, because the calculated number of available nodes is difficult to meet the design requirements

Images