Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Automatically enhancing locality in irregular applications

Speaker  Milind Kulkarni

Affiliation  Purdue University

Host  Kathryn McKinley

Duration  01:14:24

Date recorded  9 May 2013

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.

©2013 Microsoft Corporation. All rights reserved.
> Automatically enhancing locality in irregular applications