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

Patrick Iff, Luca Oertig, Andrin Weber, Luca Benini, Torsten HoeflerarXiv 2026 · arXiv

TL;DR

PAISF introduces a novel selection function that guarantees in-order packet delivery in irregular chiplet and wafer-scale networks without the need for expensive reorder buffers. By using entropy-based hashing and localized adaptivity, it boosts saturation throughput by 15.2% and reduces energy consumption by 12.1% compared to state-of-the-art baselines.

What Problem Does This Paper Address?

As we push the limits of Moore’s Law, the industry is shifting toward chiplet-based systems and wafer-scale integration. These systems often rely on irregular network topologies rather than the traditional 2D mesh. A major headache in these networks is ensuring in-order packet delivery.

Many applications require packets to arrive in the order they were sent. If the network doesn't guarantee this, every endpoint needs a Reorder Buffer (ROB). ROBs are "area-hungry" and power-intensive; if they fill up, the system must drop and retransmit packets, tanking performance.

Current solutions are lackluster:

  1. Deterministic Routing: Simple and in-order, but it can't exploit multiple paths to avoid congestion, leading to poor throughput.
  2. Adaptive Routing: Great for performance, but it frequently delivers packets out-of-order.
  3. The "Multi" Layer: A middle-ground approach that uses disjoint paths but is prone to complex message-level deadlocks (see Figure 2 below).
Fig. 2: (§III-C) Example of a message-level deadlock in Multi.

Methods

The authors propose two new Selection Functions (SFs): ISF (In-order Selection Function) and PAISF (Partially Adaptive ISF).

  • ISF (The Foundation): Every packet carries an "entropy" value in its header. Each router uses a hash function to map this entropy to one of the valid next hops provided by the routing function. If all packets in a message share the same entropy, they are guaranteed to follow the same path and arrive in order. If a message doesn't require ordering, the sender can assign random entropy to each packet to exploit path diversity.
  • PAISF (The Adaptive Upgrade): PAISF adds a layer of intelligence at the injection router. It looks at current congestion (via credit-based flow control) and picks the "best" first hop. To maintain ordering, the router "remembers" this choice for that specific entropy value. Subsequent routers then use the standard ISF hashing to complete the path.

The logic for these functions is designed to be hardware-efficient, requiring only simple XOR gates and small multipliers, adding negligible area overhead to the router.

Logic flow for RND, ADP, DET, and the proposed ISF and PAISF selection functions.

Datasets

The researchers evaluated their approach using the BookSim2 cycle-accurate simulator across a massive range of scenarios:

  • Topologies: 18 different topologies across three domains: Networks-on-Chip (NoC), Inter-Chiplet Interconnects (ICI), and Wafer-Scale Integration (WSI).
  • Synthetic Workloads: Uniform, Random Permutation, and Asymmetric traffic patterns.
  • Real-World Traces: CPU traces (Netrace/blackscholes) and GPU traces (training a Llama-7B model generated via the ATLAHS toolchain).

Key Insights and Ideas

  • Entropy as a Control Knob: The beauty of this approach is that the sender decides the trade-off. By controlling the entropy bits, the application can choose between strict ordering or maximum performance on a per-message basis.
  • Partial Adaptivity is Enough: Full adaptivity is the enemy of ordering. By restricting adaptivity to the first hop (or the first time a router sees a specific entropy value), PAISF achieves significant load balancing without the reordering chaos.
  • Deadlock Immunity: Unlike the "Multi" approach, PAISF does not require destination-side stalling to reorder packets. This eliminates the risk of message-level deadlocks, making the network much more robust.

Key Results

Compared to the best existing in-order delivery methods (like LASH-TOR or the "Multi" layer), PAISF delivers impressive gains:

  • Throughput: Increases saturation throughput by 15.2% on average.
  • Energy: Reduces energy per transmitted packet by 12.1%.
  • Latency: Reduces latency under load by 11.3%.
  • The "Tax": These gains come at a small cost—a 3.3% increase in zero-load latency, caused by the additional arbitration cycles needed for hashing.
  • Efficiency: Ablation studies showed that just 3 entropy bits are sufficient to reach peak performance in most topologies.
Overview of strategies to achieve in-order delivery, highlighting the path diversity of PAISF.

Limitations and Future Work

While PAISF excels in NoC and ICI environments, its benefits are more muted in Wafer-Scale (WSI) systems (only a 7.8% throughput gain). The authors attribute this to the massive diameter of WSI networks; adapting only at the "first hop" isn't enough to mitigate congestion that occurs many hops downstream.

Future work could explore "multi-hop adaptivity"—finding ways to allow routers further down the path to change a packet's route based on local congestion without breaking the global arrival order. Additionally, while PAISF handles faults well, it is currently outperformed by LASH-TOR in extremely high-fault scenarios, suggesting room for improvement in network resilience.

Summary updated

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.
BibTeX
@misc{iff2026paisf,
  author = {Patrick Iff and Luca Oertig and Andrin Weber and Luca Benini and Torsten Hoefler},
  title = {{PAISF: A Partially Adaptive In-Order Selection Function for Routing in On-Chip, Inter-Chiplet, and Wafer-Scale Networks}},
  year = {2026},
  eprint = {2611.22772},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22772},
}
Figure