Title: Mapping Parallel Graph Algorithms to Throughput-Oriented Architectures

Adam McLaughlin

Ph.D. Candidate

School of Electrical and Computer Engineering College of Engineering Georgia Institute of Technology adam27x@gatech.edu http://users.ece.gatech.edu/~amclaughlin7/

Date: Tuesday, September 22nd, 2015

Time: 12:30pm-2pm

Location: Klaus Advanced Computing Building (KACB) 1212

Committee

--------------

Dr. David Bader (Advisor, School of Computational Science and Engineering, Georgia Institute of Technology; Adjunct, School of Electrical and Computer Engineering, Georgia Institute of Technology) Dr. Sudhakar Yalamanchili (School of Electrical and Computer Engineering, Georgia Institute of Technology) Dr. Aaron Lanterman (School of Electrical and Computer Engineering, Georgia Institute of Technology) Dr. Richard Vuduc (School of Computational Science and Engineering, Georgia Institute of Technology) Dr. Mark Clements (School of Electrical and Computer Engineering, Georgia Institute of Technology)

Abstract

------------

The stagnant performance of single core processors, increasing size of data sets, and variety of structure in information has made the domain of parallel and high-performance computing especially crucial. Graphics Processing Units (GPUs) have recently become an exciting alternative to traditional CPU architectures for applications in this domain. Although GPUs are designed for rendering graphics, research has found that the GPU architecture is well-suited to algorithms that search and analyze unstructured, graph-based data, offering up to an order of magnitude greater memory bandwidth over their CPU counterparts.

This thesis focuses on GPU graph analysis from the perspective that algorithms should be efficient on as many classes of graphs as possible, rather than being specialized to a specific class, such as social networks or road networks. Using betweenness centrality, a popular analytic used to find prominent entities of a network, as a motivating example, we show how parallelism, distributed computing, hybrid and on-line algorithms, and dynamic algorithms can all contribute to substantial improvements in the performance and energy-efficiency of these computations. We further generalize this approach and provide an abstraction that can be applied to a whole class of graph algorithms that require many simultaneous breadth-first searches. Finally, to show that our findings can be applied in real-world scenarios, we apply these techniques to the problem of verifying that a multiprocessor complies with its memory consistency model.