StreamGrid: Streaming Point Cloud Analytics via Compulsory Splitting and Deterministic Termination

Accelerators for point clouds — the 3D dot-scans that self-driving cars and robots see the world through — waste huge energy shuttling half-finished data out to off-chip memory between processing stages, and the elegant trick that image chips use to avoid this (keep just a sliding window of data on-chip) does not fit point clouds because their key operations can touch any point and take an unpredictable amount of time; this paper (Shanghai Jiao Tong and Rochester) makes point clouds fit that trick anyway, by chopping the data into chunks and capping each operation at a fixed deadline, then training the model to tolerate both, cutting on-chip memory by 61 percent and energy by 41 percent while running 10 times faster than prior accelerators.

The argument in one glance

Problem

Point cloud accelerators keep spilling half-finished data to off-chip memory

Point clouds — sets of 3D points from sensors like LiDAR — power autonomous driving, robotics, augmented reality, and 3D modeling, and specialized accelerators exist to process them fast. But those accelerators share a fundamental inefficiency: between one pipeline stage and the next, they write the intermediate results out to off-chip memory and read them back. Going off-chip stalls the pipeline waiting on slow memory, and it burns energy — an off-chip memory access costs orders of magnitude more than an on-chip one, which is punishing on the mobile and embedded devices where point clouds are often processed. Point cloud designs typically paper over the latency with double buffering, overlapping the next stage's reads with the current stage's writes, but that hides the delay without removing the traffic, so the energy cost remains. The data never needed to leave the chip; the accelerator just had nowhere on-chip to keep it.
What people did

Borrow the line-buffer trick from image accelerators

Image processing accelerators already solved this. Their pipelines are dominated by stencil operations, where each output pixel depends only on a small neighborhood of nearby input pixels. So they use a line buffer: keep just the few rows of the producer's output that the consumer still needs on-chip, let the consumer read its neighborhood directly from there, and stream the whole pipeline with no off-chip traffic at all. Point cloud accelerators should be able to do the same.
Why it fell short

Point cloud operations break every assumption a line buffer needs

Line buffers work only when three things hold: each operation is locally dependent so its data fits in a small on-chip window, producer and consumer have fixed throughput so the minimal buffer size can be computed ahead of time, and access patterns are regular so there are no bank conflicts. Point cloud operations violate all three. Many are globally dependent: a single output of a sort or a nearest-neighbor search may, in principle, need to look at every input point, so a line buffer would have to hold the entire intermediate data — bitonic-sorting half a million points would need tens of megabytes on-chip, impossible on a mobile chip — and the global dependency also serializes the pipeline. And many are non-deterministic: the number of steps a tree-traversal search takes depends on the input (on a real dataset, one search averages 8,400 steps with a standard deviation of 6,800), so the throughput varies, the buffer size cannot be fixed offline, and the irregular accesses cause bank conflicts that stall the pipeline.
This paper's idea

Force point clouds to fit the streaming model, then train the model to tolerate it

StreamGrid makes point clouds streamable with two deliberate approximations. Compulsory splitting partitions the point cloud into small spatial chunks and relaxes the data dependencies across chunks, so a "global" operation only ever looks at a few neighboring chunks at a time — turning it into something like a stencil over chunks, which needs only a small buffer and pipelines cleanly. Deterministic termination caps each non-deterministic operation at a fixed deadline — for example, a fixed number of tree-traversal steps — so every operation finishes in a known time and the buffer size can be computed offline. Because both changes perturb the algorithm, an integrated co-training procedure bakes them into training so the model stays accurate. A framework then formulates the minimal buffer sizes as an optimization problem and solves it, generating a fully-streaming accelerator.

Why this problem is worth solving

The whole cost being attacked is memory traffic that should never have happened, and the fix that works for images is exactly the one point clouds resist.

In a staged accelerator pipeline, each stage produces intermediate data the next stage consumes. If there is nowhere on-chip to hold that data, it goes out to off-chip memory and comes back, which both stalls the pipeline behind slow memory and spends energy — off-chip access energy is orders of magnitude higher than on-chip, so on a mobile device this dominates. Image accelerators avoid it with line buffers, which exploit the fact that image operations are stencils: each output depends only on a small local neighborhood, so the pipeline only ever needs a few of the producer’s recent output rows kept on-chip. As the producer writes new rows the oldest are discarded, the consumer reads its neighborhood straight from the buffer, and the pipeline streams end to end with zero off-chip traffic for intermediates. This is why line buffering is a cornerstone of efficient image hardware. The question StreamGrid asks is whether point cloud pipelines, which have the same off-chip-traffic problem, can be made to enjoy the same solution — and the answer is not directly, because point cloud computation looks nothing like a stencil.

The barrier is that point cloud operations are global and unpredictable in exactly the ways line buffers cannot accommodate.

Point cloud operations fall into two kinds. Locally-dependent operations — elementwise scaling, small-neighborhood reductions and stencils — are fine; their data fits on-chip. The trouble is globally-dependent operations: sorting, range search, and k-nearest-neighbor search, where algorithmically a single output point may need to access every input point. Feeding such an operation from a line buffer would require buffering the whole intermediate point cloud, which for large clouds is tens of megabytes, infeasible on mobile hardware, and the global dependency also blocks pipelining because the consumer cannot start until all of the producer’s output exists. On top of that, these operations are typically non-deterministic: they traverse tree structures whose depth depends on the input, so their latency and throughput vary from point to point, which makes the required buffer size impossible to pin down before running, and their irregular memory accesses collide in the buffer’s banks and stall the pipeline. Local fit, fixed throughput, and regular access are precisely the three things a line buffer needs, and global-dependent, non-deterministic operations deny all three. Bridging that gap without giving up accuracy is what the paper is about.

What people did before, and where it broke

Double buffering to hide off-chip latency. Overlap the next stage’s reads with the current stage’s writes so the pipeline does not visibly stall on memory. Where it broke. It hides latency but does not remove the off-chip traffic, so the energy cost — the dominant concern on mobile devices — remains fully paid.
Line buffers, taken directly from image processing. Keep a small sliding window of intermediate data on-chip and stream the pipeline with no off-chip traffic. Where it broke. It assumes stencil-like local dependence, fixed throughput, and regular access; point cloud global operations need to buffer everything, do not have fixed throughput, and access memory irregularly.
Bigger on-chip buffers for the global operations. Simply provision enough on-chip memory to hold what a global operation might touch. Where it broke. The worst case is the entire intermediate point cloud — tens of megabytes for a large sort — which is impractical on the mobile systems-on-chip that are the target.
Naive independent splitting. Cut the point cloud into fully independent chunks and process each alone, shrinking each operation’s footprint. Where it broke. Isolating chunks discards the cross-chunk relationships the algorithm relied on; pushed far (in the limit, one point per chunk) it causes a large accuracy drop.
The gap. No approach let point cloud pipelines use line-buffer streaming — eliminating off-chip traffic — despite their global, non-deterministic operations, while keeping accuracy. Making the operations fit the streaming model by construction, and training the model to tolerate it, is what StreamGrid contributes.

How StreamGrid works

Reshaping point cloud pipelines until they stream on-chip

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

A “global” operation is only global on paper; in practice it stays local, so make that official. Compulsory splitting rests on a measured observation: although a sort or a nearest-neighbor search could algorithmically touch every point, each output actually interacts with only a small spatial subset, because these operations already partition space to find local relationships. On a real dataset split into an eight-by-eight grid, even a query asking for 256 neighbors touches only about sixteen chunks. So StreamGrid partitions the cloud into chunks and deliberately relaxes the dependencies across them, but rather than isolating chunks — which would throw away the cross-chunk relationships and hurt accuracy — it processes a small sliding window of neighboring chunks together, exactly like a stencil operating over chunks instead of pixels. That shrinks the buffer a global operation needs and lets consecutive chunk-groups pipeline. Making a search over a huge space tractable by exploiting that any one query only ever needs a small, spatially-local slice of the data is the same bet the work on high-dimensional approximate nearest-neighbor search covered elsewhere on this site makes, trading exhaustive reach for locality that is good enough in practice.

Give unpredictable operations a deadline, and teach the model to live with it. Deterministic termination confronts the other barrier — that tree-traversal searches run for an input-dependent number of steps, so their timing cannot be known offline — by simply capping every operation at a fixed number of steps: queries that finish early are untouched, queries that would run longer stop at the deadline and return their best answer so far. This converts variable, input-dependent delay into a fixed, known delay, which is what lets the buffer sizes be computed ahead of time. Because both this and the splitting perturb the algorithm, StreamGrid co-trains the model with both behaviors active so it learns to be robust to them, keeping accuracy loss marginal, and it sidesteps the non-differentiability by letting gradients flow only through the value-carrying local operations, not the relationship-establishing global ones. Deliberately dropping work to gain hardware efficiency and then retraining the model to absorb the loss is the same algorithm-and-hardware co-design the work on dynamic neural-network pruning covered elsewhere on this site relies on, cutting computation the model can be taught not to miss.

Once the pipeline is regular, sizing the buffers is an optimization problem to be solved, not guessed. After splitting and termination convert the pipeline into a deterministic, locally-windowed one, the last question is the smallest line buffer between each pair of stages that still eliminates off-chip traffic — and StreamGrid answers it automatically. The user describes the algorithm as a dataflow graph through an abstract interface, without operation details; StreamGrid extracts the data dependencies and communication patterns, forms a constrained buffer-minimization problem, and hands it to an integer linear programming solver under a chosen performance target, pruning the exploding parameter space by exploiting monotonicity in the constraints, then emits the hardware. Compiling a high-level dataflow description of a streaming, locality-bound computation down into efficient buffered hardware is the same generative path the work on a compilation stack for distributed-memory stencil parallelism covered elsewhere on this site takes, turning a description of local data movement into a concrete, efficient implementation.

Following a nearest-neighbor search through StreamGrid

Streaming a k-nearest-neighbor stage that would otherwise spill off-chip

A trace, following the paper's examples, of how StreamGrid turns a global, non-deterministic search into a streamable pipeline stage.

Step 1 of 5

The naive stage needs the whole cloud and a variable time

A k-nearest-neighbor search over the raw point cloud is globally dependent — any query might examine any point — so a line buffer would need to hold every intermediate point, and its kd-tree traversal takes an input-dependent number of steps, so its throughput is unpredictable.

On a real dataset, traversals average 8,400 steps with a standard deviation of 6,800 — far too variable to size a buffer for.

Why it works

Global operations are local in practice, so a small window suffices. Algorithmically a global operation could touch every point → but empirically each output touches only a few spatial chunks (about sixteen even for 256 neighbors) → so windowing over neighboring chunks captures almost all of the real dependency while needing only a tiny fraction of the buffer.
Windowing over chunks restores pipelining that global dependence destroyed. A truly global consumer must wait for its producer to finish entirely → but grouping adjacent chunks into independent stencil-like units lets consecutive chunk-groups run concurrently → so the pipeline overlaps stages instead of serializing them.
A fixed deadline turns unpredictable timing into schedulable timing. Input-dependent traversal length makes buffer sizing impossible offline → but capping every operation at a fixed number of steps makes its delay known and uniform → so the minimal line buffer between stages can be computed before the accelerator ever runs.
Co-training converts approximation into learned robustness. Splitting and early termination perturb the algorithm and could wreck accuracy → but training the model with both behaviors active, with gradients through the local operations, teaches it to tolerate them → so accuracy loss stays marginal rather than severe like naive splitting.
Regularizing the pipeline makes buffer sizing a solvable program. Non-deterministic, global pipelines have no well-defined minimal buffer → but once deterministic and local-windowed, sizing becomes a constrained integer program, tamed by pruning parameters via constraint monotonicity → so the framework finds provably minimal on-chip buffers automatically.

What it costs (trade-offs and scope)

Both core techniques are approximations. Compulsory splitting relaxes real cross-chunk dependencies and deterministic termination cuts searches short, so results differ from the exact algorithm; accuracy is kept only marginally reduced, and only through co-training that must fit the perturbed behavior.
It requires retraining the model. The accuracy guarantee comes from folding both behaviors into training, so applications that cannot be retrained, or classical non-learned pipelines that have no training loop to absorb the change, do not get the same protection.
Key parameters are chosen, not derived. The number of chunks and the termination deadline are tunable parameters set empirically for performance; splitting is applied uniformly and offline, and the authors leave more fine-grained or adaptive splitting to future work, so a poor choice trades accuracy against efficiency.
Some hard parts are borrowed, not solved. Bank conflicts from irregular access are handled by adopting an existing conflict-elision technique that simply drops the conflicting requests — another approximation — and the paper explicitly claims no contribution there, so that source of inaccuracy and its tuning remain.
The evaluation covers specific pipelines and operations. Results span four domains — classification, segmentation, registration, and neural rendering — over sorting, range, and nearest-neighbor operations; how the approach generalizes to other point cloud operations, pipelines, or accuracy-critical settings is not established here.

The evaluation

Making a point cloud pipeline stream on-chip

Property	Double buffering	Naive independent splitting	StreamGrid
Off-chip traffic for intermediates
Global operations
Non-deterministic timing
Accuracy
On-chip memory and energy	Baseline

From the paper's evaluation across four application domains (classification, segmentation, registration, neural rendering). Versus baselines without its techniques, StreamGrid reduces on-chip memory by 61.3 percent and energy by 40.5 percent with marginal accuracy loss; against five state-of-the-art accelerators it averages 10.0 times speedup and 3.9 times energy reduction with comparable hardware resources.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is a clean way to import a proven efficiency technique — line-buffer streaming — into a domain that structurally rejects it. StreamGrid observes that point cloud global operations are effectively local in practice and that non-deterministic ones can be capped, so it makes them fit the streaming model by construction: compulsory splitting windows global operations over spatial chunks, deterministic termination fixes their runtime, co-training keeps the model accurate under both, and an integer-programming framework sizes the minimal on-chip buffers and generates the hardware. The payoff is real: 61.3 percent less on-chip memory and 40.5 percent less energy than not using the techniques, and on average 10.0 times the speed and 3.9 times the energy efficiency of prior accelerators. Read it within scope. Both techniques are approximations that only stay accurate through retraining, so non-trainable or accuracy-critical pipelines are outside the guarantee; the chunk count and deadline are hand-tuned and splitting is uniform and offline; bank-conflict handling is borrowed and lossy; and the evidence covers four domains and a specific set of operations. Within those bounds it is a strong example of co-designing an algorithm, a training procedure, and a hardware dataflow to unlock streaming where it seemed impossible.

Background

Why streaming and line buffers matter for accelerators

It helps to see the bigger pattern StreamGrid fits into. Across specialized hardware, the expensive thing is rarely the arithmetic — it is moving data, and especially moving it off the chip to and from main memory, which costs orders of magnitude more energy than an on-chip access and stalls the pipeline waiting on slow memory. So a recurring goal in accelerator design is to keep data resident on-chip and let it flow directly from one processing stage to the next, a streaming or dataflow style of execution, of which the line buffer is a classic instance born in image processing: hold only the sliding window of data the next stage still needs, and never touch off-chip memory for intermediates at all. The difficulty is always that streaming demands regularity — predictable, local, fixed-rate data movement — which many interesting computations lack. Turning an irregular, data-dependent computation into a regular streaming dataflow that hardware can pipeline efficiently is exactly the reason the neural-rendering accelerator work on Gaussian-splatting rendering covered elsewhere on this site builds custom dataflow support for its sorting-heavy pipeline, wrestling an awkward, data-dependent workload into a form that streams. StreamGrid earns that same regularity for point clouds by reshaping the algorithm itself until it streams.

If you remember only three things

1. Point cloud accelerators waste energy and stall pipelines by writing intermediate results to off-chip memory between stages, and the line-buffer technique that lets image accelerators keep everything on-chip does not transfer, because point cloud operations are often globally dependent (a single output of a sort or nearest-neighbor search could need every input point, blowing up the buffer and serializing the pipeline) and non-deterministic (tree-traversal searches take an input-dependent number of steps, so throughput varies and buffer sizes cannot be fixed offline).
2. StreamGrid makes point clouds streamable with two deliberate approximations plus co-training: compulsory splitting partitions the cloud into spatial chunks and relaxes cross-chunk dependencies, running global operations over a small sliding window of neighboring chunks (a stencil over chunks) because empirically each output only touches a few chunks; deterministic termination caps each non-deterministic operation at a fixed step deadline so its timing is known offline; and an integrated co-training procedure folds both behaviors into training — with gradients flowing only through the local, value-carrying operations — so accuracy loss stays marginal rather than the large drop naive independent splitting causes.
3. A framework then formulates the minimal on-chip line-buffer sizes as an integer linear program from a dataflow-graph description, prunes the exploding parameter space using monotonicity in the constraints, and generates a fully-streaming accelerator; across four domains it cuts on-chip memory by 61.3 percent and energy by 40.5 percent versus not using the techniques, and averages 10.0 times speedup and 3.9 times energy reduction against five state-of-the-art accelerators — with the caveats that both techniques are approximations dependent on retraining, key parameters are hand-tuned, bank-conflict handling is borrowed and lossy, and the evidence covers a specific set of pipelines and operations.

Check yourself

Check your understanding

1. Why can the line-buffer technique from image accelerators not be applied directly to point clouds?
2. What is compulsory splitting, and why does it not wreck accuracy?
3. What do deterministic termination and co-training accomplish?
4. What did StreamGrid achieve, and what are its limits?

Sources

The paper is “StreamGrid: Streaming Point Cloud Analytics via Compulsory Splitting and Deterministic Termination” by Yu Feng, Zheng Liu, Weikai Lin, Zihan Liu, Jingwen Leng, Minyi Guo, Zhezhi He, Jieru Zhao, and Yuhao Zhu (Shanghai Jiao Tong University, Shanghai Qi Zhi Institute, and University of Rochester), published at ASPLOS 2025, DOI 10.1145/3676641.3716021.

This explainer is written from the full text of the authors’ arXiv version (arXiv:2503.05197). Everything above comes from the paper’s own sections: the introduction and background on frequent off-chip memory traffic in point cloud accelerators, the line-buffer technique in image processing and its three requirements (local dependence, fixed throughput, regular access), and why point cloud operations — classified into local-dependent and global-dependent (sorting, range search, k-nearest-neighbor search) categories — violate them; the challenges of global-dependent operations requiring unaffordable on-chip buffers (for example tens of megabytes to bitonic-sort half a million points) and disrupting pipelining, and of non-determinism where tree-traversal runtime is input-dependent (measured average 8,400 steps with standard deviation 6,800 on the KITTI dataset) causing variable throughput and bank conflicts; the two techniques — compulsory splitting, motivated by the observation that global operations touch few chunks in practice (about sixteen chunks even for 256 neighbors on an eight-by-eight grid) and implemented as a stencil-like sliding window over neighboring chunks rather than naive isolation, and deterministic termination, which caps non-deterministic operations at a fixed step deadline; the integrated co-training procedure that folds both behaviors into training, with gradients flowing only through local-dependent operations, and the borrowed bank-conflict-elision technique; the StreamGrid framework that takes a dataflow-graph description, extracts dependencies and communication patterns, formulates a constrained line-buffer-minimization problem solved with an integer linear programming solver under a performance target, and prunes parameters using monotonicity in the constraints before generating register-transfer-level hardware; and the evaluation across four domains reporting a 61.3 percent on-chip memory reduction and 40.5 percent energy savings with marginal accuracy loss versus baselines without the techniques, and an average 10.0 times speedup and 3.9 times energy reduction against five state-of-the-art accelerators with comparable hardware resources.