Fault-tolerant adaptive routing method based on ant colony algorithm

Abstract

The invention discloses a fault-tolerant adaptive routing method based on an ant colony algorithm. The method comprises the steps of marking a position of each node in a two-dimensional network and setting a routing table; detecting a fault node, and computing a fault value and effective buffer length of an adjacent node of the fault node if the fault node exists; searching and obtaining one or more to-be-selected routing paths through utilization of an adaptive routing algorithm if the fault node does not exist; selecting the optimum routing path from the to-be-selected routing paths according to an assessment scale, and updating a pheromone routing table according to an ant colony routing algorithm; detecting whether a destination node arrives or not, and finishing routing if the destination node arrives; judging whether deadlock occurs in the routing path or not if the destination node does not arrive, and finishing routing if the deadlock occurs; and detecting the fault node againif the deadlock does not occur. On the basis of the ant colony algorithm, a path selection mechanism in the fault-tolerant adaptive routing method is optimized and the pheromone routing table is updated, under the condition that the fault node exists, data transmission delay of a whole network-on-chip is reduced, and network load balance is realized.

Description

technical field [0001] The invention relates to the technical field of routing of on-chip networks, in particular to a fault-tolerant adaptive routing method based on an ant colony algorithm. Background technique [0002] With the development of semiconductor technology, chips are gradually developing from single-core to multi-core and even many-core, which requires more and more attention to the interconnection of the system when designing the chip architecture. However, the current mainstream bus-based interconnection method can no longer meet the needs of the growing chip scale. In response to this situation, researchers have proposed a chip interconnection method based on a network on chip. In an on-chip network, if the network scale is small, deterministic routing is generally used because it is simple to implement and can meet performance requirements; as the network scale increases, adaptive routing algorithms are used because deterministic routing has a large It may...

AI Technical Summary

Problems solved by technology

The fault-tolerant adaptive routing algorithm solves this problem from the routing algorithm level. Traditional fault-tolerant adaptive algorithms generally use a single value for fault reminders. At the same time, the storage overhead of the routing table is too large, and a large amount of time is spent on routing path selection. time overhead

Although the effect of reducing the delay is achieved to a certain extent, there are also certain limitations.

Images