Improving autonomous driving systems with CPU extensions for point cloud processing

Abstract

(English) Autonomous Driving Systems (ADS) are at the cusp of large-scale adoption, promising accident reduction and market potential. However, the complex software and sensor data pressure for better hardware support in this safety-critical scenario, where high performance is mandatory to meet latency deadlines. Additionally, energy efficiency, cost, and volume must also be first-class for market feasibility, calling computer architects into action. To enrich hardware support for ADS, we carry out a performance and power characterization of Autoware.ai, a state-of-the-art ADS software stack. We find significant time spent processing Light Imaging Detection and Ranging (LiDAR) sensor data, which are widely used by ADS. LiDAR captures 3D point clouds for tasks such as segmentation, localization, and object detection. Despite its importance, hardware support for LiDAR has only recently gained traction. Further, while most point cloud processing algorithms run on CPUs, recent works propose costly hardware accelerators. Instead, we aim to use existing general-purpose hardware and software for point cloud processing with minor CPU augmentations. For that, we introduce a small set of CPU instructions targeting point cloud neighbor search based on k-d trees, a key operation used in various algorithms. The first technique we propose is K-D Bonsai, which reduces data movement during the neighbor search by compressing k-d tree leaves in execution time, exploiting value similarity. K-D Bonsai further compresses the data using a reduced floating-point representation, exploiting the physically limited range of point cloud values collected with LiDAR. We implement K-D Bonsai through a small set of new CPU instructions to compress, decompress, and operate on points. To maintain baseline accuracy, we carefully craft the instructions 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. K-D Bonsai improves the end-to-end latency of the segmentation task of Autoware.ai by 9.26% on average, 12.19% in tail latency, and reduces energy consumption by 10.84%. Unlike the expensive accelerators proposed in related work, K-D Bonsai improves neighbor search with minimal area increase (0.36%). In the second technique, we found that consecutive neighbor search queries are often similar, visiting k-d tree nodes with considerable resemblance. We leverage this observation to cheaply speed up neighbor search with the available CPU Vector Processing Unit (VPU). We propose a hardware/software co-design called Caravan. At the software level, Caravan- SW exploits 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 the 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) in Autoware.ai point cloud segmentation. With the additional Caravan-HW support, the leaf processing part of neighbor search can be further optimized, boosting gains to 5.19× (1.97× end-to-end), with minimal area costs. Our programmable and minimally intrusive solution has end-to-end benefits comparable to accelerators.

