Approximate time-parallel cache simulation

In time-parallel simulation, the simulation time axis is decomposed into a number of slices, which are assigned to parallel processes for concurrent simulation. Although a promising parallelization technique, it is difficult to be applied. Recently, using approximation with time-parallel simulation has been proposed to extend the class of suitable models and to improve the performance of existing models. In trace-driven cache simulation, sequences of memory requests are processed to determine the performance of variously sized caches. Time-parallel simulation has been applied to trace-driven cache simulation, but only with limited scalability of the parallel algorithm. In order to solve the scaling problem, this work uses approximation with time-parallel cache simulation. Although introducing an uncertainty in the results, the approximate algorithms work in a way that result accuracy increases monotonically with time, allowing direct control of the quality of results. Experiments with a prototypical implementation indicate the viability of this approach.