-
Understanding and Improving Graph Algorithm Performance
Wed, May 11, 2016 @ 10:30 AM - 11:30 AM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
Speaker: Mr. Scott Beamer, Computer Architecture PhD Candidate/UC Berkeley
Talk Title: Understanding and Improving Graph Algorithm Performance
Abstract: Graph processing is experiencing a renewed surge of interest as applications grow in importance in social networks analysis, recognition and the sciences. Unfortunately, graph algorithms often execute inefficiently on today's hardware platforms. In particular, graph algorithms are often able to simultaneously underutilize a platform's compute throughput and memory bandwidth.
In this talk, I will describe my work to identify these hardware bottlenecks and their causes. By understanding the main factors for graph algorithm performance, we can design hardware better suited for graph algorithms or improve graph algorithm software implementations. Through our characterization work, we find that contrary to the notion that graph algorithms have a random memory access pattern, we find well-tuned parallel graph codes exhibit substantial locality and thus experience a moderately high cache hit rate.
To understand these graph processing bottlenecks and the solutions to them requires a vertically integrated approach, ranging from algorithms with a novel breadth-first search algorithm to architecture with a detailed graph workload characterization. In between, this includes a graph domain-specific language, a performance model, and a benchmark suite. I will conclude the talk with our recent work on reducing memory communication via an algorithmic transformation.
Biography: Scott Beamer is a Computer Architecture PhD candidate at UC Berkeley advised by Krste Asanovic and David Patterson. He is currently investigating how to accelerate graph algorithms through software optimization and hardware specialization. In the past, he looked into how to best use monolithically integrated silicon photonics to create memory interconnects. He received a B.S. in Electrical Engineering and Computer Science and a M.S. in Computer Science, both from UC Berkeley.
Host: Professor Sandeep K. Gupta
Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: Mayumi Thrasher
