• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips

Mohammad Fattah, Antti Airola, Rachata Ausavarungnirun, Nima Mirzaei, Pasi Liljeberg, Juha Plosila, Siamak Mohammadi, Tapio Pahikkala, Onur Mutlu, Hannu Tenhunen, A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips. In: Andre Ivanov, Diana Marculescu (Eds.), 2015 9th ACM/IEEE International Symposium on Networks-on-Chip, 1–8, ACM/IEEE, 2015.

Abstract:

This paper introduces a new, practical routing algorithm 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 paths exist 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 provide a new variant of face routing in on-chip
networks and make use of deflections in routing. Our evaluations
show that the proposed algorithm has 8X less area overhead than
other algorithms that provide guaranteed delivery. Our 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.

BibTeX entry:

@INPROCEEDINGS{inpFaAiAuMiLiPlMoPaMuTe15a,
  title = {A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips},
  booktitle = {2015 9th ACM/IEEE International Symposium on Networks-on-Chip},
  author = {Fattah, Mohammad and Airola, Antti and Ausavarungnirun, Rachata and Mirzaei, Nima and Liljeberg, Pasi and Plosila, Juha and Mohammadi, Siamak and Pahikkala, Tapio and Mutlu, Onur and Tenhunen, Hannu},
  editor = {Ivanov, Andre and Marculescu, Diana},
  publisher = {ACM/IEEE},
  pages = {1–8},
  year = {2015},
}

Belongs to TUCS Research Unit(s): Embedded Computer and Electronic Systems (ECES)

Edit publication