Decoupling Data Layouts from Bounding Volume Hierarchies
For developers of high-performance computing and graphics applications, this work enables systematic exploration of data layouts, breaking the false dichotomy between performance and portability.
The paper tackles the entanglement of data layouts and traversal logic in bounding volume hierarchies, which hinders performance portability. Scion, a DSL and compiler, decouples layouts from algorithms, enabling independent optimization and achieving Pareto-optimal layouts across architectures and workloads.
Bounding volume hierarchies are ubiquitous acceleration structures in graphics, scientific computing, and data analytics. Their performance depends critically on data layout choices that affect cache utilization, memory bandwidth, and vectorization -- increasingly dominant factors in modern computing. Yet, in most programming systems, these layout choices are hopelessly entangled with the traversal logic. This entanglement prevents developers from independently optimizing data layouts and algorithms across different contexts, perpetuating a false dichotomy between performance and portability. We introduce Scion, a domain-specific language and compiler for specifying the data layouts of bounding volume hierarchies independent of tree traversal algorithms. We show that Scion can express a broad spectrum of layout optimizations used in high-performance computing while remaining architecture-agnostic. We demonstrate empirically that Pareto-optimal layouts (along performance and memory footprint axes) vary across algorithms, architectures, and workload characteristics. Through systematic design exploration, we also identify a novel ray tracing layout that combines optimization techniques from prior work, achieving Pareto-optimality across diverse architectures and scenes.