SC15 Austin, TX

Design of a NVRAM Specialized Degree Aware Dynamic Graph Data Structure

Authors: Keita Iwabuchi (Tokyo Institute of Technology), Roger A. Pearce (Lawrence Livermore National Laboratory), Brian Van Essen (Lawrence Livermore National Laboratory), Maya Gokhale (Lawrence Livermore National Laboratory), Satoshi Matsuoka (Tokyo Institute of Technology)

Abstract: Large-scale graph processing, where the graph is too large to fit in main-memory, is often required in diverse application fields. Recently, Non-Volatile Random Access Memories (NVRAM) devices, e.g., NAND Flash, have enabled the possibility to extend main-memory capacity without extremely high cost and power consumption. Our previous work demonstrated that NVRAM can be a powerful storage media for graph applications. However, constructing large graphs is expensive especially for NVRAM devices, due to sparse random memory accesses. In many graph applications, the structure of the graph changes dynamically over time and may require online analysis. We describe a NVRAM specialized degree aware dynamic graph data structure using open addressing compact hash tables in order to minimize the number of page misses. We demonstrate that our dynamic graph structure can scale near-linearly on an out-of-core dynamic edge insertion workload.

Poster: pdf
Two-page extended abstract: pdf

Poster Index