Abstract
At extreme scale, irregularities in the structure of scale-free graphs such as social network graphs limit our ability to analyze these important and growing datasets. A key challenge is the presence of high-degree vertices (hubs), that leads to parallel workload and storage imbalances. The imbalances occur because existing partitioning techniques are not able to effectively partition high-degree vertices. We present techniques to distribute storage, computation, and communication of hubs for extreme scale graphs in distributed memory supercomputers. To balance the hub processing workload, we distribute hub data structures and related computation among a set of delegates. The delegates coordinate using highly optimized, yet portable, asynchronous broadcast and reduction operations. We demonstrate scalability of our new algorithmic technique using Breadth-First Search (BFS), Single Source Shortest Path (SSSP), K-Core Decomposition, and Page-Rank on synthetically generated scale-free graphs.
Original language | English (US) |
---|---|
Article number | 7013032 |
Pages (from-to) | 549-559 |
Number of pages | 11 |
Journal | International Conference for High Performance Computing, Networking, Storage and Analysis, SC |
Volume | 2015-January |
Issue number | January |
DOIs | |
State | Published - Jan 16 2014 |
Externally published | Yes |
Event | International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014 - New Orleans, United States Duration: Nov 16 2014 → Nov 21 2014 |
ASJC Scopus subject areas
- Computer Networks and Communications
- Computer Science Applications
- Hardware and Architecture
- Software