Source-linked AI summary
MailRail: Mitigating Incast Congestion with User-Space, Node-Based Flow Control
Noel Gomillion, Lance Fletcher, Trevor Steil, Eun Jung Kim, Roger Pearce
TL;DR
Irregular GNN and MoE workloads create severe incast, while rank-based credit accounting becomes impractical as process density grows. MailRail combines asynchronous out-of-order messaging with user-space credit flow control that pools credits by node. Node-based control achieves up to 1132× speedup over unconstrained execution at 4096:1 adversarial incast, with minimal overhead or modest improvements on evaluated uniform and trace-replay workloads.
Problem
Incast from irregular workloads creates severe communication congestion, while rank-based credit accounting can fall below one usable buffer slot per sender as process density grows.
Source: §I · p. 1Method
MailRail combines asynchronous out-of-order messaging with user-space receiver-driven credit control, including shared per-node credit pools.
Source: §I · pp. 1–2Results
Up to 1132× speedup over unconstrained execution at an adversarial incast ratio of 4096:1, with minimal overhead or modest improvements on evaluated uniform and trace-replay workloads.
Source: §VI · p. 9Takeaways & Limitations
Shared node-level credits maintain credit availability when receiver memory slots fall below one per rank, with local ranks able to use available credits dynamically.
Source: §I · p. 1
Abstract
from arXiv · showhide
Irregular workloads, such as those stemming from Graph Neural Networks (GNNs) and Mixture-of-Experts (MoE) models, frequently induce severe incast congestion in large-scale parallel environments. Existing fabric-level congestion control mechanisms rely on reactive, link-level rate limiting that degrades overall throughput. While receiver-driven, credit-based flow control offers a proactive alternative, as process counts scale memory slots per rank fall below usable thresholds, rendering traditional rank-based accounting untenable. To address this challenge, we introduce MailRail, an out-of-order, asynchronous messaging framework, along with a novel user-space, node-based credit flow control system. By shifting credit accounting from individual processes to shared per-node pools, our proactive, fabric-agnostic approach maintains sufficient credit availability even as process density grows, enabling processes to dynamically utilize freed credits without waiting for receiver-side redistribution. Experimental evaluations demonstrate that node-based flow control achieves up to a 1132x speedup over unconstrained execution at an adversarial incast ratio of 4096:1 while adding minimal overhead on uniform workloads.
I. INTRODUCTION
Irregular GNN and MoE traffic creates severe many-to-few incast, while reactive fabric-level mitigation can degrade throughput and rank-based credits become impractical as process density grows. MailRail pairs asynchronous out-of-order messaging with user-space, receiver-driven credit control, including node-level shared pools, and reports strong gains on adversarial incast workloads.
I. INTRODUCTION
- GNN hub-node aggregation and popular MoE experts create many-to-few traffic spikes, while incast can stall communication and degrade system throughput.Incast congestion can leave compute and memory resources underutilized and drive throughput near zero.Source: §I · p. 1
- Existing incast mitigation is reactive and hardware-level, with sender rate limiting reported to degrade effective throughput.Receiver-driven credits offer a proactive alternative, but rank-based accounting can fall below one usable buffer slot per sender at high process densities.Source: §I · p. 1
- Node-based flow control pools credits per host, letting local ranks dynamically use available credits without waiting for receiver-side redistribution.Unlike receiver-side redistribution strategies, sender-side pooling reallocates available credits as local processes complete transfers.Source: §I · p. 1
- Up to 1132× speedup over unconstrained execution at an adversarial incast ratio of 4096:1; node-based control also sustains goodput under extreme incast and scales linearly with victim workload.The evaluation also reports consistent goodput at 4096:1.Source: §I · pp. 1–2
- The paper contributes two fabric-agnostic, user-space credit-control schemes, an adversarial incast benchmark, and an analysis of unconstrained incast sensitivity on Dane and Lynx.It also introduces an asynchronous API for out-of-order communication.Source: §I · p. 2
II. BACKGROUND
The background describes incast as a buffer-saturating many-to-few pattern and surveys fabric mechanisms that manage congestion through feedback, credits, or notifications. Their approaches differ in where congestion is detected and how senders are throttled.
II. BACKGROUND
- Incast rapidly saturates victim buffers, causing network backpressure, buffer bloat, and throughput collapse.Prior mitigation approaches predominantly use hardware-level or sender-side rate limiting.Source: §II · p. 2
1) Ethernet with RoCEv2:
- RoCEv2 uses PFC for link-level losslessness and DCQCN feedback to throttle senders, but its multi-RTT response can cause oscillations, buffer overruns, pause storms, and head-of-line blocking.DCQCN feedback uses ECN and Congestion Notification Packets.Source: 1) Ethernet with RoCEv2 · p. 2
2) Receiver-Driven Congestion Control for InfiniBand:
- InfiniBand hop-by-hop credits can be depleted by fan-in incast, cascading backpressure upstream and freezing uncongested flows.Receiver-driven paradigms instead grant transmission windows and credit tokens from the receiving host.Source: 2) Receiver-Driven Congestion Control… · p. 2
3) Ultra Ethernet Consortium:
- Ultra Ethernet Transport's RCCC targets last-hop incast by having the receiver track active senders and allocate bandwidth in microsecond slots via ACK CC packets.Source: 3) Ultra Ethernet Consortium · p. 2
4) Omni-Path Express (OPX):
- OPX uses in-fabric telemetry, flit-level credits, and backward notifications to throttle traffic to a congested endpoint while allowing traffic to uncongested recipients to continue.Per-virtual-lane credit accounting caps ingress data volume to prevent buffer overruns.Source: 4) Omni-Path Express (OPX) · p. 2
1) MPI Protocols:
The section contrasts handshake-based MPI protocols and existing credit allocation with the motivation for asynchronous communication. MailRail's interface uses nonblocking, out-of-order messaging, buffer-based sender backpressure, and user-managed quiescence.
1) MPI Protocols:
- MPI rendezvous and synchronous-send protocols require acknowledgment handshakes that add round-trip latency, although MPI Issend can overlap that delay with computation.Source: 1) MPI Protocols · p. 2
2) Flow Control for GASNet-EX:
- GASNet-EX ties per-process sending credits to receiver buffer space, initially underallocating credits and reallocating surplus to processes stalled by credit starvation.Source: 2) Flow Control for GASNet-EX · p. 2
C. Motivation
- Small asynchronous messages can cause congestion, buffer overflows, and out-of-memory errors; handshakes and receiver-side adjustments add delays, motivating proactive user-space traffic shaping.The passage describes node-based control as allocating credits naturally to active senders.Source: C. Motivation · p. 2
III. MAILRAIL INTERFACE
- MailRail offers one-sided, nonblocking asynchronous messages processed in arrival order, with a transport-agnostic data path and MPI-specific dependencies limited to initialization.The API does not provide synchronization, so user code must handle quiescence detection.Source: §III · pp. 2–3, Figure 1 · p. 3
A. Buffer Reservation and Sender-side Backpressure
- Applications reserve a send buffer before filling its payload; a null return signals buffer saturation, and cooperative polling interleaves reservation attempts with receives to drain incoming queues.The send operation is nonblocking and fire-and-forget.Source: A. Buffer Reservation and Sender-side… · p. 3
B. Zero-copy Receive and User-driven Progress
MailRail uses receive calls both to process incoming messages and to make runtime progress, including draining pending sends. Its MPI implementation uses nonblocking operations and reusable send and receive buffer pools.
B. Zero-copy Receive and User-driven Progress
- Nonblocking receive returns a pointer into MailRail's receive pool, and the application releases the buffer after processing; receive calls also drain deferred outbound sends.The API example describes interleaving receive calls with reservation attempts while waiting for a buffer.Source: B. Zero-copy Receive and User-driven… · p. 3, Figure 2 · p. 3, Figure 3 · p. 3
IV. MAILRAIL IMPLEMENTATION
- MailRail's implementation choices are intended to support experimentation across communication paradigms, with the described implementation centered on MPI.Source: §IV · p. 3
A. MailRail over MPI
- The MPI implementation uses nonblocking Isend and Irecv, processes messages in arrival order, and recycles dedicated send and receive buffers through pools.Environment variables configure datagram size, pool sizes, and maximum outstanding receive requests.Source: A. MailRail over MPI · pp. 3–4
B. Flow Control
MailRail regulates incast with receiver-driven credits tied to available receive-buffer slots, using either per-rank accounting or shared per-node pools. Node-based pooling reduces tracking memory and credit-return traffic while allowing local senders to draw on a collective quota.
B. Flow Control
- Both mechanisms tie credits to available receive-buffer slots, so senders transmit only when receiver capacity is available.If credits are unavailable, MailRail queues the send and returns control to the application; queue draining preserves FIFO order for messages to each target.Source: B. Flow Control · p. 4
1) Rank-Based Flow Control
- Rank-based flow control assigns each sender a static credit count tied to its reserved receive-buffer slots and tracks credits symmetrically at sender and receiver.Senders decrement credits on transmission; receivers return consumed credits after a configured threshold, either via a dedicated communicator or piggybacking.Source: 1) Rank-Based Flow Control · p. 4
C. Node-Based Flow Control
- Node-based flow control pools credits per node, letting local senders use credits freed by neighboring processes without receiver-side redistribution.Shared sender- and receiver-side counts are updated as messages are sent, received, and returned.Source: C. Node-Based Flow Control · p. 4
- On 112-core processors, node-based flow control uses 425× to 850× less memory than rank-based flow control and supports buffer pools smaller than one slot per rank.The reduction depends on whether credit entries use 4- or 8-byte bit widths.Source: C. Node-Based Flow Control · p. 4
- Aggregating credits at the node level can reduce inter-node credit updates by up to a factor of k, while intra-node updates use shared memory.The actual reduction depends on traffic distribution; fewer fine-grained control packets also reduce the risk of fabric congestion.Source: C. Node-Based Flow Control · pp. 4–5
V. EXPERIMENTATION
Experiments were run on the Dane supercomputer using 4 KiB datagrams and 64 ranks per node unless otherwise noted. Rank-based and node-based experiments used specified credit allocations and a return threshold of 2.
A. Hardware and Software
- Unless otherwise specified, experiments ran on Dane, a 1,544-node LLNL supercomputer with two 56-core Xeon Platinum 8480+ CPUs per node and Omni-Path networking.The system used TOSS4, PSM2, OpenMPI 4.1.2, and GCC 10.3.1.Source: A. Hardware and Software · p. 5
- Experiments generally used 4 KiB datagrams and 64 ranks per node, with 8 rank-based credits per receiving rank or 512 shared node-based credits per receiving node.Rank-based experiments used credit piggybacking.Source: A. Hardware and Software · p. 5
- The credit-return threshold was set to 2, so receivers returned credits after half of the senders’ credits were consumed.The threshold was chosen to reduce credit-return messages while combating credit starvation.Source: A. Hardware and Software · p. 5
B. Adversarial
The adversarial benchmark tests severe incast, and weak-scaling experiments compare flow control with unconstrained execution. Node-based flow control is strongest at high incast, though unconstrained goodput is an optimistic truncated estimate.
B. Adversarial
- The adversarial benchmark randomly selects victim processes and send order, and tests severely imbalanced communication with no compute.Weak scaling uses four victim ranks; the 12.8 MiB-per-rank experiment enables unconstrained runs through 4096 ranks, while the 128 MiB-per-rank comparison truncates unconstrained runs after 600 seconds.Source: B. Adversarial · p. 5, 1) Weak Scaling · pp. 5–6
1) Weak Scaling
- At up to 1024:1 incast, node-based speedups over unconstrained execution range from 149× to 4431×; rank-based speedups range from 156× to 1902×.For the 12.8 MiB-per-rank experiment, node-based runtime approximately doubles as workload doubles, while rank-based runtime nearly triples.Source: 1) Weak Scaling · p. 5, Table I · p. 6
- Direct unconstrained comparisons at larger scales are infeasible because runtimes grow sharply; reported truncated-goodput speedups are conservative estimates for flow control.The truncation favors unconstrained execution by excluding its latency tail.Source: 1) Weak Scaling · p. 6
- 287× to 1132× speedups over the unconstrained upper-bound goodput estimate, with node-based goodput declining only 14.9% from 128:1 to 4096:1 incast.The comparison spans 512 ranks at 128:1 and 16,384 ranks at 4096:1; unconstrained execution is truncated and omits its latency tail.Source: 1) Weak Scaling · p. 6, Figure 4 · p. 6
- Rank-based flow control is 153× to 456× faster than unconstrained execution, but its aggregate goodput drops 84% from 128:1 to 4096:1 incast.Unconstrained execution reaches only 0.05% to 0.01% of peak ingress throughput in the reported conditions.Source: 1) Weak Scaling · p. 6
2) Incast Degree Sensitivity:
A victim sweep varies incast severity at fixed scale and total data volume. Node-based flow control is most resilient under severe incast, while all methods perform similarly under more uniform traffic.
2) Incast Degree Sensitivity
- The sweep holds scale at 4096 ranks and aggregate data at 512 GiB while varying victims from 1 to 4096, moving from maximum incast to uniform traffic.Workload per victim rank doubles as the incast ratio increases.Source: 2) Incast Degree Sensitivity · pp. 6–7
- At 4096:1 and 2048:1 incast, node-based flow control achieves a 3.7× speedup over rank-based flow control.Node-based flow control grows more slowly than rank-based flow control after both begin growing linearly with workload at incast ratios of 64:1 and higher.Source: 2) Incast Degree Sensitivity · p. 7
- At 8:1 incast, node- and rank-based flow control are 15.8× and 10.8× faster than baseline; at 32:1, they are 512× and 391× faster.PSM2 timeout errors at 64 victims prevent unconstrained data collection beyond 128 victims.Source: 2) Incast Degree Sensitivity · p. 7
- With 1024, 2048, or 4096 victims, node-, rank-based, and unconstrained execution perform similarly; rank-based flow control is 1.47× to 1.66× faster than baseline.Node-based flow control is 1.06× to 1.58× faster than baseline in these more uniform cases.Source: 2) Incast Degree Sensitivity · p. 7
C. Histogram
The histogram benchmark finds that MailRail’s flow-control modes impose little overhead on uniform communication and outperform YGM across tested configurations. It evaluates weak-scaled, coalesced histogram traffic.
C. Histogram
- The weak-scaled histogram benchmark doubles table size with process count and gives each rank 67,108,864 entries, or 512 MiB.It coalesces 8-byte entries by receiver and runs 50 trials per configuration, discarding the first as warmup.Source: C. Histogram · p. 7
- All MailRail configurations show more than 2× speedup over YGM.The study notes that active-message and metadata overhead in YGM may explain the difference, but does not isolate those effects.Source: C. Histogram · p. 7
- Node-based overhead ranges from −6.7% at 4096 ranks to 4.8% at 1024 ranks, averaging −1.3%.Rank-based overhead ranges from −7.4% at 2048 ranks to 4.5% at 1024 ranks, averaging −1.84%.Source: C. Histogram · p. 7
D. Communication Trace Replay
MailRail replays YGM communication traces, which omit computation, across node counts at 112 ranks per node. Results vary by trace: Reddit sort is irregular, while triangle-counting communication is relatively uniform at the largest scale.
1) Reddit Sort Traces:
- For these traces, node-based flow control achieves 1.36×–6.91× speedup over unconstrained execution at larger rank counts, while rank-based flow control is nearly 4× worse at 14,336 ranks.Source: 1) Reddit Sort Traces · pp. 7–8
- At 14,336 ranks, 8.6% of Reddit sort sender-receiver pairs have no communication, leaving their preallocated credits unavailable to active pairs.The authors identify this as a potential source of rank-based credit starvation; node-based sharing avoids this limitation.Source: 1) Reddit Sort Traces · p. 8
- At 14,336 ranks, rank-based flow control averaged 17.8–26.4 million credit-return messages per trial, versus 116,922–435,055 for node-based flow control, reducing congestion from control messages.Source: 1) Reddit Sort Traces · p. 8
2) Triangle Counting Traces:
- Triangle-counting traces deliver 38–41.5 GB to each rank at 14,336 ranks, indicating relatively uniform communication at that scale.The replay uses weak scaling with R-MAT graph traces.Source: 2) Triangle Counting Traces · p. 8
- At 14,336 ranks, node- and rank-based flow control exhibit about 10× speedup over unconstrained execution, suggesting benefits extend beyond extreme incast workloads.At lower rank counts, both achieve 1.07×–1.53× speedup.Source: 2) Triangle Counting Traces · p. 8
E. OPX Comparison
On evaluated workloads, node-based flow control delivers substantial gains for adversarial incast and minimal overhead or modest improvements on uniform and trace-replay workloads. On Lynx, rank-based flow control also completes tests at high rank counts despite unconstrained OOM errors.
E. OPX Comparison
- At 14,336 ranks, triangle-counting traces deliver 38–41.5 GB to each rank, indicating relatively uniform communication.The OPX comparison includes flow-control performance on replayed YGM traces.Source: Figure 10 · p. 9, Figure 9 · p. 9
- On Lynx, rank-based flow control achieves 3× speedup at 128:1 incast and 2.3× at 512:1 incast.At 4096:1 incast, its goodput is approximately the same as unconstrained execution at 512:1.Source: E. OPX Comparison · p. 9
- Rank-based flow control completes execution on 49,152 ranks at a 12,288:1 incast ratio, though trials take about 2.75 hours.Unconstrained execution on Lynx experiences OOM errors beginning at 1,024 ranks.Source: E. OPX Comparison · p. 9, Figure 11 · p. 9
VI. SUMMARY AND CONCLUSION
- Up to 1132× speedup over unconstrained execution is achieved by node-based flow control at an adversarial incast ratio of 4096:1.The conclusion also reports minimal overhead or modest improvements on evaluated uniform and real-world communication patterns.Source: §VI · p. 9