A low-overhead, fully-distributed, guaranteed-delivery routing algorithm for faulty network-on-chips

• 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. Copyright 2015 ACM.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Nyckelord

Deflection routing

Distributed algorithms

Face routing

Link failure

Network-on-chips

Permanent fault

Routing algorithm

Algorithms

Network-on-chip

Parallel algorithms

Routers

Routing algorithms

Centralized components

Deflection routings

Guaranteed delivery

Link failures

Permanent faults

Reconfiguration overhead

Saturation throughput

Network routing

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)