Final Exam Review Lecture

EECS 370 ?Introduction to Computer Organization ?Winter 2008 23. Final Exam Review ?Last Lecture!!! © Mahlke& Narayanasamy, 2008 The material in this presentation cannot be copied in any form without our written permission Prof. Scott Mahlke& Prof. SatishNarayanasamy EECS Department University of Michigan in Ann Arbor, USA Announcements boxshadowdwn Office hours ? Satish -Thursday, April 17th: 1pm to 3pm ? Chris -Thursday, April 17th: 10:30am to 12:30pm ? GSIs will hold office hours at the regular time slots as well The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 2/20 boxshadowdwn Midterm 2 re-grade requests due today ? Write a note and slip your midterm under Scott?s or my office door boxshadowdwn Pick up the homeworks from my office Finals boxshadowdwn Time ? April 18th(Fri), 7-9p ? We will start at 7pm sharp! boxshadowdwn Location The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 3/20 ? 9am section -DOW 1013 ? Noon section -CSE 1670 and 1690 Exam Format boxshadowdwn Style ?same as midterms ? Few simple questions, multiple choice or true/false questions ? Mix of easy/moderate/difficult problems boxshadowdwn Format ? Open book, open notes (No laptops!, must print out any material that you want to bring) The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 4/20 ? Covers all material for the semester boxshadowdwn What to bring ? Pencils, book, notes, calculator, homework solutions, old exams, and of course yer brain ? Most Important Slide -Topics You Can Ignore boxshadowdwn Don?t waste your time studying these, they won?t be covered on the exam ? Symbol/relocation table (linking) ? Lecture meeting 7 - Combinational logic - Sequential logic and timing diagrams The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 5/20 ? Lecture meeting 8 - Alu design, carry lookahead adders, floating point arithmetic, timing diagrams ? All of lecture meeting 27 - Parallel Processing Important Topics (1) boxshadowdwn Exam 1 (Instruction sets) ? Addressing modes ? RISC vs CISC, load-store vs memory ? Data organization (stack, heap, static), data alignment, structure sizing/alignment ? Stack frames, recursion The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 6/20 ? Caller/callee save registers ? Assembly code (both LC2k and MIPS) - Byte, half-word, word memory operations, sign extend vs zero extend ? Machine code Important Topics (2) boxshadowdwn Exam 2 (Datapath design, caches) ? Single cycle, multicycle datapath - Control signals, organization/operation - Performance calculation ? Pipelining - Organization - Data and control hazards (detection/forwarding) The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 7/20 - Performance calculation - Branch prediction ? Extending designs to support new instructions ? Caches - Address breakdown (tag, index, block offset) - Associativity - Locality principles - 3 C?s (compulsory, capacity, conflict) Important Topics (3) boxshadowdwn Post exam 2 ? Disks and ECC ? Virtual memory - Virtual to physical address translation - Page tables (single level, multilevel) - Translation lookaside buffers (TLBs) The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 8/20 - Virtual vs. physical caches - Performance Select Questions From Old Exams There are lots of important topics not The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 9/20 covered by these sample questions! ECC boxshadowdwn Data values are encoded with ECC using the following formula. ? P0 = odd_parity(D0, D1, D2) ? P1 = odd_parity(D0, D1, D3) ? P2 = odd_parity(D1, D2, D3) The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 10/20 boxshadowdwn Fix the error in the following values ? 1001 011 ? 1001 100 Virtual Memory: W02, #3 boxshadowdwn Given the following: 16 byte cache line, 64 byte, 2-way cache, 4KB page size, direct mapped TLB with 2 entries, physical memory of 16KB, page table stored in physical page 0 and can never be evicted, 20 bit, byte-addressable virtual address space. boxshadowdwn The page table initially has virtual page 0 in physical page 1, The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 11/20 virtual page 1 in physical page 2 and no valid data in other physical pages. The TLB holds information on both virtual pages 0/1. Virtual page 1 is the LRU. Virtual Memory (continued) Virt addr Virt page TLB miss? Page fault? Phys addr 0x00F0C 0x01F0C 0x20F0C The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 12/20 0x00100 0x00200 0x30000 0x01FFF 0x00200 Virtual Memory, W04, #8 boxshadowdwn Given the following: 32-bit addresses, byte addressable, 2KB page size, page table entries are 4 bytes, 3 level page table with 7 address bits devoted to each level boxshadowdwn (a) for 1-level page table, how many page tables are there if all addresses are used? boxshadowdwn (b) for 1-level page table, how much memory is used for the page tables if all addressed The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 13/20 are used? boxshadowdwn (e) for 3-level page table, how many page tables are there if all addresses are used? boxshadowdwn (f) for 3-level page table, how much memory is used for page tables if all addresses are used? Memory Systems: W04, #2 boxshadowdwn Given the following: 32 bit addresses, byte addressable memory, 4k page size, 2-way associative cache, 32 byte block size, write allocate, write back 2.2) Given the parameters above, what cache sizes will have The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 14/20 boxshadowdwn the property that the set index bits consist of bits that are not affected by the virtual to physical address translation Memory Systems: W04, #2 (cont) boxshadowdwn Given the following: 32 bit addresses, byte addressable memory, 4k page size, 2-way associative cache, 32 byte block size, write allocate, write back. Again you want your cache such that set index bits consist of bits that are not affected by the virtual to physical address translation boxshadowdwn 2.3) How would you maximize the total size of your cache? ? a) Use larger block size The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 15/20 ? b) Use smaller block size ? c) Block size makes no diff boxshadowdwn 2.4) How would you maximize the total size of your cache? ? a) Use lower degree of cache associativity ? b) Use higher degree of cache associativity ? c) Associativity makes no diff Memory Systems: W04, #2 (cont) boxshadowdwn Given the following: 32 bit addresses, byte addressable memory, 4k page size, 2-way associative cache, 32 byte block size, write allocate, write back. Again you want your cache such that set index bits consist of bits that are not affected by the virtual to physical address translation boxshadowdwn 2.7) How would you maximize the total size of your cache? The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 16/20 ? a) Use a larger page size ? b) Use a smaller page size ? c) Page size makes no difference Multi-cycle Datapath boxshadowdwn Suppose that you want to replace the no-op instruction in the LC- 2Kx instruction set with an I-type instruction called the indirect branch instruction : jmpi regB, regA (offset). The new jmpi instruction has the following semantics: If (regB!= 0) then PC = Memory [ regA+ offset] The University of Michigan © Mahlke & Narayanasamy - 2008 Else PC = PC + 1 boxshadowdwn Extend the LC-2kx multi-cycle data-path to support the jmpi instruction EECS 370: Introduction to Computer Organization 17/20 Multicycle LC2Kx Datapath The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 18/20 PC Memory Registerfile M U X M U M U X A L U M U X M U X I n s t r u c t i o n R e g addr data En En 1 0 A L U r e s u l t Equal The University of Michigan © Mahlke & Narayanasamy - 2008 19/41 Regen IRen X Sign extend R/WEn EnControl PCen MUXaddr Memen Memr/w MUXdest MUXrdata MUXalu2 MUXalu1 ALUop Single cycle, Multicycle datapaths: F03, #8 boxshadowdwn 8A. In an implementation of the single cycle datapath, the clock period is 10ns. The critical path is comprised of many components of the datapath including the ALU. To reduce costs, another implementation is done replacing the 2ns ALU with a 5ns one. If a program took 30s to run on the original implementation, how long will it take to run on the second? The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 20/20 boxshadowdwn 8B. In an implementation of the multicycle datapath, the clock period is 3ns. The datapath has a separate state for performing the ALU operation, in this state the only active component is the ALU. Again, the 2ns ALU is replaced with a 5ns one. If a program took 30s to run on the original implementation, how long will it take to run on the second? Performance: W02, #4 boxshadowdwn Given the following: Instruction breakdown, LW 25%, Add 20%, BEQ 20%, SW, 15%, Nand 20%; branches are taken 60% of the time, LW followed by immediate use occurs 20% of the time boxshadowdwn Consider 2 implementations of the LC2k, 1stpipelined implementation from Project 3, 2ndis multicycle design where it takes 3 cycles for LW/SW The University of Michigan © Mahlke & Narayanasamy - 2008 EECS 370: Introduction to Computer Organization 21/20 and 2 cycles for all other instructions. If the pipelined implementation runs at 200 MHz, what frequency must the multicycle run to complete the benchmark in the same amount of time? satish Microsoft PowerPoint - 370-final-review [Compatibility Mode]