CS 301 - Assembly Language

Meets MWF 3:30-4:30 PM
Room 106 Chapman Building
University of Alaska Fairbanks

CS F301-F01
3.0 Credits, Fall 2009
Prerequisite: CS 201 (Programming)

Instructor: Dr. Orion Lawlor
lawlor@alaska.edu, 474-7678
Office: 201E Chapman
Office Hours: 11:15-Noon (plus!)

Book Cover

Optional Textbook: Computer Systems, Bryant and O'Hallaron, Prentice Hall 2003

ADA Compliance: Will work with Office of Disabilities Services (203 WHIT, 474-7043) to provide reasonable accommodation to students with disabilities.

Course Website: http://www.cs.uaf.edu/2009/fall/cs301/

Course Goals and Requirements

By the end of the course, you will understand how your code actually executes on a real machine: from electrons on a semiconductor, to registers and binary arithmetic, to machine code and assembly, to C++ source code.  Understanding this process is useful for debugging code, and making all your code faster, smaller, and more secure. This course will focus on the middle levels of this chain of abstractions--you'll eventually learn much more about the lower levels (electrons, semiconductors, logic circuits) in EE 341 & 443, and about the higher levels (languages, compilers) in CS 331.  To understand this course, you will have to be familiar with all the basics of C or C++: variables, loops, arrays, pointers, structures, and functions. 

Calendar

First day of class: 3:30pm Friday, September 5. 
Last day to drop: Friday, September 18. 
Midterm: 3:30pm Wednesday, October 21. 
Last day to withdraw: Friday, October 30. 

Pre-Thanksgiving fun lecture:  Wednesday,  November 25.
Thanksgiving break (no class): Friday,  November 27.
Last day of class: Monday, December 14.
Final Exam: 3:15-5:15 PM Friday, December 18. 

Student Resources

Google, Rasmuson Library, Academic Advising Center (509 Gruening, 474-6396), Math Lab (Chapman Room 305), English Writing Center (801 Gruening Bldg, 478-5246).

Grading

Your work will be evaluated on correctness, rationale, and insight, not on successful regurgitation of random trivia.  Grades for each assignment and test may be curved upward by scaling.  Each homework and the midterm will then be clamped to the range [0%,100%]. Your grade is then computed based on four categories of work:

  1. HW: Homeworks and machine problems, to be distributed through the semester.

  2. PROJ: Two sizable class projects--big programs written in or relating to assembly.

  3. MT: Midterm Exam

  4. FINAL: Final Exam (comprehensive)

The final score is then calculated as:

TOTAL = 30% HW + 20% PROJ + 25% MT + 25% FINAL

This percentage score is transformed into a plus-minus letter grade via these cutoffs: A >= 93%; A- 90%; B+ 87%; B 83%; B- 80%; C+ 77%; C 70%; D+ 67%; D 63%; D- 60%; F. The grades “C-”, “F+”, and “F-” will not be given. “A+” is reserved for truly extraordinary work. Homeworks are due by midnight at the end of the day they are due.  

THE TEN COMMANDMENTS (OF CS 301)

  1. THOU SHALT ASK QUESTIONS IN CLASS WHEN THY PROFESSOR STOPS MAKING SENSE.

  2. THOU SHALT LEARN THE GENERAL PRINCIPLES, BY LEARNING THE CURRENT SPECIFIC IMPLEMENTATIONS.

  3. THOU SHALT COME TO CLASS, EVEN WHEN SLEEPY.  BUT THOU SHALT NOT SLEEP IN CLASS.

  4. REMEMBER THY BOOK, AND KEEP IT HANDY.

  5. THOU SHALT TURN IN THY ASSIGNMENTS BEFORE MIDNIGHT ON THE REQUIRED DAY, FOR  THOU SHALT RECEIVE A ZERO FOR LATE ASSIGNMENTS.

  6. THOU SHALT NOT START WORK ON THY ASSIGNMENTS 20 MINUTES BEFORE THEY ARE DUE. NOR EVEN 25 MINUTES. START THEM DAYS AHEAD OF TIME OR THOU SHALT BE VEXED!

  7. THOU SHALT CITE ALL THY SOURCES.  EVEN THOSE FROM THE INTERNET.

  8. THOU SHALT NOT COPY THY NEIGHBOR'S ASSIGNMENTS, NOR HIS TESTS.

  9. ALL THY ASSIGNMENTS AND TESTS SHALL BE THY OWN WORK.  ANY CHEATING OR PLAGARISM SHALL INCUR THE WRATH* OF THY PROFESSOR.

  10. THOU SHALT REGULARLY CHECK THE WEB.  I MAY POST ASSIGNMENTS THERE AT ANY TIME, FOR I AM THY PROFESSOR.  BUT I WILL GIVE YOU AT LEAST FIVE DAYS WARNING.

At my discretion, I may allow late work without penalty when due to circumstances beyond your control.  Department policy does not allow tests to be taken early; but in extraordinary circumstances may be taken late.  All classes and exams will normally be in the usual classroom at the usual time; in extraordinary circumstances, such as an infectious disease outbreak, classes may be held on Blackboard/Elluminate Live.

*The minimum penalty for plagiarism is that entire section of your grade.  For example, one copied homework problem will negate your entire homework score.  Note that without homework, the highest grade you can even  theoretically achieve is a C-! Even substantial reuse of other people's work is fine (and not plagiarism) if it is clearly cited; you'll be graded on what you've added to others' work. 

Course Outline (Tentative)

(September)

Data representation (Chapter 2.1)

  • Bits--counting, bitwise operations

  • Binary, decimal, hex, octal, and base conversion

Operations

  • Bitwise operations (Chapter 2.1)

    • AND, OR, XOR

  • "SIMD Within A Register" (SWAR), like Cohen-Sutherland clipping

  • Left & right shifting; finite integer range.

  • Extract integer into bits, reassemble from bits.

  • C Arithmetic operations (Chapter 2.2 & 2.3)

    • Unsigned addition.

    • Overflow.  Wraparound.  Range.

    • Subtraction: two's complement addition; signed numbers

    • Multiplication & acceleration via bit shifts

    • Division & acceleration via bit shifts

    • Modulus, implementation, acceleration via bit masks

  • Relative speed of each operation on various machines

  • Multiple-precision implementations of numerical operations

(October)

Machine Language / Instruction encoding (Chapter 3.1-4)

  • Concept of registers: stash stuff here

    • Register hardware implementation

    • Register uses: program counter, address, data, etc.

    • Concept of memory: big bunch o' bytes

  • Opcodes: do this now

  • Tiny example encoding: use of all above features in a tiny emulator

  • Hardware implementation of above encoding (preview of EE 341, CS 441)

  • Real example instruction sets

    • x86 (ancient variable-length CISC)

    • PIC (embedded RISC)

Assembly & disassembly (Chapter 3.15)

  • opcode mnemonics, naming a register, immediate values

  • Inline (__asm) assembly syntaxes; standalone (.S) assembly syntaxes

    • Operand order dyslexia

    • Labels, macros, etc.

    • Subroutine Linkage

  • .S files, Win32, gcc x86 inline assembly

(Midterm to Thanksgiving)

Memory

  • C pointers: p*, p++, p--, p[i]

  • Memory, files as big arrays of bytes

  • Integer representation as bits, bytes

    • Big endian (like PowerPC)

    • Little endian (like x86)

  • Structures (Chapter 3.9)

    • In-memory layout

    • Alignment & padding

    • sizeof, offsetof

  • Array indexing (Chapter 3.8)

    • 1D, 2D, 3D, nD

    • For structs

  • Global variables

Subroutines (Chapter 3.7)

  • Stack allocation: push & pop

  • Program Counter push & pop: call & return

  • Parameter passing, pass by reference

  • Calling conventions

  • Subroutine linkage and naming

Heap memory

  • Allocation & free (Chapter 10.9)

  • Garbage collection (Chapter 10.10)

Advanced control flow

  • Function pointers, implementation

  • C++ virtual method _vtable implementation

  • Dynamic linking (Chapter 7)

(Thanksgiving to End)

Performance and Optimization (Chapters 4, 5, and 9)

  • General optimization checklist

    • Timing and profiling

    • Algorithmic Optimization

    • Invariant hoisting, constant propagation

  • Memory Performance

    • Caching

    • Levels & performance of cache

    • Program transformations to improve memory performance

  • Concurrency

    • Hardware and Software Pipelining

    • Cost of branches

Floating point (Chapter 2.4, 3.14, and beyond)

  • Instructions

  • IEEE floating-point representation

    • Sign, exponent, mantissa

    • normalization, roundoff

    • Fun bitwise hacks (fast absolute value, log-base-2, float-to-int, etc.)

    • denormalized numbers, NaNs, and performance penalty

    • Operations, like floating-point addition

  • Interfaces

    • PPC sensibility

    • x86 stack horror

  • 4-vector of floating point numbers

    • x86 SSE & <mmintrin.h> intrinsics

    • Graphics card GLSL