Achieving Linear Speedup in Parallel LRU Cache Simulation.
Tobias Kiesling · 2004
Previous work on simulation of LRU caching led to the development of parallel algorithms that are efficient for small numbers of processors. However, these algorithms exhibit a sub-linear speedup, where the efficiency seriously decreases with a higher number of processors. In order to achieve linear speedup, this work proposes the use of approximation techniques with the existing parallelization approaches. The nature of the approximate algorithm allows direct control of the introduced error, which can be used to achieve reasonable speedup with a minimal error. 1