You are designing a controller for a tiny cache that is fully associative but has only three words in it. The cache has an LRU replacement policy. A reference record module (RRM) monitors references to the cache and always outputs the binary value 1, 2, or 3 on two output signals to indicate the least recently used cache entry. The RRM has two signal inputs, which can encode the number 0 (meaning no cache reference is occurring) or 1, 2, or 3 (indicating a reference to the corresponding word in the cache).
A. What hit ratio will this cache achieve if faced with a repeating string of references to the following addresses: 100, 200, 104, 204, 200?
B. The RRM can be implemented as a finite-state machine. How many states does the RRM need to have? Why?
C. How many state bits does the RRM need to have?
D. Draw a state-transition diagram for the RRM.
E. Consider building an RRM for a 15-word fully associative cache. Write a mathematical expression for the number of bits in the ROM required in a ROMand-register implementation of this RRM. (You need not calculate the numerical answer.)
F. Is it feasible to build the 15-word RRM of part E using a ROM and register in today's technology? Explain why or why not.