Final Exam Review
COMP 273 – Fall 2021
Slide deck number, roughly corresponding to lectures…
Introduction to Machine Structures
L1, PH 1.1-1.3
Textbook (Patterson and Hennessey) sections (see end of these slides wrt edition numbers)
• The 5 components of a PC
– Control + Datapath (the processor)
– Memory
– Input and Output devices
• The Big Picture
– High Level Language to Assembly
Language (the compiler)
– Assembly Language to machine code (the assembler)
• Technology trends
Number Representation
L2, Provided Notes, PH 2.4, 3.1-3.4
• Positional notation
• Conversion between bases 10 (decimal), 2 (binary),
8 (octal) 16 (hexadecimal)
• Conversion of fractions
• Signed numbers, 2’s complement notation
• Basic arithmetic, addition, subtraction, overflow – (multiplication and division covered more later)
• BCD, ASCII, Parity
Number Representation L3, PH 3.5
• IEEE Floating Point
– Normalization to get scientific notation
– Sign, biased exponent, fractional part (mantissa)
– Single, double, precision
– Special numbers
• +/- infinity, NaN
• denormalized numbers
– Addition, Multiplication
– Rounding of floating point numbers (discussed again in a later class)
Boolean Algebra and Digital Circuits L4, PH C.1-C.3
• Laws of Boolean algebra
• Algebraic simplification
• Truth tables / Don’t Cares
• Sum of Products / Product of Sums / PLA
• Design of simple arithmetic circuits – Digital circuit gates: AND, OR, NOT, XOR
– Half adder, Full adder, Subtraction
– Encoders, Decoders, Multiplexors (L5)
• Circuit Minimization, hard (not on exam)
More, and Sequential Circuits L5, C.7-C.8
• Decoder, Encoder, MUX, ALU
• Combinational versus sequential circuits
• Clocks, Timing Diagrams
(how inputs propagate to outputs)
• Sequential Circuits – SR latch,
– D latch,
– D flip-flop,
– Toggle Flip Flop
Registers and Memory L6, C.9
• Registers (shift registers, count registers) – Count up, count down, shift left, shift right
• Register File
• Memory – SRAM
– DRAM
– Tri-state buffers
– Synchronous RAM, DDR RAM
Multiplication and Division / FSMs L7, PH 3.3-3.4 (again), C.10
• Sequential multiplication circuit (two versions)
– Shift registers, and control logic
• Sequential division circuit
(two versions)
– Issues with signed division
• FiniteStateMachines
– Moore Machine vs Mealy Machine – Transition and output functions
– Traffic light example, and others
MIPS arithmetic and memory access L8, PH 2.1-2.3
• Assembly operands are registers • Addition and subtraction in MIPS
– add, sub
• The 32 MIPS registers
• Instructions with an immediate – addi
• Data transfer from registers to memory and vice-versa. – The “lw” instruction and its syntax
– The “sw” instruction and its syntax
• Byte-addressablememory
– Recall L13 wrt big/little endian!!
MIPS assembly decisions L9, PH 2.7
• Assembly operands are registers • If-elsestatementsusing:
– beq, bne, j
MIPS procedures L10, PH 2.8, B.5, B.6
• Memory layout and the stack
• Register conventions – Return address $ra – Arguments
– Return value
– Local variables
• jal, jr
• Nested procedures
$a0, $a1, $a2, $a3 $v0, $v1
$s0, $s1, … , $s7
• MIPS naïve mult example
– see sort example in PH 2.13 for more
Logical operations, shifts, arithmetic L11, PH 2.6
• Logical
– and, or, nor, andi, ori
• Shifts
– sll, srl, sra
• Masking bits and setting bits
• Image colour component swapping example
MIPS Instruction Representation L12-L13, PH 2.5, 2.10 (B.9, B.10)
• R-format,I-format,J-format
– rs, rt, rd, opcode, funct, shamt, immediate
• I-formatlimitationsolvedwithlui
• PC-relative addressing, J-format addressing
• Disassembly
• Pseudo-instructions vs True instructions – move, li, ror, nop (PH 3.9 discusses briefly)
• Organization of an assembly program, – Data declarations, System calls
• Little Endian (LSB (least significant byte) in lowest) VS Big Endian (MSB in lowest)
MIPS Integer Mult/Div & Floating Point L14, PH 3.3-3.5
• Integer Multiplication and Division – mul, mult, div, divu, mfhi, mflo
• Floating point addition subtraction multiplication – add.s, sub.s, mul.s, add.d, sub.d, mul.d, div.d
• Coprocessor commands, mfc1, mtc1
• Closer look at denormalized numbers
• Closer look at rounding modes – (up, down, truncate, even)
• Non-Associativity of floating point
• Fahrenheit to Celsius example, and A3
Assembling, Linking and Loading L15, PH 2.12 B.1-B.4
• Assembler – Directives
– Pseudo-instruction replacement – Creates object file
– Symbol Table, Relocation Table
• Linker (Link-Editor)
– Combines object files into a module – Resolves references
• Loader
• A detailed example
Steps to starting a program
I/O Polling and Interrupts L16, (PH 6.5-6.7, B.7,B.8)
• I/O background, speed mismatches between processor, memory, devices
• Memory-mapped I/O and polling costs
• MARS I/O simulation, Receiver, Transmitter
– Control (command) register, Data register
– Control strategy (ready bit, received/transmitted byte) – I/O example (keyboard and terminal)
• Interrupt I/O: save PC, jump to service routine, perform transfer, then return
• Portion of MIPS architecture for interrupts called “coprocessor 0”, instructions
and registers:
– Data transfer(lwc0, swc0) Move (mfc0, mtc0)
– Status $12 Interrupt enable,
Cause $13 Exception type, EPC $14 Return address
The Memory Hierarchy – Caches Part 1 L18, PH 5.1-5.3
• Levels of the memory hierarchy
• General behaviour as you go from level 1 to level n
(increased distance from processor)
• Caches
– Notion of cache size versus block size
– Direct-mapped cache: tag, index, offset
– Detailed example of accessing data in a direct-mapped cache
– Big picture: spatial and temporal locality
The Memory Hierarchy – Caches Part 2 L19, PH 5.1-5.3
• Block Size Tradeoff
• Types of Cache Misses
• Average Access Time
• Fully Associative Cache
• N-Way Associative Cache – A detailed example
• Block Replacement Policy – Random Versus LRU
• Multilevel Caches
• Cache write policy
– Write-thru versus write-back
• Cache in action java demos
Virtual Memory Part 1 L20, PH 5.4, 5.5
• Mapping Physical Memory to Virtual Memory – Page no. and offset
– Page Table
– Calculation of physical address – Page Table Base register
• Virtual Memory Problems
– Indirection to calculate physical address is slow
• Use a TLB (a cache of recently used translations)
– Not enough RAM
– Too much space used to store page tables • Multi-level page tables (not on exam)
Virtual Memory Part 2 L21, PH 5.4, 5.5
• The advantages provided by virtual memory
– translation, protection, sharing • The overall process:
– Check TLB (input: VPN, output: PPN) • hit: fetch translation
• miss: check page table (in memory)
– Page table hit: fetch translation
– Page table miss: page fault, fetch page from
disk to memory, return translation to TLB
– Check cache (input: PPN, output: data) • hit: return value
• miss: fetch value from memory
Single Cycle CPU Datapath L22, PH 4.1-4.3
• Design of a Processor
– Instruction set architecture
– Datapath Requirements
– Establish clocking
– Assemble datapath
– Determine control settings – Assemble control logic
• Registertransferlanguage
• Example with reduced MIPS instruction set
• Register-Register timing for one complete cycle
Single Cycle CPU Control L23, PH 4.4
• Critical Path of single cycle CPU
• Meaning of Control Signals
• Instruction Fetch Unit
• Control Signals for MIPS-Lite
– Truth table with don’t care
• Datapath during Branches and Jumps
Pipelining
L24-L25, PH 4.5, 4.7, 4.8
• The 5 stages of the datapath (laundry analogy) – Fetch, decode, execute, memory, writeback
• Latency vs Throughput
• Pipeline Hazards / Bubbles
– Structure (shared resources, e.g., memory)
– Control (e.g., branches)
– Data (e.g., need results of previous instruction)
• Pipeline stalls / bubbles
Pipelining
L24-L25, PH 4.5, 4.7, 4.8
• Optimizations and addressing hazards – Data forwarding / bypass
– Branch delay slot
– Interlock
– Load delay slot
– Instruction reordering – Loop unrolling
Strategy for Reviewing Material
• Review all slides and review your notes
• Review the examples we did in lectures
• Review the relevant portions of the textbook (especially for anything you find unclear!)
• Post your questions to MyCourses general discussion
Sections in 4th edition
• Review the noted sections marked at the top of the slides in
Patterson and Hennessey Computer Organization and Design
4th edition
1.1 1.2 1.3
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8
3.1 3.2 3.5
4.1 4.2 4.3 4.4 4.5 4.7 4.8
5.1 5.2 5.3 5.4 5.5
B.1 B.2 B.3 B.4 B.5 B.6
C.1 C.2 C.3 B.6 C.7 C.8 C.9
Book material will typically provide a less terse explanation than the slides / lectures, and may in some cases go into more depth.
2.10 2.12
B.9 (SPIM, not MARS) B.10
Sections in 5th edition
• Review the noted sections marked at the top of the slides in
Patterson and Hennessey Computer Organization and Design
5th edition
1.1 1.3 1.4 (1.2 also a nice review of big ideas)
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 3.1 3.2 3.5
4.1 4.2 4.3 4.4 4.5 4.7 4.8 5.1 5.3 5.4 5.5 5.6
2.10 2.12
A.9 (SPIM, not MARS) A.10
A.1 A.2 A.3 A.4 A.5 A.6
B.1 B.2 B.3 B.6 B.7 B.8 B.9
Book material will typically provide a less terse explanation than the slides / lectures, and may in some cases go into more depth.
(red highlights where section numbers differ in 5th edition)
(class schedule shows 6th edition sections which are also different)
A few other comments • MIPS reference sheet, know how to use it!
• Exam will have multiple choice questions – Some questions are very easy and
you will answer in seconds
– Other questions will be harder, but DON’T PANIC!
You have 4.5 minutes on average per question! • Unanswered questions are worth zero
– If you do not know the answer, then make an educated guess among the 4 responses.
COMP557 Computer Graphics
• Fundamental mathematical, algorithmic and representational issues in computer graphics
• Learn by doing! 4 assignments.
Homogeneous Coordinates, 3D Affine Transformations, Ray Tracing, Rasterization, Z-buffer, Illumination Models, Perspective Projection, Anaglyphs, Mesh Data Structures, Curves, Surfaces, Subdivision, Simplification, Texture Mapping, Shadows, Radiosity, Colour, Compositing
COMP559 Computer Animation
• Computational techniques for creating computer animation.
• Focus on physically based methods
• Learn with small interactive assignments and mini-project
ODEs, Numerical Integration, Stability, Mass-spring Systems, Constraints and Stabilization, Collision Detection, Collision Response, Contact LCPs, Motion Capture, Character Animation, Fluid Simulation (SPH and Eulerian), 3D Rigid Motion, IK, Elastic Solids
DON’T FORGET
TO DO COURSE
EVALUATIONS
…official evaluations, but also consider ratemyprofessors.com
4 on Scale of 1 to 5? If 1 is 0% and 5 is 100%…
75% B+
(just barely)
Reducing discrimination through norms or information [Boring, Philippe 2017]
a) Simply reminding people not to be biased when filling out their teaching evaluations seems not to have an effect.
b) If as well as the reminder, you inform people that that bias really does exist, in their exact setting, then does help reduce the resulting bias.