From: Paul Mackerras <paulus@sa...>  20051013 01:24:25

Nicholas Nethercote writes: > On Wed, 12 Oct 2005, Julian Seward wrote: > > > I did have a different speedup idea however. I don't know if it > > is valid, but might be worth looking into. > > > > cg_sim.c simulates general 2^nway associative caches. Doing > > that involves endlessly rearranging entries in this set[] array > > when a tag matches set[i] for i > 0. In that case (which > > is the second most common case after matching set[0]) the > > section set[0 .. i] is rotated to put set[i] at the start. > > > > This seems expensive, and it could be that simply swapping > > set[i] and set[i1] would be cheaper  it would remove the > > loop setup/control overhead whilst still bringing a popular > > line to the top quickly given a sequence of references to it. > > > > What I can't figure out is if this would change the actual > > simulated behaviour or not. > > Sounds like it would  it wouldn't be LRU any more. Well, it depends on how the code chooses a line to cast out. If the algorithm is to pick set[N1], then maybe the change to the algorithm would change the actual simulated behaviour. If the castout algorithm doesn't depend on the order of the entries, then moving them around is just an optimization. The multiway set associative caches that I have seen actually use a pseudoLRU 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 Nway 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. Regards, Paul. 