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

Abstract

The invention relates to a multi-fault tolerant large-scale three-dimensional network-on-chip deterministic path routing method, which comprises the following steps of: maintaining a routing table oneach node of a three-dimensional network-on-chip, performing line routing on each node based on the routing table, and dynamically updating the routing table when a fault is detected, wherein the updating comprises the following steps: calculating the maximum strongly connected component of the three-dimensional on-chip network by adopting a Tarjan algorithm so as to abandon nodes which cannot work normally; processing a fault link located at the boundary based on a constructed three-dimensional steering model, so that each link cluster has and only has one steering forbidding pair, and updating a routing table; and processing the internal fault link according to a preset routing rule, and updating the routing table. Compared with the prior art, the method has the advantages that a network-on-chip can bear the influence of various faults, available nodes in the reconstructed network-on-chip can be utilized to the maximum extent, and the performance of the method is superior to that ofan existing solution in the aspects of average delay, throughput and energy consumption.

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