The stack growth function: cache line reference models

To model cache behavior in a multiprogramming environment, it is necessary to know the number of distinct lines referenced in an execution interval. The stack growth function (SGF) relates the mean number of references (or instructions) to the number of distinct lines referenced; it can be viewed as the inverse function of the mean working set size. A fast, one-pass algorithm to compute the SGF for a given referenced string is presented. SGFs measured for some 40 real programs show that a simple exponential model fits the SGFs reasonably well over a range of execution intervals. Parameters of the inverse exponential model are presented for several program mixes and cache line sizes of 32 and 64 bytes. Separate instruction and data SGFs also are examined, and execution interval distribution effects are considered