|
From: Josef W. <Jos...@gm...> - 2005-10-13 08:59:40
|
On Thursday 13 October 2005 03:21, Paul Mackerras wrote: > The multi-way set associative caches that I have seen actually use a > pseudo-LRU scheme that uses a binary tree, with 1 bit per node, where > the ways are the leaves of the tree (so the tree has lg(N)+1 levels > for an N-way cache). Updating the tree for an access (i.e. marking > one way as most recently used) involves setting 1 bit at level of the > tree (except for the leaves). Finding the "LRU" element involves > traversing the tree from the top down; the bit on each interior node > tells you whether to go left or right from that node. The MRU update > involves setting each of the bits on the path from the root to the > leaf being accessed to point away from the path down to the leaf. It > doesn't do exactly LRU but it does a good approximation and it is easy > to implement. So you wouldn't shuffle around the tags in the set, but update a bit field? I suppose these needs an additional indirection for the most common case (checking MRU), but it could be worth it as only the bitfield has to be updated. Another problem is how to do this bit shuffling with a variable associativity. Still, if we do this, we have to make it clear to cachegrind users that we use another replacement strategy, i.e. hit/miss numbers change slightly. Josef |