Empirical Study of Parallel LRU Simulation Algorithms

Eric Carr, David M. Nicol

Research output: Book/Report/Conference proceedingTechnical report

Abstract

This paper reports on the performance of five parallel algorithms for simulating a fully associative cache operating under the LRU (Least-Recently-Used) replacement policy. Three of the algorithms are SIMD, and are implemented on the MasPar MP-2 architecture. Two other algorithms are parallelizations of an efficient serial algorithm on the Intel Paragon. One SIMD algorithm is quite simple, but its cost is linear in the cache size. The two other SIMD SIMD algorithms compute all stack distances; the second SIMD algorithm is completely general, whereas the third SIMD algorithm presumes and takes advantage of bounds on the range of reference tags. Both MIMD algorithm implemented on the Paragon are general, and compute all stack distances; they differ in one step that may affect their respective scalability. We assess the strengths and weaknesses of these algorithms as a function of problem size and characteristics, and compare their performance on traces derived from execution of three SPEC benchmark programs.
Original languageEnglish (US)
Place of PublicationFt. Belvoir
PublisherDefense Technical Information Center
Number of pages16
StatePublished - Oct 1994
Externally publishedYes

Fingerprint

Dive into the research topics of 'Empirical Study of Parallel LRU Simulation Algorithms'. Together they form a unique fingerprint.

Cite this