ORIANNA: An Accelerator Generation Framework for Optimization-based Robotic Applications

Robots localize, plan, and control by repeatedly solving big sparse least-squares problems in real time, and accelerating that has meant an awful choice — a general matrix accelerator wastes most of its work on the 98% zeros, while a hand-built accelerator per algorithm costs a fortune to design and a robot runs several algorithms at once; Orianna (Chinese Academy of Sciences and Georgia Tech) escapes the dilemma by finding what all these algorithms share — recast every robot pose in one unified representation and every algorithm becomes FACTOR-GRAPH inference, which shatters the giant sparse matrix into many small DENSE ones (11x smaller, density up from 5% to 59%) — so a single framework compiles any of them down to nine primitive operations and auto-generates one accelerator that matches dedicated designs using just 36% of their hardware, at 6.5x the speed and 15x the energy efficiency of a desktop CPU.

The argument in one glance

Problem

A robot solves the same kind of hard math over and over, in real time

The core algorithms that let a robot know where it is (localization), decide where to go (motion planning), and steer itself (control) are all OPTIMIZATION problems. Each is solved iteratively: guess a solution, linearize, build and solve a large linear system to compute a correction, and repeat until it converges (Gauss-Newton, Levenberg-Marquardt). The linear system is huge and SPARSE — a localization step might be a 1126-by-333 matrix that is 98.5% zeros. And it must run in real time on a battery-powered robot, which general-purpose hardware cannot manage: a traditional localization algorithm runs at only 5 frames per second even on a desktop CPU. So robots need custom acceleration for this iterative sparse-solve, and they need it for SEVERAL such algorithms at once.
What people did

Build an accelerator — general matrix hardware, or a dedicated chip

There are two established ways to accelerate this. Use GENERAL matrix hardware — a GPU or a systolic array — which is flexible and already exists, and throw the linear algebra at it. Or design a DEDICATED accelerator for the specific robotic algorithm, hand-crafting hardware that matches its exact dataflow for maximum efficiency. General hardware for reuse, or a bespoke chip for speed — the usual fork in accelerator design.
Why it fell short

General hardware wastes work on zeros; dedicated chips cost a fortune and do not compose

Both roads are bad. General matrix hardware IGNORES the sparse structure — it computes on all the zeros — so it wastes most of its work; a GPU baseline managed only about 2x over an ARM core, because the linear-equation construction is a small part of the time and the sparse SOLVE has no structural sparsity that a sparse library can exploit. Dedicated per-algorithm accelerators, on the other hand, each demand manual hardware design with enormous non-recurring-engineering (NRE) cost, cannot share compute units with each other, and — since a real robot runs localization AND planning AND control — must be STACKED, wasting large amounts of chip area. So you are stuck choosing between hardware that is efficient but bespoke-and-uncomposable, and hardware that is general but wasteful. Neither gives an efficient accelerator that covers the many algorithms a robot actually needs.
This paper's idea

Find what all the algorithms share, and generate one accelerator for all of them

Orianna (Chinese Academy of Sciences and Georgia Tech — Hao, Gan, Yu, Liu, Han, Wan, Liu) escapes the dilemma by unifying the algorithms so one generated accelerator serves them all. Two ideas make it work. A UNIFIED POSE REPRESENTATION — a Lie algebra for orientation plus a translation vector for position — replaces the incompatible pose formats different algorithms use (quaternions, transformation matrices), so every algorithm compiles to identical matrix operations, and it drops the zero-and-one padding of the common alternative, cutting 52.7% of the multiply-accumulate work. And FACTOR-GRAPH inference — recasting each algorithm as a bipartite graph of measurements and variables — captures the sparse structure and decomposes the giant sparse solve into many SMALL DENSE matrices (11.1x smaller, density up from 5.3% to 58.5%). A three-layer toolchain then compiles any such algorithm to nine primitive operations and auto-generates an accelerator that matches dedicated designs using only 36.1% of their hardware.

Why this problem is worth solving

Autonomy runs on a handful of optimization algorithms, and their speed and energy directly bound how capable and how long-lived a robot can be — so accelerating them well matters, and doing it without a bespoke chip per algorithm matters even more. The shared computational heart of all these algorithms is the

