A set associative cache is implemented with a psuedo LRU rep

A set associative cache is implemented with a \"psuedo LRU\" replacement scheme (to achieve cheaper hardware than a \"true LRU\"). Assume that there are four slots in each set, and name the slots A, B, C, and D. Within each set, three flip flops are used to indicate the \"psuedo LRU\" block for replacement: FF1 is set when slot A or slot B is referenced and reset when slot C or slot D is referenced. FF2 is set when slot A is referenced and reset when slot B is referenced. FF3 is set when slot C is referenced and reset when slot D is referenced. The \"pseudo LRU\" block selected for replacement upon cache miss to this set is selected as follows:

FF1 FF2 FF3 psuedo LRU block

0 0 X A

0 1 X B

1 X 0 C

1 X 1 D

a) What is the probability (assuming independent identically distributed references to A, B, C, and D) that the psuedo LRU block is in fact the true LRU block? b) How many flip flops are required for this scheme with 2 blocks per set? c) How would the probability of part (a) change (up, down, constant) as i increases?

Solution

ans) a.  LRU policy with a binary tree that probability to independent identically to that Pseudo LRU Algorithm 4-way SA Tree-based O(N) 3 bits for 4-way, Cache ways are the leaves of the tree Combine ways as we proceed towards the root of the tree.

b .  flip flops are required for this scheme with 2 blocks per set is 3

2-ways --->AB BA = 2 = 2!

  3-ways ----> ABC ACB BAC BCA CAB CBA = 6 = 3!

c . LRU policy increases cache access times Additional hardware bits needed for LRU state machine