Computer Science 231 - Introduction to Computer Organization - Section 1 - Fall 2009

This document can be found in http://www.cs.clemson.edu/~mark/231.html
The department syllabus can be found in http://www.cs.clemson.edu/html/syllabi/cpsc231.shtml

TENTATIVE

Objectives: Study machine architectures on which algorithms are implemented and identify architectural support for high-level languages, programming environments, and applications.

Major Concepts:

a data structure model:
- basic representation of data, such as integers, logic values, and characters;
- homogeneous data structures, such as arrays and strings;
- heterogeneous data structures, such as floating point numbers and records;
- accessing of data structures, involving pointers and values, field extraction;
- addressing mode support for particular data structures.
a machine model:
- processor, memory, and I/O;
- processor data paths and register transfers;
- instruction cycle of fetch/execute and interrupts;
- bus interconnections;
- relative speeds and capacities of components;
- performance metrics, such as storage space, memory traffic, execution time.
a programming language translation model:
- compilation versus interpretation;
- steps: compilation, conditional assembly, macro processing, assembly, link, load, execute;
- code generation issues demonstrating the relationship between HLL and machine code.
a system model:
- run-time environment, including stack frame and heap support;
- procedure call support, including such issues as parameter passing and register conventions;
- I/O support, such as level of intelligence in controllers and synchronization;
- operating system support, including memory protection and interrupts;
- sharing and reentrancy;
- virtual memory support.

Prerequisite: CPSC 102 or CPSC 210 or equivalent

Course Type: Required for BS CS, BS CIS, and CS minor.

Meetings: 1:25-2:15 MWF, McAdams 114
Late Arrival: Please wait up to 15 minutes if I am late to class.

Required Textbook: R. Paul, SPARC Architecture, Assembly Language Programming, & C, Prentice Hall, 2nd ed., 2000.

Instructor: Mark Smotherman, 209 McAdams Hall, mark@cs.clemson.edu, 656-5878
office hours: 2:30-4:30 MW; also email or call since I'm often available at other times

Labs:

Lab TA - Tacksoo Im (tim@cs.clemson.edu)

Grading:

Components of the final grade:
- Programs (5 at 4% = 20%)
- Lab grade (20% - also see below)
- In-class exams (5 at 10% = 50%)
- Final exam (10%)
A ten-point grading scale will be the default, but the individual letter grade bands may be widened at the end of the semester to obtain the final letter grades. (However, note that this widening is not guaranteed, so do not count on it to improve your grade.)
Lab attendance and participation is vital. Thus a failing grade in lab will result in a failing grade in the course regardless of your exam and program averages.

Drop Days: Last day to drop without record is Sept. 1; last day to drop without final grades is Oct. 9.

Programs:

Programs must run on department SPARC Solaris systems.
Unless otherwise noted, programs are to be submitted electronically via the handin command.
Programs are due by midnight on due date.
Programs that do not assemble or compile correctly will be limited to a maximum score of 25 out of 100 (score will be less when it is clear that the program logic cannot fulfill the assignment).
Programs that work correctly for a few test cases but not for all reasonable inputs will not be given full points. It is your responsibility to code correctly for reasonable inputs.
Late programs will be accepted but 10 points will be deducted for each day late. Thus a program that is 4 days late will have a maximum possible point total of 60.
Unless otherwise noted, programming is to be individual work. Do not discuss the solution to an assignment with anyone else (either a class member or someone else). If you have questions, ask me in person or by email.

Academic Integrity: "As members of the Clemson University community, we have inherited Thomas Green Clemson's vision of this institution as a `high seminary of learning.' Fundamental to this vision is a mutual commitment to truthfulness, honor, and responsibility, without which we cannot earn the trust and respect of others. Furthermore, we recognize that academic dishonesty detracts from the value of a Clemson degree. Therefore, we shall not tolerate lying, cheating, or stealing in any form."

from the Academic Integrity Policy:

