Seminar by Rupesh Nasre
Irregular algorithms on GPUs
Rupesh Nasre
Univ. of Texas at Austin
Date: Tuesday, February 19th, 2013
Time: 3PM
Venue: CS101.Abstract:
I will present parallelization techniques for irregular algorithms on graphics processing units (GPUs). Programs with unpredictable control-flow or data-access patterns are termed irregular. Graph algorithms such as the shortest paths computation, approximate n-body simulation and mesh refinement are a few examples of irregular algorithms. Unlike regular algorithms like matrix multiplication, irregular algorithms are relatively difficult to parallelize, since static analysis techniques fail to capture the unstructured access patterns that are input dependent. The challenge of scalable parallelization of such irregular algorithms is further exacerbated in the presence of massive multithreading such as that on the GPUs. In fact, until recently, it was unclear how to parallelize irregular algorithms. Therefore, we devised a set of parallelization principles for irregular algorithms on GPUs. Extending these principles, I will illustrate how to parallelize serveral morph algorithms wherein the underlying graph itself gets modified, e.g., in mesh refinement. Finally, I will briefly discuss how to synthesize such GPU programs from a higher level specification.