Dynamic Page Mapping Policies for Cache Conflict Resolution on Standard Hardware

Theodore H. Romer, Dennis Lee, Brian N. Bershad
Department of Computer Science and Engineering, University of Washington
Seattle, WA 98195
{romer, dlee, bershad}@cs.washington.edu

J. Bradley Chen
Division of Applied Sciences, Harvard University
29 Oxford Street
Cambridge, MA 02138
bchen@das.harvard.edu

Abstract

In computer systems with large, physically-indexed, direct-mapped caches, a poor mapping from virtual to physical pages causes excessive cache conflict misses. In a previous paper we proposed a simple hardware device, the Cache Miss Lookaside Buffer, which identifies pages that are suffering from conflict misses. The operating system can use this information to implement a dynamic page page mapping policy that resolves conflicts by performing an in-memory copy of one of the conflicting pages, and updating the virtual to physical mapping. In this paper, we propose several dynamic page mapping policies that detect and resolve cache conflicts using hardware available in existing systems, such as a TLB and cache miss counter, to locate possible cache conflicts. We evaluate the simulated performance of a variety of mapping policies, and show that a dynamic page mapping policy using standard hardware can improve upon the performance of a static policy, but is not as effective as special-purpose hardware such as an associative cache or a CML buffer. We also describe the implementation and performance of a software-based dynamic policy on a DEC Alpha workstation running DEC OSF/1.