Revised April 28, 2010
CS 251: Computer Organization and Design
General Description
CS 251 has the goals to
-
Develop an accurate mental model of the architecture and
organization of physical computers.
-
Explain theoretical and practical concepts relevant to the structure
and design of modern digital computers.
-
Enable students to understand and predict the behaviour and
performance of computer programs executing on real machines.
Logistics
Intended for students in Computer Science, normally at the 2B level, although
the term may vary. Students in the Digital
Hardware option should take ECE 222 or 223 in place of
CS 251. Normally available in Fall, Winter and Spring.
Related courses (see calendar for official details)
- Predecessors: CS 136, 138, 145 (before Fall 2011), or 146
(imperative programming and the basic memory model).
-
Friends: Taking CS 241 along with CS 251 works well.
-
Successors: CS 350, CS 370, CS 450. Through
CS 350 and 370, many CS upper-year courses.
-
Conflicts: Courses that explore the basics of computer hardware.
Typical Reference(s)
D. Patterson, J. Hennessy, Computer Organization and
Design, 4th ed., Morgan Kaufmann, 2004.
Course notes also required.
Required preparation
Students should have the following at the start of the course.
-
Some facility with an imperative programming model: an ability
to use array indexing for both read and write (mutable
memory model); an ability to follow programs written using
imperative control flow.
-
An ability to use basic algebra, calculus, and probability.
-
Algebra is used for combinational design, where Boolean
formulas need to be manipulated according to a set of
axioms and theorems.
-
Calculus is used for some aspects of performance analysis---for
example, limits are taken to predict theoretically obtainable speedup
in parallel computers (Amdahl's law).
-
Basic probability theory is assumed when average-case
performance is computed using a weighted average of
probabilities---for example, computing average clocks
per instruction, cache-miss penalties, and average disk
rotational latencies.
Learning objectives
By the end of the course, students should have the ability to do the following.
-
Design simple combinational and sequential
hardware at the logic gate level in order to implement simple
algorithms and computations, such as addition, multiplication,
and data-path control for processors.
-
Describe number systems used by computer hardware,
including IEEE floating point and two's complement, at the bit
level, including
-
operate on these number representations
and compute their values, and
-
explain the limits
of these representations, including rounding error and overflow
conditions.
-
Explain how machine language is executed by
hardware, and describe a simple processor
architecture for executing a RISC machine language.
-
Explain some simple processor implementation optimization techniques,
in particular pipelining, and how differences in code ordering can
impact performance for processors using these optimizations, including
-
analyze performance of a
code sequence executing on a pipelined architecture, and
-
reorganize (given) code in order to improve performance on a
pipelined architecture.
-
Explain basic cache and virtual-memory
architectures, and how they can impact performance, including
-
analyze a memory-access trace relative to these architectures in order
to predict performance,
-
compute average-case performance given miss probabilities and
miss penalties, and
-
recognize specific cases (such
as loop index ordering) that can impact performance, and
reorganize such code to improve performance.
-
Describe a basic multicore and multiprocessor
architecture, and explain the key factors that
will affect performance and scalability of programs written for
such an architectures.
Typical syllabus
Introduction (2 hours)
Overview of computer organization.
Measuring performance.
Digital Logic Design (6 hours):
Gates, truth tables, and logic equations.
Combinational logic and basic components.
PLAs and ROMs.
Memory elements.
Finite-state machines (informally).
Data Representation and Manipulation (6 hours)
Signed and unsigned integer representations.
Addition and subtraction.
Using (informal) finite-state machines to control datapaths.
Multiplication.
IEEE floating-point representation.
Basic Processor Design (5 hours)
Basic processor datapaths.
Processor design using single-cycle control.
Pipelining (5 hours)
Pipelined datapaths.
Data hazards.
Branch hazards.
Load-use hazards.
Input/Output (3 hours)
Buses and bus arbitration.
Storage (disks).
Interrupts.
Point-to-point (routed) networks.
Networks and clusters.
Memory Hierarchies (3 hours)
Caches: direct-mapped, fully-associative, set-associative.
Virtual memory.
Page tables and TLBs.
Multiprocessing (3 hours)
Multi-processor systems and core processors.
Synchronization and locking.
Cache consistency.
Last modified: Wednesday, 15-Feb-2012 10:35:57 EST
