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
(1) What is the AMAT for the computer?
(2) 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.
(1) Assuming an LRU replacement policy, how many hits does this address sequence exhibit?
(2) Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit?
(3) 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
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
(1) 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.
(2) Repeat question (1), but this time use 16 KB pages instead of 4 KB pages.
(3) What would be some of the advantages and disadvantages of having a larger page size?
(4) Show the final contents of the TLB if it is 2-way set associative.
