ToolSphere

Cache Mapping Calculator

Computer science

Tag, index and offset bits for direct-mapped, set-associative and fully associative caches, address breakdowns, and a hit/miss simulation with LRU.

Cache mapping calculator

Type the address bits, cache size and block size to split an address into tag, index and offset bits, look up addresses and simulate hits and misses.

Address split: 16 tag bits, 12 index bits, 4 offset bits. Tag identifies the block, index selects a set, and offset selects a byte within the block.

Address split

Tag 16
Index 12
4
Lines
4096
Sets
4096
Ways
1
Offset bits
4
Tag storage
65,536 bits

offset = log₂(16) = 4; index = log₂(4096 sets) = 12; tag = 32 − 12 − 4 = 16

Look up addresses

AddressBinary (tag | index | offset)TagSetOffset
305419896 (0x12345678)0001001000110100 | 010101100111 | 10004660 (0x1234)13838
43981 (0xABCD)0000000000000000 | 101010111100 | 11010 (0x0)274813

Simulate references (LRU within a set)

RefBlockSetTagResultSet afterwards (LRU first)
0000Miss0
16110Miss1
64440Miss4
0000Hit0
102464640Miss64
16110Hit1

2 hits, 4 misses: hit ratio 33.3%

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Cache Mapping Calculator

  1. 1Enter the address width in bits, the cache size and the block size (for example 32, 64 KB, 16 B).
  2. 2Choose the mapping: direct mapped, 2-, 4- or 8-way set associative, or fully associative.
  3. 3Read the tag, index and offset bits, then type addresses to see how each one splits.
  4. 4Enter a reference string (byte addresses or block numbers) to see every hit and miss and the hit ratio.

About Cache Mapping Calculator

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.

Guides and tutorials

Frequently asked questions

How do you calculate tag, index and offset bits?

Offset bits = log₂(block size in bytes). Index bits = log₂(number of sets), where sets = (cache size ÷ block size) ÷ associativity. Tag bits = address bits − index bits − offset bits.

What changes in a set-associative cache?

Each set holds n blocks, so there are n times fewer sets. The index loses log₂ n bits and the tag gains them. A fully associative cache has a single set: no index bits, and the tag is the whole block address.

How do I know if an access is a hit or a miss?

Work out the block number (address ÷ block size), its set (block mod number of sets) and its tag (block ÷ number of sets). If a block with that tag is already in the set, it is a hit; otherwise it is a miss and the block is loaded, evicting the least recently used block if the set is full.

What is the tag storage overhead?

Every line stores its tag, so the cache needs lines × tag bits of tag memory on top of the data (plus a valid bit per line in real hardware). The calculator shows the tag total for your settings.

Have a suggestion for Cache Mapping Calculator?Share your feedback ↗