Graptor: efficient pull and push style vectorized graph processing

Hans Vandierendonck*

*Corresponding author for this work

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

Abstract

Vectorization seeks to accelerate computation through data-level parallelism. Vectorization has been applied to graph processing, where the graph is traversed either in a push style or a pull style. As it is not well understood which style will perform better, there is a need for both vectorized push and pull style traversals. This paper is the first to present a general solution to vectorizing push style traversal. It more-over presents an enhanced vectorized pull style traversal. Our solution consists of three components: CleanCut, a graph partitioning approach that rules out inter-thread race conditions; VectorFast, a compact graph representation that supports fast-forwarding through the edge stream; and Graptor, a domain-specific language and compiler for auto-vectorizing and optimizing graph processing codes. Experimental evaluation demonstrates average speedups of 2.72X over Ligra, 2.46X over GraphGrind, and 2.33X over GraphIt. Graptor outperforms Grazelle, which performs vectorized pull style graph processing, 4.05X.

Original languageEnglish
Title of host publicationProceedings of the 34th ACM International Conference on Supercomputing, ICS 2020
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Electronic)9781450379830
DOIs
Publication statusPublished - 29 Jun 2020
Event34th ACM International Conference on Supercomputing, ICS 2020 - Barcelona, Spain
Duration: 29 Jun 202002 Jul 2020

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

Conference34th ACM International Conference on Supercomputing, ICS 2020
CountrySpain
CityBarcelona
Period29/06/202002/07/2020

Keywords

  • data structures
  • graph analytics
  • vectorization

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Graptor: efficient pull and push style vectorized graph processing'. Together they form a unique fingerprint.

Cite this