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: Find the width of the physical address.
The physical memory is 1 MB, which is
\[ 2^{20} \text{ bytes} \]
Since each word is 1 byte, every byte needs its own address, so the physical address is 20 bits wide, running from bit 19 down to bit 0.

Step 2: In a direct mapped cache, split the address into three fields.
The address is read as
\[ \text{Tag} \;|\; \text{Block Index (b bits)} \;|\; \text{Word Offset (w bits)} \]
where the offset picks a byte inside a block, and the index field, read as a binary number, gives the cache block number. Here \(b+w \le 20\), because the tag takes up whatever bits are left.
The cache size in bytes is the number of blocks times the block size, which is
\[ \text{Cache Size} = 2^{b} \times 2^{w} = 2^{b+w} \]
So to get the maximum cache size, we need to make \(b+w\) as large as possible.

Step 3: Convert the address to binary.
\[ 0\text{xA2C28} = 1010\ 0010\ 1100\ 0010\ 1000 \]
Written out with bit numbers from bit 19 (leftmost) to bit 0 (rightmost):
\[ \underbrace{1\,0\,1\,0}_{19-16}\ \underbrace{0\,0\,1\,0}_{15-12}\ \underbrace{1\,1\,0\,0}_{11-8}\ \underbrace{0\,0\,1\,0}_{7-4}\ \underbrace{1\,0\,0\,0}_{3-0} \]

Step 4: Locate the block index pattern in the address.
The block number is given as \(176\), and in binary
\[ 176 = 1011\,0000 \]
which needs at least 8 bits. Scanning the address bit string for this exact 8-bit pattern "10110000", it appears at bit positions 13 down to 6:
\[ \text{bits}[13..6] = 1\,0\,1\,1\,0\,0\,0\,0 = 176 \]
This is the only place in the 20-bit address where this 8-bit pattern occurs.

Step 5: Stretch the index field with the leading zero bits.
A binary number does not change value if we add zero bits above its leading 1. Looking above bit 13, the next bits are bit 14 = 0, bit 15 = 0, and bit 16 = 0, all zero, so we can pull all three into the index field without changing its value from 176.
Bit 17 is 1, so we must stop there, since including it would turn the value into something bigger than 176.
So the largest possible index field runs from bit 16 down to bit 6, which is
\[ 16 - 6 + 1 = 11 \text{ bits} \]
Check:
\[ \text{bits}[16..6] = 0\,0\,0\,1\,0\,1\,1\,0\,0\,0\,0 = 176 \]
So \(b = 11\).

Step 6: Find the word offset and the cache size.
The word offset field is whatever is below bit 6, that is bits 5 down to 0, giving
\[ w = 6 \]
So
\[ b + w = 11 + 6 = 17 \]
\[ \text{Cache Size} = 2^{17} \text{ bytes} = \frac{2^{17}}{2^{10}} \text{ KB} = 2^{7} \text{ KB} = 128 \text{ KB} \]
(The remaining \(20-17=3\) bits form the tag, which can be anything and does not affect the block number.)

Final Answer:
\[ \boxed{128} \]