XB+-Tree: Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture

Li Zheng Liang; Ming Chang Yang; Yuan Hao Chang; Tseng Yi Chen; Shuo Han Chen; Hsin Wen Wei; Wei Kuan Shih

doi:10.1109/COMPSAC.2017.267

XB⁺-Tree: Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture

Li Zheng Liang, Ming Chang Yang, Yuan Hao Chang, Tseng Yi Chen, Shuo Han Chen, Hsin Wen Wei, Wei Kuan Shih

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Non-volatile memory (NVM) has widely participated in the evolution of the next-generation memory architecture by way of being the substitution of the main memory. To cope with the problem of asymmetric read/write speeds of NVM, several excellent researches have been proposed to reduce the number of writes to the NVM-based main memory. Nevertheless, most of these existing approaches do not take the cache-line-based access behavior between the processor and the main memory into consideration. Thus, in order to essentially improve the access performance of the NVM-based memory architecture, this work aims to optimize the cache-line-based access performance over the NVM-based memory architecture based on the special access patterns in many popular internet of things (IoT) and in-memory database applications. Our experiments based on the well-known Gem5 full system simulator reveal that, compared to other existing representative approaches, the proposed design can effectively reduce the total execution time of insertion by 20.92~55.20% and improve the execution time of query by 2.06~23.36%.

Original language	English
Title of host publication	Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017
Editors	Claudio Demartini, Thomas Conte, Motonori Nakamura, Chung-Horng Lung, Zhiyong Zhang, Kamrul Hasan, Sorel Reisman, Ling Liu, William Claycomb, Hiroki Takakura, Ji-Jiang Yang, Edmundo Tovar, Stelvio Cimato, Sheikh Iqbal Ahamed, Toyokazu Akiyama
Publisher	IEEE Computer Society
Pages	483-491
Number of pages	9
ISBN (Electronic)	9781538603673
DOIs	https://doi.org/10.1109/COMPSAC.2017.267
State	Published - 7 Sep 2017
Event	41st IEEE Annual Computer Software and Applications Conference, COMPSAC 2017 - Torino, Italy Duration: 4 Jul 2017 → 8 Jul 2017

Publication series

Name	Proceedings - International Computer Software and Applications Conference
Volume	1
ISSN (Print)	0730-3157

Conference

Conference	41st IEEE Annual Computer Software and Applications Conference, COMPSAC 2017
Country/Territory	Italy
City	Torino
Period	4/07/17 → 8/07/17

Keywords

access-pattern-aware
cache-line-based tree
in-memory database
Non-Volatile main memory
NVM

Access to Document

10.1109/COMPSAC.2017.267

Cite this

Liang, L. Z., Yang, M. C., Chang, Y. H., Chen, T. Y., Chen, S. H., Wei, H. W., & Shih, W. K. (2017). XB⁺-Tree: Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture. In C. Demartini, T. Conte, M. Nakamura, C-H. Lung, Z. Zhang, K. Hasan, S. Reisman, L. Liu, W. Claycomb, H. Takakura, J-J. Yang, E. Tovar, S. Cimato, S. I. Ahamed, & T. Akiyama (Eds.), Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017 (pp. 483-491). [8029647] (Proceedings - International Computer Software and Applications Conference; Vol. 1). IEEE Computer Society. https://doi.org/10.1109/COMPSAC.2017.267

Liang, Li Zheng ; Yang, Ming Chang ; Chang, Yuan Hao ; Chen, Tseng Yi ; Chen, Shuo Han ; Wei, Hsin Wen ; Shih, Wei Kuan. / XB⁺-Tree : Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture. Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017. editor / Claudio Demartini ; Thomas Conte ; Motonori Nakamura ; Chung-Horng Lung ; Zhiyong Zhang ; Kamrul Hasan ; Sorel Reisman ; Ling Liu ; William Claycomb ; Hiroki Takakura ; Ji-Jiang Yang ; Edmundo Tovar ; Stelvio Cimato ; Sheikh Iqbal Ahamed ; Toyokazu Akiyama. IEEE Computer Society, 2017. pp. 483-491 (Proceedings - International Computer Software and Applications Conference).

