Login
Computer Science @ Rochester
Monday, May 12, 2003
11:00 AM
CSB 209
Ph.D. Thesis Proposal
Yutao Zhong
University of Rochester
Program Locality Study through Reuse Distance Analysis
As the speed gap between CPU and memory widens, cache performance increasingly determines performance, cost and power consumption of computer systems. The efficiency of caching depends on program locality, or the pattern of data reuse. It is therefore important to understand the fundamental memory reference behavior of programs.

We use reuse distance (originally called LRU stack distance) as a metric of program locality. Unique properties of reuse distance make it possible to compare data access pattern in different program executions. By selective run-time monitoring and efficient reuse distance measurement, we can analyze memory reference pattern of part or whole programs in different granularity. Preliminary results show that reuse distance analysis can predict whole-program locality through profiling. This analysis can then be used to estimate cache miss rate for all data inputs of a program.

We propose to further develop reuse distance analysis in depth and width. We will divide program data into subgroups based on group locality. Clustering will be applied based on the access pattern of individual elements. By measuring reuse distance distribution for different cache line sizes, we will estimate spatial locality. Based on program locality, we plan to study new techniques in memory benchmark design and cache-sensitive job scheduling. We will show that reuse distance analysis can improve the effectiveness in program understanding, optimization and scheduling.