Set-Associative Cache Design (Numerical)

Given: Block = $4 \times 16$-bit words $=64$ bits $=8$ bytes
Cache capacity $=4096$ words $\times16$ bit $=65536$ bits $=8192$ bytes
Set size $k =2$ (2-way set-associative)
Cacheable main memory $=64K \times32$ bits $=65536\times4$ bytes $=256$ KB

1. Number of Blocks & Sets

$$N_{blocks}= \frac{\text{Cache words}}{\text{words per block}} = \frac{4096}{4}=1024 \text{ blocks}$$

$$N_{sets}= \frac{N_{blocks}}{k}= \frac{1024}{2}=512 \text{ sets}$$

$$Set\;index\;bits = \log_2 N_{sets}= \log_2 512 =9 \text{ bits}$$

$$Block\;offset\;(word) = \log_2 4 =2 \text{ bits (selects one of 4×16-bit words)}$$
If normalized to 32-bit CPU word: block $=2\times32$ bits $\Rightarrow$ offset $=1$ bit. Add byte offset $1$ bit if byte-addressed.

2. Address Interpretation

Main memory $64K\times32$ bits needs $16$ bits for 32-bit word address ($2^{16}=64K$). Equivalent $128K\times16$ bits needs $17$ bits for 16-bit word address.

Case A - 16-bit word address (most exam-expected):
Total 17 bits ($0$-$16$ for $128K$)

$$Tag\;bits = 17 - Set\;bits - Word\;offset =17-9-2=6 \text{ bits}$$

17-bit word address:
| Tag (6) | Set index (9) | Word (2) |
  16-11      10-2            1-0

If CPU byte-addressed: add $1$ bit byte offset inside 16-bit word:
Tag(6) | Set(9) | Word(2) | Byte(1) =18 bits total for $256$KB.

Case B - 32-bit word address (normalized):
Total $16$ bits, block $=2$ words

16-bit address:
| Tag (6) | Set (9) | Block offset (1) |
 15-10      9-1          0

With byte offset: Tag(6)|Set(9)|Word(1)|Byte(2) =18 bits ($Byte2$ because 32-bit =4 bytes).

3. Cache Structure Design

• Organization: $512$ sets $\times$ $2$ lines/set $=1024$ lines.
• Each line: Valid(1) + Dirty(1) + Tag(6) + Data(64 bits = 4×16 bits). Optionally LRU bit per set (1 bit for 2-way).
• Data RAM: $8192$ bytes, divided into $1024$ blocks of 8 bytes.
• Tag RAM: $1024 \times 6$ bits (or $512\times2\times6$ ).
• Size: Total tag storage $\approx 1024\times6=6144$ bits.

CPU Address (17-bit word) ---> [Tag 6] [Set 9] [W 2]
                                  |       |      |
                          +-------+ +-----+ +----+
                          |         |      |    word mux 4:1
                  Tag compare (×2)  --> set decoder 512 --> selected set's 2 tags
                          | HIT if tag match & Valid=1
                          v
                    Data out (selected 16-bit word or 32-bit word)

Operation: Set field selects one of 512 sets (both ways read in parallel); Tag field compared associatively with 2 tags in set; if match, Word offset selects one of 4 words in block (or 1 of 2×32-bit words). Replacement uses LRU per set.

For exam diagram show set decoder, two comparators, $2:1$ MUX and valid/LRU bits. Numbers: 512 sets, 2 lines/set, 8 bytes/block, 9+2+6 split.

Check: Cache ratio $= 8\text{KB} / 256\text{KB}=1/32$.