Cache mapping locality and average access time
Learning objectives and scope
Distinguish hits from misses, split a byte address into tag/index/offset fields, trace a small cache, and calculate average memory access time (AMAT). Prerequisites: powers of two, integer division and remainder, and the address-versus-contents distinction. For example, 2^4=16 means four bits can select one of sixteen byte positions. This lesson introduces cache organization; write policies, multilevel hierarchies, coherence, virtual indexing and replacement algorithms require later lessons.
All address calculations use byte-addressed memory, power-of-two cache sizes and block sizes, ordinary low-bit indexing, and data capacity that excludes metadata. Traces use one-byte read requests, an initially empty cache and allocation of the complete block on every miss. A loaded block is available for the next request. No prefetching, invalidation or intervening accesses occur. We do not count tags and valid bits as data capacity.
1. Why a cache can help
A cache stores copies of memory blocks so that many requests can be served from a smaller, typically faster store. Temporal locality means reusing recently accessed locations; spatial locality means accessing nearby locations. Repeatedly reading one counter can exploit temporal locality. Scanning neighboring array elements can exploit spatial locality when several elements share a block.
A hit means the requested block is present and valid. A miss means it is not, so this model fetches it from the next memory level. The first access to a block in an empty cache is a compulsory miss. Later accesses are not automatically hits: replacement may have evicted the block. A cache need not help every possible access sequence.
2. Blocks lines sets and ways
A memory block is the unit copied into the cache. A cache line is a storage position for one such block plus metadata. If data capacity is C bytes and each block is B bytes, the number of lines is L=C/B.
In a direct-mapped cache, each memory block has exactly one possible line. In an E-way set-associative cache, it has one possible set and E possible lines in that set. The number of sets is S=C/(B×E). Direct mapping is E=1. A fully associative cache has one set, so a block can occupy any line. Placement determines where a block may go; replacement decides which current line to evict when all eligible lines are occupied.
Associativity does not multiply an already specified total capacity. With C=1024 bytes, B=16 bytes and E=4, there are 64 total lines and 16 sets, not 256 lines.
3. Derive address fields
For byte address a:
- block number q=floor(a/B);
- byte offset o=a mod B;
- set index i=q mod S;
- tag t=floor(q/S).
For an A-bit address, offset uses b=log2(B) bits and index uses s=log2(S) bits. Tag uses A−s−b bits. A direct-mapped cache uses the same rule with S=L. A fully associative cache has s=0; there are no index bits. On lookup, the selected set is searched for a matching tag in a valid line. An equal tag in an invalid line is not a hit.
These formulas assume the stated power-of-two, low-bit-indexed organization. They do not describe every real implementation. A machine's “word size” does not replace the byte offset unless the question explicitly uses word-addressed memory.
4. Worked example: fields and a particular address
Take a 16-bit byte address, direct-mapped data capacity C=1024 bytes and B=16 bytes. L=S=64. Thus b=4, s=6 and tag width=16−6−4=6 bits. The address layout, from high to low bits, is tag 6, index 6, offset 4.
For a=1170, q=floor(1170/16)=73 and o=2. The line index is 73 mod 64=9 and tag is floor(73/64)=1. Reconstruction checks the answer: ((1×64)+9)×16+2=1170. The block spans byte addresses 1168 through 1183 inclusive.
If the same capacity and block size use four-way associativity, S=16, so index width is 4 and tag width is 8. The byte-offset width remains 4. The same address has set index 73 mod 16=9 and tag 4. A tag is relative to the organization, not an invariant label on the address.
5. Worked example: trace conflicts
Use a direct-mapped cache with two lines and four-byte blocks. Read byte addresses 0, 1, 8, 0, 4, 8 in that order. Block numbers are 0, 0, 2, 0, 1, 2; line index is block number mod 2.
| Address | Block | Line | Result | Reason |
|---|---|---|---|---|
| 0 | 0 | 0 | Miss | Initially empty; load block 0 |
| 1 | 0 | 0 | Hit | Another byte of the resident block 0 |
| 8 | 2 | 0 | Miss | Block 2 replaces block 0 |
| 0 | 0 | 0 | Miss | Block 0 was evicted; it replaces block 2 |
| 4 | 1 | 1 | Miss | First access to block 1 |
| 8 | 2 | 0 | Miss | Block 2 was evicted again |
There is one hit in six requests, so hit rate=1/6 and miss rate=5/6. The fourth request illustrates a conflict: blocks 0 and 2 compete for one line even while the other line is unused. The first accesses to blocks 0, 2 and 1 are compulsory misses. Avoid calling every later miss a conflict without comparing against a suitable fully associative reference; limited capacity can also cause misses.
6. AMAT and the meaning of a miss penalty
Let h be hit time, m miss rate, and P the extra time on a miss after the cache lookup. A hit costs h; a miss costs h+P. Therefore
AMAT=(1−m)h+m(h+P)=h+mP.
Worked example: h=2 ns, miss rate=0.10 and extra miss penalty P=40 ns. AMAT=2+0.10×40=6 ns. Equivalently, 90% of accesses take 2 ns and 10% take 42 ns: 0.9×2+0.1×42=6 ns.
If instead a problem says the total miss-access time is 40 ns including lookup, use 0.9×2+0.1×40=5.8 ns. Then the extra penalty is 38 ns. This is a wording difference, not two competing definitions of arithmetic. Check units and whether the lookup time is already included. AMAT is time per memory access; it is not automatically the whole program's CPI or execution time.
Key points and common mistakes
- Convert byte addresses into block numbers before computing cache indexes.
- C/B counts lines; C/(B×E) counts sets. Metadata is additional unless the question includes it.
- Offset selects within a block, index selects a set, and a valid matching tag establishes a hit.
- Cache traces require the starting state, request size and replacement assumptions.
- Miss rate is a fraction: 10%=0.10, not 10.
- In h+mP, P is extra miss time. Do not count the lookup twice or omit it.
Original practice: six single-correct MCQs
These are original questions, not previous-year questions. Choose exactly one option.
K01. A direct-mapped cache has 4 KiB data capacity and 32-byte blocks, with 32-bit byte addresses. What are the tag, index and offset widths, respectively?
A. 20, 7, 5 B. 20, 5, 7 C. 15, 12, 5 D. 25, 2, 5
Answer: A
A: 4 KiB=4096 bytes; 4096/32=128 lines, so index=7, offset=5 and tag=32−7−5=20.
B: This swaps the index and offset widths.
C: Twelve bits select individual cache bytes, not the 128 lines; offset would be counted twice.
D: There are 128 lines, not four; an index of two bits is insufficient.
K02. A direct-mapped cache has 256 bytes of data and 16-byte blocks. For byte address 1100, what are the block number, line index and byte offset?
A. 68, 12, 4 B. 1100, 12, 0 C. 69, 5, 12 D. 68, 4, 12
Answer: D
A: The index and byte offset are exchanged.
B: This treats a byte address as a block number and loses the offset.
C: Integer division uses floor: 1100/16=68 remainder 12, not block 69.
D: There are 16 lines; block=floor(1100/16)=68, index=68 mod 16=4 and offset=12.
K03. An 8 KiB data cache has 64-byte blocks and four-way set associativity. How many sets does it have?
A. 128 B. 32 C. 512 D. 2048
Answer: B
A: 128 is the total number of lines; each set contains four of them.
B: Sets=8192/(64×4)=32.
C: This multiplies the line count by associativity instead of dividing it.
D: 8192/4 ignores the 64-byte block size, so it does not count sets.
K04. An initially empty direct-mapped cache has four lines and four-byte blocks. It reads one byte at addresses 0, 4, 0, 16, 0, in order, allocating on misses with no other accesses. How many hits occur?
A. 0 B. 2 C. 1 D. 3
Answer: C
A: The third access to address 0 hits before block 4 arrives.
B: The final access to 0 misses because address 16 replaced its block in line 0.
C: Blocks are 0,1,0,4,0; results are miss, miss, hit, miss, miss: exactly one hit.
D: Repeated addresses do not guarantee hits after intervening eviction.
K05. Hit time is 1 ns, miss rate is 8%, and a miss adds 50 ns after lookup. What is AMAT?
A. 4 ns B. 4.92 ns C. 51 ns D. 5 ns
Answer: D
A: Four is only the average miss-penalty contribution; every access also pays the 1 ns lookup.
B: This treats 50 ns as total miss time, but the question says it is extra after lookup.
C: Fifty-one is the time for a miss, not the average across hits and misses.
D: AMAT=1+0.08×50=5 ns; equivalently, 0.92×1+0.08×51=5.
K06. In a direct-mapped cache, the selected line has a tag equal to the address tag, but its valid bit is 0. What is the result?
A. Miss B. Hit C. Hit only when offset is zero D. The tag width must be changed
Answer: A
A: A hit requires both a matching tag and a valid line; validity is absent.
B: Tag equality alone does not make invalid data usable.
C: Offset selects a byte within a valid block; it cannot make an invalid line valid.
D: Tag width follows the cache organization; the lookup outcome does not change it.
Sources and scope
This is an introductory Computer Organization lesson, not full-topic or full-syllabus completion. The official syllabus establishes alignment; technical references check the underlying definitions. Teaching models, worked examples and practice are original. Verified 14 October 2026.
Sign in to keep your progress. Sign in