Computational Linear Algebra

Introduction to Algorithms and Data Structures

Machine Architecture

HW2-Solution.v3.pdf-CSci 2021, Spring 2016 Homework Assignment

CSCI | 1933 | Introduction to Algorithms and Data Structures | homework | 

4 20 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Linux Organizes VM as Collection of “Areas” task_struct mm_struct pgd mm mmap vm_area_struct vm_end vm_prot vm_start vm_end vm_prot vm_start vm_end vm_prot vm_next vm_start Process virtual memory Text Data Shared libraries 0  pgd:  Page global directory address  Points to L1 page table  vm_prot:  Read/write permissions for this area  vm_flags  Pages shared with other processes or private to this process vm_flags vm_flags vm_flags 21 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Linux Page Fault Handling read 1 write 2 read 3 vm_area_struct vm_end vm_prot vm_start vm_end vm_prot vm_start vm_end vm_prot vm_next vm_start Process virtual memory text data shared libraries vm_flags vm_flags vm_flags Segmentation fault: accessing a non-existing page Normal page fault Protection exception: e.g., violating permission by writing to a read-only page (Linux reports as Segmentation fault) 22 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Today  Simple memory system example  Case study: Core i7/Linux memory system  Memory mapping 23 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Memory Mapping  VM areas initialized by associating them with disk objects.  Process is known as memory mapping .  Area can be backed by (i.e., get its initial values from) :  Regular file on disk (e.g., an executable object file)  Initial page bytes come from a section of a file  Anonymous file (e.g., nothing)  First fault will allocate a physical page full of 0's ( demand-zero page )  Once the page is written to ( dirtied ), it is like any other page  Dirty pages are copied back and forth between memory and a special swap file (or partition). 24 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Sharing Revisited: Shared Objects  Process 1 maps the shared object. Shared object Physical memory Process 1 virtual memory Process 2 virtual memory 25 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Sharing Revisited: Shared Objects Shared object Physical memory Process 1 virtual memory Process 2 virtual memory  Process 2 maps the shared object.  Notice how the virtual addresses can be different.

CSCI | 2021 | Machine Architecture | study guides | 4 20 Bryant and O’Hallaron  Co

Computer Science 2021 Spring 2016 Midterm Exam 2 (solutions) April 15th, 2016 Time Limit: 50 minutes, 12:20pm-1:10pm • This exam contains 6 pages (including this cover page) and 4 questions. Once we tell you to start, please check that no pages are missing. • Before starting the exam, you can ﬁll out your name and other information of this page, but don’t open the exam until you are directed to start. Don’t put any of your answers on this page. • You may use any textbooks, notes, or printouts you wish during the exam, but you may not use any electronic devices: no calculators, smart phones, laptops, etc. • You may ask clarifying questions of the instructor or TAs, but no communication with other students is allowed during the exam. • Please read all questions carefully before answering them. Remember that we can only grade what you write on the exam, so it’s in your interest to show your work and explain your thinking. • Students often ﬁnd that the quiz questions vary in difﬁculty. Your best strategy is usually to skim over all the questions, and then start working on the ones that look easiest. We also suggest that you leave time at the end to attempt every question, since we can’t give you any partial credit if you leave a question blank. • By signing below you certify that you agree to follow the rules of the exam, not to share exam material with other students before their exams, and that the answers on this exam are your own work only. The exam will end promptly at 1:10pm. Good luck! Your name (print): Your UMN email/X.500: @umn.edu Sign and date: Question Points Score 1 30 2 20 3 30 4 20 Total: 100 Computer Science 2021 Midterm Exam 2 (solutions) - Page 2 of 6 April 15th, 2016 1. (30 points) Y86-64 instruction design. In this question you’ll design the hardware for a new Y86-64 instruction in the sequential (SEQ) im- plementation. The new instruction is “ rrxchgq rA, rB”. It takes two registers as operands, and ex- changes (swaps) their contents. After the instruction has executed, rA has the contents that were in rB before the instruction, and conversely rB has the contents that used to be in rA. The instruction is two bytes long, with an opcode byte of 0xe3 and a register speciﬁer byte holding the identities of rA and rB. Fill in the following table with what operations need to be performed in each of the stages of the SEQ implementation when the instruction is rrxchgq . You may not need to put operations in every box. rrxchgq rA, rB Fetch icode:ifun ← M 1 [ PC ] rA:rB ← M 1 [ PC + 1] valP ← PC +2 Decode valA ← R [ rA ] valB ← R [ rB ] Execute Memory Write back R [ rB ] ← valA R [ rA ] ← valB PC update PC ← valP It would also be at least as correct to pass the values of rA and rB through valE and valM, like rrmovq does: this reduces the need for new connections between signals, but requires adding new control logic to skip the memory access in the memory stage. It’s also ﬁne to swap the A and B values during the decoding stage instead. Page 2

All courses in CSCI

Popular Documents