SET-ASSOCIATIVE CACHE SIMULATION USING GENERALIZED BINOMIAL TREES

Set-associative caches are widely used in CPU memory hierarchies, I/O subsystems, and file systems to reduce average access times. This arti cle 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 a nd varying number of sets. The article also introduces a generalizatio n of the ordinary binomial tree and presents a representation of cache s in this class using the Generalized Binomial Tree (gbt). The tree re presentation permits efficient search and update of the caches. Theore tically, 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 SP EC benchmarks. A related algorithm for simulating multiple alternative direct-mapped caches with fixed cache size, but varying line size, is also presented.