Accelerating Graph Analytics through Data-Parallel Primitives

Scientific Achievement

A 10-fold performance over a state-of-the-art approach results from a novel algorithmic design of maximal clique enumeration (MCE), a key graph analytics method. The novelty is the use of data-parallel primitives (DPP), a non-traditional programming model [1].

Significance and Impact

Approaches such as this are a promising path forward for both portability and performance on rapidly evolving computer architectures, into the exascale regime and beyond into Post-Moore’s Law. This method has widespread science and security applications, from computational chemistry and bioinformatics, to cybersecurity.

Research Results

  • Challenging reformulation of a breadth-first parallel MCE algorithm to use DPPs: map, reduce, scan, compact, unique, sort, ..
  • Platform-portable, shared-memory parallel implementation: runs on CPUs and GPUs
  • Performance comparison with state-of-the-art implementations shows significant performance advantages
  • This algorithm is being used as part of a state-of-the-art image segmentation method, which is targeting analysis of image-based data from beamline science

Contact

Bibliography

  1. B. Lessley, T. Perciano, M. Mathai, H. Childs, and E. W. Bethel, “Maximal Clique Enumeration with Data Parallel Primitives,” in 7th IEEE Symposium on Large Data Analysis and Visualization (LDAV), Phoenix, AZ, USA, Oct. 2017.