Set-associative cache simulation using generalized binomial trees

Reviewer: Mircea Raducu Stan

Caches are used to decrease average access times in CPU memory hierarchies, file systems, and so on. The performance of a cache under a given workload is determined by three parameters: cache size, line size, and degree of associativity. The current wisdom for choosing an optimal set of cache parameters is to simulate various cache configurations on address traces of representative workloads (such as the SPEC89 suite). Cache simulation is time-intensive, so several methods are used to reduce simulation time: reduced-trace simulation, parallel simulation, and single-pass simulation. The authors propose two efficient single-pass simulation techniques. The first algorithm uses generalized binomial trees to simulate in a single pass a group of set-associative caches with the same line size but varying numbers of sets and varying associativity. The second, related algorithm can be used for simulating in a single pass a group of direct-mapped caches with fixed size but varying line sizes. Part 1, “Introduction,” and part 2, “Related Work,” present a good review of previous work on single-step set-associative cache simulation, with emphasis on the AA (all-associativity) and FS+ (forest simulation) algorithms. Part 3, “Set-associative Cache Simulation,” lays the theoretical foundation for single-step cache simulation, introduces the concepts of generalized binomial tree and forest with their properties, and then presents the main GBF-LS (generalized binomial forest—fixed line size) algorithm. The authors show that the new algorithm is always more efficient than the AA and FS+ algorithms. Part 4, “Direct-mapped Caches,” presents a related single-step algorithm for direct-mapped caches with varying line sizes, and part 5, “Empirical Performance Evaluations,” shows experimental comparisons between the new and previously proposed algorithms. The appendix gives formal definitions for generalized binomial trees and proves some of their properties. Anyone involved in cache simulation will find this paper useful, especially since the single-step simulation techniques described here can be used with reduced-trace and parallel simulation for maximum efficiency.