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

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