For a cache of fixed capacity and block size, increasing the associativity:

Decreases the number of index bits and increases the tag bits

Increases the number of index bits and decreases the tag bits

Decreases the number of index bits and increases the tag bits

Which of the following are true of a write-back cache compared with write-through? (More than one may be correct.)

It needs a dirty bit per cache line

It generates less memory write traffic for repeated writes to the same line

Eviction of a modified line requires a memory write

It needs a dirty bit per cache line

It generates less memory write traffic for repeated writes to the same line

Main memory always holds the current value

Eviction of a modified line requires a memory write

Increasing the cache block size, with capacity held constant, tends to:

Reduce compulsory misses but eventually increase conflict and capacity misses

Reduce all three kinds of miss without limit

Have no effect on the miss rate

A fully associative cache of 2048 lines with a 32-byte block and a 32-bit address needs how many tag bits, and how many comparators for a lookup?

27 tag bits and 2048 comparators

11 tag bits and 2048 comparators

Cache, Main Memory and Secondary Storage

The memory hierarchy exists because fast memory is small and large memory is slow, and the whole subject is one bet: that a program's next access is near its last one. That bet has two halves worth naming, because questions test them separately. Temporal locality says a location used now will likely be used again soon, which is what caching a word buys. Spatial locality says its neighbours will be used too, which is what caching a whole block buys — and it is why block size appears in every address calculation. From there the chapter is arithmetic, and the arithmetic is easier than it looks provided the fields are always laid out in the same order: the block offset comes from the block size, the index from the number of sets, and the tag is whatever is left. Get those three in that order and every mapping question falls out, including the one result that surprises people: for a cache of fixed size, raising the associativity makes the tag longer, not shorter, because fewer sets means fewer index bits and the address has to be accounted for somewhere. The other half of the chapter is average access time, where the only real trap is the difference between a local and a global miss rate in a two-level hierarchy — an L2 that misses 20% of what reaches it is missing 2% of all accesses if L1 already caught 90%, and reading one number as the other is the standard way this calculation goes wrong.

The Address Split, and the Tag That Grows

Take one cache and vary only its associativity: a 32-bit address, a 64 KB cache and a 32-byte block, so the block offset is 5 bits and the cache holds 64 KB / 32 B = 2048 lines. The number of sets is 2048 divided by the associativity, the index is log₂(sets), and the tag is 32 minus the other two.

One 64 KB cache, 32-byte blocks, 32-bit address — under three mappings
Mapping	Sets	Index bits	Tag bits
Direct-mapped (1-way)	2048	11	16
4-way set associative	512	9	18
Fully associative	1	0	27

🎯 Why more associativity means a bigger tag

The address is 32 bits and every bit must be accounted for. Five go to the block offset regardless. The rest split between index and tag, and the index is only as wide as the number of sets — so grouping lines into sets of four cuts the sets from 2048 to 512, which removes two index bits, and those two bits do not vanish: they become tag bits. A fully associative cache has one set, no index at all, and the largest tag of the three. The practical consequence is the one the exam is really after: associativity reduces conflict misses but costs tag storage and comparator hardware — a fully associative cache must compare the tag against every line at once, which is why real caches stop at 4-way or 8-way rather than going all the way.

Average Access Time, and Local Against Global Miss Rates

For one level, AMAT = hit time + miss rate × miss penalty. With a 1 ns hit, a 5% miss rate and a 100 ns penalty, that is 1 + 0.05 × 100 = 6 ns. For two levels the same formula nests: AMAT = t(L1) + m(L1) × [t(L2) + m(L2) × t(memory)]. With a 1 ns L1 missing 10%, a 10 ns L2 missing 20% of what reaches it, and 100 ns memory: 1 + 0.10 × (10 + 0.20 × 100) = 4 ns — faster than the single-level case, which is the point of adding the level.

⚠️ A local miss rate and a global miss rate are different numbers

