[en] 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.

[es] 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.