Consider a system with 1 MB physical memory and a word length of 1 byte. The…
2026
Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache with a block (cache line) size of 64 bytes, with block numbers starting from 0. The word with physical address 0xA2C28 is mapped to the cache block number 176. The maximum possible size of the cache (in KB) for this configuration is ___________. (answer in integer)
Note: 1K=210 and 1M=220
Answer: 128 — In a direct-mapped cache, a byte-addressable physical address splits into a TAG field, a BLOCK-INDEX field, and a BLOCK-OFFSET field. The offset field has…
Attempted by 32 students.
Show answer & explanation
Correct answer: 128
In a direct-mapped cache, a byte-addressable physical address splits into a TAG field, a BLOCK-INDEX field, and a BLOCK-OFFSET field. The offset field has log2(block size) bits (here block size = 64 = 26 bytes, so 6 offset bits); the remaining higher-order bits form the block address. For a cache with N = 2k blocks, the block index of any address equals its BLOCK ADDRESS (address ÷ block size, integer division) taken modulo N -- which, since N is a power of two, is exactly the value formed by the block address's lowest k bits.
So the same block index survives as k grows only as long as each newly-included bit of the block address (bit k, k+1, ...) is 0; the moment a 1-bit is included, the index changes. The "maximum possible cache size" is therefore the largest N = 2k for which the block address's low k bits still equal the given block index -- i.e. up to (but not including) the next 1-bit above that index's own bits.
Application:
Convert the physical address to decimal: 0xA2C28 = 10×164 + 2×163 + 12×162 + 2×16 + 8 = 655360 + 8192 + 3072 + 32 + 8 = 666,664.
With a 64-byte block, the block address = ⌊666,664 ÷ 64⌋ = 10,416 (the low 6 bits of the physical address, 6 bits of 40 = 101000, form the byte-within-block offset and are dropped).
Write 10,416 in binary: 10,416 = 101000101100002 (14 bits), i.e. its 1-bits sit at positions 13, 11, 7, 5 and 4 (bit 0 = least significant).
For a cache with N = 2k blocks, the block index equals the block address's lowest k bits. Taking the lowest 8, 9, 10 or 11 bits of 10,416 all give the SAME value, 176 (= 101100002 = bits 4, 5 and 7 set), because block-address bits 8, 9 and 10 are all 0 -- it only changes at k = 12, where bit 11 (which is 1) enters and pushes the value up to 176 + 2048 = 2224.
So the largest k for which the block index stays 176 is k = 11, giving the maximum cache size N = 211 = 2,048 blocks.
With block size 64 bytes, cache size = 2,048 × 64 = 131,072 bytes. In KB (1K = 210): 131,072 ÷ 1024 = 128 KB.
Cross-check:
10,416 mod 2,048 = 176, which matches the given block index. Taking one more index bit (N = 212 = 4,096 blocks = 256 KB) would instead give block index 2,224 (not 176), confirming 131,072 bytes (128 KB) is indeed the maximum cache size consistent with this mapping.
Final answer: 128 KB.