Question

Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache, with block numbers starting from 0. The word with physical address 0xA2C28 is mapped to the cache block number \(176_{10}\). The maximum possible size of the cache (in KB) is ______.

Note: \(1\text{K}=2^{10}\) and \(1\text{M}=2^{20}\)

Hint:

Write 0xA2C28 as a 20-bit binary string, locate the 8-bit pattern for 176, then extend the index field upward through any leading zero bits to maximize block-index-plus-offset width.

Answer 1

Correct Answer: 128

Step 1: Turn everything into plain numbers.
1 MB of memory with 1 byte words means $2^{20}$ addressable bytes, so addresses run from $0$ to $2^{20}-1$. The given address in decimal is
$0\text{xA2C28} = 666664$.

Step 2: Write the direct mapped cache formula.
If the block size is $2^{w}$ bytes and there are $2^{b}$ blocks, then the block that holds address $A$ is
$\text{block} = \left\lfloor \dfrac{A}{2^{w}} \right\rfloor \bmod 2^{b}$
and the cache size is $2^{w}\times 2^{b}=2^{w+b}$ bytes. We want the biggest possible $w+b$ that still gives block number $176$.

Step 3: Try shrinking the word field.
Dividing $666664$ by increasing powers of two and dropping the remainder is the same as chopping bits off the right end of the address. Doing this, the smallest working offset turns out to be $w=6$, since
$\left\lfloor \dfrac{666664}{2^{6}} \right\rfloor = \left\lfloor \dfrac{666664}{64} \right\rfloor = 10416$

Step 4: Check 10416 against 176.
Write 10416 in binary: $10100010110000$. Its rightmost 8 bits read $10110000$, which is exactly $176$. So the last 8 bits already match block number 176.

Step 5: Stretch the modulus as far as possible.
Moving from those rightmost 8 bits of 10416 further left, the next three bits are all $0$, so $10416 \bmod 2^{9}$, $\bmod 2^{10}$, and $\bmod 2^{11}$ all still equal $176$. The bit right after that is a $1$, so $2^{11}$ is the largest power of two we can use here, meaning $b=11$.

Step 6: Add the offset back in.
Total bits used $=w+b=6+11=17$.
$\text{Cache Size} = 2^{17} \text{ bytes} = 128 \times 1024 \text{ bytes} = 128 \text{ KB}$
\[ \boxed{128} \]