Automatically enhancing locality in irregular applications

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 particular 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.

Speaker Details

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 2012 recipient of the NSF CAREER award. He is a member of the ACM and the IEEE Computer Society.

Date:
Speakers:
Milind Kulkarni
Affiliation:
Purdue University
    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks