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