Course Review for Final Exam
CS 301 Lecture, Dr. Lawlor
The final exam is Friday, Dec 16, at 3:15pm, in the usual classroom (Chapman
106). It's nominally two hours long, but it'll actually be about the same length as the midterm.
Things you should know for the final exam are all contained in the lecture notes and homeworks:
- Basics of assembly language: pre-midterm review stuff
- bits and bytes
- size of char, short, int, long, and pointers
- Bitwise operations: & | ^ ~
- what they're useful for: SIMD
- how to use them to simulate branch
operations: ret=(mask&then) | (~mask&else);
- How classes get laid out in memory:
- size in bytes of a class
- byte offsets from a pointer to the start of the class
- padding for alignment
- preserved and scratch registers for x86-64
- how the stack works, especially around a function call (what happens to the stack at a "ret", for example)
- how flags work:
- how "cmp rcx,4" and "jle somewhere" actually work together
- how to detect overflow
- how to do multi-precision operations
- existence of and purpose of machine code
- Floating-point numbers:
- SSE instructions, like "addss" and how to use them to solve float problems.
SSE instructions, like "addps", and how to use them to solve bigger
problems. Basically unroll loop (i+=4) and translate. But be
careful of alignment!
- Bits used to represent the sign (1 bit), exponent (8 bits), and mantissa (23 bits, plus implicit 1)
- Floating-point roundoff:
- big + small == big ?!
- small + big - big == 0 ?!
- Fixes for roundoff:
- use a bigger datatype (replace float with double)
- switch to integer (but watch out for overflow!)
- rearrange floating-point operations to do all small numbers first, then the bigger ones
- Performance impact of denormal and NaN floats
- High performance computing:
- How to time your code, and the vagaries of timers (such as noise and quantization).
- Just a stopwatch or "time" is enough for +- 1 second. Use "_ftime" or "gettimeofday" for higher precision.
- Repeat the code often enough that you can actually measure its speed (not just timing the timer).
- Automate performance analysis as much as possible, giving median times in nanoseconds per useful operation, with error bars.
- Compiler hints, like "inline" and "const", or ways to scare the compiler, like "extern" or "volatile"
- Algebraic rearrangement, like replacing x=x*x*x*x*x*x*x*x; with x=x*x; x=x*x; x=x*x;
- Strength reduction, like replacing integer x%2n with x&(2n-1); or floating point divide "a/b" with multiply "a*(1.0/b)" .
- Removing branches, like replacing "if (m) x=a; else x=b;" with bitwise branch like "x=(a&m)|((~m)&b);".
- Dynamic translation: sticking together new machine code bytes at runtime.
- Other roads to assembly language
- PowerPC assembly language:
- Instructions always 32 bits long. (So it takes two instructions to load a 32-bit value).
- Registers named "r3" and such.
- Three-operand addition (dest=src1+src2).
- Embedded programming, like PIC microcontrollers:
- Set bits of output register to control voltage on output pins (LEDs, servos, etc.)
- Code is typically structured as an infinite loop!
- Biological computers (the computer that's made out of goo)
- Typically trillions or more components, operating at terahertz
- But components move randomly, meaning you need to make friends with entropy.