# Computer Science 237 Computer Organization

### Williams College Fall 2006

Lecture 22: Computation Circuits, Microarchitecture Introduction
Date: November 1, 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.
• 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