On fast parallel detection of strongly connected components (SCC) in small-world graphs

Authors:

Abstract
Detecting strongly connected components (SCCs) in a directed graph is a fundamental graph analysis algorithm that is used in many science and engineering domains. Traditional approaches in parallel SCC detection, however, show limited performance and poor scaling behavior when applied to large real-world graph instances. In this paper, we investigate the shortcomings of the conventional approach and propose a series of extensions that consider the fundamental properties of real-world graphs, e.g. the small-world property. Our scalable implementation offers excellent performance on diverse, small-world graphs resulting in a 5.01x to 29.41x parallel speedup over the optimal sequential algorithm with 16 cores and 32 hardware threads.
Funding Information
  • Army contract (AHPCRC W911NF-07-2-0027-1)
  • Defense Advanced Research Projects Agency (US1226344, HR0011-11-C-0007, FA8750-12-2-0335)
  • Oracle
  • Advanced Micro Devices
  • Division of Computing and Communication Foundations (IIS-1247701, CCF-1111943)
  • Division of Information and Intelligent Systems (IIS-1247701, CCF-1111943)
  • Nvidia
  • Huawei Technologies
  • Intel Corporation
  • Stanford University

This publication has 20 references indexed in Scilit: