Faster Parallel Traversal of Scale Free Graphs at Extreme Scale with Vertex Delegates

Roger Pearce, Maya Gokhale, Nancy M. Amato

Research output: Contribution to journalConference article

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. Our results show excellent scalability on large scale-free graphs up to 131K cores of the IBM BG/P, and outperform the best known Graph500 performance on BG/P Intrepid by 15%

Original languageEnglish (US)
Article number7013032
Pages (from-to)549-559
Number of pages11
JournalInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC
Volume2015-January
Issue numberJanuary
DOIs
StatePublished - Jan 16 2014
EventInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014 - New Orleans, United States
Duration: Nov 16 2014Nov 21 2014

Fingerprint

Scalability
Supercomputers
Data structures
Decomposition
Data storage equipment
Communication
Processing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Software

Cite this

Faster Parallel Traversal of Scale Free Graphs at Extreme Scale with Vertex Delegates. / Pearce, Roger; Gokhale, Maya; Amato, Nancy M.

In: International Conference for High Performance Computing, Networking, Storage and Analysis, SC, Vol. 2015-January, No. January, 7013032, 16.01.2014, p. 549-559.

Research output: Contribution to journalConference article

@article{5800667e70bf454fbf49c01f9c4c124c,
title = "Faster Parallel Traversal of Scale Free Graphs at Extreme Scale with Vertex Delegates",
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. Our results show excellent scalability on large scale-free graphs up to 131K cores of the IBM BG/P, and outperform the best known Graph500 performance on BG/P Intrepid by 15{\%}",
author = "Roger Pearce and Maya Gokhale and Amato, {Nancy M.}",
year = "2014",
month = "1",
day = "16",
doi = "10.1109/SC.2014.50",
language = "English (US)",
volume = "2015-January",
pages = "549--559",
journal = "International Conference for High Performance Computing, Networking, Storage and Analysis, SC",
issn = "2167-4329",
number = "January",

}

TY - JOUR

T1 - Faster Parallel Traversal of Scale Free Graphs at Extreme Scale with Vertex Delegates

AU - Pearce, Roger

AU - Gokhale, Maya

AU - Amato, Nancy M.

PY - 2014/1/16

Y1 - 2014/1/16

N2 - 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. Our results show excellent scalability on large scale-free graphs up to 131K cores of the IBM BG/P, and outperform the best known Graph500 performance on BG/P Intrepid by 15%

AB - 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. Our results show excellent scalability on large scale-free graphs up to 131K cores of the IBM BG/P, and outperform the best known Graph500 performance on BG/P Intrepid by 15%

UR - http://www.scopus.com/inward/record.url?scp=84983134675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983134675&partnerID=8YFLogxK

U2 - 10.1109/SC.2014.50

DO - 10.1109/SC.2014.50

M3 - Conference article

AN - SCOPUS:84983134675

VL - 2015-January

SP - 549

EP - 559

JO - International Conference for High Performance Computing, Networking, Storage and Analysis, SC

JF - International Conference for High Performance Computing, Networking, Storage and Analysis, SC

SN - 2167-4329

IS - January

M1 - 7013032

ER -