Hop-Aware Parallel-in-Time MPC for Tiled Many-Core Chips

Model predictive control (MPC) picks a robot's next action by repeatedly solving an optimization over a short window of future time. It is the standard way to run quadrupeds, drones and race cars near their physical limits, but every solve must finish before the next control deadline. That deadline is often 2.5 ms at 400 Hz. Recent solvers break the usual step-by-step sweep over the time window into a tree of parallel operations, which cuts the theoretical number of sequential steps from $N$, the window length, down to $\log N$. They have only ever been measured on large shared-memory GPUs. The low-power chips that fit on a robot look different. They are increasingly built from many small compute tiles, or from several separate dies in one package, connected by an on-chip packet network. On such a network a message's travel time grows with the distance it must cross. Communication already dominates other parallel workloads on this kind of hardware: it takes more than 70% of runtime for Transformers on an 18-chiplet package.

We propose to rebuild parallel-in-time MPC around the actual cost of moving data across a tiled chip. Each tile solves a contiguous stretch of the time window with the ordinary sequential method. The tiles then combine short summaries through a parallel prefix scan (a tree-structured running combination) whose tree is laid out so that partners sit physically near each other. The per-iteration global checks of the nonlinear solver ride along on the same messages, and hardware multicast delivers the shared results. A calibrated latency model chooses the stretch length for each problem size and chip. That choice can collapse to the fully sequential solver or to the fully parallel one, so the method never has to be worse than either. The headline measure is the longest window length that still meets a hard real-time deadline on an embedded-scale tiled chip.

Core Claim

The $O(\log N)$ promise of parallel-in-time solvers does not hold on a mesh network. A scan tree has levels that pair time steps $2^k$ apart, and those partners end up many network hops (switch-to-switch transfers) apart. Even with a compact placement of time steps onto the 2D grid of tiles, the hop count at level $k$ grows roughly like $\sqrt{2^k}$. Summed over levels, the communication term grows like $\sqrt{P}$ in the number of tiles $P$, not like $\log P$. On top of that, every Newton or interior-point iteration needs a few chip-wide reductions for merit values, residual norms and step sizes, and each costs about one network diameter. With $L$ the stretch length per tile, $P = N/L$, $t_R(n)$ the cost of one sequential Riccati step for state size $n$ (the Riccati recursion is the standard backward sweep through time), $t_\oplus(n)$ the cost of one scan combine, $h_k$ the hops at scan level $k$, $\tau$ the per-hop latency, $\beta$ the per-word transfer cost, $s(n) \approx n^2$ the summary size in words, $R$ the number of global reductions per iteration and $D$ the network diameter, the per-iteration latency is approximately

$$T(L) \approx L\, t_R(n) + \sum_{k=1}^{\log_2 P}\big[t_\oplus(n) + h_k \tau + \beta\, s(n)\big] + R\, D\, \tau .$$

Our claims are that the minimizing $L$ is usually neither 1 (full scan) nor $N$ (fully sequential), and that it shifts predictably with $n$, $N$, mesh size and hop latency. We further claim that a solver built at that point, with a hop-aware tree layout and fused, multicast-delivered reductions, meets a fixed deadline at substantially longer windows than any of the extremes.

Grounding in Prior Work

The motivation comes from two kinds of evidence. The first is the GPU parallel-in-time solvers, none of which measure communication. GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices reorders the banded system that MPC solves (nested dissection) so independent time blocks factor simultaneously. It reports logarithmic scaling only until the GPU's processor clusters saturate near $N \approx 250$ on an RTX 3080, then linear scaling, plus "staircase" slowdowns from memory alignment. A Parallel-in-Time Newton's Method for Nonlinear Model Predictive Control recasts the backward and forward passes of interior-point and ADMM solvers as associative scans on an A100. Differentiable Model Predictive Control on the GPU solves the whole optimality system at once with preconditioned conjugate gradient. That method needs repeated global dot products. All three treat the chip as uniform shared memory. We keep their algebra and instead model where the data physically goes.

The second kind of evidence shows that communication overtakes parallelism. Communication Characterization of AI Workloads for Large-scale Multi-chiplet Accelerators finds inter-chiplet traffic exceeding 50% of runtime at 18 chiplets, and finds that multicast messages travel the longest distances. It profiles only neural networks; we profile control solvers. Robot Control Computation in Microprocessor systems with Multiple Arithmetic Processors scheduled robot dynamics across arithmetic coprocessors on a shared bus. It found that more than six processors slowed execution, and concluded that keeping data on one processor beats balancing work. That conclusion sits in direct tension with the "fragment everything along time" philosophy of the GPU solvers. Our stretch length $L$ is the knob that resolves the tension: locality inside a stretch, parallelism across stretches. Li and Ahmad's schedules were static task graphs for fixed kinematics. Ours is an iterative solver whose global checks recur every iteration.

The multicast mechanism comes from A Multicast-Capable AXI Crossbar for Many-core Machine Learning Accelerators. That work is an open-source on-chip switch that delivers one write to many destinations. It was evaluated only on matrix multiply and memory-transfer microbenchmarks. Its deadlock rule makes a sender acquire all destinations at once, which could stall a latency-critical broadcast. We test whether that rule hurts small, frequent solver messages.

Parallel Model Predictive Control for Deterministic Systems parallelizes differently. Independent workers solve different-horizon problems and a hub picks the cheapest. Its workers never exchange intermediate variables, so it is complementary to ours: it parallelizes across candidate problems, and we parallelize within one.

The application regime comes from robotics. Online Dynamic Trajectory Optimization and Control for a Quadruped Robot reports 18.34 ms per iteration on a laptop but about 100 ms on ANYmal's onboard computer, which forced a two-step horizon. Time-Optimal Planning for Quadrotor Waypoint Flight shows that full nonlinear long-horizon models are what exploit actuator limits, at offline cost of 40 to 65 minutes.

Research Program

The work has four parts.

Latency model. We will build the model above and calibrate $t_R$, $t_\oplus$, $\tau$ and $\beta$ from microbenchmarks on each target fabric. Its first test is whether it predicts measured per-iteration latency and the optimal $L$ across a sweep of $n$, $N$ and $P$.

Solver. We will implement a partitioned solver built on the associative-scan formulation of Iacob and Abdulsamad. Each tile runs a sequential Riccati sweep over its stretch and emits an affine summary. The tiles then run an up-sweep and down-sweep scan over $P$ summaries, followed by local reconstruction.

Hardware mapping. We will place the scan tree on the mesh using space-filling-curve and recursive-bisection layouts, so that low tree levels stay within a neighborhood. The merit-function, residual and step-size reductions of each interior-point iteration are fused into the scan's up-sweep, and the resulting step and barrier parameters return on the down-sweep. One hardware multicast replaces a chain of point-to-point sends.

Platforms. We will run the solver on three fabrics:

  • a cycle-level tiled mesh in The gem5 Simulator: Version 20.0+ with configurable hop latency and mesh size;
  • an Occamy-style cluster system using the multicast crossbar RTL from Colagrande and Benini;
  • a multi-chiplet configuration in the GEMINI platform used by Guirado et al., to stress long inter-die hops.

The same code also runs on an RTX-class GPU, so it is anchored to published results.

Baselines

Naive reference. The fully sequential Riccati-based interior-point solver runs on a single tile of the same simulated chip at the same clock. This is the do-nothing point and the threat we take most seriously. For the small state sizes typical of reduced quadruped models it may already be fast enough. It gets the same convergence tolerance, warm start and iteration cap as our solver. Beating it means meeting the deadline at a longer horizon, or reaching tolerance faster at equal horizon, on the same chip.

Full associative scan. The full-depth scan of A Parallel-in-Time Newton's Method for Nonlinear Model Predictive Control uses one time step per lane and is mapped to tiles in naive row-major order. It is the strongest existing parallel-in-time method for nonlinear constrained MPC and the most direct competitor on tiled hardware. It runs on identical problems, tolerances and iteration caps. No reported runtime number was found on Lacuna for this method; the file states only "orders of magnitude faster than sequential methods" at $N=1000$ on an A100. We therefore re-run it ourselves on every platform.

