A Dynamic Sufficient Condition of Deadlock-Freedom for High-Performance Fault-Tolerant Routing in Networks-on-Chips

Networks-on-Chips (NoCs) are considered to be the paradigm of choice for on-chip communication and are today widely adopted in many-core systems. Many existing routing solutions make use of virtual channels (VCs) to avoid deadlocks while offering enough routing flexibility to avoid faulty and congested areas in a NoC. However, most of the current solutions rely on an overly restrictive, static partitioning of VCs, which results in an underutilization of their throughput enhancement capabilities. To overcome the limitations of such approaches, we introduce a new sufficient condition of deadlock-freedom that greatly relaxes the restrictions imposed by the classic VC-based deadlock-avoidance methods. The strength of our condition lies in the fact that it is imposed on packets at runtime and does not require any partitioning of virtual channels, which makes it possible to fully exploit them to reduce packet blocking and boost performance. Based on this condition, we present a generic, topology-agnostic routing algorithm design methodology that can be used to construct highly flexible routing algorithms in only a few steps. Several examples are presented to showcase the usefulness of our approach for the construction of fault-tolerant routing algorithms, as well as the enhancement and the proof of existing routing algorithms. The implementation of all the required mechanisms in hardware is also described in detail, thereby demonstrating its feasibility in an on-chip environment.

• Publication year

  2017

• Venue

  IEEE Transactions on Emerging Topics in Computing

• Publication date

  2017-11-23

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/TETC.2017.2776909
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• EbDa: A new theory on design and verification of deadlock-free interconnection networks

  2017cited by this paper
• Detailed and highly parallelizable cycle-accurate network-on-chip simulation on GPGPU

  2017cited by this paper
• A new approach to deadlock-free fully adaptive routing for high-performance fault-tolerant NoCs

  2016cited by this paper
• Addressing transient routing errors in fault-tolerant Networks-on-Chips

  2016cited by this paper
• A Resilient Routing Algorithm with Formal Reliability Analysis for Partially Connected 3D-NoCs

  2016cited by this paper
• d2-LBDR: Distance-driven routing to handle permanent failures in 2D mesh NoCs

  2015cited by this paper
• Analytical Fault Tolerance Assessment and Metrics for TSV-Based 3D Network-on-Chip

  2015cited by this paper
• A novel non-minimal/minimal turn model for highly adaptive routing in 2D NoCs

  2014cited by this paper
• Fault tolerant and highly adaptive routing for 2D NoCs

  2014cited by this paper
• Elevator-First: A Deadlock-Free Distributed Routing Algorithm for Vertically Partially Connected 3D-NoCs

  2013influential reference
• LEAR -- A Low-Weight and Highly Adaptive Routing Method for Distributing Congestions in On-chip Networks

  2012cited by this paper
• MAFA: Adaptive Fault-Tolerant Routing Algorithm for Networks-on-Chip

  2012influential reference
• HARAQ: Congestion-Aware Learning Model for Highly Adaptive Routing Algorithm in On-Chip Networks

  2012cited by this paper
• On Necessary and Sufficient Conditions for Deadlock-Free Routing in Wormhole Networks

  2011cited by this paper
• A Comment on “A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks”

  2011influential reference
• Throughput-Effective On-Chip Networks for Manycore Accelerators

  2010cited by this paper
• Fault-Tolerant Deadlock-Free Adaptive Routing for Any Set of Link and Node Failures in Multi-cores Systems

  2010influential reference
• Networks-on-Chip in a Three-Dimensional Environment: A Performance Evaluation

  2009cited by this paper
• Allocator implementations for network-on-chip routers

  2009cited by this paper
• On-Chip Interconnection Architecture of the Tile Processor

  2007cited by this paper
• A Tool for Automatic Detection of Deadlock in Wormhole Networks on Chip

  2006cited by this paper
• Demystifying 3D ICs: the pros and cons of going vertical

  2005cited by this paper
• Route packets, not wires: on-chip interconnection networks

  2001cited by this paper
• Characterization of Deadlocks in k-ary n-Cube Networks

  1999cited by this paper
• A General Theory for Deadlock Avoidance in Wormhole-Routed Networks

  1998cited by this paper
• A Framework for Designing Deadlock-Free Wormhole Routing Algorithms

  1996cited by this paper
• A universal proof technique for deadlock-free routing in interconnection networks

  1995cited by this paper
• A theory of fault-tolerant routing in wormhole networks

  1994cited by this paper
• Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels

  1993influential reference
• Optimal fully adaptive wormhole routing for meshes

  1993cited by this paper
• The Turn Model for Adaptive Routing

  1992influential reference
• Virtual-channel flow control

  1990cited by this paper

• Reactive Deadlock Avoidance Based on Focus Routing Graph Classification for Triplet-Based Architecture Network-on-Chip

  2026cites this paper
• Steered Bubble: An Interposer-based Deadlock Recovery Algorithm for Multi-chiplet Systems

  2024cites this paper
• Dynamic Fault Tolerance Approach for Network-on-Chip Architecture

  2024cites this paper
• On chip network with increased performance for efficient wireless communication

  2023cites this paper
• A multi-criteria decision based on adaptive routing algorithms with discrete operators for on-chip networks

  2022cites this paper
• Deflection routing mechanism using BLESS and BBUS NoC

  2021cites this paper
• ParRouting: An Efficient Area Partition-Based Congestion-Aware Routing Algorithm for NoCs

  2020cites this paper
• Fault Tolerance and Reliability for Partially Connected 3D Networks-on-Chip

  2019cites this paper
• FL-RuNS: A High-Performance and Runtime Reconfigurable Fault-Tolerant Routing Scheme for Partially Connected Three-Dimensional Networks on Chip

  2019cites this paper
• First-Last: A Cost-Effective Adaptive Routing Solution for TSV-Based Three-Dimensional Networks-on-Chip

  2018cites this paper