dress) traces and a (cache) simulator. A trace is the log of a dynamic series of memory references, recorded during the execution of a program or workload. The information recorded for each reference must include the address of the reference and may include the reference's type (instruction fetch, data read, or data write), length, and other information. A simulator is a program that accepts a trace and parameters that describe one or more caches, mimics the behavior of those caches in response to the trace, and computes performance metrics (e.g., miss ratio) for each cache. We analyze associativity in caches with trace-driven simulation for the same reasons as are discussed in [28]. The principal advantage of trace-driven simulation over random number driven simulation or analytical modeling is that there exists no generally-accepted model for program behavior (at the cache level) with demonstrated validity and predictive power. The major disadvantage is that workload samples must be relatively short, due to disk space and simulation time limits. The CPU time required to simulate many alternative caches with many traces can be enormous. Mattson et al. [I91 addressed a similar problem for virtual memory simulation by developing a technique we call stack simulation, which allows miss ratios for all memory sizes to be computed simultaneously, during one pass through the address trace, subject to several constraints including a fixed page size. While stack simulation can be applied to caches, each cache configuration with a different number of sets requires a separate simulation. For this reason, this paper first examines better algorithms for simulating alternative direct-mapped and set-associative caches, and then uses those algorithms to study associativity in caches. The rest of this paper is organized as follows. Section I1 reviews previous work on cache simulation algorithms and associativity in caches. In Section 111, we explain our methods in more detail and describe our traces. Section IV discusses cache simulation algorithms, including properties that facilitate rapid simulation, a new algorithm for simulating alternative direct-mapped caches, and an extension to an algorithm for simulating alternative caches with arbitrary setmapping functions. Section V examines the effect of associativity on miss ratio, including categorizing the cause of misses in set-associative caches, relating set-associative miss ratios to fully-associative ones, comparing miss ratios from similar set-associative caches, and extending the design target miss ratios from [28] and [30] to caches with reduced associativity. Readers interested in the effect of associativity on miss ratio but not in cache simulation algorithms may skip Section IV, as Section V is written to stand alone. II. RELATED WORK The original paper on memory hierarchy simulation is by Mattson et al. [19]. They introduce inclusion, show when inclusion holds, and develop stack simulation, which uses inclusion to rapidly simulate alternative caches. Inclusion is the property that after any series of references, larger alternative caches always contain a superset of the blocks in smaller alternative caches.' Mattson et al. show inclusion holds between alternative caches that have the same block size, do no prefetching , use the same set-mapping function (and therefore have the same number of sets), and use replacement algorithms that before each reference induce a total priority ordering on all previously referenced blocks (that map to each set) and use only this priority ordering to make the next replacement decision. Replacement algorithms which meet the above condition, called stack algorithms, include LRU, OPTIMUM, and (if properly defined) RANDOM [6]. FIFO does not qualify since cache capacity affects a block's replacement priority. In Section IV-A, we will prove when inclusion holds for caches that use arbitrary set-mapping functions and LRU replacement. Mattson et al. develop stack simulation to simulate alternative caches that have the same block size, do no prefetching, use the same set-mapping function, and use a stack replacement algorithm. Since inclusion holds, a single list per set, called a stack, can be used to represent caches of all associatives, with the first n elements of each stack representing the blocks in an n-way set-associative cache. For each reference, stack simulation performs three operations: 1) locate the reference in the stack, 2) update one or more metrics to indicate which caches contained the reference, and 3) update the stack to reflect the contents of the caches after the reference. We ' Inclusion is different from multilevel inclusion defined by Baer and Wang [ 5 ] . While inclusion is a property relating alternative caches, multilevel inclusion relates caches in the same cache hierarchy.
Hill and Smith REF investigate the effect of associativity on the miss ratio.
Evaluating Associativity in CPU Caches
IEEE Trans. Computers
IEEE Trans. Computers
Computer Science