Consider a system with a processor and a 4 KB direct mapped cache with block size of 16 bytes. The system has a 16 MB physical memory. Four words P, Q, R, and S are accessed by the processor in the same order 10 times. That is, there are a total of 40 memory references in the sequence P, Q, R, S, P, Q, R, S, …….
Assume that the cache memory is initially empty. The physical addresses of the words are given below (1 word = 1 byte).
P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32
Which of the following statements is/are true?
Note: 1K=$2^{10}$ and 1M=$2^{20}$
This solution analyzes memory accesses in a direct mapped cache system to determine the correctness of given statements about cache hits and misses.
Cache Parameters Calculation
First, we determine the cache parameters based on the given information:
- Cache Size: 4 KB = $4 \times 1024$ bytes = $2^{12}$ bytes.
- Block Size: 16 bytes = $2^4$ bytes.
- Number of Blocks: Cache Size / Block Size = $2^{12} / 2^4 = 2^8$ blocks.
- Index Bits: Since there are $2^8$ blocks, 8 bits are required for the cache index.
- Offset Bits: Block Size is $2^4$ bytes, so 4 bits are required for the block offset.
- Physical Address Size: 16 MB = $16 \times 1024 \times 1024$ bytes = $2^4 \times 2^{10} \times 2^{10} = 2^{24}$ bytes. Thus, physical addresses are 24 bits long.
- Tag Bits: Total Address Bits - Index Bits - Offset Bits = 24 - 8 - 4 = 12 bits for the tag.
Address Breakdown
We break down the physical addresses to determine their tag, index, and offset components. The least significant 4 bits are the offset, the next 8 bits are the index, and the most significant 12 bits are the tag.
| Word | Physical Address (Hex) | Binary Address (24 bits) | Tag (12 bits) | Index (8 bits) | Offset (4 bits) | Index (Decimal) | Tag (Hex) |
|---|---|---|---|---|---|---|---|
| P | 0x845B32 | $1000 0100 0101 1011 0011 0010$ | $1000 0100 0101$ | $1011 0011$ | $0010$ | 179 (0xB3) | 0x845 |
| Q | 0x845B26 | $1000 0100 0101 1011 0010 0110$ | $1000 0100 0101$ | $1011 0010$ | $0110$ | 178 (0xB2) | 0x845 |
| R | 0x845B36 | $1000 0100 0101 1011 0011 0110$ | $1000 0100 0101$ | $1011 0011$ | $0110$ | 179 (0xB3) | 0x845 |
| S | 0x846B32 | $1000 0100 0110 1011 0011 0010$ | $1000 0100 0110$ | $1011 0011$ | $0010$ | 179 (0xB3) | 0x846 |
Memory Access Analysis
The sequence P, Q, R, S is accessed 10 times. The cache is initially empty. We analyze the behavior for each statement.
Statement A: Every access to P results in a cache miss
- P maps to Index 0xB3 with Tag 0x845.
- Access 1 (P): Cache is empty, so it's a MISS. Block for P is loaded into Cache[0xB3] with Tag 0x845.
- Access 5 (P): In the previous cycle, S (Tag 0x846) replaced P's block in Cache[0xB3]. Accessing P (Tag 0x845) now results in a MISS. P's block (Tag 0x845) is reloaded.
- This pattern repeats. P (Tag 0x845) always causes a MISS because the block at Cache[0xB3] is either empty, holds S's block (Tag 0x846), or is being reloaded by P itself after being evicted by S.
- Therefore, Statement A is TRUE.
Statement B: Every access to R results in a cache hit
- R maps to Index 0xB3 with Tag 0x845, same as P.
- Access 3 (R): P was accessed just before (Access 1), causing a miss and loading its block (Tag 0x845) into Cache[0xB3]. R finds this block. This is a HIT.
- Access 7 (R): Between Access 3 and 7, S (Tag 0x846) caused a miss and replaced P's block. However, the next access (Access 5) was P (Tag 0x845), which caused a miss and reloaded P's block (Tag 0x845) into Cache[0xB3]. R finds this block again. This is a HIT.
- This cycle ensures that Cache[0xB3] always contains Tag 0x845 when R is accessed.
- Therefore, Statement B is TRUE.
Statement C: Every access to Q results in a cache miss
- Q maps to Index 0xB2 with Tag 0x845.
- Access 2 (Q): Cache is empty, so it's a MISS. Block for Q is loaded into Cache[0xB2] with Tag 0x845.
- Access 6 (Q): The block for Q (Tag 0x845) is still present in Cache[0xB2] as no other address maps to this index. This is a HIT.
- Subsequent accesses to Q will also be hits.
- Therefore, Statement C is FALSE.
Statement D: Except the first access to S, all subsequent accesses to S result in cache hits
- S maps to Index 0xB3 with Tag 0x846.
- Access 4 (S): This is the first access to S. It causes a MISS and loads S's block (Tag 0x846) into Cache[0xB3].
- Access 8 (S): Before this access, P (Tag 0x845) was accessed (Access 5), causing a miss and loading P's block (Tag 0x845) into Cache[0xB3]. Accessing S (Tag 0x846) finds Tag 0x845, resulting in a MISS. S's block (Tag 0x846) replaces P's block.
- Subsequent accesses to S will always find P's block (Tag 0x845) there and cause a miss.
- Therefore, Statement D is FALSE.
Conclusion
Based on the analysis, statements A and B are true.
Important Questions from Cache Memory
In advanced microprocessors, cache memories are used to
- The transformation of data from main memory to cache memory is referred as:
- Which of the following statements are true?
A. In the write-through policy, only the cache is updated
B. In the write-back policy, both cache and main memory are updated
C. Cache coherence problems exist in multiprocessors with private caches because of the need to share writable data
D. Cache coherence problem can be solved by means of hardware-only scheme
Choose the correct answer from the options given below: A hierarchical memory system that uses cache memory has cache access time of 50 nano seconds, main memory access time of 300 nano seconds, 75% of memory requests are for read, hit ratio of 0.8 for read access and the write-through scheme is used. What will be the average access time of the system both for read and write requests ?
- For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block.
Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?
