efficient stack distance computation for priority replacement policies
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. This work introduces a class of inclusion policies called policies with nearly static priorities , which encompasses several of the policies considered in the literature. The Min-Tree algorithm is proposed for these policies. The performance of the Min-Tree algorithm is very sensitive to the replacement policy as well as to the address trace. Under suitable probabilistic assumptions, the expected time per access is O (log 2 V ). Experimental evidence collected on a mix of benchmarks shows that the Min-Tree algorithm is significantly faster than Linear-Scan, for interesting policies such as OPT (or Belady), Least Frequently Used (LFU), and Most Recently Used (MRU). As a further advantage, Min-Tree can be parallelized to run in time O (log V ) using O ( V /log V ) processors, in the worst case. A more sophisticated Lazy Min-Tree algorithm is also developed which achieves O (? log V ) worst-case time per access. This bound applies, in particular, to the policies OPT, LFU, and Least Recently/Frequently Used (LRFU), for which the best previously known bound was O ( V ).
optimal page replacement