Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!hplabs!cello!renglish
From: renglish@cello.hpl.hp.com (Bob English)
Newsgroups: comp.arch
Subject: Re: memory management implementations
Message-ID: <1991Apr02.194431.11154@cello.hpl.hp.com>
Date: 2 Apr 91 19:44:31 GMT
References: <1726@spim.mips.COM>
Organization: Hewlett Packard Labs
Lines: 23

mash@mips.com (John Mashey) writes:
> In article <JONATHAN.91Apr1213714@speedy.cs.pitt.edu> jonathan@cs.pitt.edu (Jonathan Eunice) writes:
> >My impression is that most workstations...use some low-cost
> >approximation of the LRU algorithm... Are the LRU approximations
> >used "good enough?"

> I don't recall the exact numbers, but I recall that the effect was:
> 1) If you have 2-set-associative TLB, LRU is important, and has a
> better miss rate than random replacement, and is cheap to do.
> 2) as the degree of associativity rises, the difference between
> LRU and random mostly disappears; the cost for implementing LRU may go
> up; the cost to implement random is minimal.

For caches and TLBs, this is probably right.  It's not clear to me,
however, whether the question refers to the hardware replacement
policies used by the uPs, or the software replacement policies used in
paging VM systems.  In the latter case, the miss penalty for choosing
the wrong page can be 50MHz * ~20msec = 1 Million cycles, and it can be
worth spending a lot of CPU time to avoid a single miss, particularly if,
as is often the case, the workstation doesn't have other, important work
to do.

--bob--