(Català) Els Sistemes de Conducció Autònoma (ADS) estan a punt de l'adopció a gran escala, podent reduir accidents i oferir possibilitats de mercat. No obstant això, el complex programari i la pressió de la quantitat de dades generada pels seus sensors exigeixen un millor suport de maquinari en aquesta aplicació crítica, on l'alt rendiment és obligatori per minimitzar el temps de reacció. A més, l'eficiència energètica, el cost i el volum han de ser optimitzats per garantir la viabilitat del mercat. Per millorar el suport de maquinari per als ADS, caracteritzem el rendiment i la potència demandada per Autoware.ai, un programari d'última generació per a ADS. Hem trobat que es dedica un temps significatiu al processament de dades del sensor Light Imaging Detection and Ranging (LiDAR), àmpliament utilitzat pels ADS. Els LiDAR capturen núvols de punts 3D per a tasques com la segmentació, la localització i la detecció d'objectes. Malgrat la seva importància, el suport de maquinari per a tasques amb LiDAR només ha guanyat tracció recentment. A més, tot i que la majoria dels algoritmes de processament de núvols de punts s'executen a la CPU, treballs recents proposen acceleradors de maquinari costosos i complexos. En lloc d'això, el nostre objectiu és utilitzar maquinari i programari de propòsit general existent per processar núvols de punts amb petites modificacions a la CPU. Per a això, introduïm un petit conjunt d'instruccions de CPU dirigides a la cerca de veïns en núvols de punts basats en arbres k-d, una operació clau en diversos algoritmes. Comencem amb K-D Bonsai, una tècnica que redueix el moviment de dades en la cerca de veïns comprimint les fulles de l'arbre k-d en temps d'execució, explotant la similitud de valors. Les dades es comprimeixen encara més reduint la representació de punt flotant, aprofitant la limitació dels valors recollits amb LiDAR. Implementem K-D Bonsai amb noves instruccions de CPU per comprimir, descomprimir i operar sobre punts. Projectem les instruccions perquè detectin pèrdues de precisió degudes a la compressió, permetent recomputar en la representació original si és necessari. Així, es redueix el moviment de dades, es millora el rendiment i l'eficiència energètica, i no s'afecta la precisió o la programabilitat. K-D Bonsai millora la latència d'extrem a extrem en la segmentació usada per Autoware.ai en un 9,26% de mitjana, un 12,19% en latència de cua, i redueix el consum d'energia en un 10,84%. A diferència dels treballs relacionats, K-D Bonsai millora la cerca de veïns amb un augment mínim en l'àrea (0,36%). En una segona tècnica, vam veure que les consultes consecutives en la cerca de veïns solen ser similars, visitant nodes d'arbres k-d amb similitud. Utilitzem aquesta observació per accelerar la cerca de veïns amb la VPU disponible en les CPUs, a baix cost. Proposem un co-disseny de maquinari/programari anomenat Caravan. A nivell de programari, Caravan-SW explota la similitud de cerca, agrupant consultes consecutives per buscar els seus veïns en paral·lel amb instruccions SIMD. No obstant això, quan la navegació de les consultes divergeix, especialment en els nivells més profunds de l'arbre k-d, Caravan-SW enfronta dispersió i els carrils de la VPU es subutilitzen. Per a això, proposem Caravan-HW, afegint dues noves instruccions que reindexen elements vectorials vàlids per reordenar-los ràpidament i densificar les operacions SIMD, eliminant la dispersió de Caravan-SW. Amb AVX512, Caravan-SW accelera la cerca de veïns en un 4.05× (1.85× d'extrem a extrem) en la segmentació de núvols de punts d'Autoware.ai. Si afegim Caravan-HW, el processament de fulles de la cerca de veïns s'optimitza encara més, augmentant els guanys a 5.19× (1.97× d'extrem a extrem), amb costos mínims d'àrea. La nostra solució programable i poc intrusiva ofereix beneficis d'extrem a extrem comparables als acceleradors.

(Español) Los Sistemas de Conducción Autónoma (ADS) están a punto de la adopción a gran escala, podiendo reducir accidentes y posiblidades de mercado. Sin embargo, el software complejo y la presión de cantidad de datos generado por sus sensores exigen un mejor soporte de hardware en esta aplicación crítica, donde el alto rendimiento es obligatorio para minimizar el tiempo de reacción. Además, la eficiencia energética, el coste y el volumen deben ser optimizados para garantizar viabilidad de mercado. Para mejorar el soporte de hardware para los ADS, caracterizamos el rendimiento y potencia demandada por Autoware.ai, una software del estado del arte para ADS. Encontramos un tiempo significativo dedicado al procesamiento de datos del sensor Light Imaging Detection and Ranging (LiDAR), ampliamente utilizado por los ADS. Los LiDARs capturan nubes 3D para tareas como segmentación, localización y detección de objetos. A pesar de su importancia, el soporte de hardware para tareas con LiDAR solo ha ganado tracción recientemente. Además, aunque la mayoría de los algoritmos de procesamiento de nubes de puntos se ejecutan en la CPU, trabajos recientes proponen aceleradores de hardware costosos y complejos. En lugar de eso, nuestro objetivo es utilizar hardware y software de propósito general existente para processar nubes de puntos con pequeñas modificaciones en la CPU. Para ello, introducimos un pequeño conjunto de instrucciones de CPU dirigidas a la búsqueda de vecinos en nubes de puntos basados en árboles k-d, una operación clave en varios algoritmos. Empezamos con K-D Bonsai, técnica que reduce el movimiento de datos en la búsqueda de vecinos comprimiendo las hojas del árbol k-d en tiempo de ejecución, explotando la similitud de valores. Los datos se comprimen aún más reduciendo la representación de punto flotante, aprovechando la limitación de los valores recogidos con LiDAR. Implementamos K-D Bonsai con nuevas instrucciones de CPU para comprimir, descomprimir y operar sobre puntos. Proyectamos las instrucciones para que detecten pérdidas de precisión debido a la compresión, permitiendo recomputar en la representación original si es necesario. Así, se reduce el movimiento de datos, se mejora el rendimiento y la eficiencia energética, y no se afecta la precisión o la programabilidad. K-D Bonsai mejora la latencia de extremo a extremo en la segmentación usada por Autoware.ai en un 9.26% en promedio, un 12.19% en latencia de cola, y reduce el consumo de energía en un 10.84%. Diferente de los trabajos relacionados, K-D Bonsai mejora la búsqueda de vecinos con un aumento mínimo en el área (0.36%). En una segunda técnica, vimos que las queries consecutivas en la búesquedas de vecinos suelen ser similares, visitando nodos de árboles k-d con similitud. Usamos esta observación para acelerar la búsqueda de vecinos con la VPU disponible en las CPUs, a bajo coste. Proponemos un co-diseño de hardware/software llamado Caravan. A nivel de software, Caravan-SW explota la similitud de búsqueda, agrupando queries consecutivas para buscar a sus vecinos en paralelo con instrucciones SIMD. Sin embargo, cuando la navegación de las queries diverge, especialmente en los niveles más profundos del árbol k-d, Caravan-SW enfrenta disperción y los carriles dela VPU se subutilizan. Para eso, proponemos Caravan-HW, añadiendo dos nuevas instrucciones que reindexan elementos vectoriales válidos para reordenarlos rapidamente y densificar las operaciones SIMD, quitando la disperción de Caravan-SW. Con AVX512, Caravan-SW acelera la búsqueda de vecinos en un 4.05× (1.85× de extremo a extremo) en la segmentación de Autoware.ai. Si agregamos Caravan-HW, el procesamiento de hojas de la búsqueda de vecinos se optimiza aún más, subiendo las ganancias a 5.19× (1.97× de extremo a extremo), con costos mínimos de área. Nuestra solución programable y poco intrusiva ofrece beneficios de extremo a extremo comparables a los aceleradores.