Question 1. Virtual Memory
Suppose we have a 32-bit virtual address space with a page size of 8K, and 4 bytes per page table entry.
1) Compute the number of pages in the virtual address space?
2) What is the maximum size of addressable physical memory in this system?
3) If the average process size is 8GB, would you use a one-level, two-level, or three-level page table? Why?
Question 2. Cache Coherence Transactions
Assume that you have the following multiprocessor system configuration:
• 4 CPU Cores (C0, C1, C2, and C3)
• MESI coherence protocol
• Each core has a 32 KB private L1 Cache (2-way set-associative, uses write-back scheme, with a 64 byte cacheline)
• Shared L2 between all cores (512 KB cache, 8-way set-associative, with a 64 byte cacheline)
Given the following sequence of memory accesses, write the state of each cacheline accessed in the respective core's L1 cache.
Hint: C0 performs a Load operation on address 0x00ffabc0. There will be a miss at both L1 and L2 (due to a cold cache). The requested cache line is fetched from DRAM and mapped to L2 and then on to L1. Thus, this access causes the cacheline to have an Exclusive (E) state in C0.
|
|
Core
|
Request Type
|
Address
|
C0 L1
State
|
C1 L1
State
|
C2 L1
State
|
C3 L1
State
|
|
1
|
0
|
Load
|
0x00ffabc0
|
E
|
-
|
-
|
-
|
|
2
|
0
|
Store
|
0x00ffabc8
|
|
|
3
|
1
|
Load
|
0x00ffabd4
|
|
4
|
1
|
Store
|
0x00ffabd8
|
|
5
|
1
|
Load
|
0x00afabc0
|
|
6
|
2
|
Load
|
0x00afabc8
|
|
7
|
1
|
Load
|
0x00bfabf0
|
|
8
|
0
|
Load
|
0x00ffabc0
|
Question 3. Paging
Assume we have a processor that support virtual memory with 4KB page size. The proces- sor uses one page table per program to track the mapping of virtual addresses to physical addresses, and has 28-bit virtual address. Assume we have 4-entry fully associative TLB, with the content specified in table below.
|
Valid
|
Tag
|
Physical Address
|
|
0
|
0x10
|
0x11
|
|
1
|
0xF
|
0x1F
|
|
1
|
0x3
|
0x13
|
|
1
|
0x6
|
0x16
|
Assume we start with the following series of accesses: 0x6D10, 0x9000, 0xF200, 0xF800, 0x8800, 0x0000, 0x3100
Also assume the following page table content:
|
Index
|
Valid
|
Physical Mapping
|
|
0
|
0
|
disk
|
|
1
|
1
|
0x11
|
|
2
|
1
|
0x12
|
|
3
|
1
|
0x13
|
|
4
|
0
|
disk
|
|
5
|
0
|
disk
|
|
6
|
1
|
0x16
|
|
7
|
1
|
0x17
|
|
8
|
1
|
0x18
|
|
9
|
0
|
disk
|
|
A
|
0
|
disk
|
|
B
|
0
|
disk
|
|
C
|
0
|
disk
|
|
D
|
0
|
disk
|
|
E
|
0
|
disk
|
|
F
|
1
|
0x1F
|
A. A Program Table Entries
Assume each entry in page table is 4-bytes. How many entries does the processor need to have in the page table for each program, and what is the total page table size? How about if the processor supports 16KB page size?
B TLB and Page Table States
Given the address sequence and the initial state of TLB and page table, what would be the final state of the TLB and page table? Assume ideal LRU replacement for the TLB. Specify what accesses hit on TLB, what addresses hit on page table, and what addresses are page fault.
C Two-Way Set-Associative TLB
Assume the TLB is 2-way set-associative instead of fully-associative. Given the address sequence and the initial state of TLB and page table, what would be the final state of the TLB and page table? Assume ideal LRU replacement for the TLB. Specify what accesses hit on TLB, what addresses hit on page table, and what addresses are page fault.
D Direct-Mapped TLB
Assume the TLB is direct-mapped instead of fully-associative. Given the address sequence and the initial state of TLB and page table, what would be the final state of the TLB and page table? Assume ideal LRU replacement for the TLB. Specify what accesses hit on TLB, what addresses hit on page table, and what addresses are page fault.
E Initial TLB and Page Table state
Assume the processor supports 16KB page size. Update the initial TLB state. Note that with 16KB page size, more bits are used for page offset, and less bits are used for tag in the TLB or for index in page table. Also note that TLB cannot have a entry which does not exist in the page table.
F Final TLB state
This question depends on the the results from part E. We are continuing on the assumption that the processor supports 16KB page size. What would be the state of TLB and Page table after running the given address sequence?
Discuss the advantages and disadvantages of a larger page size.