Leveraging Write Heterogeneity of Phase Change Memory on Supporting Self-Balancing Binary Tree

Che Wei Chang*, Chun Feng Wu, Yuan Hao Chang*, Ming Chang Yang, Chieh Fu Chang

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

3 Scopus citations


With the increasing demand of massive/big data applications, nonvolatile memory (NVM), such as phase-change memory (PCM), has become a promising candidate to replace DRAM because of its low leakage power, nonvolatility, and high density. However, most of the existing memory read/write intensive algorithms and data structures are not aware of the PCM write heterogeneity in terms of both energy consumption and latency. In particular, self-balancing binary search trees, which are widely used to manage massive data in the big-data era, were designed without the consideration of PCM characteristics. Thus, the multiple rotations of the tree balancing process would degrade the memory performance. This work explores the relations among nodes and analyzes tree operations, and the node indexing and address mapping are redesigned to reduce the tree management overhead on single-level cell (SLC) PCM by decreasing the number of bit flips of tree rotations. When multilevel cell (MLC) PCM is included, our address mapping algorithm is developed to reduce the total energy consumption and latency with considerations of the heterogeneous write operations of different cell states. Experimental results show that our solution significantly outperforms the original implementation of a self-balancing binary search tree when the amount of data is large.

Original languageEnglish
Pages (from-to)1757-1770
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number6
StatePublished - 01 06 2022

Bibliographical note

Publisher Copyright:
© 1982-2012 IEEE.


  • Energy saving
  • multilevel cell (MLC)
  • nonvolatile memory (NVM)
  • phase-change memory (PCM)
  • tree data structure
  • write heterogeneity


Dive into the research topics of 'Leveraging Write Heterogeneity of Phase Change Memory on Supporting Self-Balancing Binary Tree'. Together they form a unique fingerprint.

Cite this