Accession Number:

ADA289706

Title:

Empirical Study of Parallel LRU Simulation Algorithms.

Descriptive Note:

Contractor rept.,

Corporate Author:

INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s):

• Carr, Eric
• Nicol, David M.

Report Date:

1994-10-01

Pagination or Media Count:

16.0

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.

Descriptors:

• *ALGORITHMS
• *PARALLEL PROCESSING
• *DATA STORAGE SYSTEMS
• *ASSOCIATIVE PROCESSING
• COMPUTERIZED SIMULATION
• POLICIES
• SIZES(DIMENSIONS)
• COSTS
• STANDARDS
• GEOMETRY
• REPLACEMENT
• STACKING
• LABELS

Subject Categories:

• Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE