Optimizing Spatial Data Structure with Near-Cache Acceleration by Exploiting Physical Locality

Spatial data structures (e.g., Kd-trees, R-trees, BVHs) are the fundamental abstraction for organizing geometric data and avoiding linear traversal, which underpin point cloud processing, ray tracing, and collision detection. We target the general problem of efficient spatial data structure search and take the point cloud as the primary case for analysis and evaluation. However, these structures introduce fundamental inefficiencies: the compute bottleneck from recursive searching and the memory bottleneck from irregular access patterns, which existing architectural solutions fail to address effectively. We present RoboCortex, a novel architecture that addresses these challenges through three synergistic designs. First, RoboCortex introduces a near-cache programmable accelerator that not only hardware-accelerates spatial data structure searches but also exposes physical coordinates to the cache hierarchy. It enables cache optimizations based on locality in physical coordinates rather than memory address patterns. Building on this coordinate visibility, RoboCortex further proposes the path buffer, a hardware structure that caches frequent searching paths, to exploit physical locality by bypassing redundant node visits. However, the path buffer may exacerbate memory access irregularity; thus, as a compensatory mechanism, RoboCortex designs a dedicated prefetching strategy to further improve search efficiency. Our experimental results demonstrate that RoboCortex achieves 2.74-13.07× speedup for autonomous driving oriented workloads and 12.73-77.94× improvement for object reconstruction oriented workload over baseline CPU implementations. To our knowledge, this is the first spatial-data-structure-oriented architecture to exploit physical locality without accuracy loss. We not only demonstrate its effectiveness on point cloud workloads, but also its generality to more domains, such as ray tracing in graphics.