The following tables define the states and transitions of a ROM-based state machine to implement the Least Recently Used (LRU) logic for a 4-way set associative cache. The current and next state indicate the reverse order of when the four sets A through D were accessed, so "ABCD" means A is most recently used and D is least recently used. The next state is chosen based on the current state and whether there was a hit on set A through D or a miss.

This state machine has 24 possible states and 120 transitions. It should fit in a 256 x 8 ROM and register, with the current LRU state as bits 0-4 of the address, the matching set as bits 5-6, and miss signal as bit 7. Bits 0-4 of the output register would be written back to the LRU state. The remaining bits of the output can be used to indicate whether the LRU data for an entry should be updated and which set should be replaced.

Code	Definition
A	Set A
B	Set B
C	Set C
D	Set D
M	Miss
N	No Operation
R	Replace
U	Update

State is a Java program that generates all the possible LRU states for an N-way set associate cache, then generates a state transition table. The purpose of this program was to determine the most efficient way to implement the logic in a lookup table.

For example, the most straight-forward approach would be to have 8 bits to encode the LRU state, 2 bits to encode the match, and a bit to indicate a miss. This would require a 2048 x 10 ROM (assuming 2 additional bits to encode the action). This is inefficient because there are only 24 possible states. This can be encoded in 5 bits, so we only need a 256 x 7 ROM.

This inefficiency grows exponentially as the number of sets increases. A simple lookup table for an 8-way cache would require 24 bits (8 x 3) to encode the state plus 4 additional bits to encode the matching set or miss. That would be untenable. The cache actually has only 40320 possible states which can be encoded in 16 bits. That's still a large ROM, but much more tenable than having a 28 bit address!