*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
