UTCS AI Colloquia - Rupesh Nasre, UT ICES, "Morph Algorithms on GPUs," PAI 3.14

Contact Name: 
John Thywissen
PAI 3.14
Jan 28, 2013 12:00pm - 1:30pm

Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Talk Abstract: There is growing interest in using GPUs to accelerate graph algorithms such as breadth-first search, computing page-ranks, and finding shortest paths. However, these algorithms do not modify the graph structure, so their implementation is relatively easy compared to general graph algorithms like mesh generation and refinement, which morph the underlying graph in non-trivial ways by adding and removing nodes and edges. We know relatively little about how to implement morph algorithms efficiently on GPUs. We present and study four morph algorithms: (i) a computational geometry algorithm called Delaunay Mesh Refinement (DMR), (ii) an approximate SAT solver called Survey Propagation, (iii) a compiler analysis called Points-to Analysis, and (iv) Boruvka’s Minimum Spanning Tree algorithm. Each of these algorithms modifies the graph data structure in different ways and thus poses interesting challenges. We overcome these challenges using algorithmic and GPU-specific optimizations. We propose efficient techniques to perform concurrent subgraph addition, subgraph deletion, conflict detection and several optimizations to improve the scalability of morph algorithms. As an example, on an input mesh with 10 million triangles, our DMR code achieves an 80x speedup over the highly optimized serial Triangle program and a 2.3x speedup over a multicore implementation running with 48 threads. This work provides several insights into how other morph algorithms can be efficiently implemented on GPUs. 

This is a joint work with Martin Burtscher and Keshav Pingali, to be presented at PPoPP 2013.

Speaker Bio: Rupesh Nasre is a postdoctoral fellow at ICES. He received Ph.D. from Indian Institute of Science, Bangalore. His research interests include program parallelization and static program analysis.

He is the recipient of the NVIDIA special prize in Code For Science, a winner of the Yahoo! University Hack Day and holds five US patents.