SME
Computer Organization & Architecture
Memory hierarchy
Use this for “A 32 KiB direct-mapped cache has 64-byte blocks and 32-bit addresses. How many tag bits?”
Diagram
tag 17 + index 9 + offset 6 = 32 bits, the whole 32-bit word.
Cache size C = 32 KiB
Block size B = 64 B
Sets S = 512
This is an example. Type your own values to start a new problem.
S
=
C (KiB)
÷
(
B (B)
×
w
)
A (bit)
=
tag (bit)
+
index (bit)
+
offset (bit)
Formulas
S
=
C
B
×
w
512
=
32,768
64 × 1
offset
=
log₂
B
6 = log₂ 64
index
=
log₂
S
9 = log₂ 512
A
=
tag
+
index
+
offset
32 = 17 + 9 + 6
Formulas are worked in B. The step-by-step shows the conversions.
Assumptions
•
Addresses name single bytes, and 1 KiB = 1024 bytes (many texts write KB).
•
A direct-mapped cache has 1 way; a fully associative cache has 1 set, so no index bits.
•
The offset picks the byte in a block, the index picks the set, and the tag is compared with every block in that set.
Step-by-step
WE KNOW
A = 32 bit, C = 32 KiB, B = 64 B, w = 1
FIND
sets (S), offset bits (offset), index bits (index), tag bits (tag)
Step 1 · Convert to the formula’s units
The formulas don’t work directly in the units you chose, so convert first (to B).
C = 32 KiB = 32,768 B (1 KiB = 1024 B)
Step 2 · Find sets (S)
Use S = C ÷ (B × w)
Each
set
holds
w
blocks
of
B
bytes,
so
the
cache’s
bytes
over
a
set’s
bytes
count
the
sets.
S
=
32,768
64 × 1
S
=
512
Step 3 · Find offset bits (offset)
Use offset = log₂ B
The offset needs one pattern for every byte of a block.
log₂
64
=
6,
since
2
6
=
64
offset = 6 bit
Step 4 · Find index bits (index)
Use index = log₂ S
The index needs one pattern for every set.
log₂
512
=
9,
since
2
9
=
512
index = 9 bit
Step 5 · Find tag bits (tag)
Use A = tag + index + offset
The bits left over after the index and offset are the tag.
tag
=
A
−
index
−
offset
tag = 32 − 9 − 6
tag = 17 bit
Check
Put the numbers back in. Both sides should match.
512
=
32,768
64 × 1
✓
6 = log₂ 64 ✓
9 = log₂ 512 ✓
32 = 17 + 9 + 6 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Average memory access time
Use this for “L1 hits in 1 cycle and misses 5% of the time; L2 hits in 10 cycles and misses 20% locally; memory takes 100 cycles. What is the AMAT?”
Page table size
Use this for “A system has 32-bit virtual addresses, 4 KiB pages and 4-byte page table entries. How big is a flat page table?”