Treelet Accelerated Ray Tracing on GPUs

Ray tracing makes games look stunning but tanks frame rates, so players often turn it off, because tracing rays through a scene thrashes the GPU's caches — the tree of geometry it searches is far too big to fit on-chip and rays wander through unrelated parts of it; a known fix from specialized hardware is to slice the tree into cache-sized chunks and process together all the rays visiting the same chunk, but that never worked on a GPU; this work from the University of British Columbia figures out why and fixes it with three coordinated tricks, roughly doubling ray-tracing performance in game-like conditions.

The argument in one glance

Problem

Ray tracing tanks frame rates because it thrashes the cache

GPUs have ray-tracing hardware, but tracing rays searches a huge tree of geometry (a bounding volume hierarchy) that will not fit on-chip, and incoherent rays wander through unrelated parts of it, so cache miss rates are high and the ray-tracing unit stalls on memory. Players often turn ray tracing off.
What people did

Slice the tree into cache-sized treelets

A known idea from specialized accelerators: cut the big tree into subtrees (treelets) that fit in cache, and process all the rays that visit a treelet together before switching, so the treelet stays cached and memory traffic drops.
Why it fell short

Naive treelets give no speedup on a GPU

On a GPU a plain treelet implementation does not help at all: the GPU cannot keep enough rays in flight to fill the treelet groups so there is little reuse, and grouping divergent rays destroys the lockstep (SIMT) efficiency GPUs need for good throughput.
This paper's idea

Virtualized treelet queues (three coordinated fixes)

The paper makes treelets work with three techniques: ray virtualization frees GPU cores so many more rays are in flight to fill the groups; dynamic treelet queues group rays by treelet for cache reuse and switch to normal traversal when groups thin out; and warp repacking regroups active rays to restore lockstep efficiency. Together they give about 95 percent average speedup, up to 2.55 times.

Why this problem is worth solving

Ray tracing is how you get truly photorealistic lighting, but it has always been too expensive to run smoothly in real time.

Ray tracing renders an image by shooting rays through a scene and computing where each one intersects the geometry, which naturally captures realistic reflections, shadows, and lighting — it is the standard for offline movie rendering. Doing it in real time is the hard part. Modern GPUs from NVIDIA, AMD, and Intel now include dedicated ray-tracing hardware (an RT unit), yet even so they can only manage limited ray-traced effects within the roughly sixty-frames-per-second budget of interactive rendering, which is why enabling ray tracing in a game so often drops the frame rate that players just turn it off. The fundamental cost is memory, not arithmetic. To avoid testing every ray against every triangle, a scene’s geometry is organized into a bounding volume hierarchy — a tree of nested boxes that the hardware walks to quickly narrow down which geometry a ray could hit. Walking this tree is where the time goes: the tree is large and does not fit in on-chip caches, so traversal constantly misses the cache and stalls on long off-chip memory accesses. Measured on real scenes, the average cache miss rate for these tree accesses is well over half and reaches as high as seventy percent, meaning the caches barely help.

The reason the caches fail is baked into how rays behave, and a classic idea addresses it — but only on hardware unlike a GPU.

Rays are incoherent: nearby pixels’ rays quickly diverge and wander through completely different parts of the tree, so at any moment the many rays in flight are touching scattered, unrelated tree nodes with no shared locality for the cache to exploit. The classic remedy, introduced for specialized ray-tracing accelerators, is the treelet: cut the big tree into small subtrees, each sized to fit in the cache, and then reorder the work so that all the rays which will visit a given treelet are processed together, before switching to the next treelet. Because a treelet stays resident in cache while all its rays are handled, this reuse dramatically cuts memory traffic — prior work reported reductions of fifty to seventy-five percent on custom accelerators. The trouble is that GPUs are different. A GPU executes rays as threads bundled into warps that run in lockstep, and it has two properties that break naive treelets: it can only keep a limited number of rays in flight at once, and it suffers when threads in a warp diverge. The authors tried the obvious treelet implementation on a GPU and got no speedup at all, because there were too few rays in each treelet group to create real reuse, and because the grouping shattered the lockstep efficiency the GPU relies on.

What people did before, and where it broke

Add a dedicated RT unit to the GPU. Give the GPU hardware to accelerate bounding-volume-hierarchy traversal and ray-triangle intersection. Where it broke. The RT unit still stalls on the memory-bound tree walk, with cache miss rates well over half, so ray tracing remains too slow for smooth real-time use.
Use treelets on a specialized accelerator. Reorder rays by treelet on custom or MIMD hardware to cut memory traffic. Where it broke. Those architectures do not have a GPU’s lockstep execution and warp-slot limits, so their design does not transfer; and some reduced traffic but raised memory bandwidth demand.
Implement treelets naively on a GPU. Port the treelet idea directly into a GPU’s RT unit. Where it broke. The GPU could not keep enough rays in flight to fill the treelet queues, so there was little cache reuse, and grouping divergent rays crushed lockstep (SIMT) efficiency — the net result was no speedup.
Prefetch treelets on a GPU. Predict and prefetch treelet data during traversal. Where it broke. It helped modestly (about a thirty percent speedup) but a large fraction of prefetches went unused, wasting memory bandwidth.
The gap. No approach made treelets actually pay off on a GPU by supplying enough concurrent rays and preserving lockstep efficiency. Providing both, with virtualized treelet queues, is what this work does.

How virtualized treelet queues work

From ineffective naive treelets to virtualized treelet queues

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

The idea

Reorder the rays so they reuse what is already in cache. The heart of the approach is the treelet: rather than let each ray wander the huge tree independently and miss the cache, the RT unit gathers all the rays that will visit the same cache-sized subtree into a queue and processes them together, so that subtree stays resident and its data is reused across many rays instead of being fetched again and again. And because rays diverge more in the later phases of traversal, leaving queues underpopulated, the design dynamically switches back to ordinary traversal when grouping stops paying off, rather than forcing an inefficient treelet pass. Reordering concurrent traversals so that the ones touching the same data are handled together, turning scattered, locality-free accesses into reuse of a resident working set, is the same move the concurrent graph-traversal work covered elsewhere on this site makes, aligning many simultaneous walks over a large structure so they share the data brought on-chip instead of each thrashing the cache on its own path.

Supply enough concurrent work to make the grouping worthwhile. Grouping rays by treelet only helps if there are enough rays visiting a treelet at once to amortize keeping it cached, and a GPU normally cannot: the number of rays in flight is capped by the warp slots in the RT unit, because each ray occupies a thread. Ray virtualization breaks that cap by terminating a raygen shader the moment its thread has handed its ray to the RT unit, reclaiming the CUDA core so the GPU can immediately launch more raygen threads and issue more rays — greatly increasing the rays concurrently in flight to fill the treelet queues. Extracting far more usable parallelism from a workload whose naive mapping leaves the hardware starved, so there is enough concurrent work to expose reuse, is the same discipline the fine-grained-parallelism accelerator work covered elsewhere on this site is built on, restructuring how work is issued so the highly parallel hardware is actually kept full rather than idling for lack of exposed independent operations.

Do not let the parallel datapath run mostly empty. A GPU gets its throughput from executing a warp of threads in lockstep, so when rays in a warp diverge and finish at different times, most lanes go inactive and the datapath wastes cycles on nothing — and grouping underpopulated treelet queues makes this worse, sharply dropping SIMT efficiency. Warp repacking counters this by regrouping the still-active rays from across partly-idle warps into freshly packed warps, so the lanes are full again and the RT unit does useful work every cycle, which the authors find is essential to getting good performance out of treelets. Compacting live work so the wide parallel hardware is not squandered on inactive lanes, keeping the datapath busy rather than stalled behind divergence, is the same goal the optimized-dataflow work covered elsewhere on this site pursues, restructuring how computation flows through the hardware so the expensive parallel units stay productively occupied instead of idling.

Following a ray-tracing frame through virtualized treelet queues

Rendering a path-traced frame with virtualized treelet queues

A trace of the paper's design handling rays on a GPU RT unit, following its ray-virtualization, treelet-queue, and warp-repacking mechanics.

Step 1 of 5

Rays are generated but the tree does not fit

A raygen shader spawns rays for the frame. Each must traverse the bounding volume hierarchy to find intersections, but the tree is far larger than the cache and incoherent rays would otherwise thrash it.

Baseline cache miss rates for tree accesses exceed half.

Why it works

Treelet grouping turns misses into reuse. Because all the rays visiting a cache-sized subtree are processed together → that subtree stays resident and its nodes are reused across many rays → so the dominant memory traffic of tree traversal is sharply reduced.
Virtualization removes the concurrency cap. Because a raygen shader is terminated once its ray is handed to the RT unit → the freed CUDA core launches more rays rather than sitting idle → so there are enough concurrent rays to actually fill the treelet queues and create reuse.
Mode switching avoids wasted treelet passes. Because rays diverge and queues thin out later in traversal → switching those underpopulated queues to regular traversal skips inefficient grouping → so effort is not spent maintaining treelets that no longer pay off.
Warp repacking preserves lockstep throughput. Because divergent rays leave lanes inactive and grouping worsens it → repacking active rays into full warps restores SIMT efficiency → so the wide RT datapath is not wasted running mostly-empty warps.
The pieces are interdependent. Because grouping needs concurrency, and concurrency plus grouping causes divergence → ray virtualization, dynamic queues, and warp repacking each fix what the others expose → so only together do treelets finally deliver a GPU speedup.

What it costs (trade-offs and scope)

It requires changes to the GPU’s RT unit. Virtualized treelet queues are a hardware architecture — dynamic treelet queues, the ray-virtualization mechanism, and warp repacking are added to the ray-tracing unit — so this is a design for future GPUs, not a software optimization for today’s hardware.
Ray virtualization adds bookkeeping. Terminating raygen shaders and relaunching rays, and tracking rays that are in flight without holding a core, requires mechanism and state to manage the extra concurrent rays; the benefit depends on that machinery being cheap enough relative to the reuse it unlocks.
The benefit depends on the workload having reuse to find. Treelets help because many rays share treelets; scenes or ray distributions with very little such overlap would offer less to gain, and the dynamic mode switching exists precisely because that overlap fades late in traversal.
Results are from simulation on one benchmark. The roughly 95 percent average and up-to 2.55 times speedups are measured in Vulkan-Sim, a cycle-level GPU simulator, on the LumiBench scenes with path tracing at one sample per pixel and three bounces per ray; real silicon and other workloads or settings would shift the numbers.
The three techniques must be co-tuned. Because the mechanisms interact — more concurrency enables grouping but also causes the divergence that repacking must fix — their benefit comes as a package, and the design’s effectiveness depends on balancing them rather than any one in isolation.
It targets traversal, the memory-bound core. The work accelerates bounding-volume-hierarchy traversal, the dominant cost; other parts of the rendering pipeline (shading, denoising) are outside its scope and would bound overall frame-rate gains.

The evaluation

Approaches to speeding up GPU ray-tracing traversal

Property	Baseline RT unit	Virtualized treelet queues
Cache behavior on tree traversal
Concurrent rays in flight
SIMT (lockstep) efficiency
Adapts as rays diverge	Not applicable
Path-tracing speedup	Baseline	About 95 percent average, up to 2.55x

Approaches to speeding up ray-tracing traversal on a GPU, as compared in the paper. A baseline GPU RT unit walks the bounding volume hierarchy per ray, but incoherent rays give cache miss rates over half and low SIMT efficiency, so traversal stalls on memory. Naively porting treelets — grouping rays that visit the same cache-sized subtree — fails on a GPU because it cannot keep enough rays in flight to fill the treelet queues (so there is little reuse) and grouping divergent rays further hurts lockstep efficiency, netting no speedup. Virtualized treelet queues fix this with three coordinated techniques: ray virtualization terminates a raygen shader once its thread issues the trace-ray instruction, reclaiming the CUDA core so more raygen threads launch and far more rays are concurrently in flight to fill the queues; dynamic treelet queues group rays by treelet for cache locality and switch to ordinary traversal when queues become underpopulated as rays diverge; and warp repacking regroups the still-active rays into full warps to restore SIMT efficiency, which the authors find crucial. Simulated in Vulkan-Sim on the LumiBench scenes with path tracing at one sample per pixel and three maximum bounces per ray, virtualized treelet queues achieve about 95 percent speedup on average over a baseline ray-tracing GPU, and up to 2.55 times better path-tracing performance under usage scenarios comparable to video games.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is a satisfying computer-architecture result that takes an idea long known to work on specialized hardware and finally makes it deliver on a GPU by diagnosing exactly why the naive port fails. The problem is concrete and familiar: ray tracing looks gorgeous but is too slow for smooth real-time rendering, so players disable it, and the bottleneck is memory — traversing the bounding volume hierarchy, a tree too big for cache, with incoherent rays that thrash it, giving miss rates over half. Treelets, which slice the tree into cache-sized subtrees and process a subtree’s rays together, cut that traffic dramatically on custom accelerators, but a naive GPU implementation yields zero speedup. The paper’s contribution is to identify the two reasons — too few rays in flight to fill the treelet groups, and lockstep-efficiency loss from grouping divergent rays — and to fix each: ray virtualization frees GPU cores to put far more rays in flight, dynamic treelet queues group for locality and gracefully fall back to normal traversal when groups thin, and warp repacking recompacts active rays to keep the SIMT datapath full. The three are interdependent, and only together do they work, which is itself the insight: treelets on a GPU are not one trick but a co-design. The reported gains are strong — about 95 percent average speedup, up to 2.55 times in game-like conditions. Read the scope carefully. This is a hardware architecture evaluated in a cycle-level simulator (Vulkan-Sim) on one benchmark suite (LumiBench) at specific path-tracing settings, so it is a design for future GPUs rather than a change to today’s, and real silicon and other workloads would move the numbers; the benefit depends on scenes having ray-treelet overlap to exploit; and it accelerates traversal specifically, with the rest of the rendering pipeline bounding overall gains. The durable idea is that a technique’s success is architecture-specific: an optimization that works beautifully on one machine can fail completely on another until it is re-engineered around that machine’s real constraints — here, a GPU’s limited ray concurrency and its dependence on lockstep execution.

Background

Why real-time ray tracing keeps pushing GPU architecture

It helps to see this work within the broader push to make real-time ray tracing practical, which has become a major driver of GPU architecture as vendors add dedicated ray-tracing units and researchers hunt for the memory and execution optimizations that will let those units run smoothly at game frame rates. The programmable-GPU graphics work covered elsewhere on this site reflects the same domain from the infrastructure side, building open, flexible GPU rendering platforms on which exactly these kinds of ray-tracing and traversal techniques can be explored and evaluated. The common thread is that rendering is one of the most demanding and economically important GPU workloads, and its performance is gated less by raw arithmetic than by how well the memory system and the parallel datapath are kept fed — which is precisely what treelets, ray virtualization, and warp repacking address. As real-time ray tracing spreads from high-end games toward being a default expectation, the pattern this paper exemplifies — taking memory-locality ideas from offline and specialized rendering and re-engineering them to fit the GPU’s concurrency and lockstep-execution model — is likely to keep shaping how ray-tracing hardware evolves.

If you remember only three things

1. Ray tracing renders photorealistic images by shooting rays through a scene to find geometry intersections, and modern GPUs include dedicated ray-tracing (RT) units, but it is still too slow for smooth real-time rendering, so players disable it. The bottleneck is memory: scene geometry is stored in a bounding volume hierarchy (BVH), a tree the hardware searches, but the tree is far larger than on-chip caches and rays are incoherent — they wander through unrelated parts of the tree — so cache miss rates for traversal average well over half (up to seventy percent) and the RT unit stalls on long memory accesses, while SIMT (lockstep) efficiency is also low. A classic fix from specialized accelerators is the treelet: cut the tree into cache-sized subtrees and process together all the rays that visit one treelet before switching, so the subtree stays cached and memory traffic drops (fifty to seventy-five percent on custom hardware). But a naive treelet implementation on a GPU gives no speedup at all, because a GPU cannot keep enough rays in flight to fill the treelet groups and because grouping divergent rays wrecks the lockstep efficiency GPUs depend on.
2. The paper presents virtualized treelet queues, a GPU RT-unit design with three coordinated techniques. Ray virtualization increases the concurrent rays in flight: normally the count is capped by warp slots because each ray is a thread, so as soon as a thread issues its trace-ray instruction to the RT unit, its raygen shader is terminated and the CUDA core reclaimed, letting the GPU launch more raygen threads and issue more rays — enough to fill the treelet queues. Dynamic treelet queues group rays by the cache-sized treelet they will visit for locality, and because rays diverge later in traversal and leave queues underpopulated, the architecture dynamically switches those queues to ordinary traversal rather than forcing an inefficient treelet pass. Warp repacking regroups the still-active rays from partly-idle warps into full warps to restore SIMT efficiency, which the authors find crucial. The three are interdependent — grouping needs concurrency, and concurrency plus grouping causes the divergence repacking fixes — so only together do treelets finally pay off on a GPU.
3. Simulated in Vulkan-Sim (a cycle-level GPU simulator) on the LumiBench scenes with path tracing at one sample per pixel and three maximum bounces per ray, virtualized treelet queues achieve about 95 percent speedup on average over a baseline ray-tracing GPU, and up to 2.55 times better path-tracing performance under usage scenarios comparable to video games. Scope: this is a hardware architecture for future GPU RT units, not a software change for current GPUs, evaluated in simulation on one benchmark at specific settings, so real silicon and other workloads would shift the numbers; the benefit depends on scenes having enough ray-treelet overlap to exploit; and it accelerates BVH traversal specifically, with the rest of the rendering pipeline bounding overall frame-rate gains. The durable lesson is that an optimization's success is architecture-specific — a technique that works beautifully on specialized hardware can fail entirely on a GPU until it is re-engineered around that GPU's real constraints, here limited ray concurrency and dependence on lockstep execution.

Check yourself

Check your understanding

1. Why is real-time ray tracing so slow on a GPU, even with dedicated ray-tracing hardware?
2. What are treelets, and why did a naive treelet implementation fail on a GPU?
3. What are the three techniques in virtualized treelet queues, and how do they fit together?
4. What did virtualized treelet queues achieve, and what are the limits of the result?

Sources

The paper is “Treelet Accelerated Ray Tracing on GPUs” by Yuan Hsi Chou and Tor M. Aamodt, published at ASPLOS 2025, DOI 10.1145/3676641.3716279. Both authors are at the University of British Columbia.

This explainer is based on the full text of the paper, obtained from an author’s copy hosted on Tor Aamodt’s University of British Columbia publications page. The problem framing (real-time ray tracing lowering frame rates so players disable it; ray tracing as a memory-bound workload dominated by traversing the bounding volume hierarchy; the tree not fitting in on-chip caches and incoherent rays causing high cache miss rates, measured averaging fifty-eight percent and reaching seventy percent on LumiBench in Vulkan-Sim, plus low SIMT efficiency in the baseline RT unit; treelets from prior work on specialized accelerators reducing memory traffic by fifty to seventy-five percent; and why a naive treelet implementation on a GPU yields no speedup, due to insufficient concurrent rays and lost SIMT efficiency), the virtualized-treelet-queues design (ray virtualization terminating raygen shaders once the trace-ray instruction is issued to reclaim CUDA cores and increase concurrent rays in flight; dynamic treelet queues grouping rays by treelet for cache locality and switching to regular traversal when queues become underpopulated as rays diverge; and warp repacking regrouping active rays into new warps to restore SIMT efficiency), and the results (about 95 percent average speedup over a baseline ray-tracing GPU across LumiBench scenes with path tracing at one sample per pixel and three maximum bounces per ray, and up to 2.55 times better path-tracing performance under game-like usage scenarios, in Vulkan-Sim simulation) are all drawn directly from the paper. Background explanations of ray tracing, bounding volume hierarchies, GPU warps and SIMT execution, RT units, and cache locality are standard and provided to make the paper’s contribution understandable.