{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"id":[{"id":"https:\/\/ror.org\/03mb6wj31","id-type":"ROR","asserted-by":"publisher"},{"id":"https:\/\/www.isni.org\/000000041937028X","id-type":"ISNI","asserted-by":"publisher"},{"id":"https:\/\/www.wikidata.org\/entity\/Q1640731","id-type":"wikidata","asserted-by":"publisher"}],"name":"Universitat Polit\u00e8cnica de Catalunya","acronym":["UPC"]}],"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T20:08:15Z","timestamp":1769285295097,"version":"3.49.0"},"reference-count":0,"publisher":"Universitat Polit\u00e8cnica de Catalunya","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>(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.\r\nTo 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.\r\nDespite 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.\r\nThe 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,\r\nwe 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%).\r\nIn 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.\r\nWith AVX512, Caravan-SW speeds up neighbor search by 4.05\u00d7 (1.85\u00d7 end-to-end) in Autoware.ai point cloud segmentation.\r\nWith the additional Caravan-HW support, the leaf processing part of neighbor search can be further optimized, boosting gains to 5.19\u00d7 (1.97\u00d7 end-to-end), with minimal area costs. Our programmable and minimally intrusive solution has end-to-end benefits comparable to accelerators.<\/jats:p>\n                <jats:p>(Catal\u00e0) Els Sistemes de Conducci\u00f3 Aut\u00f2noma (ADS) estan a punt de l'adopci\u00f3 a gran escala, podent reduir accidents i oferir possibilitats de mercat. No obstant aix\u00f2, el complex programari i la pressi\u00f3 de la quantitat de dades generada pels seus sensors exigeixen un millor suport de maquinari en aquesta aplicaci\u00f3 cr\u00edtica, on l'alt rendiment \u00e9s obligatori per minimitzar el temps de reacci\u00f3. A m\u00e9s, l'efici\u00e8ncia energ\u00e8tica, el cost i el volum han de ser optimitzats per garantir la viabilitat del mercat.\r\nPer millorar el suport de maquinari per als ADS, caracteritzem el rendiment i la pot\u00e8ncia demandada per Autoware.ai, un programari d'\u00faltima generaci\u00f3 per a ADS. Hem trobat que es dedica un temps significatiu al processament de dades del sensor Light Imaging Detection and Ranging (LiDAR), \u00e0mpliament utilitzat pels ADS. Els LiDAR capturen n\u00favols de punts 3D per a tasques com la segmentaci\u00f3, la localitzaci\u00f3 i la detecci\u00f3 d'objectes.\r\nMalgrat la seva import\u00e0ncia, el suport de maquinari per a tasques amb LiDAR nom\u00e9s ha guanyat tracci\u00f3 recentment. A m\u00e9s, tot i que la majoria dels algoritmes de processament de n\u00favols de punts s'executen a la CPU, treballs recents proposen acceleradors de maquinari costosos i complexos. En lloc d'aix\u00f2, el nostre objectiu \u00e9s utilitzar maquinari i programari de prop\u00f2sit general\r\nexistent per processar n\u00favols de punts amb petites modificacions a la CPU. Per a aix\u00f2, introdu\u00efm un petit conjunt d'instruccions de CPU dirigides a la cerca de ve\u00efns en n\u00favols de punts basats en arbres k-d, una operaci\u00f3 clau en diversos algoritmes.\r\nComencem amb K-D Bonsai, una t\u00e8cnica que redueix el moviment de dades en la cerca de ve\u00efns comprimint les fulles de l'arbre k-d en temps d'execuci\u00f3, explotant la similitud de valors. Les dades es comprimeixen encara m\u00e9s reduint la representaci\u00f3 de punt flotant, aprofitant la limitaci\u00f3 dels valors recollits amb LiDAR. Implementem K-D Bonsai amb noves instruccions de CPU per\r\ncomprimir, descomprimir i operar sobre punts. Projectem les instruccions perqu\u00e8 detectin p\u00e8rdues de precisi\u00f3 degudes a la compressi\u00f3, permetent recomputar en la representaci\u00f3 original si \u00e9s necessari. Aix\u00ed, es redueix el moviment de dades, es millora el rendiment i l'efici\u00e8ncia energ\u00e8tica, i no s'afecta la precisi\u00f3 o la programabilitat. K-D Bonsai millora la lat\u00e8ncia d'extrem a extrem en la segmentaci\u00f3 usada per Autoware.ai en un 9,26% de mitjana, un 12,19% en lat\u00e8ncia de cua, i redueix el consum d'energia en un 10,84%. A difer\u00e8ncia dels treballs relacionats, K-D Bonsai millora la cerca de ve\u00efns amb un augment m\u00ednim en l'\u00e0rea (0,36%).\r\nEn una segona t\u00e8cnica, vam veure que les consultes consecutives en la cerca de ve\u00efns solen ser similars, visitant nodes d'arbres k-d amb similitud. Utilitzem aquesta observaci\u00f3 per accelerar la cerca de ve\u00efns amb la VPU disponible en les CPUs, a baix cost.\r\nProposem 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\u00efns en paral\u00b7lel amb instruccions SIMD. No obstant aix\u00f2, quan la navegaci\u00f3 de les consultes divergeix, especialment en els nivells m\u00e9s profunds de l'arbre k-d, Caravan-SW enfronta dispersi\u00f3 i els carrils de la VPU es subutilitzen. Per a aix\u00f2, proposem Caravan-HW, afegint dues noves instruccions que reindexen elements vectorials v\u00e0lids per reordenar-los r\u00e0pidament i densificar les operacions SIMD, eliminant la dispersi\u00f3 de Caravan-SW.\r\nAmb AVX512, Caravan-SW accelera la cerca de ve\u00efns en un 4.05\u00d7 (1.85\u00d7 d'extrem a extrem) en la segmentaci\u00f3 de n\u00favols de punts d'Autoware.ai. Si afegim Caravan-HW, el processament de fulles de la cerca de ve\u00efns s'optimitza encara m\u00e9s, augmentant els guanys a 5.19\u00d7 (1.97\u00d7 d'extrem a extrem), amb costos m\u00ednims d'\u00e0rea. La nostra soluci\u00f3 programable i poc intrusiva ofereix beneficis d'extrem a extrem comparables als acceleradors.<\/jats:p>\n                <jats:p>(Espa\u00f1ol) Los Sistemas de Conducci\u00f3n Aut\u00f3noma (ADS) est\u00e1n a punto de la adopci\u00f3n a gran escala, podiendo reducir accidentes y posiblidades de mercado. Sin embargo, el software complejo y la presi\u00f3n de cantidad de datos generado por sus sensores exigen un mejor soporte de hardware en esta aplicaci\u00f3n cr\u00edtica, donde el alto rendimiento es obligatorio para minimizar el tiempo de reacci\u00f3n. Adem\u00e1s, la eficiencia energ\u00e9tica, el coste y el volumen deben ser optimizados para garantizar viabilidad de mercado.\r\nPara 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\u00f3n, localizaci\u00f3n y detecci\u00f3n de objetos.\r\nA pesar de su importancia, el soporte de hardware para tareas con LiDAR solo ha ganado tracci\u00f3n recientemente. Adem\u00e1s, aunque la mayor\u00eda 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\u00f3sito general existente para processar nubes de puntos con peque\u00f1as modificaciones en la CPU. Para ello, introducimos un peque\u00f1o conjunto de instrucciones de CPU dirigidas a la b\u00fasqueda de vecinos en nubes de puntos basados en \u00e1rboles k-d, una operaci\u00f3n clave en varios algoritmos.\r\nEmpezamos con K-D Bonsai, t\u00e9cnica que reduce el movimiento de datos en la b\u00fasqueda de vecinos comprimiendo las hojas del \u00e1rbol k-d en tiempo de ejecuci\u00f3n, explotando la similitud de valores. Los datos se comprimen a\u00fan m\u00e1s reduciendo la representaci\u00f3n de punto flotante, aprovechando la limitaci\u00f3n 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\u00e9rdidas de precisi\u00f3n debido a la compresi\u00f3n, permitiendo recomputar en la representaci\u00f3n original si es necesario.\r\nAs\u00ed, se reduce el movimiento de datos, se mejora el rendimiento y la eficiencia energ\u00e9tica, y no se afecta la precisi\u00f3n o la programabilidad. K-D Bonsai mejora la latencia de extremo a extremo en la segmentaci\u00f3n usada por Autoware.ai en un 9.26% en promedio, un 12.19% en latencia de cola, y reduce el consumo de energ\u00eda en un 10.84%.\r\nDiferente de los trabajos relacionados, K-D Bonsai mejora la b\u00fasqueda de vecinos con un aumento m\u00ednimo en el \u00e1rea (0.36%).\r\nEn una segunda t\u00e9cnica, vimos que las queries consecutivas en la b\u00faesquedas de vecinos suelen ser similares, visitando nodos de \u00e1rboles k-d con similitud. Usamos esta observaci\u00f3n para acelerar la b\u00fasqueda de vecinos con la VPU disponible en las CPUs, a bajo coste. Proponemos un co-dise\u00f1o de hardware\/software llamado Caravan. A nivel de software, Caravan-SW explota la similitud de b\u00fasqueda, agrupando queries consecutivas para buscar a sus vecinos en paralelo con instrucciones SIMD. Sin embargo, cuando la navegaci\u00f3n de las queries diverge, especialmente en los niveles m\u00e1s profundos del \u00e1rbol k-d, Caravan-SW enfrenta disperci\u00f3n y los carriles dela VPU se subutilizan. Para eso, proponemos Caravan-HW, a\u00f1adiendo dos nuevas instrucciones que reindexan elementos vectoriales v\u00e1lidos para reordenarlos rapidamente y densificar las operaciones\r\nSIMD, quitando la disperci\u00f3n de Caravan-SW.\r\nCon AVX512, Caravan-SW acelera la b\u00fasqueda de vecinos en un 4.05\u00d7 (1.85\u00d7 de extremo a extremo) en la segmentaci\u00f3n de Autoware.ai. Si agregamos Caravan-HW, el procesamiento de hojas de la b\u00fasqueda de vecinos se optimiza a\u00fan m\u00e1s, subiendo las ganancias a 5.19\u00d7 (1.97\u00d7 de extremo a extremo), con costos m\u00ednimos de \u00e1rea. Nuestra soluci\u00f3n programable y poco intrusiva ofrece beneficios de extremo a extremo comparables a los aceleradores.<\/jats:p>","DOI":"10.5821\/dissertation-2117-417338","type":"dissertation","created":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T01:22:12Z","timestamp":1731288132000},"approved":{"date-parts":[[2024,10,21]]},"source":"Crossref","is-referenced-by-count":0,"title":["Improving autonomous driving systems with CPU extensions for point cloud processing"],"prefix":"10.5821","author":[{"sequence":"additional","affiliation":[]},{"given":"Pedro Henrique","family":"Exenberger Becker","sequence":"first","affiliation":[]}],"member":"3865","container-title":[],"original-title":[],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T06:43:29Z","timestamp":1769237009000},"score":1,"resource":{"primary":{"URL":"https:\/\/hdl.handle.net\/2117\/417338"}},"subtitle":[],"editor":[{"given":"Jos\u00e9 Mar\u00eda","family":"Arnau Monta\u00f1\u00e9s","sequence":"first","affiliation":[]},{"given":"Antonio Mar\u00eda","family":"Gonz\u00e1lez Col\u00e1s","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.5821\/dissertation-2117-417338","relation":{},"subject":[]}}