Bypass-Enabled Topology-Agnostic Multicast Router for Fault-Tolerant Network-on-Chips
TL;DR
BEAM is introduced, which integrates three key components: a sequential topology embedding algorithm that employs a heuristic search with Warnsdorff’s rule to construct a near-Hamiltonian path, abstracting any arbitrary physical network into a unified logical sequence, enabling concurrent packet forwarding to improve throughput and fairness.
Abstract
While dynamic rerouting represents the predominant fault-tolerant strategy for Network-on-Chip (NoC) multicast communications, circumventing permanent hardware failures inevitably concentrates detour traffic at specific intermediate nodes. Rerouting exacerbates pre-existing traffic skew and accelerates hardware aging — a problem that existing solutions fundamentally fail to address. Furthermore, as modern application-specific system-on-chips (SoCs) increasingly adopt irregular topologies, an effective fault-tolerant architecture must extend to such custom topologies. To address these challenges, we introduce BEAM, which integrates three key components: (1) A sequential topology embedding algorithm that employs a heuristic search with Warnsdorff’s rule to construct a near-Hamiltonian path, abstracting any arbitrary physical network into a unified logical sequence. (2) A neighbor-aware route distribution scheme that partitions multicast destinations into independent subsets based on router indices, enabling concurrent packet forwarding to improve throughput and fairness. (3) A lightweight bypass router architecture featuring a dedicated fault control unit that instantly redirects incoming packets to a physical bypass channel upon fault detection, circumventing faulty components without the overhead of full structural redundancy. Evaluation results demonstrate that under two fault conditions on different 64-node topologies, BEAM achieves 20.4% higher saturation throughput and 16.0% higher fairness on average than the evaluated schemes, with negligible hardware overhead.