Local Context Matching for Page Replacement

In this paper we investigate the application of adaptive sequence prediction techniques the problem of page replacement in computer systems. We demonstrate the ability of a method based on local context-matching to substantially outperform well-known existing alternatives (such as least recently used, or LRU) in terms of minimizing page faults for common UNIX programs. Page traces track the sequences of memory addresses made by a program into its (paged) virtual memory space. We show that it is possible to characterize these types of sequences eÆciently using only local information. This local characterization translates into the ability to achieve high prediction accuracy on these sequences motivating the new paging algorithm. The method empirically outperforms LRU with reductions of up to 70% in page faults in terms of reducing the gap between LRU and the optimal oine strategy. Trace no. Program name Version No. of Distinct Pages 1-6 gnuplot 3.50.1.17 85 7-12 latex C 3.14t3 80 13-..