Trishul Chilimbi Talk (PL seminar)

[Shai Rubin <shai@xxxxxxxxxxx>]

All,
Sorry for the late notice, but we are fortunate to have two talks in the
PL seminar this week.
This talk is scheduled for tomorrow, we have another one on Thursday.
More details: 
  http://www.cs.wisc.edu/areas/pl/

-----------------------------------------------------------------------
Speaker:   Trishul Chilimbi
           Measurement and Performance Group
           Programmer Productivity Research Center
           Microsoft Research

Date  :    Wednesday Oct. 18
Place :    101 Psychology
Time  :    3:00-4:00
 
The Daedalus Project -- Exposing and Exploiting Data Reference Locality
-----------------------------------------------------------------------
	With the growing processor-memory performance gap, understanding and
optimizing a program's cache performance is becoming increasingly important.
While optimization technology for improving instruction cache performance is
mature, data cache optimization techniques are at an early stage. We believe
the primary reason for this imbalance is the lack of a suitable
representation for a program's dynamic data reference behavior. Unlike
control flow graphs and program paths, which are a convenient and compact
abstraction of a program's control flow, no corresponding analogue exists
for a program's data accesses.

	In this talk I will describe the Daedalus project. The goal of the
Daedalus project is to build a framework for optimizing a program's data
cache performance.  At the core of this framework are two representations of
a program's dynamic data reference behavior--Hot Program Data Accesses
(HPDA) and Hot Data Access Graphs (HDAG)--and an abstraction of a temporal
sequence of data accesses called a Hot Data Block (HDB). As I will discuss
in the talk, these representations are compact (three to four orders of
magnitude smaller than the program's data reference trace) and permit
efficient analyses (in the order of seconds to a few minutes) even for large
and complex commercial applications. Applying this framework to several
SPECint 2000 benchmarks and a commercial MS application, indicates that 90%
of program references are attributable to a small number of hot data blocks
(60--80,000). In most cases, these hot data blocks contain only 1--2% of all
program data addresses. The hot data blocks are small, containing 10--25
objects, and are repeated very frequently making them an attractive target
for data locality optimizations. Finally, the hot data blocks occupy 1.5--3
times the number of cache lines that an "optimal" data layout would require
indicating that data locality optimizations offer potentially significant
cache performance improvements. Current and future research will focus on
using the HPDA and HDAG representations, and the hot data block abstraction,
to drive data locality optimizations.