research-article

Open access

Hamming Tree: The Case for Energy-Aware Indexing for NVMs

Authors:

Faisal NawabAuthors Info & Claims

Proceedings of the ACM on Management of Data, Volume 1, Issue 2

Article No.: 182, Pages 1 - 27

https://doi.org/10.1145/3589327

Published: 20 June 2023 Publication History

Abstract

Non-volatile memory (NVM) technologies are widely adopted in data storage solutions and battery-powered mobile and IoT devices. Wear-out and energy efficiency are two vital challenges facing the use of NVM. In Hamming Tree, we propose a software-level memory-aware solution that picks the memory segment of where a write operation is applied judiciously to minimize bit flipping. It has been shown that reducing bit flips leads to reducing energy consumption and improving write endurance. We performed real evaluations on an Optane memory device that show that Hamming Tree can achieve up to 67.8% reduction in energy consumption.

Supplemental Material

MP4 File

Presentation video - Hamming Tree: a software-level memory-aware solution that judiciously selects memory locations for new writes, which reduces bit flipping and consequently improves NVM devices' energy efficiency and write endurance.

Download
18.93 MB

References

[1]

Alaa Alameldeen and David Wood. 2004. Frequent pattern compression: A significance-based compression scheme for L2 caches. Technical Report. University of Wisconsin-Madison Department of Computer Sciences.

[2]

Milad Andalibi, Mojtaba Hajihosseini, Sam Teymoori, Maryam Kargar, and Meysam Gheisarnejad. 2021. A time-varying deep reinforcement model predictive control for dc power converter systems. In 2021 IEEE 12th International Symposium on Power Electronics for Distributed Generation Systems (PEDG). IEEE, 1--6.

[3]

Joy Arulraj et al. 2015. Let's talk about storage & recovery methods for non-volatile memory database systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, Melbourne, Victoria, Australia, 707--722.

[4]

Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017. FloDB: Unlocking memory in persistent key-value stores. In Proceedings of the Twelfth European Conference on Computer Systems. Association for Computing Machinery, Rome, Italy, 80--94.

Digital Library

[5]

Sana Benhamaid, Abdelmadjid Bouabdallah, and Hicham Lakhlef. 2022. Recent advances in energy management for Green-IoT: An up-to-date and comprehensive survey. Journal of Network and Computer Applications 198 (2022), 103257.

Digital Library

[6]

Daniel Bittman et al. 2019. Optimizing Systems for Byte-Addressable {NVM} by Reducing Bit Flipping. In 17th {USENIX} Conference on File and Storage Technologies ({FAST} 19). USENIX, Boston, MA, United States, 17--30.

[7]

Maurizio Capra, Riccardo Peloso, Guido Masera, Massimo Ruo Roch, and Maurizio Martina. 2019. Edge computing: A survey on the hardware requirements in the internet of things world. Future Internet 11, 4 (2019), 100.

[8]

Yuezhi Che, Yuanzhou Yang, Amro Awad, and Rujia Wang. 2020. A Lightweight Memory Access Pattern Obfuscation Framework for NVM. IEEE Computer Architecture Letters 19, 2 (2020), 163--166.

Digital Library

[9]

Shimin Chen and Qin Jin. 2015. Persistent b-trees in non-volatile main memory. Proceedings of the VLDB Endowment 8, 7 (2015), 786--797.

Digital Library

[10]

Sangyeun Cho and Hyunjin Lee. 2009. Flip-N-Write: A simple deterministic technique to improve PRAM write performance, energy and endurance. In MICRO 2009. Association for Computing Machinery, New York, USA, 347--357.

Digital Library

[11]

Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM symposium on Cloud computing. Association for Computing Machinery, Indiana, USA, 143--154.

Digital Library

[12]

Luís Cruz. 2021. Tools to Measure Software Energy Consumption from your Computer. http://luiscruz.github.io/2021/ 07/20/measuring-energy.html. https://doi.org/10.6084/m9.figshare.19145549.v1 Blog post.

[13]

Brian A Davey and Hilary A Priestley. 2002. Introduction to lattices and order. Cambridge university press, Cambridge, United Kingdom.

[14]

Arnaldo Carvalho De Melo. 2010. The new linux'perf'tools. In Slides from Linux Kongress, Vol. 18. Linux Kongress, Nuremberg, Germany, 1--42.

