Proceedings of the 9th ACM/IEEE International Symposium on Networks on Chip (NOCS), Vancouver, BC, Canada, September 2015.
Mohammad Fattah1, Antti Airola1, Rachata Ausavarungnirun2, Nima Mirzaei3, Pasi Liljeberg1, Juha Plosila1, Siamak Mohammadi3, Tapio Pahikkala1, Onur Mutlu2, Hannu Tenhunen1,4
1 Department of Information Technology, University of Turku, Turku, Finland
2 Electrical and Computer Engineering Department, Carnegie Mellon University, Pittsburgh, PA
3 School of Electrical and Computer Engineering, University of Tehran, Tehran, Iran
4 Department of Electronic Systems, Royal Institute of Technology– KTH, Stockholm, Sweden
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.
FULL PAPER: pdf