src/nmutil/plru.txt

   1 pseudo-LRU
   2
   3 two-way set associative - one bit
   4
   5    indicates which line of the two has been reference more recently
   6
   7
   8 four-way set associative - three bits
   9
  10    each bit represents one branch point in a binary decision tree; let 1
  11    represent that the left side has been referenced more recently than the
  12    right side, and 0 vice-versa
  13
  14               are all 4 lines valid?
  15                    /       \
  16                  yes        no, use an invalid line
  17                   |
  18                   |
  19                   |
  20              bit_0 == 0?            state | replace      ref to | next state
  21               /       \             ------+--------      -------+-----------
  22              y         n             00x  |  line_0      line_0 |    11_
  23             /           \            01x  |  line_1      line_1 |    10_
  24      bit_1 == 0?    bit_2 == 0?      1x0  |  line_2      line_2 |    0_1
  25        /    \          /    \        1x1  |  line_3      line_3 |    0_0
  26       y      n        y      n
  27      /        \      /        \        ('x' means       ('_' means unchanged)
  28    line_0  line_1  line_2  line_3      don't care)
  29
  30    (see Figure 3-7, p. 3-18, in Intel Embedded Pentium Processor Family Dev.
  31     Manual, 1998, http://www.intel.com/design/intarch/manuals/273204.htm)
  32
  33
  34 note that there is a 6-bit encoding for true LRU for four-way set associative
  35
  36   bit 0: bank[1] more recently used than bank[0]
  37   bit 1: bank[2] more recently used than bank[0]
  38   bit 2: bank[2] more recently used than bank[1]
  39   bit 3: bank[3] more recently used than bank[0]
  40   bit 4: bank[3] more recently used than bank[1]
  41   bit 5: bank[3] more recently used than bank[2]
  42
  43   this results in 24 valid bit patterns within the 64 possible bit patterns
  44   (4! possible valid traces for bank references)
  45
  46   e.g., a trace of 0 1 2 3, where 0 is LRU and 3 is MRU, is encoded as 111111
  47
  48   you can implement a state machine with a 256x6 ROM (6-bit state encoding
  49   appended with a 2-bit bank reference input will yield a new 6-bit state),
  50   and you can implement an LRU bank indicator with a 64x2 ROM
  51