How a cache finds a block
A cache splits every memory address into three fields. The offset picks the byte within a block, so it needs log₂(block size) bits. The index picks which set of the cache the block can live in, so it needs log₂(number of sets) bits. The tag is everything left over, stored alongside the block so the cache can tell which of the many memory blocks that map to this set is actually there.
Direct mapped, set associative, fully associative
In a direct-mapped cache each block can go in exactly one line: sets = lines. In an n-way set-associative cache each block can go in any of n lines of its set: sets = lines ÷ n, so the index shrinks by log₂ n bits and the tag grows by the same amount. In a fully associative cache a block can go anywhere: there is one set, no index bits at all, and the tag is the whole block address. For a 32-bit address, 64 KB cache and 16-byte blocks: direct mapped gives offset 4, index 12, tag 16; 4-way gives offset 4, index 10, tag 18; fully associative gives offset 4, tag 28.
Hits, misses and replacement
The simulation runs a reference string through the cache. For each reference it computes the block number, the set it maps to and the tag, then reports a hit if that block is already in the set, or a miss if it has to be loaded. When a set is full, the least recently used block is evicted. The Patterson & Hennessy example (an 8-block direct-mapped cache with references 22, 26, 22, 26, 16, 3, 16, 18) gives 3 hits and 5 misses, with block 18 evicting block 26 because both map to set 2. Make the same cache 2-way and conflicts like that one go away.
Byte addresses or block numbers
Textbook problems give references either as byte addresses or as block (word) numbers. Choose which: byte addresses are divided by the block size to find the block; block numbers are used as they are.
Where this fits
Cache mapping is the hardware version of the problem the page replacement calculator solves in software: which block stays when space runs out. For how memory is handed to processes in the first place, see the memory allocation calculator.