Cache memory and mapping functions
Cache memory mapping functions: direct-mapped, fully associative and set-associative mapping, how to compute tag/index/offset bits, and performance metrics (hit/miss, AMAT) with worked examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Cache memory sits between the CPU and main memory to reduce average access time. Engineers use mapping functions to decide which memory block goes into which cache line; correct calculations of index/tag/offset and AMAT are needed to design and size caches and to solve exam problems.
Key ideas
Block offset: the number of address bits that select a byte within a block. If block size = B bytes then offset bits = log2(B).
Cache size (C): total data capacity of cache in bytes (not including tag and control bits). Assumption: cache size is an integer multiple of block size.
Number of lines (L): L = C / B when counting data lines only.
Associativity (A): number of lines per set. For
- Direct-mapped cache: A = 1 (each memory block maps to exactly one line).
- Fully associative cache: A = L (a block may go to any line, there is one set).
- Set-associative cache: 1 < A < L, number of sets S = L / A.
Index bits: bits used to select a set. If number of sets S then index bits = log2(S). In fully associative caches S = 1 so index bits = 0.
Tag bits: remaining high-order address bits used to identify which block is stored in the selected line: tag bits = (address bits) − (index bits) − (offset bits).
Valid bit: one control bit per line indicating whether the data in that line is valid.
Hit: the requested memory address is found in the cache (same tag and valid bit set) in the addressed set/line.
Miss: requested data not found in cache; memory block must be fetched from lower level memory (incurs miss penalty).
Miss types: compulsory (first-time access to a block), capacity (working set exceeds cache capacity), and conflict (mapping collisions in set/direct-mapped caches); in multiprocessors, coherence/invalidations can also cause misses.
Miss rate: fraction of memory accesses that result in misses. If not specified, assume an overall miss rate across all accesses; if separate read/write (or instruction/data) miss rates are given, use them as specified (e.g., compute a weighted AMAT).
Miss penalty: extra time (or cycles) required to fetch a block from lower-level memory and place it in cache.
Hit time: time to access data from cache when there is a hit (includes tag comparison and data read).
Average Memory Access Time (AMAT): a standard performance metric. Exact statement: AMAT = Hit time + (Miss rate × Miss penalty). This assumes memory hierarchy of two levels (cache and next-level) and independent miss penalty.
Derivations universities ask for (step-by-step):
- Computing offset bits: from block size B bytes, offset bits = log2(B). Draw: a single memory address as a binary string; label the lowest log2(B) bits as "offset".
- Computing number of lines L: L = C / B. Draw: a rectangle labelled "Cache data array" with C bytes divided into L equal boxes, each box size B.
- For set-associative: S = L / A. Draw: cache as S sets, each set has A ways (lines). Label sets 0..S-1 and ways 0..A-1.
- Index bits = log2(S). Show address bits split as [tag | index | offset]. Label sizes and how to extract tag/index/offset from an example address.
- Tag bits = address width (e.g. 32) − index bits − offset bits.
When drawing diagrams in an answer: draw a horizontal address with boxes for tag/index/offset. Draw a cache array with S rows (sets) and A columns (ways); inside each cell label: Valid bit, Tag field, Data block (B bytes), Dirty bit if write-back.
Note: For write policies, tag and dirty-bit usage differs (write-through : dirty bit not needed; write-back : dirty bit needed). Refer to the later topic "Cache replacement and write policies" for replacement algorithms and write policy trade-offs.
Formulas
L = C / B where L = number of cache lines (unit: lines), C = cache data size (bytes), B = block size (bytes). Applies for data capacity only.
S = L / A where S = number of sets (unit: sets), A = associativity (ways). Applies to set-associative caches.
offset_bits = log2(B) where B is block size in bytes; result is in bits. Requires B to be power of two.
index_bits = log2(S) where S is number of sets; result is in bits. Requires S to be power of two.
tag_bits = address_bits - index_bits - offset_bits where address_bits is width of physical address (bits).
block_number = floor(address / B) for a byte-addressable system; then set_index = block_number mod S and tag_value = floor(block_number / S) for direct-mapped or set-associative caches.
AMAT = Hit_time + Miss_rate × Miss_penalty where Hit_time and Miss_penalty are in same time units (e.g., cycles). Assumes single-level cache over next-level memory. For two-level caches: AMAT = L1_hit_time + L1_miss_rate × (L2_hit_time + L2_miss_rate × L2_miss_penalty).
Total_tag_storage_bits = L × (tag_bits + 1 + dirty_bit) gives tag-storage requirement in bits, where dirty_bit = 1 for write-back and 0 for write-through; replacement-policy metadata (e.g., LRU bits per set) is not included and should be added separately if required.
Worked examples
Example 1 — Direct-mapped cache (numerical): Given: physical addresses are 32 bits, cache size C = 64 KB = 65536 bytes, block size B = 64 bytes, direct-mapped (A = 1). Steps:
L = C / B = 65536 / 64 = 1024lines.offset_bits = log2(B) = log2(64) = 6bits.- For direct-mapped S = L = 1024 so
index_bits = log2(1024) = 10bits. tag_bits = 32 - 10 - 6 = 16bits.- For address 0x1234ABCD, compute fields:
- Tag = high 16 bits = 0x1234.
- Remaining low 16 bits = 0xABCD (43981 decimal). Index = high 10 bits of 0xABCD -> index = floor(43981 / 2^6) = floor(43981/64) = 687 (decimal) = 0x2AF.
- Offset = low 6 bits = 43981 mod 64 = 13 (decimal) = 0x0D. Final: Tag=0x1234, Index=687 (0x2AF), Offset=13 (0x0D). Bold final answers: Tag = 0x1234, Index = 687, Offset = 13.
Example 2 — 4-way set-associative and fully associative: Same address width and cache size: 32-bit, C = 64 KB, B = 64 bytes, associativity A = 4.
- L = 65536 / 64 = 1024 lines.
- S = L / A = 1024 / 4 = 256 sets.
- offset_bits = 6, index_bits = log2(256) = 8, tag_bits = 32 − 8 − 6 = 18. For fully associative (A = 1024): S = 1, index_bits = 0, tag_bits = 32 − 0 − 6 = 26.
Example 3 — AMAT calculation (performance):
Given: Hit_time = 1 cycle, Miss_rate = 4% = 0.04, Miss_penalty = 100 cycles.
AMAT = 1 + 0.04 × 100 = 1 + 4 = 5 cycles. Final: AMAT = 5 cycles.
Common mistakes
- Using log base 10 instead of log base 2 for bit counts; always use log2.
- Forgetting index_bits = 0 for fully associative caches.
- Omitting the valid bit (and dirty bit for write-back) when computing tag storage.
- Confusing tag value with physical page number (tags are not full page numbers unless sizes match).
- Not carrying units (bytes, cycles) through numeric AMAT calculations.
For your exam
Typical question types:
- Definitions: define cache, block, hit/miss, associativity, tag/index/offset.
- Derivations: show how to split an N-bit address into tag/index/offset for given C, B, A. Include diagram of address and cache set/ways.
- Numericals: compute number of lines, index/tag bits, and map a hex address to tag/index/offset.
- Performance: compute AMAT given hit time, miss rate and miss penalty.
- Short notes: trade-offs between direct-mapped, set-associative and fully associative caches; write-through vs write-back; replacement policies (see "Cache replacement and write policies").
What full-marks answers include:
- Clear statement of assumptions (byte-addressable, address width in bits, B/C/A values).
- Step-by-step calculation with formulas written, numbers substituted, and units shown.
- If asked, a clear diagram: draw address split [tag | index | offset] with bit counts; draw cache as S × A grid with labels Valid, Tag, Data.
Quick check
- For a byte-addressable system with 16-bit addresses, cache 4 KB, block size 16 bytes, direct mapped: how many offset, index and tag bits?
- A cache has 512 lines and is 8-way set-associative. How many sets and what is index_bits?
- If Hit_time = 2 cycles, Miss_rate = 1%, Miss_penalty = 200 cycles, what is AMAT? Answers: 1) offset = 4 (log2 16), L = 4096/16 = 256 lines, index = 8 (log2 256), tag = 16 − 8 − 4 = 4 bits. 2) S = 512/8 = 64 sets, index_bits = 6. 3) AMAT = 2 + 0.01 × 200 = 2 + 2 = 4 cycles.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?