the computation at the core of optimization-based robotics. Localization, planning, control, and bundle adjustment are all posed as nonlinear least-squares problems, and solved by iteration: from the current estimate, linearize the problem, build a linear system Ax=b whose matrix A encodes how each measurement constrains each variable, solve it for a correction, apply the correction, and repeat until convergence. The matrix A is large and extremely sparse — most measurements touch only a few variables, so the vast majority of A is zero (98.5% in one localization example). Each iteration is dominated by constructing this sparse system and, especially, solving it, and a robot must do this many times per second, in real time, within a tight power budget

. Because the same sparse-solve structure recurs across every one of these algorithms, it is the obvious target for acceleration — but it is a target that general hardware and bespoke hardware both handle badly.

The reason both fail is that the sparsity is real but treacherous, and the algorithms look different on the surface even though they share a core. The

the fact that a robotic optimization matrix is overwhelmingly sparse, yet its zeros are NOT arranged in a regular, exploitable pattern. Nearly 99% of the entries are zero, so a dense matrix engine wastes almost all of its work multiplying zeros. But the non-zeros are scattered irregularly, so a general sparse-matrix library — which relies on structured sparsity to skip work efficiently — finds no pattern to exploit either, and its bookkeeping overhead can exceed its savings. So the sparsity is abundant but not in a form either kind of general engine can use, which is exactly why dedicated accelerators, built by hand to match one algorithm’s specific structure, have been the only efficient option — at the price of NRE cost, no reuse across algorithms, and wasted area when several must run together

. Orianna’s opportunity is to notice that a change of representation can convert this abundant-but-unusable sparsity into a form hardware loves — many small DENSE blocks — and that a single unified representation can make every robotic optimization algorithm compile to the same operations, so one automatically-generated accelerator can be both efficient AND general. That is the escape from the dilemma.

What people did before, and where it broke

General matrix accelerators (GPUs, systolic arrays). Flexible and available, but they ignore the sparse structure and compute on the 98.5% of entries that are zero — so a GPU baseline reached only about 2x over an ARM core, because construction is a small fraction of the time and the sparse solve has no structure a sparse library can exploit.
General sparse-matrix libraries. Built to skip zeros, but they need STRUCTURED sparsity to do so efficiently, and robotic matrices are irregularly sparse, so their overhead can outweigh their savings on these problems.
Dedicated per-algorithm accelerators (FGALIO, Blitzcrank, FGLQR). Hand-designed to match one algorithm’s exact dataflow, so very efficient — but each carries huge NRE cost, cannot share compute with the others, and must be stacked when a robot runs several algorithms, wasting chip area.
Accelerating one algorithm in isolation. Most prior robotic accelerators target a single task (say, just SLAM). A real robot needs localization, planning, AND control, so single-task designs do not add up to a whole-robot solution without stacking.
The gap. No approach was both efficient (exploiting the sparsity) and general (covering many algorithms) without per-algorithm manual design. Orianna is, by unifying the algorithms’ representation and generating the accelerator automatically.

How Orianna works

Unify the pose, express as a factor graph, compile to primitives, generate the chip

Escape the dilemma by unifying the algorithms new

Rather than a generic engine (which misses sparsity) or many dedicated ones (NRE and area), Orianna finds the structure common to all optimization-based robotic algorithms so one framework can generate a single efficient accelerator that serves them all — being general without being generic.
↓ →
Adopt one unified pose representation new

Different algorithms represent a robot's pose incompatibly (quaternions, transformation matrices), which blocks unified hardware. Orianna standardizes on a Lie algebra for orientation plus a translation vector for position, so diverse algorithms compile to identical matrix operations — and because this representation avoids the zero-and-one padding of transformation matrices, it cuts 52.7% of multiply-accumulate work at the same accuracy.
↓ →
Express each algorithm as a factor graph new

The user composes an algorithm by adding FACTOR nodes — sensor measurements (LiDAR, GPS, IMU, camera) and constraints (collision-free, dynamics, kinematics) — connected to VARIABLE nodes (the poses to solve for). This bipartite factor graph is a natural, uniform description of the optimization problem that captures its sparse structure, and custom factors need only an error function.
↓ →
Turn the giant sparse solve into small dense blocks new

