Accelerating Key-Value Data Structures Using AVX-512 SIMD Extensions
2025 (English)In: Proceedings - IEEE International Conference on Cluster Computing, Institute of Electrical and Electronics Engineers (IEEE), 2025Conference paper, Published paper (Refereed)
Abstract [en]
Advanced Vector Extensions 512 (AVX-512), a modern SIMD instruction set for x86 architectures, enables data-level parallelism through 512-bit wide ZMM registers capable of processing multiple data elements concurrently within a single instruction cycle. In this study, we present a high-throughput, lock-free, in-memory architecture for key-value data-stores that exploits AVX-512 vector operations to accelerate fundamental operations such as insertion and lookup. Our design introduces an optimized memory layout that partitions the key space into two disjoint regions (primary and secondary) and employs three independent hash functions to identify candidate slots. This asymmetric layout improves key distribution, reduces collision probability, and enhances overall lookup efficiency. Experimental evaluation shows that this strategy yields the lowest insertion failure rate among tested memory partitioning schemes. By leveraging AVX-512 instructions in combination with most optimized memory layout, our implementation achieves insertion throughput within 6% of Intel TBB’s highly optimized multithreaded hash map, despite avoiding explicit synchronization or thread-level parallelism. Under workloads with 550 million entries and a 90% miss rate, our approach delivers 4.0-5.1x speedup over standard STL, Boost, Robin-Hood, and Abseil hash maps, and up to 2.5 x improvement relative to TBB and Abseil. These gains are consistently observed for both 32-bit and 64-bit floating-point key types. The results confirm the viability of AVX-512-centric designs as a cost-effective alternative to thread-level parallelism, particularly in environments where minimizing synchronization overhead and ensuring deterministic execution are critical. Our findings suggest for a paradigm shift in CPU and system architecture, emphasizing wider vector units and improved memory bandwidth utilization as primary levers for scalable high-performance computing. These findings suggest that future extensions of AVX-512 capabilities, such as non-blocking memory loads, expanded vector registers, and asynchronous prefetching, could enhance the efficiency of data-intensive workloads.
Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2025.
Keywords [en]
Data structures, Digital arithmetic, Hash functions, Memory architecture, Multitasking, Program processors, Table lookup, Throughput, Vectors, Advanced vector extension 512 intrinsic, CPU-based key-value data structure, Data access, Hash table, Hash table acceleration, High performance computing, Key values, Layout designs, Low latency, Low-latency data access, Memory layout, Memory layout design, Multiple data, Multiple data (SIMD) parallelism, Performance computing, Single instruction, Value data, Vectorized hashing, Failure analysis
National Category
Computer Systems Computer Engineering Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kau:diva-107584DOI: 10.1109/CLUSTER59342.2025.11186494ISI: 001701307900006Scopus ID: 2-s2.0-105019791230ISBN: 979-8-3315-3019-8 (electronic)ISBN: 979-8-3315-3020-4 (print)OAI: oai:DiVA.org:kau-107584DiVA, id: diva2:2014709
Conference
IEEE International Conference on Cluster Computing (CLUSTER), Edinburgh, United Kingdom, September 2-5, 2025.
Funder
Knowledge Foundation2025-11-182025-11-182026-03-27Bibliographically approved