Change search
ReferencesLink to record
Permanent link

Direct link
A low-overhead, fully-distributed, guaranteed-delivery routing algorithm for faulty network-on-chips
Show others and affiliations
2015 (English)In: Proceedings - 2015 9th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2015, ACM Digital Library, 2015Conference paper (Refereed)
Abstract [en]

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.
Keyword [en]
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
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-196173DOI: 10.1145/2786572.2786591ScopusID: 2-s2.0-84984614742ISBN: 9781450333962OAI: 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 20161115

Available from: 2016-11-15 Created: 2016-11-14 Last updated: 2016-11-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Tenhunen, Hannu
By organisation
Electronic Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link