Computer Science 237 Computer Organization Williams College Fall 2006

Agenda

• Announcements
  • registration pizza with the CS department: tonight 6 PM
  • please report any problems with CSLab computers!
• CS 337 next semester - it's a tutorial and often pretty popular.
• Lab 6 back
• Lab 7 discussion
• Lab 8 continues
  • working circuit in my office - come see it
  • pushbuttons in LogicWorks - hook up power and ground
  • buses in LogicWorks - simplifying your designs - on the breadboards, use some tape
  • binary probes are useful (and free) in LogicWorks
  • think very carefully about who's driving the bus - LogicWorks can help here too - probes will display "C" in LogicWorks, whereas chips might behave unpredictably or fry
  • Beware of timing issues - for example, if you need to put a value on a bus and activate a chip to read that value based on the same event (a button press), make sure your data gets to the bus before your chip samples it
  • label your chips and wires - for your benefit and mine
• Optional bonus lab
• Computation Circuits
  • final words on multiplication by repeated addition
  • another one: multiplication using bit shift and addition

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

    • here, multiplying 2 8-bit values to get an 8-bit value, ignoring overflow
    • this one is potentially a lot faster - 8 cycles (the number of bits) rather than X adds.
    • Data path: main data bus carries values of X, Y
      • four possible bus drivers: X keypad, Y keypad (during initializaition), LSR X register, LSR Y register (during computation)
      • access to the bus must be carefully coordinated to avoid conflicts.
    • addition is done by a two ripple-carry adders
      • the adders always add, but we only store the result back in the when the 1's bit of X is 1
    • the shifting part of the computation is done in wires!
      • LSR X is done by copying down bits to one position right, LSL Y is done by copying down bits to one position left and making the 1's bit a 0.
    • clock/sequencing for the whole circuit is based off an init switch and a clock generator
      • shift register: initialize to 0001 on init, on each clock leading edge, the 1 shifts to the left, rotating around when it gets to Q3 (note Q3 is fed to SI - shift in)
      • the outputs of the shift register define the 4 phases for our computation
      • 4-bit counter starts at 0, counts up each time we reach phase 4 - on the 8th iteration, when we know we are done, the Q3 output is used to indicate that the product is ready
      • D-type flip-flop indicates initialization phase, sets to 1 on the leading edge of the init signal, sets back to 0 when phase 3 of the init cycle is complete (Q3 of the shift register becomes 1)
    • Initialization phases:
      • Phase 0: clear all registers
      • Phase 1: enable X input TriStates, then after a delay buffer, load X register
      • Phase 2: enable Y input TriStates, then after a delay buffer, load Y register, trigger load of LSR X
      • Phase 3: reset D-type flip-flop, increment 4-bit counter, if 1's bit of X is 1, copy output of adders (PRODUCT+Y) into PRODUCT, trigger load of LSL Y
    • Computation phases:
      • Phase 0: quiet time - nothing happening (although our adders are adding)
      • Phase 1: enable LSR X output TriStates, then after a delay buffer, load X register
      • Phase 2: enable LSR Y output TriStates, then after a delay buffer, load Y register, trigger load of LSR X
      • Phase 3: reset D-type flip-flop (no effect), increment 4-bit counter, if 1's bit of X is 1, copy output of adders (PRODUCT+Y) into PRODUCT, trigger load of LSL Y
    • note the amount of parallel computation here
    • note the speculative computation - we always compute Y+PRODUCT but only copy it in when the 1's bit of X is 1 - is there a cost to this?
    • we could speed the whole thing by having separate data buses for X and Y
  -- EXAM TOPIC CUTOFF POINT --
• Introduction to Microarchitecture
  • Consider a calculator-like device:
    
  • If the ALU has four functions, it can be controlled with 2 control lines:
    
  • Similarly for the Shifter, if it has 4 functions, it requires 2 control lines.
  • Each input bus A and B needs 3 control lines (assuming 8 registers) as well as 3 for the C bus.
  • Total of 13 control lines to run this calculator device.

Examples

• ByteMultiplier