CS Paper Radar

LASH-PAT: Deadlock-Free Adaptive Shortest-Path Routing for Inter-Chiplet Interconnects

Patrick Iff, Torsten Hoefler

cs.AR cs.NI ·submitted 2026-11-17 15:31 UTC · v1

Abstract

With the slowdown of transistor scaling, chipletbased systems, and in particular chiplet-based wafer-scale integration, have emerged as a promising approach to sustain growth in computing capability per cost for modern processors and accelerators. In recent years, many specialized inter-chiplet interconnect topologies have been proposed. In these topologies, the simple, well-established, and deadlock-free dimension-order routing scheme is not applicable due to its reliance on regular mesh structures. In this work, we study routing in these recently proposed inter-chiplet interconnect topologies by categorizing and evaluating nine deadlock-free routing functions for irregular topologies known from data center networking in this new context. This reveals a trade-off between turn-based routing, which enables path diversity, and layered routing, which ensures shortest-path delivery. To resolve this trade-off, we propose LASH-PAT, a routing function that extends layered shortestpath routing with adaptive path diversity. LASH-PAT supports multiple shortest paths and dynamically selects among them based on local congestion while preserving deadlock freedom. When compared to the best-performing baseline routing function for each combination of topology, traffic pattern, and evaluated metric, LASH-PAT improves throughput by 21.15% and reduces energy per packet by 12.77%, while providing latency comparable to the lowest-latency baseline routing function.

Closest papers

Nearest neighbours by meaning across the whole index.

PAISF: A Partially Adaptive In-Order Selection Function for Routing in On-Chip, Inter-Chiplet, and Wafer-Scale Networks

cs.AR cs.NI ·2026-11-17 ·Patrick Iff, Luca Oertig, Andrin Weber, Luca Benini, Torsten Hoefler
similarity 0.74
Abstract

The growing number of compute elements per chip, along with advances such as chiplet systems and wafer-scale integration, drives the need for scalable and efficient routing algorithms for irregular topologies. A routing algorithm consists of a routing function (RF) that ensures deadlock freedom and a selection function (SF) that avoids congestion and, in some cases, guarantees in-order packet delivery. We propose two novel SFs for irregular topologies, ISF and PAISF, which ensure in-order delivery by hashing a packet's entropy value to determine its path. Packets with the same entropy follow the same path and arrive in order. Compared to a deterministic RF, a deterministic SF, and Multi, three alternative in-order delivery strategies, (PA)ISF improves throughput by 15.2% and reduces energy per packet and latency under load by 12.1% and 11.3%, at the cost of a zero-load latency increase by 3.3% on average across workloads and topologies.

0.24

The Road Less Traveled: Congestion-Aware NoC Placement and Packet Routing for FPGAs

cs.AR ·2026-08-18 ·Soheil Gholami Shahrouz, Vaughn Betz
publishedcode/data similarity 0.69
Abstract · 10 pages, 5 figures, 3 tables. Published at the 2024 34th International Conference on Field-Programmable Logic and Applications (FPL), Torin…

To help scale to ever-larger and more complex designs, recent FPGA architectures now integrate network-on-chips (NoCs). NoCs help transfer high-bandwidth data over long distances within the chip without using scarce low-delay long routing wire segments. While NoC-enhanced FPGAs aid system integration and design reuse, they also complicate FPGA computer-aided design (CAD) flows by introducing new constraints and metrics. Placement and routing need to optimize NoC metrics like latency and bandwidth utilization and avoid link oversubscription (congestion), while simultaneously optimizing the programmable routing resource usage of the design modules attached to NoC routers. In this work, we develop several new approaches to reduce NoC congestion while minimizing the impact on other design metrics. First, we incorporate a NoC link congestion cost into the placement engine of the open-source CAD flow, versatile place & route (VPR). Second, we integrate turn model NoC routing algorithms into the placement engine to leverage path diversity to further reduce congestion. On average over a suite of 29 benchmarks, combining placement congestion modeling with turn model packet routing reduces NoC congestion by 90.7% at the cost of increasing aggregate bandwidth demand by 4%. In cases where the enhanced placement engine and NoC routing fail to fully resolve congestion, we formulate NoC routing as a Boolean satisfiability (SAT) problem. This approach yields significant additional improvements; the combined algorithm reduces congestion by 95.1% compared to the baseline placement. Finally, we enhance the reinforcement learning (RL) agent in VPR's placement engine by introducing a NoC-aware move type, resulting in an 8.8% reduction in wirelength on designs that make extensive use of the NoC.

0.50

Rethinking Adaptive Routing on Dragonfly

