科研之友
微信
新浪微博
Facebook
分享链接
摘要
Non-volatile memory technologies (NVMs) are promising candidates for building future memory systems, due to their advantages of high density, high scalability, and requiring near-zero standby power, while suffering from the limited endurance and asymmetric properties of reads and writes, compared with traditional memory technologies including DRAM and SRAM. The significant changes of low-level memory devices cause nontrivial challenges to high-level in-memory and in-cache data structure design due to overlooking the NVM device properties. In this paper, we study an important and common data structure, hash table, which is ubiquitous and widely used to construct the index and lookup table in main memory and caches. Based on the observations that existing hashing schemes cause many extra writes to NVMs, we propose a cost-efficient write-friendly hashing scheme, called path hashing, which incurs no extra writes to NVMs while delivers high performance. The basic idea of path hashing is to leverage a novel hash-collision resolution method, i.e., position sharing, which meets the needs of insertion and deletion requests without extra writes to NVMs. By further exploiting double-path hashing and path shortening techniques, path hashing delivers high performance of hash tables in terms of space utilization and request latency. Nevertheless, the original path hashing has low utilization of each cache line for small items, causing low cache efficiency. We hence propose a cache-optimized path hashing to pack multiple cells in the same path together and store them into one cache line, thus improving the cache line utilization to obtain higher performance. We have implemented path hashing and used a gem5 full system simulator with NVMain to evaluate its performance in the context of NVMs. Extensive experimental results demonstrate that path hashing incurs no extra writes to NVMs, and achieves up to 95 percent space utilization ratio as well as low request latency, compared with existing state-of-the-art hashing schemes. We have released the source code of path hashing for public use at github.
- 出版日期2018-5-1
- 单位华中科技大学
