Half-Precision Floating-Point Formats for PageRank: Opportunities and Challenges

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

105 Downloads (Pure)

Abstract

Mixed-precision computation has been proposed as a means to accelerate iterative algorithms as it can reduce the memory bandwidth and cache effectiveness. This paper aims for further memory traffic reduction via introducing new half-precision (16 bit) data formats customized for PageRank. We develop two formats. A first format builds on the observation that the exponents of about 99% of PageRank values are tightly distributed around the exponent of the inverse of the number of vertices. A second format builds on the observation that 6 exponent bits are sufficient to capture the full dynamic range of PageRank values. Our floating-point formats provide less precision compared to standard IEEE 754 formats, but sufficient dynamic range for PageRank. The experimental results on various size graphs show that the proposed formats can achieve an accuracy of le-4., which is an improvement over the state of the art. Due to random memory access patterns in the algorithm, performance improvements over our highly tuned baseline are 1.5% at best.

Original languageEnglish
Title of host publication2020 IEEE High Performance Extreme Computing Conference, HPEC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728192192
DOIs
Publication statusPublished - 22 Dec 2020
Event2020 IEEE High Performance Extreme Computing Conference, HPEC 2020 - Virtual, Waltham, United States
Duration: 21 Sep 202025 Sep 2020

Publication series

NameIEEE High Performance Extreme Computing Conference: Proceedings
ISSN (Print)2377-6943
ISSN (Electronic)2643-1971

Conference

Conference2020 IEEE High Performance Extreme Computing Conference, HPEC 2020
Country/TerritoryUnited States
CityVirtual, Waltham
Period21/09/202025/09/2020

Bibliographical note

Publisher Copyright:
© 2020 IEEE.

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Customized Floating-Point Data Format
  • Graph Processing
  • PageRank
  • Transprecision Computing

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Half-Precision Floating-Point Formats for PageRank: Opportunities and Challenges'. Together they form a unique fingerprint.

Cite this