@inproceedings{e4f22f3f1ede45b2937ec039dddaf0f6,

title = "XB+-Tree: Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture",

abstract = "Non-volatile memory (NVM) has widely participated in the evolution of the next-generation memory architecture by way of being the substitution of the main memory. To cope with the problem of asymmetric read/write speeds of NVM, several excellent researches have been proposed to reduce the number of writes to the NVM-based main memory. Nevertheless, most of these existing approaches do not take the cache-line-based access behavior between the processor and the main memory into consideration. Thus, in order to essentially improve the access performance of the NVM-based memory architecture, this work aims to optimize the cache-line-based access performance over the NVM-based memory architecture based on the special access patterns in many popular internet of things (IoT) and in-memory database applications. Our experiments based on the well-known Gem5 full system simulator reveal that, compared to other existing representative approaches, the proposed design can effectively reduce the total execution time of insertion by 20.92~55.20% and improve the execution time of query by 2.06~23.36%.",

keywords = "access-pattern-aware, cache-line-based tree, in-memory database, Non-Volatile main memory, NVM",

author = "Liang, {Li Zheng} and Yang, {Ming Chang} and Chang, {Yuan Hao} and Chen, {Tseng Yi} and Chen, {Shuo Han} and Wei, {Hsin Wen} and Shih, {Wei Kuan}",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; null ; Conference date: 04-07-2017 Through 08-07-2017",

year = "2017",

month = sep,

day = "7",

doi = "10.1109/COMPSAC.2017.267",

language = "???core.languages.en_GB???",

series = "Proceedings - International Computer Software and Applications Conference",

publisher = "IEEE Computer Society",

pages = "483--491",

editor = "Claudio Demartini and Thomas Conte and Motonori Nakamura and Chung-Horng Lung and Zhiyong Zhang and Kamrul Hasan and Sorel Reisman and Ling Liu and William Claycomb and Hiroki Takakura and Ji-Jiang Yang and Edmundo Tovar and Stelvio Cimato and Ahamed, {Sheikh Iqbal} and Toyokazu Akiyama",

booktitle = "Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017",

}

Liang, LZ, Yang, MC, Chang, YH, Chen, TY, Chen, SH, Wei, HW & Shih, WK 2017, XB⁺-Tree: Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture. in C Demartini, T Conte, M Nakamura, C-H Lung, Z Zhang, K Hasan, S Reisman, L Liu, W Claycomb, H Takakura, J-J Yang, E Tovar, S Cimato, SI Ahamed & T Akiyama (eds), Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017., 8029647, Proceedings - International Computer Software and Applications Conference, vol. 1, IEEE Computer Society, pp. 483-491, 41st IEEE Annual Computer Software and Applications Conference, COMPSAC 2017, Torino, Italy, 4/07/17. https://doi.org/10.1109/COMPSAC.2017.267

