Syllabus of EE 2310, Computer Organization and Design EE 2310 logo

COMPUTER ORGANIZATION AND DESIGN

FALL 1999

PROF. C. D. CANTRELL

DESCRIPTION and SYLLABUS

TEXTS:

Computer Organization and Design, Second Edition, by David Patterson and John Hennessy (Morgan Kaufmann Publishers, 1997). (Required) Please DO NOT buy a copy of the first edition.

Professors Patterson and Hennessy are the academic originators of RISC (Reduced Instruction Set Computer) architectures. Professor Hennessy designed the first of the MIPS family of processors, now used in computers manufactured by Silicon Graphics. Professor Patterson's RISC design underlies the SPARC family of processors used by Sun Microsystems and manufacturers of Sun-compatible computers. The industrial originator of RISC processing was Seymour Cray, who used nearly all of the most important RISC concepts in the Control Data 6600 (1964) and 7600 (1968), and in the CRAY series of supercomputers.

Of all RISC microprocessors, MIPS processors are the most widely used in embedded systems, including Nintendo 64 and Sony PlayStation. 19 million MIPS processors were sold in 1996.

Introduction to RISC Assembly Language Programming, by John Waldron (Addison-Wesley, 1998). (Required)

LogicWorks 3, by Capilano Computing Systems, Inc. (Addison-Wesley, 1996). (Required)

This book documents the software used in this course to design and simulate logic circuits. The software is included with the book.

Schaum's Outline of Theory and Problems of Digital Principles, Third Edition, by Roger L. Tokheim, ISBN 0-07-065050-0 (published by McGraw-Hill) (Recommended)

Like all Schaum's outlines, this book contains many worked problems and many more practice problems. Topics covered include data representations, logic gates, Karnaugh maps, latches, flip-flops, counters, shift registers, and basic RAM architecture.

TARGET AUDIENCES:

This is a required course for all degree-seeking undergraduate students in Electrical Engineering.
An understanding of the material in this course is strongly recommended for all students who intend to take EE 6481, Computational Methods in Engineering.
Others who can benefit from this course include employees of local high-technology companies who need an introduction to computer architecture.

CONCEPTS/TOOLS TO BE ACQUIRED IN THIS COURSE:

OVERALL GOALS OF EE 2310:

Acquire the ability to use a hierarchical (layered) approach to understand a complex system
- Hardware
- Software
- This ability is useful in many EE courses and on the job
Become sufficiently well acquainted with the principles of computer architecture to be able to make intelligent use of computers for designing and simulating engineering systems, components, and devices
Acquire a basic knowledge of assembler language --- a tool for accomplishing the first two goals

SPECIFIC CONCEPTS AND TOOLS:

Computer abstractions and technology
- Hierarchical approach to understanding & designing a complex system
  - Software
  - Hardware
- Computer organization
  - Processor
    - Control
    - Datapath
  - Memory
  - Input & output
- Survey of computer history
  - Markets for early computers
  - Development of computer & software technology
  - Lessons from computer history
- Components of retail price in the computer industry
  - Component costs
  - Direct costs
  - Gross margin
- Why learn an assembly language?
  - Programming DSPs & other embedded processors
  - Understanding of computer systems
  - Why learn MIPS assembly language?
    - Simplicity
    - The RISC revolution in processor performance
    - Special-purpose and embedded processors
    - Time-critical routines (device drivers, real-time systems)
- How to access course materials on the the World Wide Web
Performance measurement and comparison
- Possible definitions of performance
  - Execution time
  - Operations per second
  - Throughput (e.g., transactions per hour)
  - Real-time computing and performance metrics
- Metrics for processor performance
  - Formula for execution time
  - Wall-clock (elapsed) time vs. user CPU time + system time
  - MIPS
  - MFLOPS (maximum vs. actual)
  - Linpack
- Relating the metrics
- The SPEC performance metrics
- Choosing benchmark programs to evaluate processor performance
- Comparing and summarizing performance
Data representations
- Data types supported in RISC architectures
- Bases
  - 2 (binary)
  - 8 (octal)
  - 10 (decimal)
  - 16 (hexadecimal)
- Unsigned integers
  - ASCII representation of characters
  - Conversion from binary representation to base-2^k representations
  - End of line conventions in DOS, UNIX, MacOS, VMS
  - Ranges of 1-byte, 2-byte, 4-byte, and 8-byte unsigned integer representations
