Cache Design for a 2-Set-Associative Cache: Address Interpretation

Verified Sources

Nov 3, 2026

We will design a set-associative cache given:

Block size: 4 words, each word is 16 bits (so block size in bits is $4 \times 16$ )
Set size (associativity): 2 ways
Total cache capacity: 4096 words (not bytes)
Main memory: 64K words, each word is 32 bits (so main memory size in bits is $64K \times 32$ )

Key cache terms we’ll use:
block
set
tag
index

Cache Address Breakdown (Tag, Index, Block Offset) — How Set-Associative Caches Split Addresses

1) Convert all sizes into consistent units

Given cache block size

4 words/block
16 bits/word
So block size in bits: $B = 4 \times 16 = 64\text{ bits}$

Cache total words

4096 words total
each word = 16 bits
So cache total capacity in bits: $C = 4096 \times 16 = 65536\text{ bits}$

Main memory

64K 32-bit words
So memory words: $M = 64K = 65536\text{ words}$ and memory is: $65536 \times 32 = 2{,}097{,}152\text{ bits}$

2) Determine number of sets (and number of lines)

For a set-associative cache:

way
Each set has 2 ways, so each set contains:

2 lines
each line holds 1 block

Let:

$S$ = number of sets
$B_w$ = block size in words = 4 words
total cache words = 4096

Total words in cache: $4096 = (\text{#sets}) \times (\text{ways per set}) \times (\text{words per block})$ $4096 = S \times 2 \times 4 = 8S$ So: $S = \frac{4096}{8} = 512$

Answer:

Number of sets $S = 512$
Total number of cache lines (ways) = $S \times 2 = 1024$

Also, total cache “lines” check:

each line holds 4 words
1024 lines $\times$ 4 words/line = 4096 words ✅

Design-to-Address Interpretation Roadmap

Fix units

Step A

Convert word sizes and block size into bits/words."

Compute sets

Step B

Use total cache words = sets × ways × words/block."

Compute address fields

Step C

Split main-memory addresses into tag, set index, block offset."

Lay out structures

Step D

Tag store per line, valid bits, data store per line."

3) Cache structure (what each set/line contains)

We will describe the structure at the level needed to “design the cache structure and show address interpretation.”

Each cache line (one way within a set) stores:

Data block: 4 words (each 16-bit) $\Rightarrow$ 64-bit data per line
Tag bits: identify which main-memory block is cached
Valid bit (and typically optionally Dirty/Replacement metadata)

Keywords:
tag store
valid bit
replacement policy

Minimal required arrays

Data array: Data[sets][ways][blockWords]
Tag array: Tag[sets][ways]
Valid array: Valid[sets][ways]

A compact diagram of the organization:

Mapping rule on lookup

Use processor address to compute:
- block offset (within the 4-word block)
- set index (select set)
- tag (compare with both ways in that set)
If either way’s valid&tag match => hit; return the word indicated by block offset.

Compute address field widths (block offset, set index, tag)

1
Step 1
Main memory is 64K 32-bit words, so there are 65536 distinct word addresses. Processor/CPU addresses are assumed to be word addresses; thus total word-address bits = log2(65536)=16.
2
Step 2
Block has 4 words → need log2(4)=2 bits to select which word within the block.
3
Step 3
Number of sets is 512 → need log2(512)=9 bits for set index.
4
Step 4
Tag bits = total address bits − (set index bits + block offset bits) = 16 − (9 + 2) = 5 bits.
5
Step 5
Processor word address splits as: [tag:5][set index:9][block offset:2].

4) Address interpretation for processor lookups

From the step-by-step:

Main memory word address bits:
$\log_2(64K) = \log_2(65536) = 16$
Block offset bits:
$\log_2(4)=2$
Set index bits:
$\log_2(512)=9$
Tag bits:
$16 - 9 - 2 = 5$

So the processor’s word address is interpreted as:

\text{Address} = \underbrace{\text{tag}}_{5\ \text{bits}} \ \underbrace{\text{set index}}_{9\ \text{bits}} \ \underbrace{\text{block offset}}_{2\ \text{bits}}

Keywords:
block offset
set index
word address

Important consistency check

If you instead interpret addresses as byte addresses, block offset and total address bits change. Here the problem states main memory is given as 64K 32-bit words, so using word addresses yields clean integer splits.

Word-size mismatch (16-bit cache words vs 32-bit memory words)

Cache stores 16-bit words but main memory is 32-bit words. A common assumption is that the cache fetches the needed 16-bit granularity from the 32-bit memory word (e.g., two cache words per memory word). If your course assumes a different transfer granularity, recompute offsets accordingly.

5) Derive the formulas used in hardware/software

Let:

$A$ = processor word address
Define:
- $d$ = block offset bits = 2
- $i$ = set index bits = 9
- $t$ = tag bits = 5

Then:

Block offset (word within the block):

\text{offset} = A \bmod 2^d = A \bmod 2^2

Set index:

\text{index} = \left\lfloor \frac{A}{2^d} \right\rfloor \bmod 2^i = \left\lfloor \frac{A}{4} \right\rfloor \bmod 512

Tag:

\text{tag} = \left\lfloor \frac{A}{2^{d+i}} \right\rfloor = \left\lfloor \frac{A}{2^{2+9}} \right\rfloor = \left\lfloor \frac{A}{2048} \right\rfloor

Look-up procedure

Access set: set = index
Compare both ways’ tags with tag
If match and valid: return Data[set][way][offset]

6) Example address breakdown (illustrative)

Let an example processor word address be: $A = 12345_{10}$

Compute:

offset = $A \bmod 4$
index = $\left\lfloor A/4 \right\rfloor \bmod 512$
tag = $\left\lfloor A/2048 \right\rfloor$

This yields an address split consistent with:

2-bit offset (0..3)
9-bit index (0..511)
5-bit tag (0..31)

(You can plug any $A$ you’re given in homework; the formulas above are the core.)

Cache Geometry Summary

Key structural counts and address field sizes

Common variations and how to adapt

Cache Address Interpretation Quick Checks

1 / 4

Question · Term

For this cache, how many sets exist?

Click to reveal

Answer · Definition

$512$ sets (from $4096 = sets \times 2 \times 4$ ).

Knowledge Check

Question 1 of 4

Q1Single choice

Given block size = 4 words and set size = 2 ways, total cache capacity = 4096 words, the number of sets is:

$128$

$256$

$512$

$1024$

Explore Related Topics

Content-Addressable Memory (CAM): Organization and Operation

Paging Addressing: Logical vs Physical Bits and Page Table Size

Cache Memory Organization: Mapping, Replacement, and Write Policies

Browse all research articles