TY - GEN
T1 - Obfuscated red-black tree
T2 - 2017 IEEE International Conference on Applied System Innovation, ICASI 2017
AU - Hsieh, Yun Shan
AU - Liu, Yun Fei
AU - Chen, Yi Hua
AU - Chen, Min Chun
AU - Huang, Po Chun
AU - Chen, Hsin Hsin
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/7/21
Y1 - 2017/7/21
N2 - Due to the excellent performance and energy efficiency, modern nonvolatile memories (NVMs) have become popular alternatives to DRAM as main memory. However, the intrinsic characteristics of NVMs are quite different from those of DRAM, making existing designs of system and application software unfavorable on NVMs. For example, a write operation typically takes much more time and energy than a read operation on NVMs, and system or application software should try to reduce write activities so as to enhance the overall performance and energy efficiency of the system. In this work, we propose a novel design of NVM-based self-balancing binary search trees for red-black tree, a widely used dictionary structure. Through intentionally mixing up the pointers of red-black tree nodes, we effectively decouple the pointers of a red-black tree into two parts, namely (a) the pointers that maintain the logical structure of the red-black tree and (b) the pointers that keep the memory addresses of the nodes of the red-black tree. By doing so, the NVM writes are significantly reduced, and the performance and energy efficiency are remarkably improved. The efficacy of the proposed design is then verified by experimental studies, where the results are quite encouraging.
AB - Due to the excellent performance and energy efficiency, modern nonvolatile memories (NVMs) have become popular alternatives to DRAM as main memory. However, the intrinsic characteristics of NVMs are quite different from those of DRAM, making existing designs of system and application software unfavorable on NVMs. For example, a write operation typically takes much more time and energy than a read operation on NVMs, and system or application software should try to reduce write activities so as to enhance the overall performance and energy efficiency of the system. In this work, we propose a novel design of NVM-based self-balancing binary search trees for red-black tree, a widely used dictionary structure. Through intentionally mixing up the pointers of red-black tree nodes, we effectively decouple the pointers of a red-black tree into two parts, namely (a) the pointers that maintain the logical structure of the red-black tree and (b) the pointers that keep the memory addresses of the nodes of the red-black tree. By doing so, the NVM writes are significantly reduced, and the performance and energy efficiency are remarkably improved. The efficacy of the proposed design is then verified by experimental studies, where the results are quite encouraging.
UR - https://www.scopus.com/pages/publications/85028532436
UR - https://www.scopus.com/pages/publications/85028532436#tab=citedBy
U2 - 10.1109/ICASI.2017.7988178
DO - 10.1109/ICASI.2017.7988178
M3 - Conference contribution
AN - SCOPUS:85028532436
T3 - Proceedings of the 2017 IEEE International Conference on Applied System Innovation: Applied System Innovation for Modern Technology, ICASI 2017
SP - 1075
EP - 1078
BT - Proceedings of the 2017 IEEE International Conference on Applied System Innovation
A2 - Meen, Teen-Hang
A2 - Lam, Artde Donald Kin-Tak
A2 - Prior, Stephen D.
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 13 May 2017 through 17 May 2017
ER -
