May 12 (Wed): "Benchmarking, Performance Analysis, and Domain-Specific Architectures for Graph Processing Applications," Abanti Basak, ECE PhD Defense

https://ucsb.zoom.us/j/86388833606

ABSTRACT:

Both static and streaming graph processing are central in data analytics scenarios such as recommendation systems, financial fraud detection, and social network analysis. The rich space of graph applications poses several challenges for the computer architecture community. First, standard static graph algorithm performance is sub-optimal on today’s general-purpose architectures such as CPUs due to inefficiencies in the memory subsystem. It is currently increasingly difficult to rely on relative compute/memory technology scaling for continued performance improvement for a given optimized static graph algorithm on a general-purpose CPU. Second, while a large body of research in the computer architecture community focuses on static graph workloads, streaming graphs remain completely unexplored. The primary practical barriers for computer architecture researchers toward studying streaming graphs are immature software, a lack of systematic software analysis, and an absence of open-source benchmarks. This dissertation seeks to solve these challenges for both static and streaming graph workloads through benchmarking, performance analysis, and CPU-centric domain-specific architectures using software/hardware co-design.

For static graph workloads, this thesis highlights novel performance bottleneck insights such as 1) the factors limiting memory-level parallelism, 2) the heterogeneous reuse distances of different application data types, and 3) the difference in the performance sensitivities of the different levels of the cache hierarchy. Guided by the workload characterization, a domain-specific prefetcher called DROPLET is proposed to solve the memory access bottleneck.

For streaming graph workloads, this thesis develops a performance analysis framework called SAGA-Bench and performs workload characterization at both the software and the architecture levels. The findings include 1) the performance limitation of the graph update phase, 2) the input-dependent software performance trade-offs in graph updates, and 3) the difference in the architecture resource utilization (core counts, memory bandwidth, and cache hierarchy) between the graph update and the graph compute phases. In addition, the thesis demonstrates that input knowledge-driven software and hardware co-design is critical to optimize the performance of streaming graph processing.

BIO:

Abanti Basak is a fifth year Ph.D. student at University of California, Santa Barbara working under the supervision of Professor Yuan Xie and Professor Yufei Ding. Her current research interests include benchmarking, performance analysis, and software/hardware co-design techniques for graph processing workloads.

Hosted by: Professor Yufei Ding

Submitted by: Abanti Basak <abasak@ucsb.edu>