Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs

Federico Busato, Oded Green, Nicola Bombieri, David A. Bader

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

68 Scopus citations

Abstract

Sparse data computations are ubiquitous in science and engineering. Unlike their dense data counterparts, sparse data computations have less locality and more irregularity in their execution, making them significantly more challenging to parallelize and optimize. Many of the existing formats for sparse data representations on parallel architectures are restricted to static data problems, while those for dynamic data suffer from inefficiency both in terms of performance and memory footprint. This work presents Hornet, a novel data representation that targets dynamic data problems. Hornet is scalable with the input size, and does not require any data re-allocation or re-initialization during the data evolution. We show a Hornet implementation for GPU architectures and compare it to the most widely used static and dynamic data structures.

Original languageEnglish (US)
Title of host publication2018 IEEE High Performance Extreme Computing Conference, HPEC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538659892
DOIs
StatePublished - Nov 26 2018
Externally publishedYes
Event2018 IEEE High Performance Extreme Computing Conference, HPEC 2018 - Waltham, United States
Duration: Sep 25 2018Sep 27 2018

Publication series

Name2018 IEEE High Performance Extreme Computing Conference, HPEC 2018

Conference

Conference2018 IEEE High Performance Extreme Computing Conference, HPEC 2018
Country/TerritoryUnited States
CityWaltham
Period9/25/189/27/18

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Hardware and Architecture

Keywords

  • Dynamic Graph Structures
  • GPU Computing
  • Graph Analytics

Fingerprint

Dive into the research topics of 'Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs'. Together they form a unique fingerprint.

Cite this