Caravan: A Hardware/Software Co-Design for Efficient SIMD Neighbor Search on Point Clouds

Neighbor search is the backbone task for point cloud processing, which is widely employed in current 3D computer vision applications.To be efficient, neighbor search relies on spatial data structures such as k-d trees, to prune the search space.We found that consecutive neighbor search queries in point cloud processing are often similar, visiting k-d tree nodes with considerable resemblance.In this work, we show how to leverage this observation to effectively exploit the available CPU Vector Processing Unit (VPU) to cheaply speed up neighbor search.We devise our solution with a hardware/software co-design called Caravan.At the software level, Caravan-SW exploits this search similarity, gathering consecutive queries to search for their neighbors in parallel with SIMD instructions.Yet, when the navigation of queries diverges, particularly in the deeper levels of the k-d tree, Caravan-SW faces sparsity and VPU lanes are underutilized.We tackle this with Caravan-HW, adding two new instructions that re-index valid vector elements and allow fast operand shuffling and dense SIMD operations to take place, suppressing the hard-to-predict runtime sparsity of Caravan-SW.With AVX512, Caravan-SW speeds up neighbor search by 4.05× (1.85× end-to-end) during point cloud segmentation in a commodity CPU.With the additional Caravan-HW support, the leaf processing part of neighbor search can be further optimized, boosting speed up to 5.19× (1.97× end-to-end), with minimal area costs of 0.032 mm2.Our programmable and minimally intrusive solution has end-to-end benefits comparable to accelerators.