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

Patrick Iff, Torsten HoeflerarXiv 2026 · arXiv

As Moore’s Law slows down, the semiconductor industry is pivoting toward chiplet-based systems. Instead of one massive, expensive chip, we’re building systems from smaller "chiplets" connected on a common substrate. This shift has birthed a variety of specialized, often irregular, interconnect topologies. However, these new shapes break our old, reliable routing algorithms like Dimension-Order Routing (DOR), which only work on neat, regular grids.

In their paper, Patrick Iff and Torsten Hoefler from ETH Zurich introduce LASH-PAT, a new routing function designed to squeeze every drop of performance out of these irregular inter-chiplet interconnects (ICIs).

TL;DR

LASH-PAT is a deadlock-free routing algorithm for irregular chiplet networks that combines the low latency of shortest-path routing with the high throughput of adaptive path diversity. By dynamically selecting between multiple shortest paths, it improves throughput by 21% and reduces energy consumption by 12% compared to the best existing baseline methods.

What Problem Does This Paper Address?

Routing in irregular networks has historically faced a frustrating trade-off:

  1. Turn-based routing: These methods (like Up/Down) are great at providing multiple paths to a destination, which helps avoid congestion (path diversity). However, they often force packets to take long, "non-shortest" detours to avoid deadlocks.
  2. Layered routing: These methods (like LASH) guarantee packets always take the shortest path, which is great for latency. But they typically only provide a single path, meaning the network hits a "saturation" wall very quickly when traffic gets heavy.

In the world of high-performance AI accelerators and wafer-scale systems, we need both: the speed of shortest paths and the capacity of multiple paths.

Methods

LASH-PAT (Layered Adaptive Shortest-Path) bridges this gap through two primary mechanisms:

  • M1: Adaptive Path Diversity: Unlike traditional layered routing that picks one path and sticks to it, LASH-PAT’s routing tables store multiple next-hop candidates for every destination. At runtime, the router looks at local congestion (using credit-based flow control) and picks the least busy path.
  • M2: Fine-Grained Layer Assignment: To prevent deadlocks (where packets wait on each other in a circular loop), LASH-PAT uses Virtual Channels (VCs) to create "layers." It builds a Channel Dependency Graph (CDG) at the level of individual VCs rather than physical links. This allows for much more flexible path assignments, ensuring deadlock freedom while using fewer VCs than previous methods.

The algorithm works in two phases: an offline phase that uses a modified Dijkstra’s algorithm to pre-calculate these multi-path routing tables, and an online phase where routers make split-second adaptive decisions.

Fig. 1: (§IV-B) An example of LASH-PAT routing in a 5-router ring network.

Datasets

The researchers evaluated LASH-PAT across a massive range of scenarios:

  • 10 Topologies: Including standard Meshes and Toruses, as well as specialized ICI designs like Hypercube, Kite, and ButterDonut.
  • Synthetic Workloads: Random Uniform and Random Permutation traffic patterns.
  • Real-World Traces: CPU traces (PDE-based financial applications) and GPU traces (training the Llama-7B large language model).
  • Baselines: Nine different state-of-the-art routing functions for irregular networks.

Key Insights and Ideas

  • Diversity is King for Throughput: The biggest "aha" moment is how much throughput is left on the table by single-path routing. As shown in the evaluation, just adding one or two additional shortest paths can more than double the saturation throughput.
  • Shortest Paths are Essential for Latency: While turn-based routing can be robust, the "latency tax" of non-shortest paths is significant. LASH-PAT proves you don't have to pay that tax to get high throughput.
  • Chiplets Change the Constraints: In traditional Network-on-Chip (NoC) design, routing table area is a huge concern. However, chiplets are relatively large. LASH-PAT’s routing tables (about 20 Kbit) take up a negligible 0.001–0.003 $mm^2$ of silicon—a tiny price to pay for a 20% performance boost.

Key Results

LASH-PAT consistently outperformed all nine baselines:

  • Throughput: Achieved 21.15% higher throughput on average than the best-performing baseline for any given topology. Against the best turn-based baseline (SCB), it was 31.92% better.
  • Energy: Reduced energy per packet by 12.77% on average. By moving data more efficiently and avoiding congestion, the system spends less time idling and wasting power.
  • Latency: Maintained zero-load latency comparable to the best specialized low-latency algorithms (like DFSSSP).
Saturation throughput vs. number of additional paths

Limitations and Future Work

While LASH-PAT is highly effective, the authors note a few areas for further exploration:

  • Routing Table Size: While negligible for current chiplets, the table size grows with the number of routers and VCs. Very large-scale systems (thousands of nodes) might require table compression techniques.
  • Fault Tolerance: The current implementation assumes a static, healthy network. Extending the offline table generation to handle dynamic link failures in real-time would be a valuable next step.
  • Global Congestion: LASH-PAT currently makes decisions based on local congestion. Integrating global congestion signals could potentially push throughput even higher.

For engineers building the next generation of AI hardware, LASH-PAT offers a compelling blueprint for interconnects that are both fast and incredibly efficient.

Summary updated

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.
BibTeX
@misc{iff2026lash,
  author = {Patrick Iff and Torsten Hoefler},
  title = {{LASH-PAT: Deadlock-Free Adaptive Shortest-Path Routing for Inter-Chiplet Interconnects}},
  year = {2026},
  eprint = {2611.22937},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22937},
}
Figure