Authors: Roger Pearce, Maya Gokhale, Nancy M. Amato

Venue: IEEE International Symposium on Parallel and Distributed Processing (IPDPS)
DOI: 10.1109/IPDPS.2013.72
Link to Publication

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 [1]. 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)." 

@inproceedings{Pearce-stfmsg-2013, 
 author = {Roger A. Pearce and 
Maya B. Gokhale and 
Nancy M. Amato}, 
 bibsource = {dblp computer science bibliography, https://dblp.org}, 
 biburl = {https://dblp.org/rec/conf/ipps/PearceGA13.bib}, 
 booktitle = {27th {IEEE} International Symposium on Parallel and Distributed Processing, 
{IPDPS} 2013, Cambridge, MA, USA, May 20-24, 2013}, 
 doi = {10.1109/IPDPS.2013.72}, 
 pages = {825--836}, 
 publisher = {{IEEE} Computer Society}, 
 timestamp = {Mon, 20 Apr 2020 17:14:44 +0200}, 
 title = {Scaling Techniques for Massive Scale-Free Graphs in Distributed (External) 
Memory}, 
 url = {https://doi.org/10.1109/IPDPS.2013.72}, 
 year = {2013} 
}