2023/06/30 by Akhil Shekar, Shekar, Akhil, Morteza Baradaran +5
Computer Science · #Advanced Data Storage Technologies #Bandwidth (computing) #Collision #Computer architecture #Computer hardware #Computer network #Computer science #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #Dram #FOS: Computer and information sciences #Hardware Architecture (cs.AR) #Hash function #Hash table #Implementation #Key (lock) #Memory bandwidth #Operating system #Parallel Computing and Optimization Techniques #Parallel computing #Programming language #Speedup
paper · pdf · doi:10.48550/arxiv.2306.17721
openalex publication_date 2023/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hashmaps are widely utilized data structures in many applications to perform a probe on key-value pairs. However, their performance tends to degrade with the increase in the dataset size, which leads to expensive off-chip memory accesses to perform bucket traversals associated with hash collision. In this work, we propose HashMem, a processing-in-memory (PIM) architecture designed to perform bucket traversals along the row buffers at the subarray level. Due to the inherent parallelism achieved with many concurrent subarray accesses and the massive bandwidth available within DRAM, the execution time related to bucket traversals is significantly reduced. We have evaluated two versions of HashMem, performance-optimized and area-optimized, which have a speedup of 49.1x/17.1x and 9.2x/3.2x over standard C++ map and hyper-optimized hopscotch map implementations, respectively.