XB⁺-Tree : Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture. / Liang, Li Zheng; Yang, Ming Chang; Chang, Yuan Hao; Chen, Tseng Yi; Chen, Shuo Han; Wei, Hsin Wen; Shih, Wei Kuan.

Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017. ed. / Claudio Demartini; Thomas Conte; Motonori Nakamura; Chung-Horng Lung; Zhiyong Zhang; Kamrul Hasan; Sorel Reisman; Ling Liu; William Claycomb; Hiroki Takakura; Ji-Jiang Yang; Edmundo Tovar; Stelvio Cimato; Sheikh Iqbal Ahamed; Toyokazu Akiyama. IEEE Computer Society, 2017. p. 483-491 8029647 (Proceedings - International Computer Software and Applications Conference; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - XB+-Tree

AU - Liang, Li Zheng

AU - Yang, Ming Chang

AU - Chang, Yuan Hao

AU - Chen, Tseng Yi

AU - Chen, Shuo Han

AU - Wei, Hsin Wen

AU - Shih, Wei Kuan

PY - 2017/9/7

Y1 - 2017/9/7

N2 - Non-volatile memory (NVM) has widely participated in the evolution of the next-generation memory architecture by way of being the substitution of the main memory. To cope with the problem of asymmetric read/write speeds of NVM, several excellent researches have been proposed to reduce the number of writes to the NVM-based main memory. Nevertheless, most of these existing approaches do not take the cache-line-based access behavior between the processor and the main memory into consideration. Thus, in order to essentially improve the access performance of the NVM-based memory architecture, this work aims to optimize the cache-line-based access performance over the NVM-based memory architecture based on the special access patterns in many popular internet of things (IoT) and in-memory database applications. Our experiments based on the well-known Gem5 full system simulator reveal that, compared to other existing representative approaches, the proposed design can effectively reduce the total execution time of insertion by 20.92~55.20% and improve the execution time of query by 2.06~23.36%.

AB - Non-volatile memory (NVM) has widely participated in the evolution of the next-generation memory architecture by way of being the substitution of the main memory. To cope with the problem of asymmetric read/write speeds of NVM, several excellent researches have been proposed to reduce the number of writes to the NVM-based main memory. Nevertheless, most of these existing approaches do not take the cache-line-based access behavior between the processor and the main memory into consideration. Thus, in order to essentially improve the access performance of the NVM-based memory architecture, this work aims to optimize the cache-line-based access performance over the NVM-based memory architecture based on the special access patterns in many popular internet of things (IoT) and in-memory database applications. Our experiments based on the well-known Gem5 full system simulator reveal that, compared to other existing representative approaches, the proposed design can effectively reduce the total execution time of insertion by 20.92~55.20% and improve the execution time of query by 2.06~23.36%.

KW - access-pattern-aware

KW - cache-line-based tree

KW - in-memory database

KW - Non-Volatile main memory

KW - NVM

UR - http://www.scopus.com/inward/record.url?scp=85031926174&partnerID=8YFLogxK

U2 - 10.1109/COMPSAC.2017.267

DO - 10.1109/COMPSAC.2017.267

M3 - 會議論文篇章

AN - SCOPUS:85031926174

T3 - Proceedings - International Computer Software and Applications Conference

SP - 483

EP - 491

BT - Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017

A2 - Demartini, Claudio

A2 - Conte, Thomas

A2 - Nakamura, Motonori

A2 - Lung, Chung-Horng

A2 - Zhang, Zhiyong

A2 - Hasan, Kamrul

A2 - Reisman, Sorel

A2 - Liu, Ling

A2 - Claycomb, William

A2 - Takakura, Hiroki

A2 - Yang, Ji-Jiang

A2 - Tovar, Edmundo

A2 - Cimato, Stelvio

A2 - Ahamed, Sheikh Iqbal

A2 - Akiyama, Toyokazu

PB - IEEE Computer Society

Y2 - 4 July 2017 through 8 July 2017

ER -

Liang LZ, Yang MC, Chang YH, Chen TY, Chen SH, Wei HW et al. XB⁺-Tree: Access-Pattern-Aware Cache-Line-Based Tree for Non-volatile Main Memory Architecture. In Demartini C, Conte T, Nakamura M, Lung C-H, Zhang Z, Hasan K, Reisman S, Liu L, Claycomb W, Takakura H, Yang J-J, Tovar E, Cimato S, Ahamed SI, Akiyama T, editors, Proceedings - 2017 IEEE 41st Annual Computer Software and Applications Conference, COMPSAC 2017. IEEE Computer Society. 2017. p. 483-491. 8029647. (Proceedings - International Computer Software and Applications Conference). https://doi.org/10.1109/COMPSAC.2017.267