Optimizing Program Locality Using Hot Data Streams

Thursday May 18, 2006
Hamerschlag Hall D-210
4:00 pm

Trishul Chilimbi
Microsoft Research

We describe hot data streams, which are sequences of data accesses that frequently repeat in the same order, and show that they can be computed efficiently. We describe and evaluate three techniques that use these hot data streams to improve a program's cache performance. First, we show that cache-conscious coallocation of a hot data stream can be achieved by isolating and combining allocation sites of object instances that appear in the stream such that intervening allocations from other sites are separated.

Second, we describe a garbage collected system that uses hot data streams to perform data reorganization. We piggyback data reorganization on top of copying garbage collection but show that larger benefits are obtained when data reorganization is triggered independently of normal garbage collection.

Finally, we describe a dynamic software prefetching scheme that detects and prefetches hot data streams.

Trishul Chilimbi is a researcher at Microsoft Research, where he leads the Runtime Analysis and Design research group. His research interests include programming languages, compilers, runtime systems, and computer architecture. He has worked extensively on improving memory system performance and has founded an ACM workshop on this topic. He currently works on applying runtime technologies to improve software performance, reliability, and security. He received his Ph.D. from the University of Wisconsin-Madison.