cs.NI ·2026-11-09 ·Ziyu Wang, Dezun Dong, Fei Lei
similarity 0.66
Abstract · 12 pages, 9 figures. Preliminary version. An updated final version will follow, and the source code will be open-sourced

The Dragonfly topology is widely deployed in leading supercomputers, where adaptive routing is crucial for high-performance interconnection. Despite years of research, a dilemma remains: state-of-the-art adaptive routing algorithms achieve excellent performance but demand hardware budgets far beyond what real router chips can afford -- prohibitive buffers, logically dependent floating-point operations, or exhaustive path-set traversals -- whereas realizable algorithms deliver unsatisfactory performance. Furthermore, existing algorithms fail to exploit the abundant almost-minimal paths in Dragonfly: when only the local channels of a minimal path are congested, they reroute packets to significantly longer global non-minimal paths, wasting global bandwidth and increasing latency. To address both limitations, we analyze intra-group path contention and propose the Decoupled Incremental Adaptive Routing (DIAR) algorithm, which decouples routing into global path selection at the source and incremental local detours onto almost-minimal paths, guaranteeing deadlock freedom without additional virtual channels, escape rings, or turn models. Requiring only a few comparators, shifters, adders, and multiplexers, DIAR reduces buffer overhead by up to four orders of magnitude compared with state-of-the-art algorithms, while achieving comparable or superior performance across all evaluated scenarios: relative to the strongest realizable adaptive routing algorithm in each scenario, DIAR improves saturation throughput by up to 30.0% across synthetic traffic patterns and improves performance by up to 34.9% (13.2% on average) across HPC workloads.

0.30

A Global Routing Method for Electronic Circuit Design Integrating Flow Matching and Constrained A*

eess.SY ·2026-11-01 ·Sanghoon Jin, Sumin Lee, Namwoo Kang
similarity 0.65
Abstract

Global routing is a fundamental issue in the design of electronic circuits, as it directly relates to the efficiency, reliability, and compactness of the overall layout of integrated systems. As the demand for higher functionality and reliability within a limited chip area increases, the importance of routing as a design consideration has never been greater. Efficient global routing optimization techniques are therefore required to connect all pins with minimal wirelength (WL), while avoiding congestion and interference across multiple nets within the design space. As the number of nets to be routed increases, global routing inherently suffers from a combinatorial explosion in the design space, making it increasingly difficult to obtain feasible solutions. In this paper, we focus on solving constrained global routing problems based on a heuristic A*-based framework. Based on this concept, a hybrid approach is proposed by integrating constrained A* with flow matching (FM). The method utilizes FM to construct a global cost map that captures routing tendencies across the design space, which is then used to guide the constrained A* search process. This enables efficient exploration of the solution space while satisfying routing constraints. Experimental results demonstrate that the proposed method achieves comparable WL and via usage to baseline methods while maintaining constraint satisfaction across a wide range of scenarios. Notably, the framework shows strong capability in solving complex routing instances that are difficult to handle using conventional approaches. Additionally, the method shows robust generalization performance across different problem sizes and net configurations.

0.27

DiffRouter: A Differentiable Routing Framework for UltraScale FPGAs

cs.AR ·2026-10-24 ·Xiaohan Gao, Zhili Xiong, Yusu Wang, David Z. Pan
published similarity 0.62
Abstract

Routing has become a major bottleneck in large-scale FPGA design flows, where traditional routers rely on sequential net-by-net processing and rip-up-reroute heuristics. This inherent sequentialism limits parallelism, leads to suboptimal utilization of routing resources, and significantly increases runtime on modern FPGAs. This paper introduces DiffRouter, the first differentiable, gradient-based FPGA routing framework with GPU acceleration. By lifting routing into a continuous optimization space, DiffRouter enables highly concurrent routing and improved global optimality before projecting solutions back onto the discrete fabric. The framework consists of three key stages: (1) Resource-pruned preprocessing, which extracts compact routing variables per net to reduce memory footprint and problem complexity; (2) Differentiable global routing via gradient descent, which formulates routing as a Lagrangian-relaxed optimization that minimizes wirelength while iteratively enforcing connectivity and congestion constraints as relaxed terms; and (3) Postprocessing, which maps the continuous wire distributions to a valid UltraScale routing solution and completes solutions by detailed routing. Experiments on the FPGA 2024 Routing Contest benchmarks show that DiffRouter outperforms state-of-the-art parallel routers, achieving over 5x speedup over RWRoute and 2x over Vivado, and running 18% faster than the state-of-the-art academic FPGA router Potter while delivering competitive critical path wirelength.

0.28

Assessing Triple Modular Redundancy for Wide-Link, Low-Latency NoC Routers: Reliability and Physical Design Challenges

cs.AR ·2026-08-21 ·Chen Wu, Michael Rogenmoser, Luca Benini, Angelo Garofalo
publishedbenchmark similarity 0.62
Abstract · 6 pages, 8 figures, 1 table. Accepted at the 2026 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Syst…

Protecting the Network-on-Chip (NoC) of physical-AI tile-based accelerators deployed in harsh environments against single-event effects (SEEs) is paramount for preventing NoC failures that can lead to deadlocks and silent data corruption (SDC). Prior work on reliable NoCs has largely focused on narrow links (e.g., 32-bit), deeply pipelined routers, and single-event upsets (SEUs). However, the state of the art has evolved toward low-latency NoC routers with ultra-wide links, implemented on advanced technology nodes and operating at frequencies above 1 GHz. We evaluate the cost and reliability trade-offs of implementing Triple Modular Redundancy (TMR) at three granularities (coarse, state-only, and full) for a 2-cycle-latency NoC router with 512-bit wide links. We carry out RTL-to-GDSII physical design in TSMC 7nm technology, as well as both RTL- and netlist-level SEU and SET fault injection campaigns. We evaluate the three TMR approaches in terms of reliability, cost, and physical design strategies, further extending the assessment from a standalone router to a full AI acceleration tile. Our results show that state-only and coarse-grained TMR do not provide sufficient protection against SEEs, whereas full TMR eliminates all observed failures across more than one million injected faults per experiment. Although the standalone full-TMR router incurs a 7.04x area overhead, this cost is drastically amortized once integrated into a complete AI accelerator tile with processors and local L1 memories: the same design adds only 16.8% area and 15.2% power consumption under a GEMM benchmark at the system level, with the critical path of the tile entirely unaffected. These results demonstrate that advanced technology nodes provide sufficient routing capacity to make full TMR a practical and deployable solution for protecting NoCs in Physical AI systems operating in harsh environments.

0.35

Budgeted Express-Mesh: Traffic-Aware Link Placement and Deadlock-Free Adaptive Routing

cs.AR cs.NI ·2026-09-15 ·Li Cao, Jingyuan Ma
code/data similarity 0.61
Abstract · 14 pages, 14 figures, 9 tables. Code and artifacts: https://github.com/tsjyma/Express_mesh

We present Budgeted Express-Mesh, a topology-routing co-design that adds a small number of traffic-aware express links under a fixed wire budget. An ASPL-based greedy placement is refined by simulation-guided annealing, while packets use committed top-K routes selected from delayed express-link congestion and reservation signals. Across four synthetic workloads, optimized placements consistently improve high-load throughput over Mesh and random placement, and annealing further improves Greedy. The gains persist under delayed quantized congestion information, longer express-link latency, multi-flit packets, and a 16-by-16 heterogeneous workload.

0.39

A Unified Interconnection Network for Chiplet-Based Scaling of the BrainScaleS Neuromorphic System

cs.AR ·2026-09-11 ·Robin Heinemann, Johannes Schemmel
similarity 0.61
Abstract

The BrainScaleS-2 (BSS-2) neuromorphic architecture combines analog emulation of spiking neural network (SNN) primitives with tightly coupled ADCs and digital processing units. These analog SNN primitives are fixed hardware resources that cannot be multiplexed, limiting the emulated network size to the number of physical hardware copies. To overcome the challenges of scaling analog designs, chiplet-based designs offer a promising approach with cost and flexibility advantages over monolithic scaling. Implementing a chiplet-based BSS-2 architecture requires an interconnection network that handles two distinct classes of traffic: error-tolerant traffic such as spikes and error-intolerant traffic like configuration data or data exchanged by the processing units. This work presents the design of a routing chiplet for the BSS-2 architecture that enables interconnection of multiple BSS-2 units in a 2D mesh topology. Both traffic classes are multiplexed over a single wide parallel die-to-die link. Exploiting the fault tolerance of SNNs, spikes are transmitted unsecured and synchronously, with the arrival time on the receiving side directly determining the pre-synaptic time of the spike. Conversely, error-intolerant data transmission is secured by a point-to-point Automatic Repeat Request protocol and uses credit-based flow control. These design choices are validated in simulation, where the proposed design can sustain $95\,\%$ link bandwidth utilization for the use case of surrogate gradient training across a wide range of spike-to-secured traffic ratios under a $1 \times 10^{-10}$ bit error rate with little impact on spike timing jitter.

0.30