CSC 372
Systems II

Computer Architecture
Spring, 1998

This course meets from 3:05-4:20 PM TTh in room 116 of Alumnae Hall (just a few steps from my office). Note: the printed schedule of classes says it meets in Business 39, but we know better, don't we?

The book Computer Organization & Design: the Hardware/Software Interface, by David Patterson and John Hennessy, is required. This is the second edition of a textbook whose first edition I've used for the past three years. I've downloaded the errata sheet from the authors, dated 2 March, 1998.

For information on the electronic hardware components we're using in the lab, see Texas Instruments' page on logic chips. In addition, we sometimes need resistors (e.g. to pull down the output of an unpowered switch); resistors are marked with a standard color code.

The syllabus is available in LaTeX, DVI, Postscript, and HTML.

An updated schedule will contain the latest updates to homework due dates, lecture topics, etc.

We'll be using the same MIPS processor simulator, SPIMSAL, that we used last semester in Systems I, but will no longer use the SAL extensions to the language.

I also taught this course in Spring 1995, Spring 1996, and Spring 1997.

Homework Assignments

I shall assign several homework assignments during the semester, mostly "paper assignments" (i.e. not programming), although they may be turned in on paper or by email.

Homework 1 assigned 5 Feb, due 17 Feb.

Choose 50 points' worth (see the numbers in brackets next to the problem number in the book) of the following, including at least one problem from each group:

• 1.45, 1.46, 1.48,
• 2.1 through 2.9
• 2.10 through 2.13
• 2.18 through 2.24

Homework 2 assigned 19 Feb, due 5 Mar.

• Design and build a 4-bit ripple-carry adder. Turn in a circuit diagram on paper, and demonstrate a working circuit on a breadboard. You may use NAND, NOR, NOT, AND, OR, XOR gates, toggle switches, LED's, and stuff like that.
• Textbook problems B.3,B.5,B.10,B.11
• Recall the definitions of "size" and "depth" of circuits given in class. Recall also that two different approaches to building large multiplexers gave different size and depth results. Find formulae for the size and depth of an n-bit ripple-carry adder.
  Note: You'll need to make some design decisions and assumptions along the way. Since I may have made those decisions differently, my formulae may be slightly different from yours; if you want credit for it, show your work!
• Extra credit: For one or more of the following approaches, find formulae for the size and depth of an n-bit adder. As before, show your work! Compare your formulae with the corresponding formulae for the ripple-carry adder.
  • the "infinite hardware" (or "sum of products") approach on pp. 241-242
  • simple carry-lookahead; see pp. 242-243
  • two-level carry-lookahead, using groups of k bits (the treatment on pp. 243-248 uses k=4)
  Note that the analysis on pp. 248-249 assumes that a 16-input OR gate takes the same time as a 2-input OR gate, which isn't quite realistic. (Our assumption that a 16-input OR gate is built from a binary tree of 15 2-input OR gates isn't quite realistic either, but let's go with it for now....)

Homework 3 assigned 2-8 April, due 16 April.

• Design and build a 3-bit ALU capable of at least four operations:
  • add
  • subtract
  • either and or or (your choice)
  • set if less than
  I recommend starting with your adder from homework 2, ripping out one bit of it (if you wish, to save chips and space on the board) and adding the necessary chips and wires to handle the additional operations.

  The four operations should be distinguished by a two- or three-bit opcode; you may choose what numeric opcode to use for what operation. The opcode will be input on a set of toggle switches, as will both 3-bit data inputs. The output should appear on four LEDs (including the carry out of the add and subtract instructions).

• Problems from Chapter 5: 5.6, 5.12, 5.13. (For 5.13, note the typo on p. 373: memory should take 2 ns.)

Homework 4 assigned 8 April, due 5 May.

• Problems from Appendix B: B.25, B.26, B.27, B.28
• Design and build a traffic light controller based on problems B.25-28. Outputs should include six LEDs for the red, green, and yellow lights in both directions, and two LEDs with which the controller can request the start of a 4-second or a 30-second timer. These "timers" will actually be simulated by a human being (so they don't really have to be 4 and 30 seconds respectively); you'll need push-buttons and/or toggle switches for both timers and for two pavement triggers detecting E/W-bound and N/S-bound cars respectively. You may also want a "reset" button, which resets the controller to some known state (say, green in the N/S direction).
• Problems from Chapter 5: 5.15, 5.16, 5.25.
• Problems from Chapter 6: 6.3, 6.4.

Reading assignments

Last modified: