Designing Data Structures to Minimize Bit Flips on NVM

Appeared in The 7th IEEE Non-Volatile Memory Systems and Applications Symposium (NVMSA).

Abstract

Abstract—The advent of byte-addressable non-volatile memory technologies such as phase change memory (PCM) has spurred a flurry of research on topics including consistency and durability of data structures across power failures and optimizing systems for the low-latency nature of these technologies, while typically aiming to increase lifetime and reduce power consumption by reducing the number of writes to the non-volatile memory. However, in technologies such as PCM, it is bit flips that consume power and wear out cells, not writes. Thus, PCM controllers do not rewrite cells unless the cell changes value. However, this crucial optimization, reducing the number of bits flipped, has not been sufficiently explored for the rest of the hardware and software stack. We develop a framework for using the number of bit flips as the measure of “goodness” for a range of hardware and software techniques. We also introduce several simple and straightforward modifications to existing data structures that can reduce the number of bit flips over time, and profile use cases where the approach with the fewest writes does not also minimize bit flips. Based on these findings, we discuss potential approaches that can further minimize bit flips, better optimizing hardware and software for non-volatile memory technologies such as PCM.

Publication date:
August 2018

Authors:
Daniel Bittman
Mathew Gray
Justin Raizes
Sinjoni Mukhopadhyay
Matt Bryson
Peter Alvaro
Darrell D. E. Long
Ethan L. Miller

Projects:
Storage Class Memories

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{bittman-nvmsa18,
  author       = {Daniel Bittman and Mathew Gray and Justin Raizes and Sinjoni Mukhopadhyay and Matt Bryson and Peter Alvaro and Darrell D. E. Long and Ethan L. Miller},
  title        = {Designing Data Structures to Minimize Bit Flips on {NVM}},
  booktitle    = {The 7th IEEE Non-Volatile Memory Systems and Applications Symposium (NVMSA)},
  month        = aug,
  year         = {2018},
}