V-Combiner: Speeding-up iterative graph processing on a shared-memory platform with vertex merging

Azin Heidarshenas, Serif Yesil, Dimitrios Skarlatos, Sasa Misailovic, Adam Morrison, Josep Torrellas

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

Abstract

An iterative graph algorithm applies a vertex update operation to all vertices in a graph in every iteration. For large graphs, this computation is costly. However, in practice, not all the updates contribute equally to the end result and, in fact, an exact result may not be needed. In this work, we leverage these insights to speed-up iterative graph algorithms. We propose a mechanism to identify the less important vertices and omit computations for them. Our scheme, called V-Combiner, is a deterministic, fast, and application-transparent technique to construct an approximate graph to enable faster execution. The main idea behind V-Combiner is to merge certain vertices into hubs, which are vertices that have many connections and contribute heavily to the end result of the algorithm. We also propose an inexpensive correction step to recover the contribution of the merged vertices to get higher accuracy. We evaluate V-Combiner on 4 different applications and 5 datasets. For 44-threaded runs, V-Combiner achieves an average end-to-end speedup of 1.25X over the conventional system, with an accuracy of 91.8%. It also shows a better performance-accuracy trade-off than the existing sparsification and k-core techniques.

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

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

Conference34th ACM International Conference on Supercomputing, ICS 2020
CountrySpain
CityBarcelona
Period6/29/207/2/20

Keywords

  • approximations
  • graph processing
  • shared-memory platforms

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'V-Combiner: Speeding-up iterative graph processing on a shared-memory platform with vertex merging'. Together they form a unique fingerprint.

Cite this