  Increasing the speed of cache simulation to obtain hit/miss rates en- ables
performance estimation, cache exploration for embedded sys- tems and energy
estimation. Previously, such simulations, particu- larly exact approaches, have
been exclusively for caches which uti- lize the least recently used (LRU)
replacement policy. In this paper, we propose a new, fast and exact cache
simulation method for the First In First Out(FIFO) replacement policy. This
method, called DEW, is able to simulate multiple level 1 cache configurations
(dif- ferent set sizes, associativities, and block sizes) with FIFO replace-
ment policy. DEW utilizes a binomial tree based representation of cache
configurations and a novel searching method to speed up sim- ulation over
single cache simulators like Dinero IV. Depending on different cache block
sizes and benchmark applications, DEW oper- ates around 8 to 40 times faster
than Dinero IV. Dinero IV compares 2.17 to 19.42 times more cache ways than DEW
to determine accu- rate miss rates.
