A low-overhead, fully-distributed, guaranteed-delivery routing algorithm for faulty network-on-chips
2015 (English)In: Proceedings - 2015 9th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2015, ACM Digital Library, 2015Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
ACM Digital Library, 2015.
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
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-196173DOI: 10.1145/2786572.2786591ScopusID: 2-s2.0-84984614742ISBN: 9781450333962OAI: oai:DiVA.org:kth-196173DiVA: diva2:1046754
9th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2015, 28 September 2015 through 30 September 2015
Funding Details: SRC, Semiconductor Research Corporation. QC 201611152016-11-152016-11-142016-11-15Bibliographically approved