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:
- 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.
- 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.
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).
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