Cache and Virtual Memory Management

Posted on Nov 18, 2024 in Computers

Cache and Virtual Memory

Cache Analysis

Considering the data and the accompanying table for direct correspondence with caches and block size of 32 bytes, taken on a set of test programs where the percentage of references to instructions is 75%, answer the following:

1. Which system has a lower miss rate: a 16KB instruction cache and a 16KB data cache, or a unified 32KB cache?
2. Assume a cache hit takes one clock cycle, a miss costs 50 cycles, and a hit in a load or store requires an extra cycle in the case of the unified cache. What is the average memory access time in each case?

Solution:

1. Given that 75% of accesses are instructions, the remaining 25% will access data. The miss rate for separate 16KB caches is: (75% * 0.64%) + (25% * 6.47%) = 2.10%. The table indicates the miss rate for the unified 32KB cache is 1.99%, slightly lower.
2. The average memory access time can be calculated as follows:
   • Separate caches: (75% * (1 + 0.64% * 50)) + (25% * (1 + 6.47% * 50)) = 2.05 cycles
   • Unified cache: (75% * (1 + 1.99% * 50)) + (25% * (1 + 1 + 1.99% * 50)) = 2.24 cycles
   Although the separate cache system has a higher miss rate, the average memory access time is lower.

Virtual Memory

Consider a 2-level paged virtual memory system with a page size of 512 bytes. The system has 1MB of virtual address space and 512KB of physical address space, both byte-addressable. A single process is running. The system has a 2-way set associative cache with 4 sets. Each cache line is 4 bytes. The first-level cache contents are given at a specific moment in hexadecimal. Each translation table entry is 16 bits, with the most significant bit indicating residency (1 if resident, 0 if not). The remaining bits contain the physical page number. Second-level page tables are treated like other virtual pages.

Given the virtual address B8ED1 for a byte read, detail the translation process and the values obtained.

Approach:

• Virtual address space: 1MB = 2²⁰ bytes -> 20-bit virtual addresses
• Physical address space: 512KB = 2¹⁹ bytes -> 19-bit physical addresses
• Page size: 512 bytes = 2⁹ bytes -> 9-bit offset
• Virtual address decomposition: 3 bits for first-level page table index, 8 bits for second-level page table index, and 9 bits for offset.
• Physical address decomposition: 10 bits for physical page number and 9 bits for offset.
• Cache address decomposition: 15-bit tag, 2-bit index, and 2-bit offset.

Resolution:

The virtual address B8ED1 (1011 1000 1110 1101 0001) is decomposed into:

• First-level table index: 101 (5)
• Second-level table index: 11000111
• Offset: 011010001

The first-level table entry 5 contains AF71 (1010 1111 0111 0001). The most significant bit is 1, indicating residency. The physical page number is 1101110001.

The second-level table is accessed using the physical address 1101110001 concatenated with the second-level table index 110001110. This address is searched in the cache. The cache tag is 110111000111000, the index is 11 (3), and the offset is 10 (2). The cache entry contains IF3EB0D9. The required bytes are B0D9 (1011 0000 1101 1001). This is the second-level table entry, which contains the physical page number 0011011001. The final physical address is 0011011001 011010001 (1B2D1). This address is searched in the cache. The tag is 1b2d, the index is 00 (0), and the offset is 01 (1). The cache entry contains 6A, which is the data returned to the processor.

Memory Management

A virtual memory system has a 64-byte virtual address space, a 32-byte physical address space, and an 8-byte page size. It uses a 3-entry TLB and FIFO replacement. The cache is 6 bytes with 2 sets and 2 lines per set, using LRU replacement.

Given the virtual address sequence (1D, 21, 1C, 0C), describe the memory access process.

Approach:

• Virtual address space: 64 bytes -> 6-bit virtual addresses
• Physical address space: 32 bytes -> 5-bit physical addresses
• Page size: 8 bytes -> 3-bit offset
• Virtual address decomposition: 3 bits for page number and 3 bits for offset.
• Physical address decomposition: 2 bits for page number and 3 bits for offset.
• Cache address decomposition: 3-bit tag, 1-bit index, and 1-bit offset.

Resolution:

1D: TLB hit, cache miss. Page number 011 maps to frame number 01. Physical address is 01101. Cache tag is 011, index is 0, offset is 1. Data is fetched from memory and stored in cache.

21: TLB miss, page fault. Page number 100 is not in TLB. Page table entry is accessed, and a free frame (11) is allocated. TLB is updated, and data is fetched from memory and stored in cache.

1C: TLB hit, cache hit. Page number 011 maps to frame number 01. Physical address is 01100. Cache tag is 011, index is 0, offset is 0. Data is retrieved from cache.

0C: TLB miss, page fault. Page number 000 is not in TLB. Page table entry is accessed, and a free frame is allocated. TLB is updated, and data is fetched from memory and stored in cache.