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:
- Deterministic Routing: Simple and in-order, but it can't exploit multiple paths to avoid congestion, leading to poor throughput.
- Adaptive Routing: Great for performance, but it frequently delivers packets out-of-order.
- The "Multi" Layer: A middle-ground approach that uses disjoint paths but is prone to complex message-level deadlocks (see Figure 2 below).
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.
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.
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