Instead of solving the whole sparse matrix at once, factor-graph inference does incremental variable elimination and back-substitution, decomposing the problem into many small DENSE matrices — shrinking a 147-by-90 matrix at 5.3% density into blocks around 41-by-12 at 58.5% density (11.1x smaller). Dense blocks run efficiently on the generated hardware with no cycles wasted on zeros.
↓ →
Compile to nine primitive operations and a schedule new

A compiler turns each factor into a Matrix-Operation Data Flow Graph: a forward traversal produces the error vector b, and backward propagation produces the Jacobian matrix A. Everything lowers to nine primitive matrix operations (rotation transpose, log/exp maps, skew-symmetric, Jacobians, and so on) plus QR-decomposition and back-substitution instructions, with operations in the same layer marked parallel.
↓ →
Generate the accelerator by optimization, run out-of-order new

A template-based hardware generator (systolic arrays for matrix multiply, a QR-decomposition template) decides how many of each compute unit to replicate by solving a nonlinear integer program — minimize latency subject to a resource budget — and auto-wires the datapath. At runtime a controller issues instructions out-of-order, exploiting parallelism within a factor, across factors, and between independent algorithms.

Evaluated on four real robots — a mobile robot, a 2-link manipulator, a 4-wheel autonomous vehicle, and a quadrotor drone — running localization, planning, and control, prototyped on a Xilinx Zynq-7000 FPGA (167 MHz), against an Intel i7 CPU, an embedded GPU (Jetson TX1), and a stack of state-of-the-art dedicated accelerators.

The idea

Escape the general-versus-dedicated dilemma by finding the shared structure. Accelerator design usually forces a choice between a general engine (reusable but inefficient) and a dedicated one (efficient but bespoke and single-purpose), and for robotic optimization both horns are painful — the general engine drowns in zeros, the dedicated one costs NRE and cannot compose. Orianna’s central move is to refuse the choice by discovering what every optimization-based robotic algorithm has in common: cast a robot’s pose in one unified representation, and every such algorithm becomes FACTOR-GRAPH inference over the same primitive operations. Now a single framework can generate one accelerator that is efficient (because it exploits the shared structure) AND general (because all the algorithms map onto it). This is the find-the-unifying-abstraction discipline the site rewards — the GNN-operator page expressing 160 operators as one nested loop, the graph-mining page reducing all its set operations to one bitvector primitive — where the win comes from seeing that superficially different tasks share a form, and building one efficient thing for that form.

Change the representation until the useful structure becomes explicit. The sparsity in a robotic matrix is abundant (99% zeros) but useless to both dense and sparse engines, because it is irregular. Orianna’s factor-graph inference is a change of representation that converts this abundant-but-unusable sparsity into abundant-and-usable structure: incremental variable elimination decomposes the one giant irregular-sparse matrix into many small DENSE blocks, which are exactly what matrix hardware runs efficiently. The structure was latent in the problem all along — each measurement touches few variables — and the factor graph makes it explicit and exploitable. This is the same match-the- representation-to-expose-the-structure move the site sees when viewing quantum errors in Hamming space reveals they cluster, or counting per-word accesses reveals a page is sparse — reformulate so the property you need to exploit becomes visible, and hardware that could not use the raw form runs beautifully on the transformed one.

Pick the representation that also does less work, and generate the rest. The unified pose representation is not just a common compiler target; it is a cheaper one. Transformation matrices pad their entries with structural zeros and ones that a matrix engine dutifully multiplies, whereas the Lie-algebra-plus-translation form carries only the real degrees of freedom, so it does 52.7% fewer multiply-accumulates at the same accuracy — choosing the encoding that avoids computing on structural padding, the don’t-pay-for-what- is-not-information discipline the numerics and rendering pages share. And rather than hand-design the accelerator, Orianna GENERATES it: it poses “how many of each compute unit to build” as an integer program that minimizes latency under a resource budget, the auto-generate-via-optimization move the compiler-autotuning and LLM-mutator pages make to replace expensive human design — here turning a per-algorithm NRE cost into a one-time framework that outputs an accelerator for any robotic optimization.

One framework, many robots

From a bespoke chip per algorithm to one generated accelerator

Accelerating the optimization algorithms a robot runs. Numbers from Orianna's evaluation.

Step 1 of 5

The robot's compute problem