L2 in the example above misses 20% of the accesses that reach it — that is its local miss rate, and it is the number to put inside the nested formula. But only 10% of all accesses reach it at all, so L2 misses 0.10 × 0.20 = 2% of all accesses, and that is its global miss rate. Both are correct statements about the same cache and a question will give you one and ask about the other. The tell is in the wording: "L2 has a miss rate of 20%" almost always means local, while "2% of memory references go to main memory" is global. Substituting a global rate where the formula wants a local one understates the penalty badly, and the resulting AMAT is too good rather than obviously wrong — which is why the error survives a sanity check.

Write policies and what each costs
Policy	On a write hit	Cost
Write-through	Update cache and memory	Memory traffic on every write; needs no dirty bit
Write-back	Update the cache only, mark it dirty	Memory written once on eviction; needs a dirty bit per line

Secondary storage completes the hierarchy, and its access time is a sum of three unrelated things: seek time to move the head, rotational latency to bring the sector round, and transfer time for the bytes. Average rotational latency is half a revolution, so at 7200 rpm it is 0.5 × 60/7200 s = 4.17 ms — a figure worth knowing, since it is the term candidates most often omit. An 8 ms seek plus that latency plus 4 KB at 100 MB/s comes to about 12.2 ms, and the shape of the answer is the lesson: the transfer is a rounding error and the mechanics dominate.

Key takeaways

Lay the fields out in one order every time: block offset from block size, index from number of sets, tag is the remainder.
For a fixed cache size, raising associativity cuts index bits and so GROWS the tag — 16, 18, 27 bits for 1-way, 4-way, fully.
Associativity buys fewer conflict misses and costs tag storage plus comparators, which is why caches stop at 4- or 8-way.
AMAT = hit time + miss rate × miss penalty, and for two levels the same formula nests.
A local miss rate is of the accesses that reach that level; a global rate is of all accesses — 10% × 20% = 2%.
Write-through needs no dirty bit and writes memory every time; write-back needs one and writes on eviction.
Disk time is seek + rotational latency + transfer; average latency at 7200 rpm is 4.17 ms.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A 64 KB, 4-way set-associative cache has 32-byte blocks and a 32-bit address. How many tag bits does each line need?
Numerical answer — type the value.
Show answer
Answer: 18
A 32-byte block gives a 5-bit offset. The cache holds 64 KB / 32 B = 2048 lines, and 4-way grouping makes 2048 / 4 = 512 sets, so the index is log₂512 = 9 bits. The tag is 32 − 5 − 9 = 18 bits. The number to check yourself against is the direct-mapped version of the same cache, which has 2048 sets, an 11-bit index and a 16-bit tag: raising associativity moved two bits from the index to the tag. If your answer went down when associativity went up, the index and tag have been swapped.
For a cache of fixed capacity and block size, increasing the associativity:
1. Increases the number of index bits and decreases the tag bits
2. Decreases the number of index bits and increases the tag bits
3. Leaves both unchanged
4. Increases both
Show answer
Answer: B — Decreases the number of index bits and increases the tag bits
Capacity and block size fix the number of lines, so raising associativity can only reduce the number of sets — and the index is exactly wide enough to select a set. Fewer sets means fewer index bits, and since the address length is fixed, every bit removed from the index appears in the tag. Option A is the intuition most candidates arrive with, on the reasoning that "more associativity means more places to look, so a wider index"; the opposite is true, because associativity puts more lines inside a set rather than adding sets. Option D is impossible for a fixed address length — the three fields must always sum to it.
L1 has a 1 ns hit time and a 10% miss rate. L2 has a 10 ns hit time and misses 20% of the accesses that reach it. Main memory takes 100 ns. What is the average memory access time in ns?
Numerical answer — type the value.
Show answer
Answer: 4
The formula nests: AMAT = 1 + 0.10 × (10 + 0.20 × 100) = 1 + 0.10 × 30 = 4 ns. The 20% is L2's local miss rate — of the accesses that reach L2 — which is exactly what belongs inside the bracket. Treating it as a global rate and writing 1 + 0.10 × 10 + 0.20 × 100 gives 22 ns, and treating L2's penalty as replacing rather than adding to its hit time gives 3 ns; both are common. Note also that adding the level helped: a single-level cache with the same L1 and a 100 ns penalty would be 1 + 0.10 × 100 = 11 ns.
In the hierarchy of the previous question, what fraction of ALL memory accesses reach main memory?
1. 20%
2. 10%
3. 2%
4. 30%
Show answer
Answer: C — 2%
An access reaches main memory only if it misses both levels: 10% miss L1, and 20% of those miss L2, so 0.10 × 0.20 = 2%. That is L2's global miss rate, and it is a different number from the 20% local rate the question before was given. Option A is the local rate offered as if it were global, which is the single commonest error in this topic; option B is L1's miss rate, which is the fraction reaching L2 rather than memory. Knowing which of the two a question has handed you is most of the work — "misses 20% of the accesses that reach it" is local by construction.
Which of the following are true of a write-back cache compared with write-through? (More than one may be correct.)
1. It needs a dirty bit per cache line
2. It generates less memory write traffic for repeated writes to the same line
3. Main memory always holds the current value
4. Eviction of a modified line requires a memory write
Show answer
Answer: A — It needs a dirty bit per cache line; B — It generates less memory write traffic for repeated writes to the same line; D — Eviction of a modified line requires a memory write
A, B and D, which are three faces of one design. Write-back updates only the cache and marks the line dirty (A), so ten writes to the same line cost one memory write instead of ten (B), and that deferred write has to happen when the line is evicted (D). C is the write-through property, and it is exactly what write-back gives up — memory is stale until eviction, which is why a write-back cache complicates DMA and multiprocessor coherence: another agent reading memory directly may not see the latest value. That consequence, rather than the traffic saving, is usually what a question is driving at.
A disk rotates at 7200 rpm. Its average rotational latency is:
1. 8.33 ms
2. 4.17 ms
3. 2.08 ms
4. 7.2 ms
Show answer
Answer: B — 4.17 ms
One revolution at 7200 rpm takes 60/7200 s = 8.33 ms, and on average the sector wanted is half a revolution away, so the average latency is 8.33 / 2 = 4.17 ms. Option A is the full revolution — the worst case, not the average — and it is the commonest answer here. The reason the distinction matters is that rotational latency is usually the term candidates omit entirely: an 8 ms seek plus 4.17 ms of latency plus 0.04 ms to transfer 4 KB at 100 MB/s is about 12.2 ms, and dropping the middle term understates it by a third.
Increasing the cache block size, with capacity held constant, tends to:
1. Reduce compulsory misses but eventually increase conflict and capacity misses
2. Reduce all three kinds of miss without limit
3. Have no effect on the miss rate
4. Increase compulsory misses
Show answer
Answer: A — Reduce compulsory misses but eventually increase conflict and capacity misses
A larger block brings in more neighbours per miss, so spatial locality is exploited harder and compulsory misses fall. But capacity is fixed, so a larger block means fewer lines — fewer distinct places to hold data — and past a point conflict and capacity misses rise faster than compulsory misses fall. The miss rate therefore has a minimum at some intermediate block size, which is the U-shape this question is testing. Option B ignores the fixed-capacity constraint, which is the constraint the whole question rests on: nothing in a cache gets cheaper without something else getting dearer.
A fully associative cache of 2048 lines with a 32-byte block and a 32-bit address needs how many tag bits, and how many comparators for a lookup?
1. 27 tag bits and 2048 comparators
2. 16 tag bits and 1 comparator
3. 27 tag bits and 1 comparator
4. 11 tag bits and 2048 comparators
Show answer
Answer: A — 27 tag bits and 2048 comparators
Fully associative means one set, so there is no index at all: 32 − 5 = 27 tag bits. And with no index to narrow the search, the tag must be compared against every one of the 2048 lines simultaneously — 2048 comparators. Together those two numbers are the cost of full associativity and the reason it is confined to very small caches such as a TLB. Option B is the direct-mapped answer, where a single comparator suffices because the index has already chosen the only line that could match.