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

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