A robot must run localization, planning, and control concurrently, each an iterative solve of a large sparse least-squares system, each in real time on limited power. The same computational pattern — build a sparse Ax=b, solve for a correction, repeat — recurs across all of them, which makes it the natural thing to accelerate, for several algorithms at once.

a traditional localization runs at only 5 Hz on a desktop CPU — far too slow for a moving robot
the algorithms look different on the surface but share this iterative sparse-solve core

Why it works

Every optimization-based robotic algorithm shares an iterative sparse-solve core → a unified pose representation makes them all compile to identical operations → one generated accelerator serves many algorithms instead of one dedicated chip each.
The matrix is 99% sparse but irregularly, useless to dense and sparse engines alike → factor-graph inference decomposes it into many small DENSE blocks (11.1x smaller, 58.5% dense) → hardware runs it efficiently with no cycles on zeros.
Transformation matrices pad entries with structural zeros and ones → the Lie-algebra-plus-translation representation carries only real degrees of freedom → 52.7% fewer multiply-accumulates at the same accuracy.
Hand-designing an accelerator per algorithm is costly and uncomposable → a generator picks compute-unit counts by solving an integer program under a resource budget → the accelerator is produced automatically and matches dedicated designs at 36.1% of their hardware.
A robot’s algorithms and their sub-operations are largely independent → out-of-order execution overlaps work within a factor, across factors, and across algorithms → 6.3x over in-order and high utilization of the shared compute.

What it costs

QR decomposition still dominates. Even after factorization, matrix decomposition is 74% of the latency, so it caps the overall speedup, and its decomposed subproblems have no structural sparsity a GPU sparse library could accelerate further.
Modest FPGA prototype. Evaluated on a Xilinx Zynq-7000 at 167 MHz; scaling to high-performance FPGAs or an ASIC, and the attendant frequency and area behavior, is not demonstrated.
Standardization is a precondition. The unified pose representation only unifies the algorithms that adopt it; broad use would require community consensus, much as floating-point needed IEEE 754.
Elimination order left open. Factor-graph inference’s cost depends heavily on the variable-elimination order (which controls fill-in), and Orianna does not address how to choose a good order.
Narrow, simulated scope. It is validated on three algorithm classes (localization, planning, control) on four robots, with power estimated from the synthesis tool rather than measured silicon, and the out-of-order controller’s own overhead is not quantified.

The evaluation

Four real robots — a mobile robot, a 2-link manipulator, a 4-wheel autonomous vehicle, and a quadrotor drone — running localization, planning, and control, on an FPGA prototype, compared against an Intel i7 CPU, an embedded GPU, and a stack of state-of-the-art dedicated accelerators, with accuracy checked against GTSAM.

Accelerating a robot's optimization algorithms

Property	General matrix accelerator (GPU)	Dedicated per-algorithm accelerators	Orianna (generated, unified)
Exploits the sparse structure
Covers many algorithms
Design cost (NRE)
Hardware resources
Speed / energy

Orianna gets the efficiency of dedicated accelerators (within 1% of their latency, 2.9x better energy) at 36.1% of their hardware, and the generality of a single framework across localization, planning, and control — because the unified pose representation and factor-graph abstraction expose the shared structure that lets one generated design serve them all.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Orianna’s speedup is capped by QR decomposition, which remains 74% of the latency even after factor-graph inference and whose subproblems have no structural sparsity to accelerate further. It is prototyped on a modest FPGA at 167 MHz, with power estimated from the synthesis tool rather than measured silicon, and validated on three algorithm classes across four robots — so its generality is demonstrated within robotic optimization but not beyond, and the out-of-order controller’s own overhead is not quantified. Its unified pose representation only unifies algorithms that adopt it, which would need community standardization to become universal, and factor-graph inference’s efficiency depends on a good variable-elimination order that Orianna does not address. None of this dulls the core contribution — that the general-versus-dedicated accelerator dilemma for robotic optimization dissolves once you find the shared structure: a unified pose representation makes every such algorithm compile to the same operations, and factor-graph inference converts abundant-but- irregular sparsity into many small dense blocks hardware runs efficiently, so a single framework can auto-generate one accelerator that matches bespoke designs at a third of the hardware and serves all the algorithms a robot needs at once.

Background

