Why a Cache Needs More Than Just Storage Circuits
The cache concepts discussed earlier in this series, tags, indices, and hit or miss detection, describe what data the cache holds and how it is located. But handling an actual request, especially a miss that requires fetching data from a slower level of the memory hierarchy, requires a sequence of coordinated steps over multiple clock cycles, not just a single combinational lookup. This sequencing is handled by a Cache Controller.
What a Finite-State Machine Is
A Finite-State Machine (FSM) is a model of sequential logic, introduced conceptually earlier in this series when discussing combinational and sequential circuits, that exists in exactly one of a limited number of defined States at any given time, transitioning between states based on inputs and the current state, and producing outputs based on which state it is currently in.
Modeling Cache Control as an FSM
A simplified cache controller can be modeled with a small number of states representing the stages of handling a memory request.
State: Idle
→ waiting for a memory request from the processor
State: Compare Tag
→ checking whether the requested address is a hit or miss
State: Allocate (on a miss)
→ sending a request to the next memory level to fetch the block
State: Write Cache Block (on a miss)
→ writing the newly fetched block into the cache once it arrives
State: Return to Idle
→ request satisfied, ready for the next requestTracing a Cache Hit Through the FSM
On a hit, the controller moves from Idle to Compare Tag, confirms the tag matches, immediately returns the requested data to the processor, and transitions back to Idle — a short sequence completed in very few cycles.
Tracing a Cache Miss Through the FSM
On a miss, the controller moves from Idle to Compare Tag, detects the mismatch, then transitions into the Allocate state, waiting however many cycles are required for the slower memory level to supply the missing block. Once the data arrives, the controller moves to Write Cache Block to store it, updates the relevant tag, and only then returns to Idle, finally supplying the requested data to the processor.
Why Modeling Control This Way Is Useful
Describing cache control as an explicit finite-state machine makes the design far easier to verify correctness for. Every possible situation the controller might encounter corresponds to a specific, well-defined state and set of transitions, which prevents the kind of ambiguous or incompletely specified behavior that can arise from writing control logic in a less formal, ad hoc manner.
Why This Concept Extends Beyond Simple Caches
This same finite-state machine approach to control extends naturally to far more complex controllers throughout a processor, including the pipeline control logic discussed earlier in this series and the more advanced cache controllers found in real multi-level, multi-core cache hierarchies, where correctly sequencing many possible situations is essential to avoiding subtle hardware bugs.