Name
Abstract | ||
|---|---|---|
Set-associative caches are widely used in CPU memory hierarchies, I/O subsystems, and file systems to reduce average access times. This article proposes an efficient simulation technique for simulating a group of set-associative caches in a single pass through the address trace, where all caches have the same line size but varying associativities and varying number of sets. The article also introduces a generalization of the ordinary binomial tree and presents a representation of caches in this class using the Generalized Binomial Tree (gbt). The tree representation permits efficient search and update of the caches. Theoretically, the new algorithm, GBF_LS, based on the gbt structure, always takes fewer comparisons than the two earlier algorithms for the same class of caches: all-associativity and generalized forest simulation. Experimentally, the new algorithm shows performance gains in the range of 1.2 to 3.8 over the earlier algorithms on address traces of the SPEC benchmarks. A related algorithm for simulating multiple alternative direct-mapped caches with fixed cache size, but varying line size, is also presented. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1145/200912.200918 | ACM Trans. Comput. Syst. |
Keywords | Field | DocType |
varying number,trace-driven simulation,cache modeling,all-associativity simulation,set-associative cache,new algorithm,varying line size,single-pass simulation,binomial tree,line size,inclusion properties,related algorithm,set-associative caches,generalized binomial tree,set-associative cache simulation,earlier algorithm,varying associativities,address trace,fixed cache size | Binomial distribution,Binomial options pricing model,Associative property,Content-addressable memory,Computer science,Cache,CPU cache,Parallel computing,Algorithm,Circuit design,Spec# | Journal |
Volume | Issue | ISSN |
13 | 1 | 0734-2071 |
Citations | PageRank | References |
36 | 3.49 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rabin A. Sugumar | 1 | 211 | 68.51 |
| Santosh G. Abraham | 2 | 762 | 124.08 |