Stack simulation for set-associative V/R-type caches

Efficient stack simulation has been successfully applied in the past on physically Indexed caches with physical (or real) tags to generate the number of misses and write backs for various cache configurations in a single run. In this paper, we devise a stack simulation algorithm for virtually Indexed caches with real tags (VjR-type caches). Using markers with a valid range for synonym lines, our algorithm is able to keep track of stack distances for various cache configurations. In addition to cache miss ratios and number of write backs, our algorithm reports pseudonym frequency for all cache configurations under investigation. A one-pass cache simulator based on our algorithm is developed and its results on sample traces are reported.