CS 301 - Assembly Language

Meets MWF 3:30-4:30 PM
Room 106 Chapman Building
University of Alaska Fairbanks
 CS F301-F01 (#71215)
3.0 Credits, Fall 2006
Prerequisite: CS 201 (Programming)
 Instructor: Dr. O. Lawlor
ffosl@uaf.edu, 474-7678
Office: 210C Chapman
Office Hours: 2-3 MF (plus!)
Book Cover
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 accomodation to students with disabilities. Course Website (& links to Blackboard): http://www.cs.uaf.edu/2006/fall/cs301/
UNIX Machines: on nanook.uaf.edu, in Chapman lab, or Linux CDs available

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 code.  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 (compilers and languages) 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 subroutines. 

Calendar

First day of class: 3:30pm Friday, September 1. 
Last day to drop: Friday, September 15. 
Midterm: 3:30pm Friday, October 20. 
Last day to withdraw: Friday, October 27. 
Pre-Thanksgiving fun lecture:  Wednesday,  November 22.
Thanksgiving break (no class): Friday,  November 24.
Last day of class: Monday, December 11.
Final Exam: 3:15-5:15 PM Thursday, December 14. 

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. MT: Midterm Exam, to be held 3:30pm Friday, October 20. 
  3. FINAL: Final Exam (comprehensive), to be held 3:15-5:15 PM Thursday, December 14.
  4. EXTRA: The last 10 percentage points are given for "extra effort":
The final score is then calculated as:
TOTAL = 30% HW + 30% MT + 30% FINAL + EXTRA
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.  THOU SHALT RECEIVE A ZERO FOR LATE ASSIGNMENTS.
  6. THOU SHALT NOT START WORK ON THY ASSIGNMENTS 20 MINUTES BEFORE THEY ARE DUE.
  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 ONE WEEK.
At my discretion, I may allow late assignments without penalty when due to circumstances beyond your control.  Major assignments that are slightly late may be accepted at a 50% grade penalty (e.g., on-time grade: 80%; late grade: 40%).  Even substantial reuse of other people's work is fine (and not plagarism) if it is clearly cited; you'll be graded on what you've added to others' work.  Group work on substantial assignments (not homeworks, not tests) is acceptable if you clearly label who did what work; but I do expect a two-person group project to represent twice as much work as a one-person project.  Department policy does not allow tests to be taken early; but in extraordinary circumstances may be taken late.  All classes and exams will be in the usual classroom at the usual time.

Course Outline (Tentative)

Data representation (Chapter 2.1)
  • Bits--counting, operations
  • Binary, decimal, hex, octal, and base conversion
Operations
  • Bitwise operations (Chapter 2.1)
    • AND, OR, XOR
    • "SIMD Within A Register" (SWAR): Cohen-Sutherland clipping
    • Left & right shifting; finite integer range.
    • Extract integer into bits, reassemble from bits.
  • C Arithmetic operations (Chapter 2.2 & 2.3)
    • Addition: unsigned.  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
Instruction encoding (Chapter 3.1-4)
  • Tiny example encoding: use of all above features in a tiny emulator
    • 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
  • Hardware implementation of above encoding (preview of EE 341)
  • Real examples
    • PPC (clean 4-byte register-based RISC)
    • Java (clean 1-byte stack-based unboxed)
    • CIL (1 or 2-byte stack-based boxed)
    • x86 (hideous variable-length CISC)
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.
  • Win32, gcc x86 inline assembly
  • AT&T .S files
 Memory
  • C pointers: p*, p++, p--, p[i]
  • Memory, files as big arrays of bytes
  • Integer representation as bits, bytes
    • Big endian
    • Little endian
  • 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)
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
Advanced control flow
  • Function pointers, implementation
  • C++ virtual method _vtable implementation
  • Dynamic linking (Chapter 7)
Floating point (Chapter 2.4, 3.14, and beyond)
  • Instructions
  • IEEE floating-point representation
    • Sign, exponent, mantissa
    • normalization
    • Fun bitwise hacks (fast absolute value, log-base-2, float-to-int, etc.)
    • denormalized numbers, NaNs, and performance penalty
  • Operations
    • Addition
  • Interfaces
    • PPC sensibility
    • x86 stack horror
  • 4-vector of floating point numbers
    • x86 SSE & <mmintrin.h> intrinsics
    • PPC AltiVec
    • Graphics card GLSL