Efficient stack distance computation for priority replacement policies
Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik · 2011
The concept of stack distance, applicable to the important class of inclusion replacement policies for the memory hierarchy, enables to efficiently compute the number of misses incurred on a given address trace, for all cache sizes. The concept was introduced by Mattson, Gecsei, Sluts, and Traiger (Evaluation techniques for storage hierarchies, IBM System Journal, (9)2:78-117, 1970), together with a Linear-Scan algorithm, which takes time O(V) per access, in the worst case, where V is the number of distinct (virtual) items referenced within the trace. While subsequent work has lowered the time bound to O(log V) per access in the special case of the Least Recently Used policy, no improvements have been obtained for the general case.