Graphfire: Synergizing Fetch, Insertion, and Replacement Policies for Graph Analytics

Aninda Manocha, Juan Luis Aragon, Margaret Martonosi

Research output: Contribution to journalArticlepeer-review

Abstract

Despite their ubiquity in many important big-data applications, graph analytic kernels continue to challenge modern memory hierarchies due to their frequent, long-latency, pointer indirect accesses to vertex property data. Such accesses exhibit poor locality and variable reuse that trouble cache replacement policies, and consequently increase memory bandwidth pressure. Specialized graph-tailored prefetching mechanisms, processor designs, and memory hierarchy engines have been developed to tolerate the long latencies of such accesses. However, these approaches are either too bandwidth-intensive, require invasive hardware changes that inhibit general-purpose computation flexibility, or rely on software preprocessing that limits true speedup. This work introduces Graphfire, a flexible memory hierarchy approach that learns different access patterns in graph processing and exploits the synergy of specialized fetch, insertion, and replacement optimizations for problematic indirect accesses without relying on software or ISA support. More specifically, Graphfiire identifies when these irregular accesses occur and employs tailored access granularities, data-aware insertion, and frequency-based replacement accordingly. It achieves up to a 1.79x speedup (geomean 1.3x) and these improvements scale due to bandwidth efficiency; with 64 cores, Graphfire yields up to a 71.33x speedup (geomean 63.32x) over a single baseline core and allows memory-bound graph analytic codes to scale far beyond prior work.

Original languageEnglish (US)
JournalIEEE Transactions on Computers
DOIs
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • cache
  • Encyclopedias
  • graph analytics
  • Hardware
  • Indexes
  • Kernel
  • memory hierarchy
  • Memory management
  • Optimization
  • Software

Fingerprint

Dive into the research topics of 'Graphfire: Synergizing Fetch, Insertion, and Replacement Policies for Graph Analytics'. Together they form a unique fingerprint.

Cite this