Any breach of the principles outlined in the Academic Integrity Statement is considered an act of academic dishonesty.
Academic dishonesty is further defined as:
- Giving, receiving, or using unauthorized aid on any academic work;
- Plagiarism, which includes the copying of language, structure, or ideas of another and attributing the work to one's own efforts;
- Attempts to copy, edit, or delete computer files that belong to another person or use of Computer Center account numbers that belong to another person without the permission of the file owner, account owner or file number owner;
All academic work submitted for grading contains an implicit pledge and may contain, at the request of an instructor, an explicit pledge by the student that no unauthorized aid has been received.
It is the responsibility of every member of the Clemson University community to enforce the Academic Integrity Policy.

See also the department statement.

Specifically, for this class: Publicly-available code or other material may be freely used if appropriately attributed. Each student is responsible for protecting his or her files from access by others. Work that is essentially the same and submitted without proper attribution is considered to be a violation of the academic integrity policy by all those knowingly submitting the same work, regardless of who actually did the work. (That is, the giver is just as guilty as the receiver.)

Disability Access: It is University policy to provide, on a flexible and individualized basis, reasonable accommodations to students who have disabilities. Students are encouraged to contact Student Disability Services to discuss their individual needs for accommodation.

Note: The instructor for this course reserves the right to change this syllabus. Announcements will be made in class if and when such changes occur.

Topics

- introduction, computer system components, prefixes for time, speed, and capacity, assembly [ notes]
- overall guides
  - How Stuff Works - how PCs work
  - PC Tech Guide
- input/output
  - input and output devices
- processor
- memory
  - How Stuff Works - RAM
  - Tom's RAM Guide
- storage
- game consoles
  - Sony PlayStation 3 design / 3.2 GHz PPC Cell processor / 550 MHz NVIDIA RSX gpu
  - Xbox 360 / 3.2 GHz PPC with 3 cores (each with a VMX-128 SIMD unit) / 500 MHz ATI gpu
  - Nintendo Wii (Revolution) / 729 MHz PPC cpu / 243 MHz ATI gpu
- motherboard example
  - Intel P6 motherboard
- ... and if you have a link to a helpful site for other 231 students, please email me with the URL - thanks!
- von Neumann machine design, machine types, fetch-execute cycle [ notes]
- ENIAC - the first electronic digital computer (1943-1946)
- John von Neumann (1903-1957)
- Burks, Goldstine, and von Neumann, "Preliminary discussion of the logical design of an electronic computing instrument," 1946 (though some also assign credit for the idea of the stored program computer to J. Presper Eckert and John Mauchly)
- von Neumann machine characteristics
  - random-access, one-dimensional memory (vs. sequential memories)
  - stored program, no distinction between instructions and data (vs. "Harvard architecture" with separate instruction and data memories)
  - binary, parallel by word, two's complement (vs. decimal, serial-by-digit, signed magnitude)
  - instruction fetch/execute cycle, branch by explicit change of PC (vs. following a link address from one instruction to the next)
  - three-register arithmetic -- ACC, MQ, MBR
- von Neumann's ideas were implemented in Princeton IAS machine (1946-1952)
  - JvN standing in front of IAS machine
  - another view of IAS machine
  - word size of 40 bits, binary, two's complement
  - 20-bit, 1-address instruction format (8-bit opcode, 12-bit address)
