Mohamed Zahran wrote:
> xu_feng_xu@yahoo.com wrote:
>>
>> I am looking for any datasheet or document giving the cache
>> hardware circuit to implement the Least Recently Used algorithm
>> in M-way set associative?  I have checked Intel site but can't
>> find any. My expectation is that the hardware will be
>> considerably complex, so do the modern processor (pentium)
>> implement the LRU
> 
> Actually, as you said, LRU is quite expensive. However, there are
> good approximations for LRU, known as pseudo-LRU. Take a look at:
>
>    http://ieeexplore.ieee.org/iel5/10692/33752/01607387.pdf

Many years ago I was quite successful with an algorithm that
preserved a set of bits (say 8, but I actually used 6), whose most
significant bit was the 'accessed this cycle' bit.  Whenever the
item was accessed, that bit was set.  Simultaneously a hardware
counter counted actual accesses, and every so often right shifted
the history bits (a cycle).  This made the timing dependent on
program behaviour, not clock time, and also avoided the need for a
real time clock.

This made the magnitude of the history bits measure the relative
time since last access.  When something needed to be discarded the
history bits were scanned for the minimum value, and that item was
selected.  Ties were broken by the scan order, selecting either the
last or the first of the minimum values.

Please don't top-post.  I fixed this one.  Your answer belongs
after, or possibly intermixed with, the material you quote (after
snipping irrelevant material).  See the following links:

-- 
 Some informative links:
   <news:news.announce.newusers
   <http://www.geocities.com/nnqweb/>
   <http://www.catb.org/~esr/faqs/smart-questions.html>
   <http://www.caliburn.nl/topposting.html>
   <http://www.netmeister.org/news/learn2quote.html>
   <http://cfaj.freeshell.org/google/>

Actually, as you said, LRU is quite expensive. However, there are good
approximations for LRU, known as pseudo-LRU. Take a look at:
http://ieeexplore.ieee.org/iel5/10692/33752/01607387.pdf

xu_feng_xu@yahoo.com wrote:
> Hi,
>
> I am looking for any datasheet or document giving the cache hardware
> circuit to implement the Least Recently Used algorithm in M-way set
> associative?  I have checked Intel site but can't find any. My
> expectation is that the hardware will be considerably complex, so do
> the modern processor (pentium) implement the LRU
> 
> thanks

Hi,

I am looking for any datasheet or document giving the cache hardware
circuit to implement the Least Recently Used algorithm in M-way set
associative?  I have checked Intel site but can't find any. My
expectation is that the hardware will be considerably complex, so do
the modern processor (pentium) implement the LRU

thanks