Working Sets at Function Level

The trend in computer architecture is that of an increasing gap between rapidly increasing processor speeds and the relatively slower memory subsystems. Program locality has played a crucial role in engineering economically viable computer systems. While program locality has been studied and exploited at different levels of memory hierarchy, including the cache, block and page levels, there has been little or no effort to study locality at the level of functions and to leverage it. In this paper we show that there is a strong correlation between current function references and those in the immediate future, whereas, those in the distant future tend to be more or less uncorrelated. In particular we show that an average working set (WS) size of 20% of the program size in terms of number of functions is sufficient, in all cases, to ensure a miss rate of less than 2%. Moreover, we also observe that in most cases a WS of half that size is good enough to ensure similar low miss rates. We also compare two different kinds of WSs -- fixed size maintained by LRU and variable size based on a WS parameter -- and show that the variable size WS consistently performs better. Finally we present a novel way of exploiting the locality at function level.Technical report DCS-TR-48