A Study of Program Behavior to Establish Temporal Locality at the Function Level

The trend in computer architecture is that processor speeds are increasing rapidly compared to memory access times and the relatively stagnant disk speed. Computer software, on the other hand is characterized by growing program sizes and sophisticated functionality. The combination of these factors has resulted in a processor memory bottleneck, which is worsening with time. While program behavior has been studied at page level and cache level and the locality at page, cache and block levels has been exploited, there has been comparatively much lesser amount of work to exploit locality at the level of functions, and no prior work to study program behavior at this level. In this paper we show that there is a considerable amount of temporal locality at the level of functions. In particular we show that a working set of functions containing 40% of all the programs functions results in a miss rate of less than 2%. Moreover, we observe that, in almost all cases, even working sets having half as many functions result in similar low miss rates. Our experiments indicate that program execution is characterized by a working set of functions which changes with time and a thrashing like phenomenon results when the function footprint is not resident in memory.Technical report DCS-TR-47