CS Paper Radar

Budgeted Express-Mesh: Traffic-Aware Link Placement and Deadlock-Free Adaptive Routing

Li Cao, Jingyuan Ma

cs.AR cs.NI ·submitted 2026-09-15 12:06 UTC · v2
code/data

Abstract

We present Budgeted Express-Mesh, a topology-routing co-design that adds a small number of traffic-aware express links under a fixed wire budget. An ASPL-based greedy placement is refined by simulation-guided annealing, while packets use committed top-K routes selected from delayed express-link congestion and reservation signals. Across four synthetic workloads, optimized placements consistently improve high-load throughput over Mesh and random placement, and annealing further improves Greedy. The gains persist under delayed quantized congestion information, longer express-link latency, multi-flit packets, and a 16-by-16 heterogeneous workload.

Comment
14 pages, 14 figures, 9 tables. Code and artifacts: https://github.com/tsjyma/Express_mesh

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.AR cs.NI ·2026-11-17 ·Patrick Iff, Luca Oertig, Andrin Weber, Luca Benini, Torsten Hoefler
similarity 0.62
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.

0.23

LASH-PAT: Deadlock-Free Adaptive Shortest-Path Routing for Inter-Chiplet Interconnects

cs.AR cs.NI ·2026-11-17 ·Patrick Iff, Torsten Hoefler
similarity 0.61
Abstract

With the slowdown of transistor scaling, chipletbased systems, and in particular chiplet-based wafer-scale integration, have emerged as a promising approach to sustain growth in computing capability per cost for modern processors and accelerators. In recent years, many specialized inter-chiplet interconnect topologies have been proposed. In these topologies, the simple, well-established, and deadlock-free dimension-order routing scheme is not applicable due to its reliance on regular mesh structures. In this work, we study routing in these recently proposed inter-chiplet interconnect topologies by categorizing and evaluating nine deadlock-free routing functions for irregular topologies known from data center networking in this new context. This reveals a trade-off between turn-based routing, which enables path diversity, and layered routing, which ensures shortest-path delivery. To resolve this trade-off, we propose LASH-PAT, a routing function that extends layered shortestpath routing with adaptive path diversity. LASH-PAT supports multiple shortest paths and dynamically selects among them based on local congestion while preserving deadlock freedom. When compared to the best-performing baseline routing function for each combination of topology, traffic pattern, and evaluated metric, LASH-PAT improves throughput by 21.15% and reduces energy per packet by 12.77%, while providing latency comparable to the lowest-latency baseline routing function.

0.21

The Road Less Traveled: Congestion-Aware NoC Placement and Packet Routing for FPGAs

cs.AR ·2026-08-18 ·Soheil Gholami Shahrouz, Vaughn Betz
publishedcode/data similarity 0.61
Abstract · 10 pages, 5 figures, 3 tables. Published at the 2024 34th International Conference on Field-Programmable Logic and Applications (FPL), Torin…

To help scale to ever-larger and more complex designs, recent FPGA architectures now integrate network-on-chips (NoCs). NoCs help transfer high-bandwidth data over long distances within the chip without using scarce low-delay long routing wire segments. While NoC-enhanced FPGAs aid system integration and design reuse, they also complicate FPGA computer-aided design (CAD) flows by introducing new constraints and metrics. Placement and routing need to optimize NoC metrics like latency and bandwidth utilization and avoid link oversubscription (congestion), while simultaneously optimizing the programmable routing resource usage of the design modules attached to NoC routers. In this work, we develop several new approaches to reduce NoC congestion while minimizing the impact on other design metrics. First, we incorporate a NoC link congestion cost into the placement engine of the open-source CAD flow, versatile place & route (VPR). Second, we integrate turn model NoC routing algorithms into the placement engine to leverage path diversity to further reduce congestion. On average over a suite of 29 benchmarks, combining placement congestion modeling with turn model packet routing reduces NoC congestion by 90.7% at the cost of increasing aggregate bandwidth demand by 4%. In cases where the enhanced placement engine and NoC routing fail to fully resolve congestion, we formulate NoC routing as a Boolean satisfiability (SAT) problem. This approach yields significant additional improvements; the combined algorithm reduces congestion by 95.1% compared to the baseline placement. Finally, we enhance the reinforcement learning (RL) agent in VPR's placement engine by introducing a NoC-aware move type, resulting in an 8.8% reduction in wirelength on designs that make extensive use of the NoC.

0.50

Rethinking Adaptive Routing on Dragonfly

cs.NI ·2026-11-09 ·Ziyu Wang, Dezun Dong, Fei Lei
similarity 0.60
Abstract · 12 pages, 9 figures. Preliminary version. An updated final version will follow, and the source code will be open-sourced

The Dragonfly topology is widely deployed in leading supercomputers, where adaptive routing is crucial for high-performance interconnection. Despite years of research, a dilemma remains: state-of-the-art adaptive routing algorithms achieve excellent performance but demand hardware budgets far beyond what real router chips can afford -- prohibitive buffers, logically dependent floating-point operations, or exhaustive path-set traversals -- whereas realizable algorithms deliver unsatisfactory performance. Furthermore, existing algorithms fail to exploit the abundant almost-minimal paths in Dragonfly: when only the local channels of a minimal path are congested, they reroute packets to significantly longer global non-minimal paths, wasting global bandwidth and increasing latency. To address both limitations, we analyze intra-group path contention and propose the Decoupled Incremental Adaptive Routing (DIAR) algorithm, which decouples routing into global path selection at the source and incremental local detours onto almost-minimal paths, guaranteeing deadlock freedom without additional virtual channels, escape rings, or turn models. Requiring only a few comparators, shifters, adders, and multiplexers, DIAR reduces buffer overhead by up to four orders of magnitude compared with state-of-the-art algorithms, while achieving comparable or superior performance across all evaluated scenarios: relative to the strongest realizable adaptive routing algorithm in each scenario, DIAR improves saturation throughput by up to 30.0% across synthetic traffic patterns and improves performance by up to 34.9% (13.2% on average) across HPC workloads.

0.26

Rondo: Controlling Reordering in High-Throughput Packet Spraying

cs.NI ·2026-11-03 ·Xizhi Zhang, Zhongjie Chen, Yang Zhang, Fengyuan Ren
similarity 0.58
Abstract

Modern datacenter applications demand high network bandwidth, motivating packet-level multipath transport to exploit the aggregate capacity of multiple paths. However, packet reordering under packet spraying poses challenges for hardware transports. Excessive packet reordering makes it difficult to infer packet loss, imposes substantial pressure on NIC resources, and ultimately degrades performance. Existing transports either prioritize throughput without controlling packet reordering, or mitigate reordering by restricting transmissions, which leaves available path capacity unused. In this paper, we identify two fundamental sources of packet reordering: transient inter-path queueing differences caused by control dynamics, and persistent path-delay differences due to path heterogeneity. These observations motivate a joint design of a multipath controller and a packet scheduler to address transient and persistent delay differences, respectively. We present Rondo, a packet-level multipath transport that achieves both high throughput and low packet reordering. Its multipath controller uses ACK-based per-path capacity estimation and probing to maintain stable path loads, while its packet scheduler adjusts packet transmission order to compensate for persistent delay differences. Testbed experiments and large-scale simulations show that Rondo reduces the maximum out-of-order degree by up to 97.5% while maintaining high throughput. With constrained receiver buffers, Rondo achieves up to 8.51 times higher goodput.

0.19

APPlace: Co-Optimizing Device Locations and Access Points for Routing-Aware Analog Placement

cs.AR ·2026-10-29 ·Bingyang Liu, Xiaohan Gao, Souradip Poddar, David Z. Pan
top venuecode/data similarity 0.57
Abstract · Accepted to ASP-DAC 2027. 8 pages, 6 figures, 4 tables. Code: https://github.com/bingyang1132/applace

Analog layout automation remains challenging in Analog/Mixed-Signal circuit design, because parasitics and mismatches introduced during layout strongly affect circuit performance. Placement is especially critical among the layout stages, as it constrains the routing solution space and the achievable post-layout performance. Existing analytical placement methods optimize device coordinates under center-based wirelength proxies and leave access point (AP) selection to routing. In analog circuits, however, a routing pin is an extended piece of terminal metal rather than a fixed point, and the best AP on it depends on where the other connected devices are placed, so a coordinate-only placement optimizes for connection points that the router will not use. We present APPlace, a routing-aware analog placement framework that co-optimizes device locations and AP selections during global placement, followed by a legalization stage that preserves the structure established by global placement. Experimental results on four real-world analog benchmarks show that APPlace achieves better overall post-layout performance than representative baselines at comparable layout area. Ablation studies further show that removing AP co-optimization causes up to a 13 dB CMRR loss among the OTA benchmarks and a 23% increase in comparator delay.

0.87

MeshReduce-U: Compiler-Guided Communication Reduction for Irregular Neural Reductions on Mesh NoCs

cs.AR cs.DC ·2026-08-26 ·Amirreza Khorasanian
similarity 0.56
Abstract · 19 pages, 7 figures. Extended preprint

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.

0.19

Extending Low Latency Service Across the Internet

cs.NI ·2026-08-27 ·Harkirat Singh, Fatih Berkay Sarpkaya, Hakan Gulec, Fraida Fund, Shivendra Panwar
published similarity 0.54
Abstract · Accepted to the IEEE International Conference on Network Protocols (ICNP), 2026

Protocols such as L4S for low latency network services have attracted growing interest from major industry stakeholders such as Comcast, Apple, T-Mobile, and NVIDIA. However, L4S requires isolation between L4S flows and classic flows in order to maintain its low latency benefits and safe coexistence. The L4S architecture uses a DualPI2 AQM mechanism to provide this isolation when the bottleneck occurs at the home access link. In practice, however, bottlenecks may also occur at other locations in the network, such as peering points, ingress to wide area networks, or occasionally congested links in the core, where deploying DualPI2 AQM is not feasible. Without a solution to this problem, L4S may struggle to gain deployment, since its benefits may remain limited without end-to-end support. To address this challenge, we propose a deployment strategy that reduces the need to upgrade expensive core routers by using existing networking mechanisms such as BGP communities, SRv6, and priority queues with rate caps. We demonstrate the feasibility of this approach through large scale experiments on the FABRIC testbed. Our results demonstrate a practical deployment strategy for extending low latency service across the Internet, even across independently administered networks.

0.22