Direct-mapped cache: hits, misses and conflicts, live

In a direct-mapped cache every memory address has exactly one line it can live in: the low address bits (the index) pick the line, and the high bits (the tag) are stored with it, so a lookup is a hit only if that line is valid and holds the same tag. This live 4-line cache splits a 4-bit address A3..A0 into tag A3 A2 and index A1 A0.

Each line here holds a valid bit, a 2-bit tag and 2 bits of data. The index A1 A0 selects one line through 4:1 multiplexers, and two XNOR gates compare its stored tag with A3 A2: HIT = valid AND (tag matches), MISS is the opposite, and D1 D0 show the selected line's data. On a miss, the data would come from main memory; here you play memory by setting DIN1 DIN0 and pressing FILL, and the next clock edge writes the tag and data into the line and sets its valid bit. The interesting case is the conflict miss: addresses 0101 and 1101 have the same index (01) and different tags, so they fight over line 1, and filling one evicts the other, even while lines 0, 2 and 3 sit empty. That is the price of direct mapping, and the reason caches add associativity (the cache lesson covers both). Each line's tag and data are a 4-bit register with load, written through a decoder as in the register file, and the valid bits are D flip-flops that set on a fill and clear on a clock edge with CLR high. Real caches are bigger in every direction (a line holds 32 or 64 bytes, and there are hundreds of lines), but the lookup is the same. The live circuit opens with CLR high and address 0101: turn CLK on and off once to invalidate every line (MISS lights), set CLR to 0, then FILL and pulse CLK to load line 1. Before the page is built, a 23-step sequence is checked on HIT, MISS, V and the selected line's tag and data: misses, fills, a conflict miss and eviction, an untouched line, and invalidating everything.

Big circuit: pinch, scroll or tap + to zoom in, then drag to move around.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

4× 4-bit register with load: the lines: tag (A3 A2) and data (DIN1 DIN0)
4× D flip-flop + 4 OR + 4 AND: the valid bits: set by a fill, cleared on a clock edge with CLR high
8× AND + 3 NOT: decoding the index into the fill enables, gated by FILL
5× 4:1 multiplexer: the selected line's tag, data and valid bit
2× XNOR + 2 AND + 1 NOT: HIT = valid AND tag match, and MISS

Step by step

Place inputs A3 to A0, DIN1, DIN0, FILL, CLK and CLR, and probes HIT, MISS, D1, D0, V, TAG1 and TAG0.
Give each of four lines a register for tag and data and a valid flip-flop, all written on a clock edge when FILL is high and the index A1 A0 selects that line.
Read the selected line through 4:1 multiplexers on A1 A0, and compare its tag with A3 A2 using two XNORs.
HIT = valid AND both tag bits equal. Look up 0101 (miss), fill it, look it up again (hit), then try 1101 (a conflict miss).

A short run

Address	Line (A1 A0)	Tag (A3 A2)	Result	Why
0101	01	01	miss	line 01 is empty
0101 after a fill	01	01	hit	line 01 holds tag 01
1101	01	11	miss	same line, different tag (conflict)
1101 after a fill	01	11	hit	line 01 now holds tag 11
0101	01	01	miss	evicted by 1101
0010	10	00	miss	line 10 is empty

Address = tag (2 bits) then index (2 bits). With 4 lines and 2 tag bits, this cache holds 4 of the 16 addresses at a time. A real cache line holds a block of bytes, and the lowest address bits pick a byte within it (the offset); with one data word per line, this one has no offset bits.

You can also read the full theory in the lesson on caches. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load 1011 sequence detector binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter Hamming (7,4) code encoder and corrector traffic light controller 4-bit barrel shifter CMOS AND gate CMOS OR gate CMOS XOR gate 1-bit magnitude comparator half subtractor from NAND gates full subtractor from NAND gates 8-to-3 encoder Gray to binary converter 4-to-16 decoder full adder using 4:1 multiplexers edge detector serial adder 4-bit carry-select adder 4-bit Kogge-Stone adder 4-bit carry-skip adder 4x4 Wallace tree multiplier 8-bit adder frequency divider (by 2, 4 and 3)switch debouncer (SR latch)3-bit Gray code counter Mealy machine (1011 detector)master-slave JK flip-flop (NAND)half subtractor from NOR gates 1-to-8 demultiplexer excess-3 to BCD code converter vending machine FSM 4-bit carry-save adder 3-bit synchronous counter (JK)CMOS transmission gate tri-state buffer (CMOS)2-to-1 mux from transmission gates mod-5 counter flip-flop conversion (JK to D)8-bit ALU decimal to BCD encoder BCD to decimal decoder 4-to-1 mux from 2-to-1 muxes XOR gate from NOR gates 4-bit LFSR 74LS138 decoder BCD subtractor 74181 ALU CMOS AOI gate (AOI21)D latch vs D flip-flop 74LS47 BCD to 7-segment decoder 74HC595 shift register 7400 quad NAND gate chip 7402 quad NOR gate chip 7404 hex inverter chip 7408 quad AND gate chip 7432 quad OR gate chip 7486 quad XOR gate chip 7474 dual D flip-flop 74HC165 shift register CD4017 decade counter 74LS283 4-bit adder 74LS90 decade counter 74HC161 4-bit counter 74HC151 8-to-1 multiplexer 74HC157 quad 2-to-1 multiplexer 74HC139 dual 2-to-4 decoder CD4511 BCD to 7-segment decoder 7492 divide-by-12 counter 7493 4-bit binary counter 74HC244 octal buffer Race-around condition (JK latch)74HC373 octal latch 74HC374 octal D flip-flop Turnstile state machine 1-to-2 demultiplexer half adder using 2:1 multiplexers register file (4 x 4-bit)digital PWM generator CD4013 dual D flip-flop 74LS76 dual JK flip-flop 7410 triple 3-input NAND chip 7411 triple 3-input AND chip 7420 dual 4-input NAND chip CD4011 quad 2-input NAND chip CD4001 quad 2-input NOR chip CD4081 quad 2-input AND chip CD4069 hex inverter chip 74HC164 8-bit shift register 7485 4-bit magnitude comparator 74HC125 quad tri-state buffer CD4040 12-stage binary counter CD4060 14-stage counter and oscillator 74LS193 4-bit up/down counter electronic dice circuit memory address register (MAR) and MDR hardware stack with a stack pointer 8-bit Brent-Kung adder 4x4 Dadda multiplier binary clock circuit

Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.

Open the direct-mapped cache in the lab →

Frequently asked

How does a direct-mapped cache work?

The address is split into a tag and an index. The index selects exactly one cache line, and the cache compares that line's stored tag with the address's tag: if the line is valid and the tags match it is a hit, otherwise a miss, and the block is fetched from memory into that line, replacing whatever was there.

What is a conflict miss?

A miss caused by two addresses that map to the same line. In a direct-mapped cache they keep evicting each other even if the rest of the cache is empty. Associative caches reduce conflict misses by letting a block sit in any of several lines.

What are the tag, index and offset?

The offset (lowest bits) picks a byte within a cache line, the index (middle bits) picks the line, and the tag (highest bits) is stored in the line to tell which of the many addresses with that index is there now.

What is the valid bit for?

It says whether a line holds real data. At power-on, or after the cache is flushed, every valid bit is 0, so every lookup misses even if a stored tag happens to match.