Massively Parallel Algorithms for Trace-Driven Cache Simulations

David M. Nicol, Boris D. Lubachevsky

Research output: Contribution to journalArticlepeer-review


This paper considers the use of massively parallel architectures to execute a trace-driven simulation of a single cache set. A method is presented for the Least-Recently-Used (LRU) policy, which, regardless of the set size C, runs in time O(log N) using N processors on the exclusive read, exclusive write (EREW) parallel model. A simpler LRU simulation algorithm is given that runs in O(C log N) time using N/logN processors. We present timings of the second algorithm’s implementation on the MasPar MP-1, a machine with 16 384 processors. A broad class of reference-based line replacement polices are considered, which includes LRU as well as the Least-Frequently-Used and Random replacement policies. A simulation method is presented for any such policy that on any trace of length N directed to a C line set runs in time O(C log N) time with high probability using N processors on the EREW model. The algorithms are simple, have very little space overhead, and are well suited for SIMD implementation.

Original languageEnglish (US)
Pages (from-to)849-859
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number8
StatePublished - Aug 1994
Externally publishedYes


  • Parallel algorithms
  • SIMD architecture trace-driven simulation
  • cache simulation. Leastrecently-used (LRU)

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Massively Parallel Algorithms for Trace-Driven Cache Simulations'. Together they form a unique fingerprint.

Cite this