Update on triangle counting on GPU

Carl Pearson, Mohammad Almasri, Omer Anjum, Vikram S. Mailthody, Zaid Qureshi, Rakesh Nagi, Jinjun Xiong, Wen Mei Hwu

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

Abstract

This work presents an update to the triangle-counting portion of the subgraph isomorphism static graph challenge. This work is motivated by a desire to understand the impact of CUDA unified memory on the triangle-counting problem. First, CUDA unified memory is used to overlap reading large graph data from disk with graph data structures in GPU memory. Second, we use CUDA unified memory hints to solve multi-GPU performance scaling challenges present in our last submission. Finally, we improve the single-GPU kernel performance from our past submission by introducing a work-stealing dynamic algorithm GPU kernel with persistent threads, which makes performance adaptive for large graphs without requiring a graph analysis phase.

Original languageEnglish (US)
Title of host publication2019 IEEE High Performance Extreme Computing Conference, HPEC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728150208
DOIs
StatePublished - Sep 2019
Event2019 IEEE High Performance Extreme Computing Conference, HPEC 2019 - Waltham, United States
Duration: Sep 24 2019Sep 26 2019

Publication series

Name2019 IEEE High Performance Extreme Computing Conference, HPEC 2019

Conference

Conference2019 IEEE High Performance Extreme Computing Conference, HPEC 2019
CountryUnited States
CityWaltham
Period9/24/199/26/19

Keywords

  • GPU
  • Graph algorithms
  • Triangle counting

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Update on triangle counting on GPU'. Together they form a unique fingerprint.

Cite this