Description

VE370 Introduction to Computer Organization
Homework 8

Submit a PDF file on Canvas

1. (20 points) 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? (10 points)
(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? (10 points)

2. (30 points) 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? (10 points)
(2) Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit? (10 points)
(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)
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. (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
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. (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)