Forums

hardware circuit for caching replacement

Started by Unknown December 3, 2006
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

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
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/>