Find the shared structure, transform to expose it, and generate rather than hand-build

Orianna sits in the site’s accelerator-and-robotics cluster and rhymes with several ideas covered elsewhere on this site. Its governing move is to escape the general-versus-dedicated dilemma by finding the abstraction all the algorithms share: cast a robot’s pose one way and every optimization-based robotic algorithm becomes factor-graph inference over the same primitives, so one generated accelerator can be efficient AND general — the find-the-unifying- abstraction discipline the GNN-operator page uses to express 160 operators as one nested loop and the graph-mining page uses to reduce its set operations to a single bitvector primitive. Its enabling insight is a change of representation that exposes exploitable structure: the matrix is 99% sparse but irregular, useless to dense and sparse engines alike, until factor-graph inference decomposes it into small dense blocks — the same match-the-representation-to-reveal- the-structure move the noisy-quantum page makes viewing errors in Hamming space and the tiered-memory page makes counting per-word accesses, reformulating so the latent structure becomes something hardware can use. It also picks the representation that does less work — the unified pose drops the structural padding of transformation matrices to save half its multiply-accumulates, the don’t-compute-on- padding thrift the numerics page shares — and it GENERATES the accelerator by solving an integer program rather than hand-designing it, the auto-generate-via-optimization move the compiler-autotuning page makes with Bayesian optimization and the compiler-fuzzing page makes by synthesizing tools instead of outputs. And its one flexible design replacing a stack of dedicated chips at a third the area is the amortize-one-mechanism-across-many-uses lesson the graph-mining page teaches when it packs many cheap units behind one control block.

If you remember only three things

1. Robots run optimization-based algorithms — localization, planning, control — that all iteratively build and solve a large, ~99%-sparse least-squares system in real time on limited power, and accelerating this forced a bad choice: a general matrix accelerator wastes work on the zeros (a GPU got only ~2x over ARM, and the irregular sparsity foils sparse libraries too), while a dedicated per-algorithm accelerator is efficient but costs huge manual design effort, cannot share compute, and wastes area when stacked for the several algorithms a robot needs.
2. Orianna dissolves the dilemma by finding the shared structure: a unified pose representation (a Lie algebra for orientation plus a translation vector) makes every algorithm compile to identical operations and drops transformation-matrix padding to save 52.7% of multiply-accumulates, and factor-graph inference recasts each problem as measurements-and-variables and decomposes the one giant irregular-sparse matrix into many small DENSE blocks (11.1x smaller, density up from 5.3% to 58.5%) that hardware runs efficiently; a three-layer toolchain then lowers everything to nine primitive operations and auto-generates the accelerator by solving an integer program for compute-unit counts, running out-of-order across factors and algorithms.
3. The generated accelerator matches a stack of state-of-the-art dedicated accelerators (within 1% latency, 2.9x better energy) at just 36.1% of their hardware, and beats a desktop CPU 6.5x/15.1x and an embedded GPU 28.6x, with per-task speedups of 48-61x over ARM and accuracy matching reference software — its limits being that QR decomposition still dominates (74%), the pose representation needs standardization to generalize, and elimination ordering is left open. The durable lessons: escape a general-versus-specialized dilemma by finding the abstraction the cases share, change the representation until the structure you need becomes exploitable, and generate the design by optimization rather than hand-building one per case.

Check yourself

Check your understanding

1. A robotic optimization matrix is 98.5% zeros, yet the paper says both dense matrix engines AND general sparse-matrix libraries handle it badly. Predict why abundant sparsity is not automatically useful.
2. Orianna could have built a general accelerator or a dedicated one per algorithm; instead it introduces a unified pose representation so all algorithms compile to the same operations. Predict why this is the crux of getting both efficiency and generality.
3. Orianna's unified pose representation (a Lie algebra plus a translation vector) not only unifies the algorithms but also cuts 52.7% of multiply-accumulate operations versus transformation matrices. Predict where that computational saving comes from.
4. Orianna reports that QR matrix decomposition remains 74% of its latency even after all its optimizations. Predict what this reveals about the shape of its speedup and where further gains must come from.

Sources

ACM DL: ORIANNA: An Accelerator Generation Framework for Optimization-based Robotic Applications — ASPLOS 2024 (full text read via the author-hosted PDF; no arXiv preprint).