Computer Science 237 Computer Organization Williams College Fall 2006

Agenda

• Announcements
  • Computer Science registration open house - Wednesday at 6 PM
  • Lab 6 back soon
  • Lab 7 due now
• Wrapup of Error Correcting Memory
• Lab 8 Out
  • form groups of 2 or work individually
  • meet in TCL 312b at 1:15 sharp to get started - stay as long as you'd like or leave after the intro
  • your circuits must be complete and graded by Tuesday, November 7
  • no late submissions because of the exam coming right after this lab is done
• Computation Circuits
  • Suppose we want to build a circuit for multiplication, but not a combinational circuit like we built for addition
  • Can we compute it like this function?

    int mult_by_adding(int x, int y) {
      int product = 0;
      while (x > 0) {
        product += y;
        x--;
      }
      return product;
    }
    

  • To develop this into a circuit, we use registers to represent variables and wires to represent loops
  • Hex keypads to input values (we'll use single hex digits, but it's easy enough to expand)
  • Three registers: x, y, product
  • To start, copy values from hex keypads into x and y, clear 0
    • add an "initialize" switch to do this
  • After initialization, we need to loop. On each step:
    1. add y to product, store result in product
    2. subtract 1 from x, store result in x
  • note that x register can be set by the hex keypad or by the result of a decrement - need to treat inputs as a bus and make sure it has exactly one (and the correct) driver when its CLK input goes high
  • continue looping until x becomes 0, then no more adding
  • The loop needs to happen in stages and remain synchronized
    • for each time we subtract 1 from x, we want to add y to product
    • there will be adders to do all of this, but adders are always adding whatever values are presented on their inputs - we don't want to have the result go back around and get added again and again
    • we will use a clock input (actually a switch in the circuit, but realistically it will be a clock) and come up with substages/phases where we do parts of the computation
    • how to build such a clock?
      • convert a single clock input into 4 "time shifted" clocks at a lower frequency
      • we'll use the lower 2 bits of a counter - other possibilities as well
  • Phases in this computation:
    • Phase 0: let adders add
    • Phase 1: copy results of adders into temp registers
    • Phase 2: put temp register outputs onto x/product register inputs
    • Phase 3: copy values into x/product registers
  • Need to stop when x gets down to 0, even though the clock may/will continue
  • LOTS of room for optimization - do we need all those registers? phases?
  • Think about: can we build a faster circuit to implement the "shifty multiplication" example from earlier in the semester?

    int multiply(int x, int y) {
      int product = 0;
      while (x) {
        if (x&1) product+=y;
        x >>= 1;
        y <<= 1;
      }
      return product;
    }
    

Examples

• RepeatedAddition