Advanced Data Structures on the GPU
Introduction
In the first half of this tutorial, we focused on how to execute compute dispatches and how to manage memory. We worked mostly with simple data structures like linear arrays (buffers) and 2D/3D grids (textures). While these are the bread and butter of GPU programming, many real-world problems require more complex organization.
In this chapter, we’re moving from "data-parallel" arrays to "GPU-resident" data structures. We’ll explore how to build and traverse complex structures like Trees (BVH/Octrees) (BVH for bounding boxes, Octrees for 3D space partitioning), Linked Lists, and Work Queues entirely on the device.
Moving Data Structures to the GPU
Traditionally, complex data structures were built on the CPU and then "flattened" into arrays for the GPU to read. While this works, it creates a massive bottleneck: any update to the structure requires a CPU-GPU round-trip.
Modern Vulkan compute allows us to eliminate this bottleneck by moving the construction and management of these structures to the GPU. This is made possible by three key technologies:
-
64-bit Atomics: Allowing for thread-safe updates to global counters and pointers across the entire GPU. This is critical for lock-free data structures, which we’ll explore in detail.
-
Buffer Device Address: Moving away from complex descriptor sets to raw, pointer-like flexibility for building graph-like structures.
-
Subgroup Operations: Using the wave-aware logic we learned in Chapter 4 to build these structures much faster by coalescing (combining) multiple operations into a single atomic update.
Why This Matters
GPU-resident data structures are the foundation of modern high-performance rendering and simulation:
-
Ray Tracing: Bounding Volume Hierarchies (BVH) are used to quickly find which triangles a ray might hit.
-
Physics, and Robotics: Spatial partitioning structures like Octrees or Grid-based hashes are used for collision detection.
-
Order-Independent Transparency (OIT): A technique for rendering transparent objects without pre-sorting them on the CPU; per-pixel linked lists are used to store and sort transparent fragments on the GPU.
-
GPU-Driven Pipelines: Work queues allow the GPU to generate its own work, which we’ll explore in the next chapter.
By the end of this chapter, you’ll understand how to stop treating the GPU as a "dumb array processor" and start treating it as a platform for autonomous, complex data management.