K-D Bonsai: ISA-Extensions to Compress K-D Trees for Autonomous Driving Tasks
Preprint
Abstract
Autonomous Driving (AD) systems extensively manipulate 3D point clouds for object detection and vehicle localization. Thereby, efficient processing of 3D point clouds is crucial in these systems. In this work we propose K-D Bonsai, a technique to cut down memory usage during radius search, a critical building block of point cloud processing. K-D Bonsai exploits value similarity in the data structure that holds the point cloud (a k-d tree) to compress the data in memory. K-D Bonsai further compresses the data using a reduced floating-point representation, exploiting the physically limited range of point cloud values. For easy integration into nowadays systems, we implement K-D Bonsai through Bonsai-extensions, a small set of new CPU instructions to compress, decompress, and operate on points. To maintain baseline safety levels, we carefully craft the Bonsai-extensions to detect precision loss due to compression, allowing re-computation in full precision to take place if necessary. Therefore, K-D Bonsai reduces data movement, improving performance and energy efficiency, while guaranteeing baseline accuracy and programmability. We evaluate K-D Bonsai over the euclidean cluster task of Autoware.ai, a state-of-the-art software stack for AD. We achieve an average of 9.26% improvement in end-to-end latency, 12.19% in tail latency, and a reduction of 10.48% in energy consumption. Differently from expensive accelerators proposed in related work, K-D Bonsai improves radius search with minimal area increase (0.36%).Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- A survey on hardware accelerators: Taxonomy, trends, challenges, and perspectivesJournal of Systems Architecture, 2022
- Lidar for Autonomous Driving: The Principles, Challenges, and Trends for Automotive Lidar and Perception SystemsIEEE Signal Processing Magazine, 2020
- PointPillars: Fast Encoders for Object Detection From Point Clouds2019
- Autonomous Cars: Research Results, Issues, and Future ChallengesIEEE Communications Surveys & Tutorials, 2018
- Scaling equations for the accurate prediction of CMOS device performance from 180 nm to 7 nmIntegration, 2017
- Autonomous Driving in the iCity—HD Maps as a Key Challenge of the Automotive IndustryEngineering, 2016
- An Open Approach to Autonomous VehiclesIEEE Micro, 2015
- The gem5 simulatorACM SIGARCH Computer Architecture News, 2011
- Semantic 3D Object Maps for Everyday Manipulation in Human Living EnvironmentsKI - Künstliche Intelligenz, 2010
- Mapping the world in 3DNature Photonics, 2010