ANOMALIES AND ADAPTATION IN THE ANALYSIS AND DEVELOPMENT OF PREPAGINGPOLICIES

In ''Analysis and Development of Demand Prepaging Policies,'' Horspool and Huberman (1987) showed that it is possible to design prefetching memory policies that preserve a ''stack'' inclusion property, much lik e least recently used ordering, allowing them to simulate these polici es for all sizes of memory in a single pass through a reference trace. We believe that the details of Horspool and Huberman's algorithms int roduce unexpected anomalous properties, however. In particular, their policies are not properly timescale relative: events that occur on a t imescale that should only matter to some sizes of memory, adversely af fect replacement decisions for memories of very different sizes. Sligh t changes to the algorithms can restore timescale relativity and make them much better behaved. In addition, we would like to point out that Horspool and Huberman's algorithms actually simulate adaptive policie s, which may explain some of their unexpectedly positive results. This view suggests that properly timescale-relative inclusion-preserving p olicies can be used to systematically evaluate adaptive memory managem ent schemes.