Description
1. Assume that main memory accesses take 70 ns and that memory accesses are 36% of all instructions. The following table shows parameters for a two-level cache memory.
| Size | Miss Rate | Hit Time | |
| L1 | 16 KB | 7.3% | 1.18 ns |
| L2 | 1 MB | 1.5% | 5.34 ns |
- What is the AMAT for the computer? (
- Assuming the L1 hit time determines the cycle times and a base CPI is 1.0 without any memory stalls, what is the total CPI?
2. In this exercise, we will examine how replacement policies impact miss rate. Assume a 2-way set associative cache with 4 blocks. Following table gives addresses for memory access.
-
- Assuming an LRU replacement policy, how many hits does this address sequence exhibit? (
- Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit?
- Simulate a random replacement policy by flipping a coin. For example, “heads” means to evict the first block in a set and “tails” means to evict the second block in a set. How many hits does this address sequence exhibit? Note: you should flip the coin yourself, not by computer.
You may find following table is useful：
| Block Address of memory | Hit/Miss | Evicted Block | Contents of Cache | ||||
| Set 0 | Set 1 | ||||||
| 1 | |||||||
| 3 | |||||||
| 5 | |||||||
| 1 | |||||||
| 3 | ||||||
| 1 | ||||||
| 3 | ||||||
| 5 | ||||||
| 3 |
3. Virtual memory uses a page table to track the mapping of virtual addresses to physical addresses. The following is a stream of virtual byte addresses used to access memory. Virtual addresses (in decimal): 12648, 45419, 46824, 16975, 40004, 12707, 52236
Assume 4 KB pages, a 4-entry fully associative TLB, and LRU replacement. If pages must be brought in from disk, increment to the next largest page number.
TLB:
| Valid | Tag | Physical Page Number |
| 1 | 11 | 12 |
| 1 | 7 | 4 |
| 1 | 3 | 6 |
| 0 | 4 | 9 |
Page Table:
| Valid | Physical Page Number |
| 1 | 5 |
| 0 | Disk |
| 0 | Disk |
| 1 | 6 |
| 1 | 9 |
| 1 | 11 |
| 0 | Disk |
| 1 | 4 |
| 0 | Disk |
| 0 | Disk |
| 1 | 3 |
| 1 | 12 |
Given the virtual address stream, and the initial TLB and page table states shown above, show the final state of the system. Also list for each reference if it is a hit in the TLB, a hit in the page table, or a page fault.
Repeat question (1), but this time use 16 KB pages instead of 4 KB pages.
What would be some of the advantages and disadvantages of having a larger page size?
Show the final contents of the TLB if it is 2-way set associative.
