DOC PREVIEW
Berkeley COMPSCI 152 - Quiz

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Computer Architecture and Engineering CS152 Quiz #3 March 19th, 2009 Professor Krste Asanovic Name:___Answer Key____ This is a closed book, closed notes exam. 80 Minutes 6 Pages Notes: • Not all questions are of equal difficulty, so look over the entire exam and budget your time carefully. • Please carefully state any assumptions you make. • Please write your name on every page in the quiz. • You must not discuss a quiz's contents with students who have not yet taken the quiz. If you have inadvertently been exposed to the quiz prior to taking it, you must tell the instructor or TA. • You will get no credit for selecting multiple choice answers without giving explanations if the instructions ask you to explain your choice. Writing name on each sheet ________ 1 Point Question 1 ________ 29 Points Question 2 ________ 16 Points Question 3 ________ 16 Points Question 4 ________ 18 Points TOTAL ________ 80 PointsProblem Q3.1: Page Size and TLBs 29 Points In this problem we will be analyzing two systems, both with 36-bit physical addresses, 44-bit virtual addresses, and 4-byte PTEs. One configuration is a single-level page table with 2KB pages and the second configuration is a hierarchical page table which supports both 2KB and 16MB pages. The following figure summarizes the hierarchical page table structure and indicates the sizes of the page tables and data pages (not drawn to scale): Problem Q3.1.A 8 Points For each of the proposed systems, how much space is needed for the page table for one user process if one 2KB data page is allocated? (4 points each) 2KB page => 11 bit offset Size of single level page table 235B = 32GB 244-11 = 233 VPNs Page Table Size = (# VPNs) ! (PTE size) = 233 ! 4 = 235 Size of hierarchical page table 40KB Page Table Size = (size of L1) + (size of 1 L2) + (size of 1 L3) = 4KB + 4KB + 32KB = 40KB Problem Q3.1.B 8 Points Let’s define the page table overhead (PTO) for a process to be (as in the problem set): Physical memory that is allocated to page tables PTO = Physical memory that is allocated to data pages For the hierarchical page table, which usage of data pages by a user process will result in the smallest possible PTO and which will result in the largest PTO? (4 points each) Smallest: Only 16MB pages used, consecutively allocated and enough to fill up memory Largest: One 2 KB page Note: The question did not ask you to compute the PTO. L1 Table (1024 PTEs, 4KB) L2 Table (1024 PTEs, 4KB) L3 Table (8192 PTEs, 32KB) Data Page (2KB) Data Page (16MB) Root ptr. (processor register)The processor has a fully-associative data TLB with 128 entries, and each entry can map either a 2KB page or a 16MB page. After a TLB miss, a hardware engine walks the page table to reload the TLB. The TLB uses a first-in/first-out (FIFO) replacement policy. We will evaluate the execution of the following program which adds the elements from three 4MB arrays and stores the results in a fourth 4MB array (note that, 1MB = 1,048,576 Bytes, the starting address of the arrays are given below): Assume that the above program is the only process in the system, and ignore any instruction memory or operating system overheads. The data TLB is initially empty. Problem Q3.1.C 5 Points How many TLB misses will the program incur with the single-level page table? The program will access 16MB of consecutive data, and it never reuses the same data. The problem implicitly asked about 2KB pages, but if 16MB pages were used correctly credit was given. For this problem, it doesn’t matter that the TLB has 128 entries, all that is important is that it has 4 or more entries. # misses = (total memory)/(page size) = 16MB/2KB = 224-11 = 213 = 8K misses Problem Q3.1.D 8 Points How many TLB misses will the program incur with the hierarchical page table using 2KB pages? What about if it uses 16MB pages? (4 points each) Misses with 2KB pages 8k Same as Q3.1.C. Page table doesn’t affect TLB miss rate. Misses with 16MB pages 2 Although all four arrays could fit in one page, the addresses are not correctly aligned, so the program’s data will span two pages. 2/4 points were given for 1 as a response. Additional credit was given if alignment assumptions were stated. double A[524288]; // 4MB array 0x00001800000 double B[524288]; // 4MB array 0x00001c00000 double C[524288]; // 4MB array 0x00002000000 double Y[524288]; // 4MB array 0x00002400000 for(int i=0; i<524288; i++) Y[i] = A[i] + B[i] + C[i];Problem Q3.2: Virtual Address Aliasing 16 Points A problem with virtually addressed caches is the aliasing problem. The aliasing problem happens when distinct virtual addresses refer to the same physical location (VA1 ! PA and VA2 ! PA, but VA1 " VA2). In lecture 14, a solution to this problem was presented for a direct-mapped cache. The solution was a software restriction that required if two virtual addresses want to address the same physical address, they must have the same virtual index bits. This prevents more than one of the aliases residing in the cache at a time. If VA1 is in the cache and VA2 is accessed, there will be cache miss because VA1 " VA2 and VA1 will be evicted and replaced with VA2, which happens to be mapped to the same physical address. For this problem (3.2) there is only one level of cache. Please explain your reasoning in your answers below. Problem Q3.2.A 6 Points With a virtually addressed (virtual index and virtual tag) cache, will the above solution work if the cache is 2-way set associative? Explain. The software solution will force VA1 and VA2 to have the same index, which implies they will be mapped to the same set. Since VA1 " VA2, their tags must differ, so they could each occupy a different way of the set. Having two copies in the cache is problematic. Problem Q3.2.B 10 Points Now consider a cache that is virtually indexed and physically tagged where: cache capacity page size ! associativity Insight: The above relation implies that the index will be contained within the page offset, which means an address will have the same index in its physical address as in its virtual address since the offset isn’t translated. Since both addresses map to PA, it means both VA1 and VA2 will have the same index and map to the same set. i) Do we still need the software restriction if the cache is direct mapped? Explain. (5 points) No. Because


View Full Document

Berkeley COMPSCI 152 - Quiz

Documents in this Course
Quiz 5

Quiz 5

9 pages

Memory

Memory

29 pages

Quiz 5

Quiz 5

15 pages

Memory

Memory

29 pages

Memory

Memory

35 pages

Memory

Memory

15 pages

Midterm 1

Midterm 1

20 pages

Quiz

Quiz

12 pages

Memory

Memory

33 pages

Quiz

Quiz

6 pages

Homework

Homework

19 pages

Quiz

Quiz

5 pages

Memory

Memory

15 pages

Load more
Download Quiz
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quiz and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quiz 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?