- multiple derivative machines (see list at wikipedia)
- m4 macro processor [ notes]
- example multiply-accumulate macro definition
- example of using a macro expansion counter
- assembler, m4 macros showing function of assembler [ notes]
- load/store machine simulator program in C
- assembler.m macro file for simulated load/store machine
- sample source.m file for simulated load/store machine
- memory addressing modes [ notes]
- review for first exam
- study guide
- exam from Fall 2007
- exam from Fall 2008 (with answers)
- first exam
- introduction to SPARC architecture and assembly language [ comparison, notes]
- introduction to gdb and example [ notes]
- branching and control structures in SPARC assembly, common assembly errors [ notes, list]
- printf statements for debugging [ notes]
- binary representation and logic, number conversions [ notes]
- binary arithmetic (addition and subtraction), extended precision [ notes]
- binary arithmetic (multiplication and division) [ notes]
- shifts, field extraction and insertion, conversion of ASCII digit string [ notes]
- data in memory, endianness, alignment [ notes]
- review for second exam
- study guide
- exam from Fall 2007
- exam from Fall 2008 (with answers)
- second exam
- memory stack and stack frames [ notes]
- more on pointers in C [ notes]
- 1- and 2-dimensional arrays [ notes]
- subroutine calls, parameter passing, SPARC register windows, procedure calls in SPARC [ notes]
- example subroutines [ sum and print, string length and capitalize]
- multiple entry points [ notes]
- instruction formats, 32-bit constants [ notes]
- non-stack variables [ notes]
- example subroutines [ pass by value and reference]
- review for third exam
- study guide
- exam from Fall 2007
- exam from Fall 2008 (with answers)
- third exam
- separate assembly and linking [ notes]
- example makefile and separate assembly components [ notes]
- see also notes on software development
- compilation model, compilation vs. interpretation, static linking vs. dynamic linking, loading [ notes]
- D. Novillo, "From Source to Binary: The Inner Workings of GCC," Red Hat Magazine, December 2004
- GCC internals manual
- example RTL
- scope of variables [ notes]
- command line parameters [ notes]
- application binary interface (ABI) [ notes]
- review for fourth exam
- study guide
- exam from Fall 2007
- exam from Fall 2008 (with answers)
- fourth exam
- I/O devices: keyboards, monitors, disk, etc. [ notes]; RAID storage
- interrupts, interrupt-driven I/O [ notes]
- buffering, file systems [ notes]
- review for fifth exam
- study guide
- exam from Fall 2007
- exam from Fall 2008 (with answers)
- fifth exam
- floating point [ notes]
- graphics extensions [ notes]
- Sun VIS home page
- Sun mediaLib home page
- VIS Instruction Set User's Manual (pdf)
- memory management [ notes]
- virtual machines [ notes]
- naming and binding issues [ notes]
- languages
- John Ousterhout, "Scripting: Higher level programming for the 21st century," IEEE Computer, March 1998
- Comparison Matrix: Scripting Language Survey
- review for final exam
- study guide
- exam from Fall 2007
- final exam from Fall 2008 (with answers)
- Final Exam - Friday, December 11, 3:00-5:30

Program Assignnments

Example programs

bit_rev.m - bit reverse
str_len.m - string length (string in memory)
str_cap.m - string capitalization (string in memory)
cmd_line_args.m - print command line arguments
file_io.m - file open and print
stdio.m - stdio

Helps

Assembly Language and Text Utility Resources from the Web

Edo Biagioni's ICS 312 class notes, SPARC assembly language course at Univ. of Hawaii
Peter Magnusson's notes on SPARC stack
Bruce Ediger's Technical SPARC CPU Resources
m4 reference manual
m4 examples
Michael Breen, m4 tutorial
Kenneth Turner, "Exploiting the m4 macro language," 1994 tech. rept. (pdf)

Newsgroups: alt.folklore.computers
Subject: Re: first assembler?
Date: 14 Jul 2000 21:08:32 GMT

The late Professor Don Gillies at Illinois claimed to have written the first assembler. He may have actually done so, but others unknown to him might have done the same at other sites at around the same time.

Gillies was a grad student of John Von Neumann, working on the IAS machine at Princeton. He was supposed to be working as a coder, translating programs written by more advanced researchers into machine code, but he found the job tedious, and wrote an assembler to help him do it faster.

John Von Neumann's reaction was extremely negative. Gillies quotes his boss as having said "We do not use a valuable scientific computing instrument to do clerical work!" (I wish I could reproduce Gillies' imitation of Von Neumann's Hungarian accent, he was very good at it!)

Doug Jones
jones@cs.uiowa.edu

The EDSAC (electronic delay storage automatic calculator) performed its first calculation at Cambridge University, England, in May 1949. EDSAC contained 3,000 vacuum tubes and used mercury delay lines for memory. Programs were input using paper tape and output results were passed to a teleprinter. Additionally, EDSAC is credited as using one of the first assemblers called "Initial Orders," which allowed it to be programmed symbolically instead of using machine code. [http://www.maxmon.com/1946ad.htm]