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 2011
Prerequisite: CS 201 (Programming)

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

Utterly Optional Textbook:
Introduction to 80x86 Assembly Language and Computer Architecture
Richard Detmer
(2nd edition includes 64-bit)

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

ADA Compliance: I will work with the Office of Disability Services (208 WHITAKER BLDG, 474-5655) to provide reasonable accommodation to students with disabilities.

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, OS) in CS 331 & 321.  To understand this course, you will have to be comfortable with all the basics of C or C++: variables, loops, arrays, pointers, classes, and functions. 

Calendar

First day of class: 3:30pm Friday, September 2.  
No class (Labor Day): Monday, September 5.
Last day to drop: Friday, September 16. 
Midterm: 3:30pm Wednesday, October 19. 
Last day to withdraw: Friday, October 28. 

Pre-Thanksgiving optional lecture:  Wednesday,  November 23.
Thanksgiving break (no class): Friday,  November 25.
Last day of class: Monday, December 12.
Final Exam: 3:15-5:15 PM Friday, December 16. 

Student Resources

Academic Help: 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 technical correctness, rationale, and insight.  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, typically one batch per week throughout the semester.

  2. PROJ: Two sizable class projects--big programs written in, or relating to assembly, with a short in-class presentation.

  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. THOU SHALT TURN IN THY ASSIGNMENTS BEFORE MIDNIGHT ON THE REQUIRED DAY, FOR  THOU SHALT RECEIVE A ZERO FOR LATE ASSIGNMENTS.

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

  6. VERILY, THOU SHALT CLICK “RUN” IN NETRUN ONE THOUSAND TIMES OR MORE; BUT NOT ALL IN ONE NIGHT. TRUE INSIGHT DOES NOT COME FROM THE INFINITE MONKEY THEOREM.

  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 WEBSITE.  I MAY POST ASSIGNMENTS THERE AT ANY TIME, FOR I AM THY PROFESSOR. 

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 ice storm or 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

  • Bits--counting, bitwise operations

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

Arithmetic Operations

  • Bitwise operations

    • AND, OR, XOR

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

  • Left & right shifting; finite integer range (bit count).

  • Extract integer into bits, reassemble from bits.

  • C Arithmetic operations

    • Unsigned addition.

    • Overflow.  Wraparound.  Range.

    • Subtraction: two's complement addition; signed numbers

    • Bitwise multiplication & division

Table Driven Programming
  • Storing operations in a simple array

(October)

Machine Language / Instruction encoding

  • 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

  • Control flow flags

  • Reading real example instruction sets

    • x86 (ancient variable-length CISC)

    • ARM (embedded RISC)

Assembly & disassembly syntax

  • opcode mnemonics, naming a register, immediate values

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

    • Operand order dyslexia: AT&T/gnu is backwards!

    • Labels and assembler macros

    • Subroutine Linkage

  • .S files, Win32 versus gcc x86 inline assembly

Project 1 presentations in class

(Midterm to Thanksgiving)

Subroutines

  • Stack allocation: push & pop

  • Program Counter push & pop: call & return

  • Parameter passing, pass by reference

  • Calling conventions

  • Subroutine linkage and naming

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

    • In-memory layout

    • Alignment & padding

    • sizeof, offsetof

  • Array indexing

    • 1D, 2D, 3D, nD

    • For structs

  • Global variables

Heap memory

  • Allocation & free

  • Garbage collection

Advanced control flow

  • Function pointers, implementation

  • C++ virtual method _vtable implementation

  • Dynamic linking (Chapter 7)

(Thanksgiving to End)

Performance and Optimization

  • 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

  • Multiple-precision implementations of numerical operations

  • FPU 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

Project 2 presentations in class