By: Professor Milind Kulkarni

University of Texas at Austin

Date: Thursday, February 26, 2009

Time: 11:00pm-12:00pm

Location: Klaus 1456

For more information please contact: Dr. Rich Vuduc; richie@cc.gatech.edu

 
"The Galois System: Parallelizing Irregular Applications"

Abstract:  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.

http://users.ices.utexas.edu/~milind/

~~~~~~~~~~~~~~~~~~

You are cordially invited to attend a reception that will follow the seminar to chat informally with faculty and students. Refreshments will be provided.