language: en

[Appears in "Proceedings of the First Symposium on Operating Systems Design and Implementation," Usenix Association, November 1994.]

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
{fromer,dlee,bershadg}@cs.washington.edu
J. Bradley Chen
Division of Applied Sciences
29 Oxford Street
Harvard University
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 (CML) Buffer, which identifies pages that are suffering from conflict misses. The operating system can use this information to implement a dynamic page mapping policy that resolves conflicts by performing an in-memory copy of one of the conflicting pages, and updating the virtual to physical mappings. 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.

1 Introduction