Scaling Techniques for Massive Scale-Free Graphs in Distributed (External) Memory

Roger Pearce, Maya Gokhale, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 Scopus citations

Abstract

We present techniques to process large scale-free graphs in distributed memory. Our aim is to scale to trillions of edges, and our research is targeted at leadership class supercomputers and clusters with local non-volatile memory, e.g., NAND Flash. We apply an edge list partitioning technique, designed to accommodate high-degree vertices (hubs) that create scaling challenges when processing scale-free graphs. In addition to partitioning hubs, we use ghost vertices to represent the hubs to reduce communication hotspots. We present a scaling study with three important graph algorithms: Breadth-First Search (BFS), K-Core decomposition, and Triangle Counting. We also demonstrate scalability on BG/P Intrepid by comparing to best known Graph500 results. We show results on two clusters with local NVRAM storage that are capable of traversing trillion-edge scale-free graphs. By leveraging node-local NAND Flash, our approach can process thirty-two times larger datasets with only a 39% performance degradation in Traversed Edges Per Second (TEPS). © 2013 IEEE.
Original languageEnglish (US)
Title of host publication2013 IEEE 27th International Symposium on Parallel and Distributed Processing
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages825-836
Number of pages12
ISBN (Print)9781467360661
DOIs
StatePublished - May 2013
Externally publishedYes

Fingerprint

Dive into the research topics of 'Scaling Techniques for Massive Scale-Free Graphs in Distributed (External) Memory'. Together they form a unique fingerprint.

Cite this