Parallel Hash Table Design for NDP Systems

With the increasing feasibility of die-stacked 3D memory, near-data-processing (NDP) is being widely explored to extract greater performance within a limited power budget. This processing can either be at a fine-grained instruction granularity or at coarse-grained kernel granularity. Allowing both the host processor and processing units in the memory to operate on data concurrently can potentially create coherence and consistency issues. While coherence problems have been solved by including the NDP memory in the coherence domain, porting parallel data structures like hash-table to NDP memory give rise to data structure consistency issues that have not been studied so far, as previous works do not discuss the consistency rules that should be enforced by a NDP memory controller. Instead, there is an implicit assumption that the memory controllers in NDP systems ensure the required order for memory requests. In this position paper, we propose techniques to adapt a traditional parallel hash-table data structure to a NDP system while ensuring improved performance and data structure consistency.