NVM-based Hybrid BFS with memory efficient data structure

Keita Iwabuchi; Hitoshi Sato; Yuichiro Yasui; Katsuki Fujisawa; Satoshi Matsuoka

doi:10.1109/BigData.2014.7004270

NVM-based Hybrid BFS with memory efficient data structure

Keita Iwabuchi
, Hitoshi Sato
, Yuichiro Yasui
, Katsuki Fujisawa
, Satoshi Matsuoka

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

14 Citations (Scopus)

Abstract

We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 2³¹ vertices and 2³⁵ edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 % performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

Original language	English
Title of host publication	Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014
Editors	Jimmy Lin, Jian Pei, Xiaohua Tony Hu, Wo Chang, Raghunath Nambiar, Charu Aggarwal, Nick Cercone, Vasant Honavar, Jun Huan, Bamshad Mobasher, Saumyadipta Pyne
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	529-538
Number of pages	10
ISBN (Electronic)	9781479956654
DOIs	https://doi.org/10.1109/BigData.2014.7004270
Publication status	Published - 2014
Event	2nd IEEE International Conference on Big Data, IEEE Big Data 2014 - Washington, United States Duration: Oct 27 2014 → Oct 30 2014

Publication series

Name	Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

Other

Other	2nd IEEE International Conference on Big Data, IEEE Big Data 2014
Country/Territory	United States
City	Washington
Period	10/27/14 → 10/30/14

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Information Systems

Access to Document

10.1109/BigData.2014.7004270

Cite this

Iwabuchi, K., Sato, H., Yasui, Y., Fujisawa, K., & Matsuoka, S. (2014). NVM-based Hybrid BFS with memory efficient data structure. In J. Lin, J. Pei, X. T. Hu, W. Chang, R. Nambiar, C. Aggarwal, N. Cercone, V. Honavar, J. Huan, B. Mobasher, & S. Pyne (Eds.), Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014 (pp. 529-538). Article 7004270 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2014.7004270

NVM-based Hybrid BFS with memory efficient data structure. / Iwabuchi, Keita; Sato, Hitoshi; Yasui, Yuichiro et al.
Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014. ed. / Jimmy Lin; Jian Pei; Xiaohua Tony Hu; Wo Chang; Raghunath Nambiar; Charu Aggarwal; Nick Cercone; Vasant Honavar; Jun Huan; Bamshad Mobasher; Saumyadipta Pyne. Institute of Electrical and Electronics Engineers Inc., 2014. p. 529-538 7004270 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014).

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

Iwabuchi, K, Sato, H, Yasui, Y, Fujisawa, K & Matsuoka, S 2014, NVM-based Hybrid BFS with memory efficient data structure. in J Lin, J Pei, XT Hu, W Chang, R Nambiar, C Aggarwal, N Cercone, V Honavar, J Huan, B Mobasher & S Pyne (eds), Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014., 7004270, Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014, Institute of Electrical and Electronics Engineers Inc., pp. 529-538, 2nd IEEE International Conference on Big Data, IEEE Big Data 2014, Washington, United States, 10/27/14. https://doi.org/10.1109/BigData.2014.7004270

Iwabuchi K, Sato H, Yasui Y, Fujisawa K, Matsuoka S. NVM-based Hybrid BFS with memory efficient data structure. In Lin J, Pei J, Hu XT, Chang W, Nambiar R, Aggarwal C, Cercone N, Honavar V, Huan J, Mobasher B, Pyne S, editors, Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 529-538. 7004270. (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014). doi: 10.1109/BigData.2014.7004270

Iwabuchi, Keita ; Sato, Hitoshi ; Yasui, Yuichiro et al. / NVM-based Hybrid BFS with memory efficient data structure. Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014. editor / Jimmy Lin ; Jian Pei ; Xiaohua Tony Hu ; Wo Chang ; Raghunath Nambiar ; Charu Aggarwal ; Nick Cercone ; Vasant Honavar ; Jun Huan ; Bamshad Mobasher ; Saumyadipta Pyne. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 529-538 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014).

@inproceedings{77317188f5db486ea5bb767caa4fc408,

title = "NVM-based Hybrid BFS with memory efficient data structure",

abstract = "We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 231 vertices and 235 edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 \% performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.",

keywords = "Breadth-first search, Extreme Big Data, Graph algorithms, Memory architecture, NVM",

author = "Keita Iwabuchi and Hitoshi Sato and Yuichiro Yasui and Katsuki Fujisawa and Satoshi Matsuoka",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2nd IEEE International Conference on Big Data, IEEE Big Data 2014 ; Conference date: 27-10-2014 Through 30-10-2014",

year = "2014",

doi = "10.1109/BigData.2014.7004270",

language = "English",

series = "Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "529--538",

editor = "Jimmy Lin and Jian Pei and Hu, \{Xiaohua Tony\} and Wo Chang and Raghunath Nambiar and Charu Aggarwal and Nick Cercone and Vasant Honavar and Jun Huan and Bamshad Mobasher and Saumyadipta Pyne",

booktitle = "Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014",

address = "United States",

}

TY - GEN

T1 - NVM-based Hybrid BFS with memory efficient data structure

AU - Iwabuchi, Keita

AU - Sato, Hitoshi

AU - Yasui, Yuichiro

AU - Fujisawa, Katsuki

AU - Matsuoka, Satoshi

PY - 2014

Y1 - 2014

N2 - We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 231 vertices and 235 edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 % performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

AB - We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 231 vertices and 235 edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 % performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

KW - Breadth-first search

KW - Extreme Big Data

KW - Graph algorithms

KW - Memory architecture

KW - NVM

UR - https://www.scopus.com/pages/publications/84921825024

UR - https://www.scopus.com/pages/publications/84921825024#tab=citedBy

U2 - 10.1109/BigData.2014.7004270

DO - 10.1109/BigData.2014.7004270

M3 - Conference contribution

AN - SCOPUS:84921825024

T3 - Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

SP - 529

EP - 538

BT - Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

A2 - Lin, Jimmy

A2 - Pei, Jian

A2 - Hu, Xiaohua Tony

A2 - Chang, Wo

A2 - Nambiar, Raghunath

A2 - Aggarwal, Charu

A2 - Cercone, Nick

A2 - Honavar, Vasant

A2 - Huan, Jun

A2 - Mobasher, Bamshad

A2 - Pyne, Saumyadipta

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2nd IEEE International Conference on Big Data, IEEE Big Data 2014

Y2 - 27 October 2014 through 30 October 2014

ER -

NVM-based Hybrid BFS with memory efficient data structure

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this