and Abstractions for Quantifying and Exploiting Data Reference Locality
Chilimbi, Microsoft Research
March 26, 2002 Tuesday
Hamerschlag Hall 1112
Ph.D. Student, Department of ECE, Carnegine Mellon
In this paper, Trishul Chilimbi presents new metrics for
quantatatively analyzing the amount of spatial and temporal
reference locality inherent in an algorithm, and realized
in a particular mapping of an algorithm's data references
to memory locations. Moreover, Chilimbi proposes a fundamental
abstraction and new data structures for capturing and analyzing
data reference behaviour. "Hot Data Streams" are regular
and repeated data reference streams, which cover 90% of
the total references issued by a program. Using this abstraction
as a basis, Chilimbi constructs "Stream Flow Graphs". A
stream flow graph is a weighted directed acyclic graph which
shows which hot data streams are followed by which other
hot data streams in a trace of an application's data references.
The weights on the graph edges show the frequency of occurence
of the relationship between consecutive streams. This data
structure is analogous to a weighted control flow graph.
Chilimbi proposes that analyses currently used on control
flow graphs can be used on these stream flow graphs to guide
compiler optimizations for data reference behaviour.
In this talk I present Chilimbi's work, and open a discussion
on how Chilimbi's results can help us to design hardware
to better exploit data reference behaviors like "Hot Data
Tom Wenisch is a first year PhD student
in ECE under Babak Falsafi. Tom's interests include instruction/thread
level parallelism, memory system design, and performance evaluation
methodology. Nowadays, Tom spends most of his time hacking an out-of-order
processor simulator around Virtutech's Simics simulation infrastructure.