Table of Contents
 |
[D]
Instructor: Ian Romanick - idr at freedesktop dot org
CS341A
Spring 2011, 3 credits
Wednesday, 6:00PM - 9:45PM
Room #202
Final date and time: June 15th, 5:30PM
Introduction to computer systems and hardware from a software developer's perspective. Topics include:
- Data representation
- Measurement of program performance
- Implementations of program flow-control
- Memory hierarchy and how to work with it to improve program performance
- Low-level optimization techniques
- Multithreading
Along the way the course will provide an introduction to assembly language and important tools such as debuggers and profilers.
The complete, up to date, course syllabus is also available on-line at the course website. The syllabus is available as both HTML and PDF.
The textbook for this course is:
Randal E. Bryant and David R. O'Hallaron. Computer Systems: A Programmer's Perspective, Addison Wesley, February 14, 2010. ISBN 978-0136108047. http://csapp.cs.cmu.edu/
Either the first or second edition of the book may be used. However, homework problems and readings will be assigned from the second edition. Students are responsible for making sure that they are reading the correct text and doing the correct problems.
Computer Systems: A Programmer's Perspective has a website that has a lot of useful, relevant information.
In addition to paper and writing utensils, each student will need a removable storage device. The storage device will be used to both bring documents and sample code home from class and bring homework completed assignments to class. The storage requirements should be minimal, so a small USB flash-drive (256MB) should be sufficient.
Each student's grade in this course will be primarily based on a total of seven single-week written homework assignments (from the textbook) and two two-week programming assignments. The remainder of the student's grade will be based on midterm exam and a final exam.
Programming assignments will be graded first and foremost on whether or not correct output is produced. The remaining points are based on the style of the program. This includes, but is not limited to, algorithm selection, code formatting, and naming conventions. A detailed rubric will be provided with each assignment.
| Programming Assignments | |
| Written homework assignments | 70 pts. |
| Programming assignments | 40 pts. |
| Subtotal | 110 pts. (~60%) |
| Tests | |
| Midterm | 25 pts. |
| Final Exam | 50 pts. |
| Subtotal | 75 pts. (~40%) |
| Total | 185 pts. (100%) |
Some assignments may carry extra-credit opportunities, but they will be infrequent.
| A | = | 93% and above |
| A- | = | 90%-92% |
| B+ | = | 87%-89% |
| B | = | 83%-86% |
| B- | = | 80%-82% |
| C+ | = | 77%-79% |
| C | = | 73%-76% |
| C- | = | 70%-72% |
| D+ | = | 67%-69% |
| D | = | 60%-66% |
I do not accept late work. If you miss a deadline, you will not earn the points for that activity. There are no make-up opportunities. If you are unable to attend class on the due date for a assignment, please submit it by e-mail before class.
Email communication will be through eCompanion. Be sure to check your Profile in eCompanion to update your email address so that you will receive course communications in a timely manner.
Leave food and drink outside the class. Disciplinary action will be taken toward any student found using the equipment in an inappropriate manner, taking cell phone calls or surfing the web. Disruptive, disrespectful or rude behavior will not be tolerated.
Presenting the writings, images or paraphrased ideas of another as one's own, is strictly prohibited at the Art Institute of Portland. Properly documented excerpts from other's works, when they are limited to an appropriate amount of the total length of a student's paper, are permissible when used to support a researched argument.
Students who are absent from all scheduled classes over a 14-day period (2 weeks) are subject to automatic attendance suspension - from the Institute, not just from this course. This means the student is administratively withdrawn from all courses and cannot attend classes or continue in the current quarter unless he/she successfully appeals for reinstatement. Students who anticipate violating the attendance policy should contact their Academic Advisor or Academic Department Director immediately to discuss options such as withdrawing from the Institute or navigating the appeals process.
Regular attendance is required for successful completion of this course. A student who misses the equivalent of three (3) classes will not pass this class. Exceptions for extenuating circumstances will be considered at the discretion of the instructor.
Schedule Adjustment period: The schedule adjustment period runs through the first week of the quarter (ending at 5 pm on Monday of Week 2). To add or drop a course, the student must complete a schedule adjustment form, available from the Registrar's Office. The signature of the student's academic advisor is required to make any changes to the student's schedule.
Withdrawal (W/WF): The student who withdraws from a course or from the program during the first nine weeks of the quarter will be assigned a "W" code for each course. The "W" code is not used in computation of the student's grade point average; however, "W" credits are counted toward total credits attempted. The student who withdraws from a course or from the program after the ninth week of the quarter will be assigned a "WF" code for each course. The "WF" code is the equivalent of a grade of "F" and is used in computing the student's grade point average. Students wishing to withdraw from The Art Institute of Portland must file an official status change form with the Registrar.
Free, one-on-one tutoring is available to you across all subjects through the Tutoring Center. The goal of tutoring is to help you learn and master skills so you can then confidently apply them on your own. Tutoring is helpful for students at all levels -- freshman through senior, whether you want to move from a failing to a passing grade or whether you want to cement an "A." Our tutors are faculty or, most often, fellow students who have excelled in the subject. You may find a tutor by visiting aidepartments.com or dropping by the Tutoring Center in Room 328 inside the Education Department. You may also contact Kathleen O'Brien (kpobrien@aii.edu) for tutoring for Liberal Arts classes or Mike Pacchione (mpacchione@aii.edu) for classes in the major.
It is AiPD policy not to discriminate against qualified students with a
documented disability in its educational programs, activities or services. If
you have a disability-related need for adjustments or other accommodations in
this class, contact the Dean of Student Services, Jason Clary, at 503-382-4710
or <jclary@aii.edu>.
The college provides confidential short-term counseling, crisis intervention, and community referral services through the Wellness Corporation Student Assistance Program (SAP) for a wide range of concerns, including relationship issues, family problems, loneliness, depression, and alcohol or drug abuse. Services are FREE and available 24 hours a day, 7 days a week, at 1.800.326.6142. If you have any further questions or are ever in need of immediate on-campus assistance, please stop by the Student Services Office on the 2nd Floor.
Lecture topics:
Course road-map
Crash course in computer math
Hexadecimal
Bits, bytes, words, oh my.
C strings
Big Enders vs. Little Enders
Bit-wise operations
Integer data encoding
Two's-Complement
Signed vs. unsigned
Math operations that you thought you understood
Multiplication and division using powers of two
Overflow / underflow
Modulo arithmetic
Homework assignments:
Read to recap this week:
Skim Computer Systems: A Programmer's Perspective chapter 1. Read sections 2.1, 2.2 and 2.3.
Do homework problems: 2.59, 2.60, 2.65 (or 2.66), and 2.80. Due at the start of class on April 13th.
Lecture topics:
A couple bits that I missed last week:
Shifting signed numbers
Overflow / underflow
Brief aside about fixed-point
Floating-point math
Represenatation
Rounding
Sources or error, measuring error
Non-associativity of floating point operations
Attempts to fight error
Homework assignments:
Read to recap this week:
Computer Systems: A Programmer's Perspective section 2.4.
Do homework problems: 2.86, 2.88 (compile code for x86-64 or "SSE math" to avoid using the 80-bit extended precision), 2.92, 2.94. Due at the start of class on April 20th.
Lecture topics:
Crash course in x86 assembly language, part 1
Registers
Instruction format
Data movement
Arithmetic operations
Logical operations
Homework assignments:
Read to recap this week:
Computer Systems: A Programmer's Perspective sections 3.2 through 3.6.
Lecture topics:
Crash course in x86 assembly language, part 2
Condition codes
Control flow
Procedures and stack frames
Arrays and crazy addressing modes
Complex data structures
Alignment restrictions
Packing / field ordering
Homework assignments:
Assignment #3: x86 assembly. Part 1 is due 5/11. Part 2 is due 5/25. unit_test.c, search.c, sort_test.c.
Read to recap this week:
Computer Systems: A Programmer's Perspective sections 3.7 through 3.10.
Lecture topics:
The CISC vs. RISC debate
Processor execution models
Sequential execution - the 70s
Pipelined execution - the 80s
Superscalar execution - the early 90s
Out-of-order execution - the late 90s
Homework assignments:
Prepare for the midterm: Notes
Lecture topics:
Branch prediction
Speculative execution
Memory prefetch
Principle of locality of reference
Memory hierarchy
Disk
Main memory
Cache
Dealing with the memory hierarchy
Amdahl's Law
Measuring program performance
Optimization techniques
What the compiler does (and how not to thwart it)
Avoiding branch misprediction penalties
Using the cache well
Homework assignments:
Read to recap this week:
Computer Systems: A Programmer's Perspective sections 6.1 through 6.4. We'll come back to 6.5 and 6.6 later.
Computer Systems: A Programmer's Perspective sections 5.1 through 5.6.
Assignment #4: Performance measurement and optimization. Due 6/15. mm.c (unoptimized matrix multiplication code) search_code.c (binary and linear search routines).
Lecture topics:
Single Instruction, Multiple Data - SIMD
"Little" SIMD architectures - SSE, etc.
"Big" SIMD architectures
Cray
GPUs
Using SIMD compiler "intrinsics"
Using vector arrays - OpenCL
Homework assignments:
TBD.
Lecture topics:
Memory management
Virtual memory
Memory protection
Translation look-aside buffer (TLB)
Getting memory from the operating system
Managing the "heap"
Parallel architectures
Symmetric multiprocessing (SMP)
Multi-core
Multi-threading
Cache coherency
Introduction to multithreading
Homework assignments:
TBD.