Back to search

Georgia Institute of Technology

Near-data processing for dynamic graph analytics

Abstract

dc:description.abstract

Massive data rates in cybersecurity, simulation, and social media analysis applications are driving rapid advances in the field of streaming graph analytics. The data structures that enable streaming graph analytics pose unique challenges for high-performance computing system designers. When the sorted, contiguous arrays of static graphs are replaced with the fragmented, linked data structures of dynamic graphs, these systems struggle to reach the memory bandwidth saturation point. Behaviors such as pointer-chasing and poor spatial locality expose the true latency of modern memory devices, which has not kept up with processor clock rates. This dissertation develops a streaming graph benchmark, DynoGraph, which is distinguished from static graph benchmarks by the use of realistic streaming graph inputs and dynamic graph data structures. The benchmark is used to expose performance pitfalls in existing implementations. These insights flow into the design of near-memory accelerators for streaming graph analytics, as well as software improvements. The Emu architecture is identified as a promising solution for accelerating algorithms with low spatial locality, unbalanced parallelism, and fine-grained memory accesses, since it is able to maintain high memory bandwidth utilization in a worst-case pointer-chasing scenario. The work culminates in a characterization of the Emu Chick hardware prototype, proposing efficient programming primitives, highlighting necessary system improvements, and demonstrating the potential for greatly improved performance on this important class of workloads.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hein, Eric Robert
Advisor dc:contributor.advisor
  • Conte, Thomas M.
Committee members dc:contributor.committeemember
  • Bader, David
  • Yalamanchili, Sudhakar
  • Vuduc, Richard
  • Prvulovic, Milos

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/60228

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hein, Eric Robert. Near-data processing for dynamic graph analytics. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/60228