Finding and Exploiting Parallelism in Irregular Applications

Event Date: April 22, 2009
Speaker: Milind Kulkarni
Speaker Affiliation: University of Texas at Austin
Sponsor: ECE Faculty Candidate
Computer Engineering
Time: 2:00 PM
Location: MSEE 239
Contact Name: Professor Sam Midkiff
Open To: Acceptable for ECE694A

With the advent of multicore processors, the challenge of increasing program performance has become one of parallelization. While much research over the past three decades has focused on parallelizing dense-array and matrix programs, far less attention has been paid to irregular programs, which operate over pointer-based data structures such as trees and graphs, where traditional approaches have largely failed to uncover significant amounts of parallelism. In this talk, I will show that irregular programs do, indeed, have large amounts of parallelism, and that this type of parallelism, which I call "amorphous data-parallelism," can be exploited efficiently and easily. 

I will describe the Galois system, which uses high-level abstractions to expose amorphous data-parallelism in sequential irregular programs, and uses semantic properties of these programs to perform automatic parallelization. I will then present a number of optimizations which allow programmers to exploit locality in pointer-based data structures to improve scalability and reduce overheads. I will show that the Galois approach is able to extract significant amounts of parallelism from amorphous data-parallel programs with little programmer effort.




Milind Kulkarni is a Postdoctoral Research Associate at the Institute for Computational Engineering and Sciences at the University of Texas at Austin. His research focuses on developing language features, compiler techniques and runtime systems that can be used to easily and efficiently parallelize applications for multicore processors. He received his Ph.D. in Computer Science from Cornell University in 2008, where he worked with Keshav Pingali.