Paper Info
Title
A fully associative software-managed cache design
Abstract
As DRAM access latencies approach a thousand instruction-execution times and on-chip caches grow to multiple megabytes, it is not clear that conventional cache structures continue to be appropriate. Two key features—full associativity and software management—have been used successfully in the virtual-memory domain to cope with disk access latencies. Future systems will need to employ similar techniques to deal with DRAM latencies. This paper presents a practical, fully associative, software-managed secondary cache system that provides performance competitive with or superior to traditional caches without OS or application involvement. We see this structure as the first step toward OS- and application-aware management of large on-chip caches.This paper has two primary contributions: a practical design for a fully associative memory structure, the indirect index cache (IIC), and a novel replacement algorithm, generational replacement, that is specifically designed to work with the IIC. We analyze the behavior of an IIC with generational replacement as a drop-in, transparent substitute for a conventional secondary cache. We achieve miss rate reductions from 8% to 85% relative to a 4-way associative LRU organization, matching or beating a (practically infeasible) fully associative true LRU cache. Incorporating these miss rates into a rudimentary timing model indicates that the IIC/generational replacement cache could be competitive with a conventional cache at today's DRAM latencies, and will outperform a conventional cache as these CPU-relative latencies grow.
Year
DOI
Venue
2000
10.1145/342001.339660
international symposium on computer architecture
Keywords
Field
DocType
on-chip cache,large on-chip cache,conventional cache structure,conventional cache,indirect index cache,dram latency,associative true lru cache,conventional secondary cache,generational replacement cache,generational replacement,associative software-managed cache design,compiler optimizations,computer science,virtual memory,application software,associative memory,chip,indexation,algorithm design and analysis,aging,computer architecture
Cache invalidation,Cache pollution,Cache,Computer science,CPU cache,Parallel computing,Page cache,Real-time computing,Cache algorithms,Cache coloring,Smart Cache,Operating system
Conference
Volume
Issue
ISSN
28
2
0163-5964
ISBN
Citations 
PageRank 
1-58113-232-8
79
8.10
References 
Authors
13
2
Name
Order
Citations
PageRank
Erik G. Hallnor114611.44
Steven K. Reinhardt23885226.69