Software-defined floating-point number formats and their application to graph processing

H. Vandierendonck*

*Corresponding author for this work

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

Abstract

This paper proposes software-defined floating-point number formats for graph processing workloads, which can improve performance in irregular workloads by reducing cache misses. Efficient arithmetic on software-defined number formats is challenging, even when based on conversion to wider, hardware-supported formats. We derive efficient conversion schemes that are tuned to the IA64 and AVX512 instruction sets. We demonstrate that: (i) reduced-precision number formats can be applied to graph processing without loss of accuracy; (ii) conversion of floating-point values is possible with minimal instructions; (iii) conversions are most efficient when utilizing vectorized instruction sets, specifically on IA64 processors. Experiments on twelve real-world graph data sets demonstrate that our techniques result in speedups up to 89% for PageRank and Accelerated PageRank, and up to 35% for Single-Source Shortest Paths. The same techniques help to accelerate the integer-based maximal independent set problem by up to 262%.

Original languageEnglish
Title of host publicationProceedings of the 36th ACM International Conference on Supercomputing: ICS 2022
PublisherAssociation for Computing Machinery
Number of pages17
ISBN (Electronic)9781450392815
DOIs
Publication statusPublished - 28 Jun 2022
Event36th ACM International Conference on Supercomputing, ICS 2022 - Virtual, Online
Duration: 27 Jun 202230 Jun 2022

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

Conference36th ACM International Conference on Supercomputing, ICS 2022
CityVirtual, Online
Period27/06/202230/06/2022

Bibliographical note

Publisher Copyright:
© 2022 ACM.

Keywords

  • Graph analytics
  • Software-defined number formats
  • Vectorization

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Software-defined floating-point number formats and their application to graph processing'. Together they form a unique fingerprint.

Cite this