- Addressing: An application of unsigned integers
  - Byte-addressed memory
  - Byte ordering conventions
    - Big-endian
    - Little-endian
  - Pointers: Address vs. contents
- Signed representations of integers
  - Sign-magnitude representation
  - Concept of additive inverse
    - Biased representations
    - One's complement representation
    - Two's complement representation
      - Logical variables
      - Logic functions (NOT, AND, OR)
      - One's complement of an integer
      - Two's complement of an integer
        
        Representation of additive inverse
        Examples (1 byte, 2 bytes, 4 bytes)
        Range of representable integers
- Fixed-point representations of positive rational numbers
  - Extension of binary place-value notation to fractions
- Floating-point representations
  - Motivation, concepts and base-10 examples
  - IEEE-754 single precision
    - Conversion between decimal and IEEE-754 s.p. representations
  - IEEE-754 double precision
  - TI DSP floating-point representations
    - Conversion between decimal and TI-DSP representations
  - Features of floating-point representations
    - Smallest representable positive number
    - Largest representable positive number
    - NaNs and denormalized numbers
Combinational logic circuits and Karnaugh maps
- Operations of computer hardware
  - Gate implementation of logical operations
  - Overview of circuit implementations of logical operations
  - 3-state outputs
  - Introduction to software for schematic capture and circuit simulation
- Gate count, footprint and cost
- Methods for minimizing gate count
- Boolean functions of logical variables
  - Demonstrations of basic theorems using truth tables
  - Labeling of the rows in a truth table by unsigned integers representing the combined truth values of the inputs
  - How to obtain a sum-of-products representation of a Boolean function from its truth table
    - Relation between gate count and number of products
  - 2-level representation of a Boolean function using a PLA
  - Minterms and maxterms
    - Canonical forms of sums of minterms and products of maxterms
  - Minimal sums of products; relation to minimizing gate count
  - Prime implicants
- Karnaugh maps
  - Pictures of truth tables
  - Format of Karnaugh maps for 2, 3, and 4 inputs
  - Steps in minimizing a Boolean function using a Karnaugh map
  - Detection of static-1 hazards using a Karnaugh map
    - Elementary discussion of gate delays
    - Illustration of static-1 hazards using circuit simulator
- Multiplexors
  - Gate implementation of a 2-to-1 multiplexor
  - Gate implementations of 4-to-1 and 8-to-1 multiplexors
- Adders
  - 1-bit half adder
  - 1-bit full adder
  - Bit-sliced addition of 32-bit words
    - Ripple-carry adders
      - Worst-case delay
    - More efficient adder designs
- Decoders
  - Use in memory addressing
  - Gate design of 1-to-2, 2-to-4, and 4-to-8 decoders
Sequential logic circuits
- Outputs and next state as vectors of Boolean functions of inputs and present state
- Latches
  - Set and reset latches
  - SR latch
    - Excitation table
    - Race condition when S and R are both deasserted
    - Karnaugh map
    - Characteristic equation (Q* = S + R'Q)
  - CSR latch
    - Excitation table
    - Karnaugh map
    - Characteristic equation
  - JK latch
    - Excitation table
    - Oscillational instability
  - D latch
    - Excitation table
    - Characteristic equation
    - Gate implementation
    - Circuit simulation
    - Timing diagram
    - Clocking and output stability problems
  - Master-slave D flip-flop
    - Gate implementation
    - Circuit simulation
    - Timing diagram, pointing out clock-edge-triggered state transitions
    - Use in implementation of registers
  - Lightning introduction to finite state machines
    - State diagrams for SR, CSR, D latches
    - Examples of state diagrams in other areas
Introduction to assembly language
- Instructions
  - Illustration of a C program, its representation in assembly language, and its object code
- The fetch-execute cycle
- Format of an assembly-language program
  - Comments
  - Directives
  - Data declarations in SPIM
    - Bytes
    - Integers
    - Floating-point numbers
    - Characters
    - Strings
      - Null-terminated
      - Non-null-terminated
  - Executable instructions
- Survey of differences between SAL (Simple Abstract Language), human-coded MIPS assembly language, and true MIPS assembly language
- Load-store architectures
  - Example: Implementation of integer addition using load-store approach (RISC architectures, SPIM language) vs. memory-to-memory approach (CISC architectures, SAL language)
- Survey of addressing modes
  - Direct addressing
  - Indexed addressing
  - Immediate addressing
  - Indirect addressing
  - Register direct addressing
  - Register indirect addressing
  - Relative addressing
- MIPS addressing modes and the corresponding formats in assembly language and object code
  - Register direct addressing: R-format instructions
  - Immediate addressing: I-format arithmetic and logical instructions
  - Indexed addressing using I-format: Load and store instructions
  - J format
  - The MIPS memory model
  - How to obtain an address in MIPS assembly language: The la instruction
- Survey of implementation of I/O
  - Hardware I/O instructions (Intel 80x86)
  - System calls (RISC architectures)
  - I/O system calls in SAL and SPIM
  - "Hello, world!" in SAL and SPIM
- Arrays
  - 1-D arrays in C, FORTRAN, SAL and SPIM
    - Index computation
    - Pointer arithmetic
  - 2-D arrays in C, FORTRAN, SAL and SPIM
    - Index computation
    - Use of pointers to address array elements
    - Stride in memory resulting from various combinations of higher-level language and choice of most rapidly incremented index
- Usage of arithmetic and logical instructions in SAL
  - Addressing bytes and words in SAL using m[ ] and M[ ]
  - Examples of SAL programs
- Branch instructions in SAL and SPIM
  - Implementations of a loop
  - Examples
  - Branch implementation using the slt instruction
- Stacks
  - Array implementation of a stack
  - Application of stacks to saving state prior to a procedure call
  - General layout of the system stack in the MIPS architecture
- Support for procedures in computer hardware
  - Jump register instruction
  - Jump absolute instruction
  - Examples of procedure calls
  - Execution of a program as a procedure in SUN UNIX
- Alternatives to the MIPS approach
- Examples
Computer arithmetic
- Integer addition and subtraction
  - Integer overflow
- Logical operations
- Integer multiplication
- Computational aspects of the IEEE-754 floating-point representations
  - Floating-point overflow and underflow
  - Machine epsilon
  - Consecutive floating-point numbers near 1.0
    - Wobble
  - Rounding
    - Bias in consistently rounding up or down
    - Round to nearest (or round to even in case of a tie)
  - Catastrophic cancellation of significant digits in subtraction
    - Examples
      - Evaluation of a polynomial
      - Evaluation of the sine of a large angle
  - Ill-conditioned problems
    - Example: Finding multiple roots of a polynomial
Design of the datapath and control of a processor that executes a subset of the full MIPS instruction set
- Design of the datapath of an ALU that executes the add, sub, and, or, and slt instructions
- Control signals for the ALU
- State elements and clocking
- Block view of a single-clock-cycle processor datapath
- Control of the single-clock-cycle implementation
- Performance analysis of the single-clock-cycle implementation
- A simple multiple-clock-cycle processor datapath
- Control of the multiple-clock-cycle implementation
  - State diagram
  - Implementation of state transitions using microprogrammed control
- Exceptions and interrupts
  - Exception handling in 80x86 architecture and DOS operating system
  - Exception handling in RISC architectures and UNIX operating system
Pipelining
- A pipelined datapath
- Pipelined control
- Visualization of pipelined data flow
  - Pipeline diagrams
  - Gantt charts
- Examples
- Data hazards
  - Compiler elminiation of data hazards
  - Hardware control for data hazards: Stalls
  - Reducing data hazards: Forwarding
- Branch hazards
- Performance of pipelined systems
- Programming for a pipelined processor in a higher-level language
Overview of memory system technology and architecture
- Hardware implementations of 1-bit memory
  - DRAM
  - SRAM
  - ROM
- Hardware implementations of multiple-bit memory
  - DRAM
  - SRAM
  - ROM
- SRAM and DRAM chip and system architectures
- System bus architectures (processor to/from memory)
Hierarchical memory systems
- The processor-memory speed gap
- Interleaved memory
- Caches
  - Direct-mapped caches
  - Fully associative caches
  - Set-associative caches
  - Examples
    - Level 1 caches
    - Level 2 caches
- Virtual memory
- A common framework for memory hierarchies
- Programming for hierarchical memory in a higher-level language
Interfacing processors and peripheral devices
- I/O Performance measures: Some examples from disk and file systems
- Types and characteristics of I/O devices
- Buses: Connecting I/O devices to processor and memory
- Interfacing I/O devices to the memory, processor and operating system
Parallel processors
- SIMD computers--Single Instruction Stream, Multiple Data Streams
- MIMD Computers--Multiple Instruction Streams, Multiple Data Streams
- Programming MIMDs
- MIMDs connected by a single bus
- MIMDs connected by a network
- Future directions for parallel processors
- Programming for parallel processors in a higher-level language

Back to EE2310 Home Page