Efficient Generation of Memory Reference Strings Based on the LRU Stack Model of Program Behaviour

We consider the problem of generating memory reference strings that are to be used instead of real program address traces with the generator based on the Least-Recently-Used Stack Model (LRUSM) of program behaviour. A method to transform the stack distance probability mass function that drives the generator is proposed which results in memory reference strings that are a fraction of theoriginal string length while preserving most of its essential performance characteristics. The reduced string can be processed in much the same way as the original string for virtual memory studies that deal with memory sizes greater than $k$, the parameter of the transformation