B∗-Sort: Enabling Write-Once Sorting for Nonvolatile Memory

Yu Pei Liang, Tseng Yi Chen, Yuan Hao Chang, Shuo Han Chen, Hsin Wen Wei, Wei Kuan Shih

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Nonvolatile random access memory (NVRAM) has been regarding a promising technology to replace DRAM as the main memory in embedded systems owing to its nonvolatility and low idle power consumption. However, due to the asymmetric read/write costs and limited lifetime of NVRAM, most of the existing fundamental algorithms are not NVRAM-friendly with their write pattern and write intensiveness. Thus, existing fundamental algorithms for NVRAM embedded devices has been revealed. For instance, as the sorting algorithm is one of the most fundamental algorithms, most of the existing sorting algorithms are not NVRAM-friendly because they impose heavy write traffic [i.e., mathcal {O}(nlg {n}) ] on main memory, where n is the number of unsorted elements. To resolve this issue, this article proposes a write-once sorting algorithm, namely B∗-sort, to reduce the amount of write traffic on NVRAM-based main memory. B∗-sort adopts a brand-new concept, i.e., tree-based sort, inspired by the binary-search-tree structure to achieve the write-once property which can guarantee the optimal endurance during the sorting process. According to the experimental results, B∗-sort can achieve significant performance improvement for sorting on NVRAM-based systems.

Original languageEnglish
Article number9031698
Pages (from-to)4549-4562
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume39
Issue number12
DOIs
StatePublished - Dec 2020

Keywords

  • Nonvolatile memory
  • read/write asymmetry
  • sorting algorithm

Fingerprint

Dive into the research topics of 'B∗-Sort: Enabling Write-Once Sorting for Nonvolatile Memory'. Together they form a unique fingerprint.

Cite this