  Machine perception applications are increasingly moving toward manipulating
and processing 3D point cloud. This paper focuses on point cloud registration,
a key primitive of 3D data processing widely used in high-level tasks such as
odometry, simultaneous localization and mapping, and 3D reconstruction. As
these applications are routinely deployed in energy-constrained environments,
real-time and energy-efficient point cloud registration is critical.
  We present Tigris, an algorithm-architecture co-designed system specialized
for point cloud registration. Through an extensive exploration of the
registration pipeline design space, we find that, while different design points
make vastly different trade-offs between accuracy and performance, KD-tree
search is a common performance bottleneck, and thus is an ideal candidate for
architectural specialization. While KD-tree search is inherently sequential, we
propose an acceleration-amenable data structure and search algorithm that
exposes different forms of parallelism of KD-tree search in the context of
point cloud registration. The co-designed accelerator systematically exploits
the parallelism while incorporating a set of architectural techniques that
further improve the accelerator efficiency. Overall, Tigris achieves
77.2$\times$ speedup and 7.4$\times$ power reduction in KD-tree search over an
RTX 2080 Ti GPU, which translates to a 41.7% registration performance
improvements and 3.0$\times$ power reduction.
