The minimum number of bits for each set is the ceiling (log2 (N!)), Where N is the number of methods.
This is easily seen for four-sided associativity, noting that the MRU (A) block can be any of the four blocks, the almost MRU block can be any of the three remaining blocks (B β {0,1,2, 3} and B β A), an almost LRU block can be only one of the two remaining blocks (C β {0,1,2,3} and C β A and C β B), and only one block is available for an LRU block. Therefore, the number of possible states in the aggregate is the product of the number of these independent states, i.e. 4! (or for the general case N!).
The B bit can encode 2 B states so B must be greater than or equal to log2 (the_number_of_states). For 24 states of quadrilateral associativity, five bits are needed.
(Increasing the number of bits can simplify the state machine used to manage this information, so the minimum number of bits needed may not match the actual number of bits used in real-world implementations.)
As an answer Leeor noted, the pseudo-LRU tree (which supports the tree of single-bit / two-way LRU variants) requires only N-1 bits. This pLRU is relatively simple to implement, so even with 4-sided associativity (where only two bits of memory are stored - 3 bits versus 5 bits), this form of pLRU can be attractive.
(With 8-position associativity, a true LRU requires 16 bits of status compared to 7 bits for the pLRU tree. Obviously, with higher associativity, a true LRU becomes more expensive, but it can still be useful to simplify the worst execution and it was chosen as a replacement policy for some fully associative TLBs.)
source share