Nested dissection on commodity hardware. The nested-dissection factorization of GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices runs through its released library on its native GPU, and our solver runs on the same GPU. This is the strongest commodity-hardware result, reported as more than 2x faster than NVIDIA cuDSS and more than 100x faster than QDLDL, with saturation near $N \approx 250$ on an RTX 3080. On the GPU we only need to match it within noise, since that is not our target regime. On tiled chips we compare at equal silicon area and power budgets, and report energy per solve.

PCG solve. The DiffMPC solver (Differentiable Model Predictive Control on the GPU) is included because its per-iteration global dot products are exactly the reduction-heavy pattern our fusion targets. It reports 4x to 7x over trajax.

Ablations. These isolate the key ingredients:

  • stretch length fixed at 1 or $N$ versus model-chosen;
  • hop-aware layout versus row-major;
  • fused reductions versus separate ones;
  • hardware multicast versus the hierarchical software multicast that Colagrande and Benini outperform by a reported 5.6x geometric mean on microbenchmarks.

Why not just…?

Why not just run the sequential solver on one fast core? This is a real threat. For state sizes around a dozen and horizons near 50, the sequential sweep may simply win, because scan combines cost several times more arithmetic than a Riccati step. Our design absorbs this rather than arguing with it: when the model picks $L=N$, the solver is the sequential solver. The empirical question is where the crossover lies. If no robot-relevant problem in our suite crosses over on embedded-scale meshes, we will report the crossover map as the main finding, which is still new information for chip designers. The onboard slowdown from 18 ms to about 100 ms on ANYmal in Online Dynamic Trajectory Optimization and Control for a Quadruped Robot suggests single embedded cores are short of headroom for longer horizons.

Why not just use a GPU with existing CUDA solvers? Schwan et al. report that logarithmic scaling ends at saturation and that alignment causes staircases. Discrete GPUs also draw power that drones and small legged robots cannot carry. We include the GPU comparison directly. Showing that our layout and fusion do not help there, while helping on meshes, would confirm that the gain comes from the network, not from better arithmetic.

Why not just distill MPC into a neural policy? Bootstrapped Model Predictive Control gets fast inference from a 3-million-parameter network. It is limited to a one-step temporal-difference horizon because world-model rollouts compound errors, and it gives no constraint guarantees. Policies are better seen as warm starts that reduce the iteration count our solver must hit. We will report iterations-to-tolerance with and without a learned warm start.

Why not just use software multicast on a standard mesh? Solver broadcasts are tiny scalars and small matrices, so latency rather than bandwidth may dominate, and software trees might be close enough. The multicast ablation measures exactly this. If hardware multicast gains less than the layout and fusion changes, we will say so and drop it from the recommended design.

Proposed Experiments

Problem suite. The suite spans state sizes and horizons:

  • torque-limited pendulum and force-limited cart-pole at $N$ up to 1000, as in Iacob and Abdulsamad;
  • a centroidal-momentum quadruped model in the style of Cebe et al., with horizons extended from two to many steps;
  • a full nonlinear quadrotor model following Foehn et al.;
  • the dynamic vehicle model of the DiffMPC drifting task.

Unaligned block sizes are included deliberately to probe the staircase effect.

Metrics. We measure per-iteration latency, latency to tolerance, and 99th-percentile latency over randomized initial states (deadlines are worst-case quantities). We also measure energy per solve, network hop and flit counts per scan level, and the longest horizon meeting 2.5 ms and 10 ms budgets.

Decisive checks. There are three:

  1. The model must predict the measured optimal stretch length within one power of two, and per-iteration latency within 20%, across mesh sizes from 16 to 256 tiles and hop latencies varied over a 4x range. Otherwise the design rule is not trustworthy.
  2. On meshes of at least 64 tiles, the measured communication term of the naive full scan should grow faster than $\log P$, close to the predicted $\sqrt{P}$ trend. That growth is the premise of the whole proposal, and seeing only logarithmic growth would refute it.
  3. At the 2.5 ms budget, the hop-aware partitioned solver should sustain a longer feasible horizon than both the single-tile sequential solver and the naive full scan on the quadruped and quadrotor problems.

If it only ties the better of the two, the contribution reduces to the crossover map and the latency model, and we will present it that way.