Parallel Performance Project Research Paper

Research Paper

Efficient Simulation of Multiple Cache Configurations using Binomial Trees
Rabin A. Sugumar and Santosh G. Abraham
Technical Report CSE-TR-111-91, University of Michigan, 91.

Abstract

Simulation time is often the bottleneck in the cache design process. In this paper, algorithms for the efficient simulation of direct mapped and set associative caches are presented. Two classes of direct mapped caches are considered: fixed line size caches and fixed size caches. A binomial tree representation of the caches in each class is introduced. The fixed line size class is considered for set associative caches. A generalization of the binomial tree data structure is introduced and the fixed line size class of set associative caches is represented using the generalized binomial tree. Algorithms are developed that use the data structures to determine miss ratios for the caches in each class. Analytical and empirical comparisons of the algorithms to previously published algorithms such as all-associativity and forest simulation are presented. Analytically it is shown that the new algorithms always perform better than earlier algorithms. Empirically, the new algorithms are shown to outperform earlier ones by factors of 1.0 to 5.0.