VE370 Homework 8 Solved

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 L1 16 KB L2 1 MB

Miss Rate 7.3% 1.5%

Hit Time 1.18 ns 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. n 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. (1)  Assuming an LRU replacement policy, how many hits does this address sequence exhibit?

    

2. (2)  Assuming an MRU (most recently used) replacement policy, how many hits does this

   address sequence exhibit? (10 points)

3. (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. (10 points)

You may find following table is useful:

Block Address of memory
1
3
5
1

Hit/Miss

Evicted Block

Contents of Cache

Set 0

Set 1

3 1 3 5 3

3. (50 points) 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 174 136 049

Page Table:

Valid Physical Page Number 15
0 Disk
0 Disk

16 19
1 11
0 Disk 14

0 Disk 0 Disk 13
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. (15 points)

(2) Repeat question (1), but this time use 16 KB pages instead of 4 KB pages. (15 points)

(3) What would be some of the advantages and disadvantages of having a larger page size? (5 points)

(4) Show the final contents of the TLB if it is 2-way set associative. (15 points)