"Automatically Enhancing Locality in Irregular Applications" - MIlind Kulkarni, Purdue University - Thursday, September 29, 4pm CST

"Automatically Enhancing Locality in Irregular Applications" - MIlind Kulkarni, Purdue University - Thursday, September 29, 4pm CST

Illinois-Intel Parallelism Center (I2PC) Distinguished Speaker Series

Thursday September 29, 4pm CST

Over the past several decades of compiler research, there have been great successes in automatically enhancing locality for regular programs, which operate over dense matrices and arrays. Tackling locality in irregular programs, which operate over pointer-based data structures such as trees and graphs, has been much harder, and has mostly been left to ad hoc, application specific methods. In this talk, I will describe efforts by my group to automatically improve locality in a broad class of irregular applications, those that traverse trees. The key insight behind our approach is an abstraction of data structure traversals as operations on vectors. This abstraction lets us design transformations, predict their behavior and determine their correctness.

I will present two specific transformations we are developing, "point blocking"

and "traversal splicing," and show that they can deliver substantial performance improvements when applied to several real-world irregular kernels.



Milind Kulkarni is an assistant professor in the School of Electrical and Computer Engineering at Purdue University. His research focuses on developing languages, compilers and systems that can be used to harness the power of emerging, complex computation platforms. Before joining Purdue, he was a postdoctoral research associate at the University of Texas at Austin from May 2008 to August 2009. He received his Ph.D. in Computer Science from Cornell University in 2008. Prior to that, he received his M.S. in Computer Science from Cornell University in 2005, and BS degrees in Computer Science and Computer Engineering from North Carolina State University in 2002. While at Cornell, he was a Department of Energy High Performance Computer Science

(HPCS) Fellow from 2004 to 2008. He is a member of the ACM and the IEEE Computer Society.


I2PC seminars are held on Thursdays at 4pm CST in Room 3405 of the Siebel Center, at the University of Illinois.

They are streamed live at this link accessible from Intel:

* http://media.cs.illinois.edu/live/I2PClive.asx

Questions to the speaker for live response can be posted from Intel at:

* http://i2pc.web.cs.illinois.edu/chat

The video from the last seminar is in:

* http://media.cs.illinois.edu/DCS/research/I2PC/2011-09-22.asx


Josep Torrellas

I2PC Director

University of Illinois

1 post / 0 new
For more complete information about compiler optimizations, see our Optimization Notice.