[15]

David B Dgien et al. 2014. Compression architecture for bit-write reduction in non-volatile memory technologies. In NANOARCH 2014. IEEE, Association for Computing Machinery, Paris, France, 51--56.

[16]

Gaurav Dhiman, Raid Ayoub, and Tajana Rosing. 2009. PDRAM: A hybrid PRAM and DRAM main memory system. In 2009 46th ACM/IEEE Design Automation Conference. IEEE, IEEE, San Francisco California, 664--669.

Digital Library

[17]

Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. https://archive.ics.uci.edu/ml/datasets/AmazonAccessSamples

[18]

Sanjay Ghemawat and Jeff Dean. 2022. Google LevelDB. Google. Retrieved Jan 2, 2022 from https://github.com/google/leveldb

[19]

Binbin Gu, Saeed Kargar, and Faisal Nawab. 2022. Efficient dynamic clustering: Capturing patterns from historical cluster evolution. arXiv preprint arXiv:2203.00812 (2022).

[20]

Part Guide. 2011. Intel® 64 and ia-32 architectures software developer's manual. Volume 3B: System programming Guide, Part 2, 11 (2011), 0--40.

[21]

Chenjuan Guo et al. 2012. Ecomark: evaluating models of vehicular environmental impact. In SIGSPATIAL '12. Association for Computing Machinery, Redondo Beach California, 269--278.

[22]

Yuncheng Guo, Yu Hua, and Pengfei Zuo. 2018. DFPC: A dynamic frequent pattern compression scheme in NVM-based main memory. In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, IEEE, DRESDEN, GERMANY, 1622--1627.

[23]

Fazal Hameed et al. 2017. Efficient STT-RAM last-level-cache architecture to replace DRAM cache. In MEMSYS 2017. Association for Computing Machinery, Virginia, USA, 141--151.

[24]

Jiangkun Hu et al. 2020. Understanding and analysis of B trees on NVM towards consistency and efficiency. CCF Transactions on High Performance Computing 2, 1 (2020), 1--14.

[25]

Fangting Huang, Dan Feng, Wen Xia, Wen Zhou, Yucheng Zhang, Min Fu, Chuntao Jiang, and Yukun Zhou. 2016. Security RBSG: Protecting phase change memory with security-level adjustable dynamic mapping. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, IEEE, Chicago, Illinois USA, 1081--1090.

[26]

Jianming Huang, Yu Hua, Pengfei Zuo, Wen Zhou, and Fangting Huang. 2020. An Efficient Wear-level Architecture using Self-adaptive Wear Leveling. In 49th International Conference on Parallel Processing-ICPP. Association for Computing Machinery, New York, USA, 1--11.

Digital Library

[27]

Intel. 2022. Types of Intel Optane memory. Intel. Retrieved Jan 1, 2023 from https://www.intel.com/content/www/us/ en/support/articles/000058286/memory-and-storage/intel-optane-memory.html

[28]

Majid Jalili and Hamid Sarbazi-Azad. 2016. Captopril: Reducing the pressure of bit flips on hot locations in non-volatile main memories. In DATE 2016. IEEE, IEEE, Dresden, Germany, 1116--1119.

[29]

Sudarsun Kannan et al. 2018. Redesigning LSMs for nonvolatile memory with NoveLSM. In 2018 {USENIX} Annual Technical Conference ({USENIX}{ATC} 18). USENIX, Boston, MA, USA, 993--1005.

[30]

Saeed Kargar, Binbin Gu, Sangeetha Abdu Jyothi, and Faisal Nawab. 2023. E2-NVM: A Memory-Aware Write Scheme to Improve Energy Efficiency and Write Endurance of NVMs using Variational Autoencoders. (2023).

[31]

Saeed Kargar, Heiner Litz, and Faisal Nawab. 2021. Predict and write: Using k-means clustering to extend the lifetime of nvm storage. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 768--779.

[32]

Saeed Kargar and Faisal Nawab. 2021. Extending the lifetime of NVM: challenges and opportunities. Proceedings of the VLDB Endowment 14, 12 (2021), 3194--3197.

Digital Library

[33]

Saeed Kargar and Faisal Nawab. 2021. Hamming Tree: The Case for Memory-Aware Bit Flipping Reduction for NVM Indexing. In CIDR.

