Link to CALCM Home  

Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality

Author: Trishul Chilimbi, Microsoft Research

March 26, 2002 Tuesday
Hamerschlag Hall 1112
4:00 p.m.

Thomas Wenisch

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 Streams".

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.


Department of Electrical and Computer EngineeringCarnegie Mellon UniversitySchool of Computer Science