Parallel trace-driven cache simulation by time partitioning

Abstract

The authors describe a technique for performing parallel simulation of a trace of address references for the purpose of evaluating different cache structures. One way to achieve fast parallel simulation is to simulate the individual independent sets of a cache concurrently on different computers, but this technique is not efficient in a statistical sense because of a high correlation of the activity between different sets. Only a small fraction of the sets should actually be simulated. To put parallelism to effective use, a trace of the sets to be simulated can be partitioned into disjoint time intervals, and each interval can be simulated concurrently. Because the contents of the cache are unknown at the start of the time intervals, this parallel simulation does not produce the correct counts of cache hits and misses. However, after simulating the trace in parallel, a small amount of resimulation can produce the correct counts. The resimulation effort required is proportional to the size of the cache simulated and not to the length of the trace.