Collaborative (CPU + GPU) algorithms for triangle counting and truss decomposition on the Minsky architecture: Static graph challenge: Subgraph isomorphism

Ketan Date, Keven Feng, Rakesh Nagi, Jinjun Xiong, Nam Sung Kim, Wen-Mei W Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we present collaborative CPU + GPU algorithms for triangle counting and truss decomposition, the two fundamental problems in graph analytics. We describe the implementation details and present experimental evaluation on the IBM Minsky platform. The main contribution of this paper is a thorough benchmarking and comparison of the different memory management schemes offered by CUDA 8 and NVLink, which can be harnessed for tackling large problems where the limited GPU memory capacity is the primary bottleneck in traditional computing platform. We find that the collaborative algorithms achieve 28× speedup on average (180× max) for triangle counting, and 165× speedup on average (498× max) for truss decomposition, when compared with the baseline Python implementation provided by the Graph Challenge organizers.

Original languageEnglish (US)
Title of host publication2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538634721
DOIs
StatePublished - Oct 30 2017
Event2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 - Waltham, United States
Duration: Sep 12 2017Sep 14 2017

Publication series

Name2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Other

Other2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
CountryUnited States
CityWaltham
Period9/12/179/14/17

Keywords

  • CUDA
  • GPU
  • collaborative graph algorithms
  • triangle counting
  • truss decomposition

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Collaborative (CPU + GPU) algorithms for triangle counting and truss decomposition on the Minsky architecture: Static graph challenge: Subgraph isomorphism'. Together they form a unique fingerprint.

  • Cite this

    Date, K., Feng, K., Nagi, R., Xiong, J., Kim, N. S., & Hwu, W-M. W. (2017). Collaborative (CPU + GPU) algorithms for triangle counting and truss decomposition on the Minsky architecture: Static graph challenge: Subgraph isomorphism. In 2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 [8091042] (2017 IEEE High Performance Extreme Computing Conference, HPEC 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPEC.2017.8091042