Assignment 1 — Solved

Four cache questions (10 marks): locality, a direct-mapped cache diagram, the total-bits calculation with an address split, and why set associativity lowers the miss rate. Every answer here is Module 7 material — the linked sections have the full derivations.

Q1 — Principle of locality 2 marks

Q1smallState the principle of locality for memory access. [2]

Q2 — Direct-mapped cache diagram 2 marks

Q2bigDiagram a direct-mapped cache with 256 blocks and 8-word (32-byte) block size. Assume a 32-bit memory address. [2]

Step 1 — work out the field widths.

Byte offset = $\log_2 4 = 2$ bits (4 bytes per word).
Block offset = $\log_2 8 = 3$ bits (which word inside the block).
Index = $\log_2 256 = 8$ bits (which of the 256 lines).
Tag = $32 - 8 - 3 - 2 = 19$ bits.

32-bit address split for a 256-line, 8-word-block direct-mapped cache.

Data capacity = $256 \times 32\text{ B} = 8\text{ KB}$ ; each line stores 1 valid bit + 19 tag bits + $8\times32 = 256$ data bits.

Step 2 — the diagram.

256-line direct-mapped cache, 8-word blocks. The 8-bit index picks one line (73 shown), the comparator checks its 19-bit tag against the address tag, Hit = valid AND tag-match, and the 3-bit block offset multiplexes one of the 8 words out.

Key parts to show for full marks: the 4-way address split (19 / 8 / 3 / 2), the array of 256 lines each holding V + tag + 8-word block, the comparator, the AND with the valid bit giving Hit, and the multiplexer selecting the word.

Direct-Mapped Cache →

Q3 — Total bits and address split 3 marks

Q3abig(a) How many total bits (tag + valid + data) are required for a direct-mapped cache with 512 KB of data capacity and 4-word (16-byte) block size? Assume a 32-bit memory address. [2]

① Block size = 4 words × 4 B = $16\text{ B} = 2^4$ bytes.

② Number of lines = $\dfrac{512\text{ KB}}{16\text{ B}} = \dfrac{2^{19}}{2^{4}} = 2^{15} = 32{,}768$ .

③ Field widths. byte offset = 2, block offset = $\log_2 4 = 2$ , index = $\log_2 2^{15} = 15$ .

④ Tag = $32 - 15 - 2 - 2 = 13$ bits.

⑤ Bits per line = valid 1 + tag 13 + data $(4\times32 = 128)$ = 142 bits.

\text{Total} = 2^{15}\times 142 = 32{,}768 \times 142 = \boxed{4{,}653{,}056\ \text{bits}}

≈ 4,544 Kibits ≈ 4.44 Mibits ≈ 568 KB of real SRAM — about 11 % more than the 512 KB of data, which is the overhead of the tags and valid bits.

Don't answer

512\text{ KB} = 4{,}194{,}304

bits — that counts only the data and drops the tag and valid bits the question explicitly asks for.

Total-Bits Calculation →

Q3bsmall(b) For the same cache, what are the index and tag of the address 0000 1111 0000 1111 0011 1100 0000 1100? [1]

Field	Bits	Binary	Decimal
Tag	13	`0000111100001`	481
Index	15	`111001111000000`	29632
Block offset	2	`11`	3 (word 3 of the block)
Byte offset	2	`00`	0

Q4 — Set associativity and miss rate 3 marks

Q4bigBriefly explain how a set-associative cache can reduce the cache miss rate. [3]

In a direct-mapped cache each memory block has exactly one line it may occupy ( $\text{line} = \text{block} \bmod \text{lines}$ ). Two blocks that are in active use but happen to map to the same line keep evicting each other, even while the rest of the cache sits empty. These are conflict (collision) misses.

An $n$ -way set-associative cache groups the lines into sets of $n$ lines. A block maps to one set ( $\text{set} = \text{block} \bmod \text{number of sets}$ ) but may be placed in any of the $n$ lines within that set; on a lookup all $n$ tags in the set are compared in parallel.

More placement choices per block (n lines per set instead of 1)

Colliding blocks can now coexist in the same set

no forced eviction while the set has a free/LRU-older line

A replacement policy (LRU) evicts the least useful block, not the only one

⇒ conflict misses fall ⇒ overall miss rate falls

Why associativity helps: it removes the artificial one-home-per-block restriction.

Example: blocks 12 and 20 in an 8-line cache both map to line 4 and thrash. In a 2-way, 4-set version they both map to set 0 but occupy its two different lines — both stay cached, and the misses disappear.

Organisation	Typical miss rate	Why
Direct-mapped (1-way)	10.3 %	every block has one home → conflicts
2-way set associative	8.6 %	two homes per set
4-way set associative	8.3 %	four homes per set
8-way set associative	8.1 %	close to fully associative

Set associativity gives a block several possible homes, so blocks competing for the same index no longer evict one another — conflict misses (and hence the miss rate) drop.

Mention the cost for the third mark:

n

parallel comparators, a wider multiplexer and replacement (LRU) state ⇒ more hardware and a slightly longer hit time. The gains also shrink quickly beyond 4–8 ways.

Associativity →

Assignment checklist

Locality = temporal + spatial, each with an example, and why the hierarchy works.
256 lines, 8-word blocks ⇒ tag 19 / index 8 / block offset 3 / byte offset 2; diagram needs comparator + valid AND + word MUX.
512 KB, 16 B blocks ⇒ 2¹⁵ lines, tag 13, 142 bits/line, total 4,653,056 bits.
Tag 0000111100001, index 111001111000000 for the given address.
Set associativity removes conflict misses — at the cost of comparators and hit time.