The paper presents a topology-agnostic greedy protocol for network-on-chip routing. The proposed routing algorithm can tolerate any number of permanent faults, and is proven to be deadlock-free. We introduce a specialized variant of the algorithm, which is optimized for 2D mesh networks, both flat and wireless. The adaptiveness and minimality of several variants this algorithm are analyzed through graph-based simulations.
A first category of algorithms employ face routing based techniques to find paths around areas with faulty components. Maze routing is an important example of these techniques @cite_10 . An important advantage of such methods is that recent information on the status of each link node is required only by its neighbouring nodes, thus resulting in a low reconfiguration overhead. Furthermore, these methods provide full fault coverage: a route will be found whenever a path from a source node to its destination exists. The main disadvantage is that these methods are limited to planar graph topologies and cannot easily be extended to other topologies, such as 3D NoCs, wireless NoCs or a torus topology. Additionally, when a packet encounters an area with faulty components, the lack of information on the shape of this area may result in the message being routed along the border in a suboptimal direction, thus significantly increasing the path length.
@cite_10
1989098385
This paper introduces a new, practical routing algorithm, Maze-routing, to tolerate faults in network-on-chips. The algorithm is the first to provide all of the following properties at the same time: 1) fully-distributed with no centralized component, 2) guaranteed delivery (it guarantees to deliver packets when a path exists between nodes, or otherwise indicate that destination is unreachable, while being deadlock and livelock free), 3) low area cost, 4) low reconfiguration overhead upon a fault. To achieve all these properties, we propose Maze-routing, a new variant of face routing in on-chip networks and make use of deflections in routing. Our evaluations show that Maze-routing has 16X less area overhead than other algorithms that provide guaranteed delivery. Our Maze-routing algorithm is also high performance: for example, when up to 5 links are broken, it provides 50 higher saturation throughput compared to the state-of-the-art.