Generalized Fault-Tolerance Topology Generation for Application-Specific Network-on-Chips

The network-on-chips (NoCs)-based communication architecture is a promising candidate for addressing communication bottlenecks in many-core processors and neural network processors. In this article, we consider the generalized fault-tolerance topology generation problem, where the link (physical channel) or switch failures can happen, for application-specific NoCs (ASNoCs). With a user-defined maximum number of faults, <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula>, we propose an integer linear programming (ILP)-based method to generate ASNoC topologies, which can tolerate at most <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> faults in switches or links. Given the communication requirements between cores and their floorplan, we first propose a convex-cost-flow-based method to solve a core mapping (CM) problem for building connections between the cores and switches. Second, an ILP-based method is proposed to solve the routing path allocation (PA) problem, where <inline-formula> <tex-math notation="LaTeX">$K+1$ </tex-math></inline-formula> switch-disjoint routing paths are allocated for every communication flow between the cores. Finally, to reduce switch sizes, we propose to share the switch ports for the connections between the cores and switches and formulate the port sharing problem as a clique-partitioning problem, which is solved by iteratively finding a set of the maximum cliques. Additionally, we propose an ILP-based method to simultaneously solve the CM and routing PA problems when only physical link failures are considered. The experimental results show that the power consumption of fault-tolerance topologies increases almost linearly with <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> because of the routing path redundancy for fault tolerance. When both switch faults and link faults are considered, port sharing can reduce the average power consumption of fault-tolerance topologies with <inline-formula> <tex-math notation="LaTeX">$K=1$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$K=2$ </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">$K=3$ </tex-math></inline-formula> by 18.08%, 28.88%, and 34.20%, respectively. When considering only the physical link faults, the experimental results show that compared to the fault-tolerant topology generation (FTTG) algorithm, the proposed method reduces power consumption and hop count by 10.58% and 6.25%, respectively; compared to the de Bruijn Digraph (DBG)-based method, the proposed method reduces power consumption and hop count by 21.72% and 9.35%, respectively.

• Publication year

  2019

• Venue

  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

• Publication date

  2019-08-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/TCAD.2019.2952134arXiv 1908.00165
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Area Constrained Performance Optimized ASNoC Synthesis with Thermal‐aware White Space Allocation and Redistribution

  2018cited by this paper
• Neu-NoC: A high-efficient interconnection network for accelerated neuromorphic systems

  2018cited by this paper
• Lagrangian relaxation-based routing path allocation for application-specific network-on-chips

  2017influential reference
• Design Methodology of Fault-Tolerant Custom 3D Network-on-Chip

  2017influential reference
• Clustered Fault Tolerance TSV Planning for 3-D Integrated Circuits

  2017cited by this paper
• Floorplanning and Topology Synthesis for Application-Specific Network-on-Chips with RF-Interconnect

  2016cited by this paper
• A Deadlock-Free and Connectivity-Guaranteed Methodology for Achieving Fault-Tolerance in On-Chip Networks

  2016cited by this paper
• Fault-Tolerant Topology Generation Method for Application-Specific Network-on-Chips

  2015influential reference
• ORION3.0: A Comprehensive NoC Router Estimation Tool

  2015influential reference
• TrueNorth: Design and Tool Flow of a 65 mW 1 Million Neuron Programmable Neurosynaptic Chip

  2015cited by this paper
• Deterministic Synthesis of Hybrid Application-Specific Network-on-Chip Topologies

  2014cited by this paper
• A spare router based reliable Network-on-Chip design

  2014cited by this paper
• Neurogrid: A Mixed-Analog-Digital Multichip System for Large-Scale Neural Simulations

  2014cited by this paper
• A fault tolerant NoC architecture using quad-spare mesh topology and dynamic reconfiguration

  2013cited by this paper
• A VLSI architecture for enhancing the fault tolerance of NoC using quad-spare mesh topology and dynamic reconfiguration

  2013cited by this paper
• Floorplanning and Topology Synthesis for Application-Specific Network-on-Chips

  2013cited by this paper
• CusNoC: Fast Full-Chip Custom NoC Generation

  2013cited by this paper
• Cluster Generation and Network Component Insertion for Topology Synthesis of Application-Specific Network-on-Chips

  2012cited by this paper
• Application-Specific Network-on-Chip synthesis with topology-aware floorplanning

  2012cited by this paper
• Application-specific topology generation algorithms for network-on-chip design

  2012cited by this paper
• ATree-based topology synthesis for on-chip network

  2011cited by this paper
• On the design and analysis of fault tolerant NoC architecture using spare routers

  2011cited by this paper
• Floorplanning and topology generation for application-specific Network-on-Chip

  2010cited by this paper
• SunFloor 3D: A tool for Networks On Chip topology synthesis for 3D systems on chips

  2009cited by this paper
• A Fault Tolerant NoC Architecture for Reliability Improvement and Latency Reduction

  2009cited by this paper
• Outstanding Research Problems in NoC Design: System, Microarchitecture, and Circuit Perspectives

  2009cited by this paper
• Application-specific Network-on-Chip architecture synthesis based on set partitions and Steiner Trees

  2008cited by this paper
• A fault-aware dynamic routing algorithm for on-chip networks

  2008cited by this paper
• Linear programming based techniques for synthesis of network-on-chip architectures

  2006cited by this paper
• Designing Application-Specific Networks on Chips with Floorplan Information

  2006cited by this paper
• A survey of research and practices of Network-on-chip

  2006cited by this paper
• Designing reliable systems from unreliable components: the challenges of transistor variability and degradation

  2005cited by this paper
• Principles and Practices of Interconnection Networks

  2004cited by this paper
• Trends and Challenges in VLSI Circuit Reliability

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

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

  2001cited by this paper
• Network Flows: Theory, Algorithms, and Applications

  1993cited by this paper
• A branch and bound algorithm for the maximum clique problem

  1990cited by this paper

• Pipelined Scheduling and Communication Synthesis for Application-Specific Networks-on-Chip

  2025cites this paper
• Multiobjective piecewise regressive elitism spotted hyena optimized mapping for 3D NoC architecture design

  2023cites this paper
• Systematic Construction of Deadlock-Free Routing for NoC Using Integer Linear Programming

  2023cites this paper
• Fault-Tolerant Core Mapping for NoC based architectures with improved Performance and Energy Efficiency

  2022influential citation
• Synthesizing Brain-Network-Inspired Interconnections for Large-Scale Network-on-Chips

  2021cites this paper
• A Deterministic-Path Routing Algorithm for Tolerating Many Faults on Very-Large-Scale Network-on-Chip

  2020cites this paper
• Synthesizing A Generalized Brain-inspired Interconnection Network for Large-scale Network-on-chip Systems

  2020cites this paper
• Fault-Tolerant Application-Specific Network-on-Chip Design using Discrete Particle Swarm Optimization

  2019cites this paper