[34]

Saeed Kargar and Faisal Nawab. 2022. Challenges and future directions for energy, latency, and lifetime improvements in NVMs. Distributed and Parallel Databases (2022), 1--27.

[35]

Manohar Kaul et al. 2013. Building accurate 3d spatial networks to enable next generation intelligent transportation systems. In MDM 2013, Vol. 1. IEEE, IEEE, Milan, Italy, 137--146.

[36]

Kashif Nizam Khan, Mikael Hirki, Tapio Niemi, Jukka K Nurminen, and Zhonghong Ou. 2018. RAPL in Action: Experiences in Using RAPL for Power measurements. ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS) 3, 2 (2018), 1--26.

Digital Library

[37]

Wenjie Li et al. 2020. HiLSM: an LSM-based key-value store for hybrid NVM-SSD storage systems. In Proceedings of the 17th ACM International Conference on Computing Frontiers. Association for Computing Machinery, Catania, Sicily, Italy, 208--216.

[38]

Chen Luo and Michael J Carey. 2020. LSM-based storage techniques: a survey. The VLDB Journal 29, 1 (2020), 393--418.

Digital Library

[39]

Xianlu Luo et al. 2014. Enhancing lifetime of NVM-based main memory with bit shifting and flipping. In RTCSA 2014. IEEE, IEEE, Chongqing, China, 1--7.

[40]

Haiyu Mao, Xian Zhang, Guangyu Sun, and Jiwu Shu. 2017. Protect non-volatile memory from wear-out attack based on timing difference of row buffer hit/miss. In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017. IEEE, IEEE, LAUSANNE, SWITZERLAND, 1623--1626.

[41]

Sparsh Mittal and Jeffrey S Vetter. 2015. A survey of software techniques for using non-volatile memories for storage and main memory systems. TPDS 2015 27, 5 (2015), 1537--1550.

[42]

Fargol Nematkhah, Farrokh Aminifar, Mohammad Shahidehpour, and Sasan Mokhtari. 2022. Evolution in Computing Paradigms for Internet of Things-Enabled Smart Grid Applications: Their Contributions to Power Systems. IEEE Systems, Man, and Cybernetics Magazine 8, 3 (2022), 8--20.

[43]

Jiaxin Ou et al. 2016. A high performance file system for non-volatile main memory. In EuroSys '16. Association for Computing Machinery, London, United Kingdom, 1--16.

[44]

Ismail Oukid et al. 2016. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In Proceedings of the 2016 International Conference on Management of Data. Association for Computing Machinery, San Francisco, USA, 371--386.

[45]

Poovaiah M Palangappa and Kartik Mohanram. 2015. Flip-Mirror-Rotate: An architecture for bit-write reduction and wear leveling in non-volatile memories. In GLSVLSI 2015. IEEE, Pennsylvania, USA, 221--224.

Digital Library

[46]

PMDK. accessed: 2022-02. Persistent Memory Development Kit. https://pmem.io.

[47]

Moinuddin K Qureshi, John Karidis, Michele Franceschini, Vijayalakshmi Srinivasan, Luis Lastras, and Bulent Abali. 2009. Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling. In 2009 42nd Annual IEEE/ACM international symposium on microarchitecture (MICRO). IEEE, IEEE, New York, USA, 14--23.

Digital Library

[48]

Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. Pebblesdb: Building key-value stores using fragmented log-structured merge trees. In Proceedings of the 26th Symposium on Operating Systems Principles. USENIX, Shanghai, China, 497--514.

Digital Library

[49]

Gunther Schmidt and Thomas Ströhlein. 2012. Relations and graphs: discrete mathematics for computer scientists. Springer Science & Business Media, Berlin.

[50]

Dongsuk Shin, Hakbeom Jang, Kiseok Oh, and Jae W Lee. 2022. An Energy-Efficient DRAM Cache Architecture for Mobile Platforms With PCM-Based Main Memory. ACM Transactions on Embedded Computing Systems (TECS) 21, 1 (2022), 1--22.

Digital Library

[51]

Shihao Song, Anup Das, Onur Mutlu, and Nagarajan Kandasamy. 2020. Improving phase change memory performance with data content aware access. In Proceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management. Association for Computing Machinery, New York, United States, 30--47.

Digital Library

