Source-linked AI summary
MeshReduce-U: Compiler-Guided Communication Reduction for Irregular Neural Reductions on Mesh NoCs
Amirreza Khorasanian
TL;DR
Irregular neural reductions create communication-heavy many-to-one traffic, while conventional mappers generally optimize a fixed communication graph. MeshReduce-U rewrites reducible carrier graphs before placement and routing, combines structural reduction with capacity-aware placement and fused routing, and evaluates latency and traffic separately. Across lowerable neural and synthetic workloads, the framework improves the reported communication metrics, while its replay model and workload scope define important validation boundaries.
Problem
Irregular neural workloads produce skewed many-to-one reductions, but conventional NoC mapping methods generally optimize placement and routes for a fixed communication graph.
Method
MeshReduce-U rewrites lowered reductions into fewer fixed-width carriers, forms legal local aggregations and compatible-channel blocks, selects capacity-feasible sinks, and routes with fused usage-aware costs.
Results
Across a 20-workload lowerable neural-network zoo, MeshReduce-U improves mean latency, TLU, and FusedTLU over an ABC-style source-aggregation baseline on every workload.
Takeaways & Limitations
The results support making legal communication-graph rewriting part of NoC mapping rather than relying only on route selection over an unreduced graph.
Takeaways & Limitations
The deterministic replay excludes router buffers, virtual channels, backpressure, memory hierarchy, RTL timing, area, and energy, and aggregate means do not replace cycle-accurate validation.
Abstract
from arXiv · showhide
Many irregular neural workloads induce skewed many-to-one reductions with repeated neighborhoods and nonlocal communication. Conventional NoC mappers optimize placement and routes for a fixed communication graph, even though associative reductions expose legal opportunities to eliminate traffic before routing. We present MeshReduce-U, a compiler-guided communication-reduction and routing framework for mesh-NoC-based spatial accelerators. MeshReduce-U coalesces colocated sources, forms local aggregation islands, blocks channels with compatible fan-in structure, selects capacity-feasible sinks, and routes the remaining fixed-width carriers using fused usage-aware costs. A deterministic route-replay model reports schedule-derived communication latency, total link usage (TLU), and fused link usage (FusedTLU) separately. Across a 20-workload lowerable neural-network zoo, MeshReduce-U reduces mean latency, TLU, and FusedTLU by 40.3%, 56.0%, and 48.7%, respectively, relative to an ABC-style source-aggregation baseline, improving all three metrics on every workload. Across 40 synthetic irregular reductions, it reduces mean latency and TLU by 12.3% and 19.7%. A new 30-instance pass-by-pass study further shows that the structural rewrites reduce the global carrier count by 60.9% and replay latency by 63.0%. These results show that rewriting reducible neural communication before routing can be more effective than searching harder over an unreduced traffic graph.
1 Introduction
MeshReduce-U treats legal communication-graph rewriting as part of NoC mapping for irregular, many-to-one neural reductions. It reduces carriers before placement and routing, then uses capacity-aware placement and fused usage-aware routing while reporting separate latency and traffic metrics.
- Motivation: Irregular neural workloads create skewed many-to-one reductions with repeated neighborhoods and nonlocal sources, making communication a first-order accelerator cost.Mapping each contribution independently wastes link bandwidth and increases injection and hotspot pressure.
- Motivation: Associative reductions permit local source combination, bounded aggregation islands, and compatible-channel blocking before global routes are selected.These transformations shrink the communication graph rather than optimizing only placement and routes for a fixed graph.
- Approach: MeshReduce-U rewrites lowered many-to-one reductions into fewer physical carriers, then performs capacity-aware sink placement and fused usage-aware routing.The framework reports schedule-derived route-replay latency, ordinary TLU, and FusedTLU separately.
- Scope: The framework is deliberately layer-local and many-to-one, with whole-DAG residence, one-to-many fanout sharing, and steady-state initiation-interval optimization outside scope.Its abstraction is also described as matching CGRA-like arrays with compiler-placed tiles exchanging fixed-width payloads over local links.
- Contributions: The contribution includes a legal graph-rewriting formulation, conservative reduction and routing stages, separate metrics, shared comparisons, and a matched pass-by-pass ablation.The evaluation covers 40 synthetic reductions and a 20-workload neural zoo.
3 Problem Formulation
MeshReduce-U models irregular reductions as physical carriers that can be legally rewritten before routing, then evaluates deterministic placement and routing under capacity, legality, and fixed-width constraints.
- 3 Problem Formulation: Logical branches become fewer physical carriers through same-tile coalescing, bounded island aggregation, and compatible feature blocking.These rewrites preserve the mathematical reduction when their legality guards hold.
- 3 Problem Formulation: Ordinary TLU counts physical-carrier traversals, whereas FusedTLU counts each directed edge at most once per output reduction.The two metrics distinguish routed traffic from same-output common-tail footprint.
- 3 Problem Formulation: The route-replay model advances carriers hop by hop on unit-latency directed links, serializing one carrier per link per cycle in deterministic order.It reports abstract communication cycles rather than RTL-measured latency, and TLU counts carrier traversals rather than energy.
- 3 Problem Formulation: A carrier is one configured fixed-width block payload, and blocking changes routed-transfer count without changing the mathematical reduction.Packing requires compatible fan-in signatures, payload metadata, and sufficient carrier capacity; otherwise the lowering falls back to smaller or scalar carriers.
- 4 MeshReduce-U: The compiler pipeline groups legal operands, forms bounded islands, blocks compatible signatures, selects feasible sinks, and routes paths using distance, pressure, and usage.Deterministic transformations and explicit fallback leave affected branches unchanged when associative, metadata, capacity, or payload guards fail.
- 4 MeshReduce-U: Blocking trades lower transfer multiplicity for less route diversity, while narrower physical links can serialize packed blocks into multiple flits.Even the abstract remapping can occasionally increase TLU or replay time after selecting a different sink or path.
5 The Algorithmic Core Behind Placement
Placement combines exact capacity-feasibility search with flow-based tie-breaking, while an automatic policy compares radius- and hop-oriented objectives before routing. The implementation therefore operationalizes sink placement through binary search, max-flow feasibility, and min-cost-flow selection.
- Capacity-aware sink placement: Stage I combines a bottleneck-radius objective, binary search, exact bipartite max-flow feasibility, and min-cost-flow tie-breaking.An alternative total-hop objective is also available, and the default policy evaluates both before routing.
- Capacity-aware sink placement: Radius R is feasible exactly when maximum flow in the capacity-constrained bipartite network equals the number of outputs.The network connects each output to radius-eligible candidate cores, with core capacities K_c.
- Capacity-aware sink placement: Monotone feasibility enables binary search to find the minimum feasible radius R* exactly, subject to the compiler-retained candidate set.Increasing the radius only adds output-to-core arcs.
- Capacity-aware sink placement: After fixing R*, min-cost maximum flow selects among feasible assignments to improve aggregate communication cost while preserving the worst-case radius objective.Supported tie-breaks include total hop count, radius, a radius-then-hop surrogate, and bounding-box cost.
- Alternative placement objective: The alternative hop-count placement skips radius search and directly solves a capacity-constrained min-cost-flow problem.The default auto policy compares the implemented objectives using a congestion/latency proxy before routing.
6 The Algorithmic Core Behind Routing
MeshReduce-U generates structured route alternatives, assigns carriers under peak-load thresholds, and optionally repairs hotspots with bounded detours. Its search combines reusable Dijkstra templates, capacity-aware assignment, and conservative exactness claims.
- Reusable route templates: Dijkstra-generated templates provide bounded, topologically diverse route choices without enumerating arbitrary paths.A reverse Dijkstra tree is cached per template and sink, allowing all sources assigned to that sink to recover paths through parent pointers.
- Peak-load assignment: Binary search tests whether a greedy template-assignment oracle can place all carriers below a candidate peak-load threshold.The threshold is searched between lower and upper bounds, with feasible assignments retained and infeasible thresholds rejected.
- Exactness boundary: Stage I has exact max-flow feasibility, but Stage II’s greedy oracle does not certify global feasibility or optimality.The returned threshold is therefore the best found for the fixed candidate family, with separate utilities available for small-instance certification.
- Blocking and routing: Feature blocking is legal under exact-signature metadata and width guards, but its profitability remains a routing-dependent question.Packing can reduce carriers, while separate channels may retain route diversity; fixed-width legality does not by itself establish benefit.
- Hot-edge repair: Optional splay rerouting targets a maximum-load edge and commits only bounded-detour alternatives that avoid recreating the current peak.This local repair complements global template assignment by spending extra search only on realized hotspots.
7 Feature Blocking as a Routing-Diversity Trade-off
Feature blocking trades fewer fixed-width carriers for potentially reduced route diversity. MeshReduce-U therefore treats legality and profitability as separate decisions, especially when payload serialization can matter.
- Legality versus profitability: Exact-signature blocking is legal when compatible metadata and width guards hold, but profitability is a separate routing question.Channels sharing a fan-in signature can be packed because they involve the same source coordinates, although separate channels may exploit different paths.
- Payload capacity: The service multiplier ϕ(G) compares packed-block width with link payload capacity and exposes serialization costs beyond the fixed-width abstraction.The experiments effectively restrict legal blocks to ϕ(G) = 1; larger values require joint blocking-and-routing evaluation.
- Routing-diversity trade-off: Blocking trades carrier multiplicity for route diversity and possible serialization rather than guaranteeing lower traffic or latency.A compiler can evaluate bounded legal partitions and select among them using replay latency, TLU, and FusedTLU.
8 Algorithmic Toolbox and Where Each Piece Matters
The MeshReduce search stack follows a reduce, bound, then search pattern. Each algorithmic component addresses a distinct combinatorial subproblem while keeping the default configuration compact.
- Algorithmic toolbox: Table 3 presents classical algorithms as functional components, each addressing a different combinatorial subproblem.The table is framed as an algorithmic decomposition rather than a list of incidental implementation details.
- Design pattern: The stack’s unifying pattern is reduce, bound, then search.Compiler rewrites shrink carriers, flow algorithms enforce capacity constraints, shortest paths provide route choices, and bounds indicate when more search is worthwhile.
- Search variants: The U configuration keeps search bounds small, while heavier G/L variants enlarge the route-space exploration.This composition is presented as the reason U remains fast relative to heavier variants.
- Evaluation boundary: Table 4 defines the evaluated groups and baseline boundary for the common-model comparison.Its caption identifies the table as the boundary between evaluated groups and baselines.
9 Experimental Method
Experiments use a common deterministic mesh-NoC model, broad synthetic and lowerable neural workloads, matched baselines, and a pass-by-pass ablation. The validity target is communication construction and routing under that shared model, not end-to-end accelerator throughput.
- Common model: All methods receive the same serialized instances, directed mesh, capacities, and deterministic route-replay model.Links use unit hop latency and one carrier service opportunity per cycle; FusedTLU additionally assumes legal reduction-compatible merging.
- Workloads: The evaluation spans 40 synthetic/GNN-like reductions and 20 lowerable neural workloads covering graph, sparse, recurrent, diffusion, state-space, transformer-mixer, and CNN representatives.The synthetic suite stresses skewed fan-in, hotspots, nonlocal sources, and graph-like neighborhoods.
- Baselines: Baselines include XY, unicast, placement and routing heuristics, ABC-style gather, islandization, min-cut locality, and Steiner approximation.They operate on identical lowered traffic, topology, and metrics as objective-family proxies rather than complete accelerator ports.
- Controlled ablation: The 30-instance ablation progressively applies source deduplication, radius-1 islands, signature blocking, and fused or hybrid routing.Matched 4 × 4-mesh associative reductions use controlled fan-in, source distributions, and deterministic replay to isolate carrier-graph changes.
- Reproducibility: Each headline row comes from complete mapping followed by route replay, with fixed seeds, tie breaks, and route orders.Paths, sinks, and directed-edge loads are exported before aggregation; arithmetic means and available per-instance win counts are reported.
- Validity scope: The comparison targets communication-graph construction and routing objectives under one common mesh model, not end-to-end throughput.Ordinary TLU remains alongside FusedTLU so gains cannot rely solely on idealized in-network merging.
10 Results
MeshReduce-U improves latency and communication usage across synthetic reductions and a lowerable neural-workload zoo. Pass-by-pass evidence attributes most gains to structural carrier reduction, while routing refinements provide smaller trade-offs.
- Synthetic Irregular Reductions: 12.3% lower replay latency and 19.7% lower TLU versus ABC across 40 synthetic reductions.U improves TLU in 40/40 cases and latency in 35/40.
- Lowerable Neural-Workload Zoo: 40.3% lower latency, 56.0% lower TLU, and 48.7% lower FusedTLU versus ABC across the 20-workload zoo.All three metrics improve for 20/20 workloads.
- Pass-by-Pass Structural Evidence: 60.9% fewer carriers and 63.0% lower replay latency follow feature/signature blocking in the 30-instance structural ablation.Mean replay latency falls from 20.57 to 7.60 cycles, while TLU falls from 189.03 to 73.57.
- Sensitivity to Source Locality: Source locality determines reduction headroom: hotspot and power-law cases lose roughly three quarters of carriers, while uniform cases lose 34.4%.The one full-U latency regression occurs in the uniform group because of a bounded fused-footprint detour.
- A No-Regret Candidate Guard: The candidate guard lowers mean replay from 7.83 to 7.53 cycles without increasing TLU, selecting ordinary paths in 22/30 cases.It raises FusedTLU slightly from 66.33 to 66.60.
- Route Search after Reduction: Additional route search after U improves synthetic latency by only 0.40 cycles while increasing TLU by 12.95 and FusedTLU by 31.94.On the broad zoo, LU is slightly worse than U on all three aggregate metrics.
11 Compiler Integration
MeshReduce-U integrates as a layer-local compiler pass over a reduction intermediate representation, returning rewritten carriers, sinks, paths, and replay diagnostics. Its carrier-removal approach separates it from routing-only alternatives.
- Compiler Integration: The pass consumes a layer-local reduction IR containing sources, payload metadata, operators, merge legality, and feasible sink capacities.It returns the rewritten carrier set, selected sinks, directed paths, and replay diagnostics.
- Compiler Integration: Hardware adoption can be incremental: endpoint-only substrates enable coalescing and blocking, while intermediate accumulators enable all passes.Unsupported groups fall back to branch-explicit representations.
- Compiler Integration: U separates sharply from routing-only and fused-footprint alternatives because it removes carriers before global routing.The broad-zoo view identifies carrier elimination as the distinguishing mechanism.
12 Hardware Realization Contract
MeshReduce-U’s transformations depend on concrete substrate capabilities, while its replay metrics remain abstract communication measures. The paper therefore distinguishes deployable modes, local-aggregation assumptions, and validation boundaries.
- Hardware Realization Contract: Each MeshReduce transformation has a concrete substrate requirement, separating conventional endpoint accumulation from intermediate merge support.The same carrier graph can map to different routers, buffers, links, and local accumulators.
- Hardware Realization Contract: Fixed-width carriers pack compatible independent channels without adding their values together, preserving separate reductions after unpacking.Incompatible payloads form separate blocks.
- Hardware Realization Contract: Offline sink and path emission supports static or source-routed NoCs without requiring online adaptive routing.Virtual channels and buffering remain outside the abstract replay model.
- Hardware Realization Contract: The ablation measures global traffic after legal local merges, not that local aggregation is free.Local aggregation may use a nearby PE, switch-local arithmetic, or scratchpad reduction engine.
- Hardware Realization Contract: Separate latency, TLU, and FusedTLU expose trade-offs that a single weighted score would hide.A compact fused tree can still have long ordinary routes or bottleneck serialization.
- Hardware Realization Contract: The replay model excludes buffers, virtual channels, backpressure, memory hierarchy, RTL timing, area, and energy.The model zoo prioritizes breadth of lowerable patterns and excludes complete masked-softmax attention/GAT lowering.
- Hardware Realization Contract: Aggregate means do not replace cycle-accurate validation; future work includes RTL calibration, larger real workloads, and cross-layer extensions.The ablation also requires calibration of the chosen local-aggregation substrate.
14 Design Implications
The design implications favor structural reduction before expensive search, locality-aware lowering, and separate deployment metrics. MeshReduce-U also supports graceful fallback when hardware or legality constraints prevent particular rewrites.
- Design Implications: Legal coalescing and blocking should precede large route-search budgets because structural stages dominate carrier and TLU reductions.Search can be conditioned on lower-bound gaps, edge pressure, or candidate-guard disagreement.
- Design Implications: Locality statistics can predict reduction headroom: hotspot and power-law sources benefit more than uniform sources.Useful indicators include duplicate-tile rate, island coverage, and compatible-signature frequency.
- Design Implications: Separate Tsched, TLU, and FusedTLU lets deployment policies match the actual substrate instead of inheriting one arbitrary weight.Fused footprint and ordinary route latency can move in opposite directions.
- Design Implications: Unsupported operators, full sinks, incompatible signatures, or absent intermediate arithmetic can fall back to semantically identical carrier graphs.Optimization opportunity grows with hardware capabilities, but correctness does not require every pass.
- Design Implications: Across synthetic and lowerable neural workloads, structural rewrites reduce ordinary link usage and replay latency, providing the dominant gain.The matched ablation identifies structural rewriting as the main source of improvement.