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

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.

name of conference

• 2013 IEEE 27th International Symposium on Parallel and Distributed Processing

authors

• Amato, Nancy

published proceedings

• IEEE 27TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2013)

author list (cited authors)

• Pearce, R., Gokhale, M., & Amato, N. M.

citation count

• 45

complete list of authors

• Pearce, Roger||Gokhale, Maya||Amato, Nancy M

publication date

• May 2013

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS  Journal

keywords

• Big Data
• Distributed Computing
• Graph Algorithms
• Parallel Algorithms

Digital Object Identifier (DOI)

• 10.1109/IPDPS.2013.72

start page

• 825

end page

• 836

URL

• http://dx.doi.org/10.1109/ipdps.2013.72