[52]

Shihao Song, Anup Das, Onur Mutlu, and Nagarajan Kandasamy. 2021. Aging-aware request scheduling for non-volatile main memory. In Proceedings of the 26th Asia and South Pacific Design Automation Conference. IEEE, New York, United States, 657--664.

Digital Library

[53]

Haris Volos et al. 2011. Mnemosyne: Lightweight persistent memory. ACM SIGARCH Computer Architecture News 39, 1 (2011), 91--104.

Digital Library

[54]

Yasi Wang, Hongxun Yao, and Sicheng Zhao. 2016. Auto-encoder based dimensionality reduction. Neurocomputing 184 (2016), 232--242.

Digital Library

[55]

Fei Xia et al. 2017. Hikv: A hybrid index key-value store for dram-nvm memory systems. In USENIX ATC 17. USENIX, Santa Clara, CA, USA, 349--362.

[56]

Byung-Do Yang et al. 2007. A low power phase-change random access memory using a data-comparison write scheme. In ISCAS 2007. IEEE, IEEE, New Orleans, LA, USA, 3014--3017.

[57]

Qi Zeng and Jih-Kwon Peir. 2017. Content-aware non-volatile cache replacement. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, IEEE, Orlando, Florida USA, 92--101.

[58]

Ping Zhou, Bo Zhao, Jun Yang, and Youtao Zhang. 2009. A durable and energy efficient main memory using phase change memory technology. ACM SIGARCH computer architecture news 37, 3 (2009), 14--23.

[59]

Pengfei Zuo and Yu Hua. 2017. A write-friendly and cache-optimized hashing scheme for non-volatile memory systems. IEEE Transactions on Parallel and Distributed Systems 29, 5 (2017), 985--998.

Cited By

Hao XChandramouli B(2024)Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range IndexProceedings of the VLDB Endowment10.14778/3681954.368201217:11(3442-3455)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.14778/3681954.3682012
Zheng YTan K(2024)Sorting on Byte-Addressable Storage: The Resurgence of Tree StructureProceedings of the VLDB Endowment10.14778/3648160.364818517:6(1487-1500)Online publication date: 3-May-2024
https://dl.acm.org/doi/10.14778/3648160.3648185

Index Terms

Hamming Tree: The Case for Energy-Aware Indexing for NVMs
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
  2. Information storage systems
    1. Information storage technologies
      1. Storage class memory
        Phase change memory

Recommendations

Drift-tolerant Coding to Enhance the Energy Efficiency of Multi-Level-Cell Phase-Change Memory
ISLPED '22: Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design

Phase-Change Memory (PCM) has emerged as a promising memory and storage technology in recent years, and Multi-Level-Cell (MLC) PCM further reduces the per-bit cost to improve its competitiveness by storing multiple bits in each PCM cell. However, MLC ...
Energy-Efficient Streaming Using Non-volatile Memory

The disk and the DRAM in a typical mobile system consume a significant fraction (up to 30%) of the total system energy. To save on storage energy, the DRAM should be small and the disk should be spun down for long periods of time. We show that this can ...
A content-aware writing mechanism for reducing energy on non-volatile memory based embedded storage systems

Emerging byte-addressable non-volatile memory (NVM), such as phase change memory has many advantages in terms of low power consumption, high density, in-place update, and higher write endurance. Reducing the energy consumption of NVM is a fundamental ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Management of Data

Proceedings of the ACM on Management of Data Volume 1, Issue 2

PACMMOD

June 2023

2310 pages

EISSN:2836-6573

DOI:10.1145/3605748

Editor:
Divyakant Agrawal
UC Santa Barbara, United States

Issue’s Table of Contents

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2023

Published in PACMMOD Volume 1, Issue 2

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
583
Total Downloads

Downloads (Last 12 months)379
Downloads (Last 6 weeks)47

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hao XChandramouli B(2024)Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range IndexProceedings of the VLDB Endowment10.14778/3681954.368201217:11(3442-3455)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.14778/3681954.3682012
Zheng YTan K(2024)Sorting on Byte-Addressable Storage: The Resurgence of Tree StructureProceedings of the VLDB Endowment10.14778/3648160.364818517:6(1487-1500)Online publication date: 3-May-2024
https://dl.acm.org/doi/10.14778/3648160.3648185

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents