CS Paper Radar

Certified Bank-Aware Fast-Path Coverage for Hardware-Constrained NDN Forwarding Lookup

Amirreza Khorasanian

cs.AR cs.NI ·submitted 2026-08-28 11:08 UTC · v1

Abstract

Named Data Networking (NDN) replaces address-based forwarding with longest-prefix lookup over variable-length hierarchical names, creating a difficult fit with bounded hardware fast paths. We formulate this problem as certified fast-path coverage. An offline mapper selects a prefix-closed set of parser-visible trie nodes and a separate set of action-equivalence certificates under a shared budget. A certificate relates a selected shallow FIB prefix to a deeper true-LPM class with the same forwarding action; applying the shortcut requires a sound class guard, while uncertain traffic falls back to an exact path. We present BPC-Greedy, a certificate-aware placement heuristic, and BPC-Portfolio, a multi-strategy wrapper spanning exact-heavy, repair-based, and shallow-shortcut constructions. The formulation exposes a tree-closure knapsack structure for prefix placement, exact top-k certificate selection for a fixed selected set under uniform certificate cost, and a separate bank-feasibility layer. On a synthetic parser-depth sweep and a 50k replay of public NDN testbed names under a reproducible synthetic forwarding-action snapshot, modeled certified coverage increases from 46.48% for the best exact-prefix-only bank-aware baseline to 64.06% at total budget M=48. These results characterize placement opportunity under the stated model: the evaluator uses the known true LPM as an oracle-style guard, certificate-table bank traffic is not modeled, and no claim is made about synthesized latency, area, or throughput.

Comment
19 pages, 7 figures. Extended preprint

Closest papers

Nearest neighbours by meaning across the whole index.

Cascadia: A Control-Plane-Free Alternative to Hyperconverged AI Infrastructure

cs.DC cs.AI ·2026-09-30 ·Matias Parij, Pawan Paudel, Tate Berenbaum, Muthaiah Venkatachalam
benchmark similarity 0.54
Abstract · 26 pages

We present Cascadia, a system for serving large language models on fleets of commodity Intel AIPCs using their CPU, integrated-GPU, and NPU resources. Every node embeds ingress, scheduling, and execution; inference requests require no dedicated routing control plane. Nodes join a libp2p QUIC mesh using CA-issued ed25519 admission certificates, gossip signed capabilities, exchange live load over direct peer streams, and route OpenAI-compatible requests to eligible peers. An operator-run certificate authority handles admission and fleet management outside the inference path. Three serving modes share one interface: whole-model execution on one node, load-balanced replicas, and pipeline-sharded chains using the compilation and speculative decoding mechanism of our companion paper. Optional KV-cache mobility reuses compatible conversation prefixes after a routing move, with cold recomputation on a miss. Signed response receipts and hash-chained logs support provenance and audit. A three-node Phi-3.5-mini NPU testbed delivered 3.10x the response throughput of its one-node configuration under ten concurrent requests; a separate four-node deployment recorded 4.06x the throughput of direct single-node serving. Paired latency observations, runtime measurements, and internal functional checks characterize the tested configurations. We compare Cascadia with IBM, Nutanix, VMware, and HPE platforms on deployment footprint, hardware requirements, scheduling, scaling, licensing, and trust, using vendor documentation. The paper repository provides benchmark scripts, curated measurements, and a claim-to-evidence map.

0.39

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.54
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

VPP: Virtual Pipeline Parallelism for Efficient Chunked Prefill in Long-Context LLM Inference

cs.DC ·2026-08-27 ·Yan Shi, Xiaochao Wang, Jingchun Gao, Jintao Luo, Xinyi Zhou +5 more
similarity 0.54
Abstract

Chunked prefill pipeline parallelism (CPP) is a key technique for LLM inference. However, equal-size chunks exhibit imbalanced latency, as later chunks attend longer prefix KV caches and incur higher attention costs, leading to pipeline bubbles. Existing approaches mitigate this imbalance through dynamic chunk resizing (Dynamic CPP, DCPP), but our measurements show that this trades scheduling overhead for load balancing, which becomes unfavorable on long sequences. In this study, we propose Virtual Pipeline Parallelism (VPP), which keeps chunk sizes fixed and optimizes the pipeline layout through virtual stages. A V-shaped virtual-stage traversal overlaps each chunk's expensive middle stages with the lighter head and tail stages of its neighbors, while asynchronous communication and pipelined packing further reduce communication stalls and cross-request drain bubbles. We implement VPP in vLLM-Ascend and evaluate it on three MoE-based LLMs with sequences up to 1M tokens on 16 Ascend 910C NPUs. VPP improves throughput by up to 13.1% over DCPP on long sequences and 6.7% on mixed workloads, while preserving performance on short sequences. On a 512K-token DeepSeek-V3.1 prefill workload, VPP reduces the pipeline bubble ratio from 6.4% to 0.1%, achieving a 98.0% reduction compared with DCPP.

0.38

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.54
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

Scalable Exact Path Selection via Structure-Aware Search for Virtual Payment Channels

cs.DC ·2026-08-23 ·Jiangnan Luo, Zhebei Shen, Yuan Zhang, Sheng Zhong
published similarity 0.53
Abstract · 10 pages, 9 figures. To appear in the Proceedings of the 55th International Conference on Parallel Processing (ICPP 2026)

Virtual Payment Channels (VPCs) enable efficient off-chain transactions in Payment Channel Networks (PCNs), but their performance depends on selecting high-quality underlying paths. Existing approaches either rely on simplified metrics or incur high computational cost. We study VPC path selection under generalized monotone metrics and propose a structure-aware exact solver based on quadtree search. By exploiting monotonicity and distance plateau properties, our method prunes large regions of the capacity-constrained search space while preserving optimality, significantly reducing the number of shortest-path computations. We further instantiate the framework with a composite metric that integrates economic cost and security risk, enabling flexible trade-offs across application scenarios. Experiments on synthetic graphs and real-world Lightning Network topologies (up to 12,552 nodes) show 2--5 orders of magnitude speedup over prior work, with consistent sub-100ms latency.

0.63

Routing Dense Layouts with History-Aware Offline Reinforcement Learning using LSTM

cs.AR cs.LG ·2026-09-08 ·Afsara Khan, Austin Rovinski
published similarity 0.53
Abstract · Accepted for publication at ICCAD 2026

Detailed routing remains a dominant runtime bottleneck in physical design due to increasing complexity of design rules. Modern routers can struggle to resolve persistent violations under dense operating conditions. While recent work leverages reinforcement learning (RL) to dynamically select costs for each routing iteration, we find that this technique struggles with high-density designs where routing solutions are significantly harder. To address this, we present a history-aware offline RL policy which predicts iterative cost weights in these dense regimes to improve convergence across placement densities by utilizing readily available features from the router. Our policy uses conservative Q-learning similarly to prior work; however, our key insight is that addition of a lightweight LSTM architecture and additional features can retain sequence context and improve routing convergence across multiple densities and route guide qualities. Our policy can be integrated into any cost-based router with minimal pipeline changes, as it does not interfere with the core search algorithm. We evaluate our policy on held-out density and adjustment settings, including difficult operating points induced by dense placement and low guide quality. Our policy reduces design rule violations (DRVs) by an average of 92% over the top public baseline while simultaneously reducing runtime by 10%.

0.38

Exact Memory-Time Optimization for Prefix-Cached Language Model Serving

cs.LG ·2026-10-02 ·Shivam Gupta
benchmarktheorycode/data similarity 0.53
Abstract · 16 pages, 5 figures. Code and reproducibility artifacts: https://github.com/shi1720/prefix-certificate-retention

Retaining language-model prefix states trades recomputation against storage time. Optimizing each cached block independently can overcount savings: a resident block is usable only when the required preceding prefix is also available. We introduce Prefix-Certificate Retention (PCR), an exact finite-trace formulation for static, grouped, reset-on-access timeouts. Usable-prefix rewards become nodes whose prerequisites are timeout thresholds and preceding hit certificates. The resulting maximum-weight closure reduces to one minimum cut, with graph size linear in the number of block lookups and timeout choices. A breakpoint theorem extends the construction to all nonnegative timeouts without discretization error. We also derive a linear-time-in-grid-size dynamic program for ordered timeouts and bounds that certify the cost of this restriction. Exhaustive small-instance checks and chronological replay of 39,632 public Mooncake requests validate the formulation. On the fixed grid, ordered timeouts attain the unrestricted training optimum in 118 of 120 trace-grouping-price cases. Heterogeneous retention improves several held-out memory-time tradeoffs, but finer training optimization does not uniformly improve transfer. The contribution is a tractable optimization model and an auditable benchmark for retention policies; the experiments measure usable prefix blocks and storage time, not GPU latency.

0.40

Lightweight Onboard Routing and Topology Co-Construction for Autonomous GNSSs

eess.SY ·2026-09-07 ·Huan Yan, Juan A. Fraire, Rongqin Yang, Wenfeng Li, Kanglian Zhao
similarity 0.52
Abstract · 15 pages, 6 figs

Global navigation satellite systems (GNSSs) can already plan their inter-satellite link (ISL) topology onboard, leaving routing as the last step toward autonomous networking. In GNSS ISLs, each satellite links to at most one peer per time slot. We exploit this structure to replace end-to-end path search with a single backward sweep over the slots. The proposed method, DS-SMFP, propagates earliest-arrival times backward from each destination and outputs a STORE/FORWARD decision for every slot, satellite, and destination, in time linear in the number of slots and with working memory independent of the planning horizon. Because each slot needs only its own topology and the delivery state of the next one, routing can steer link selection while the topology is built. This slotwise dependency enables Master-Oriented Topology--Routing Co-Construction (MTRCC), which favors traffic to and from a master satellite performing onboard orbit determination. In a 24-h, 30-satellite BeiDou scenario, DS-SMFP matches the delays of Contact Graph Routing (CGR) and shortest path tree (SPT) routing while running over 180 times faster and using over 36 times less peak routing working memory. Compared with fair contact plan (FCP) topology, MTRCC reduces mean master-related traffic delays by over 10\%, with an approximately 3\% increase in mean PDOP. This paper provides a methodological foundation for efficient autonomous GNSS networking.

0.27