Thirty two additions have to happen. You can spread them over thirty two clock cycles, or you can lay them out in silicon and do them all at once. Today you build both.
Collect the homework counts from last session. Then say the hour is one algorithm, two pieces of hardware.
One algorithm. Two completely different machines.
the hour in three questions
What is the algorithm? Written as a loop, it is four lines, and every line is something you already built.
Design one: run the loop. One adder, thirty two turns. Small, slow, and what most chips ever made actually do.
Design two: unroll the loop. Thirty two rows of adders in silicon. Ten times the gates, and one long cycle.
Neither design is clever yet. Cleverness is next session. Today is honest construction.
Everything you did on paper, written as four lines.
notice what is in it
A test of one bit. An addition. A shift. A counter. You have built every one of those already.
There is no multiplication anywhere in the algorithm for multiplication.
Read the loop aloud. Four lines, thirty two turns. The whole hour is about how you spend those turns.
A loop can be run, or it can be unrolled.
the same thirty two additions, either way
Run it: build one adder and use it thirty two times. You spend time.
Unroll it: build thirty two adders and use each once. You spend space.
This choice comes back for every loop in every machine you will ever design.
Name the tradeoff here explicitly. It is the most transferable idea in the hour.
the obvious datapath, and what is wrong with it
Build it the way you wrote it on paper.
it works, and it is wasteful
The multiplicand register has to be 64 bits wide, because by the last turn it has been shifted left thirty one times.
So the adder has to be 64 bits wide too, and 64-bit adders cost twice what 32-bit ones do.
And the top half of that register is zeros for most of the run. You are paying for wire that holds nothing.
Let them see the waste before the fix. The fix is much prettier if the problem is felt first.
THE REFINEMENT
Nothing says the multiplicand has to move. Shift the product right instead.
what that bought
The multiplicand never moves, so it stays thirty two bits wide, and the adder only ever needs to be thirty two bits.
Shifting the running total right by one has exactly the same effect as shifting the multiplicand left by one. The relative positions are what matter.
Half the adder, half the register. Same answer.
This is the first properly elegant idea of the hour. Do not rush it.
watch the two halves trade places
And now the trick that makes the whole design fit.
The multiplier is consumed one bit per turn. The product is produced one bit per turn. They share one register.
four turns, and check every one against your paper working
The whole algorithm, one turn at a time.
Checked against every four bit pair in code. Step it slowly, the shift is where people lose the thread.
The control is smaller than anything else on the slide.
remember
A five bit counter counts the thirty two turns. Five bits, because two to the five is thirty two.
One AND gate decides whether this turn adds: the bottom bit of Q, gated with the add-enable.
When the counter rolls over, the product is sitting in A and Q, and the machine says done.
Emphasise how little control there is. Most of the cost is the adder and the registers.
Add it all up.
judged the way you judge everything
The clock does not have to slow down. One turn is one 32-bit addition, twelve gate delays, comfortably inside a 3 GHz cycle.
But a multiply now takes thirty two cycles. In a machine that issues an instruction per cycle, that is thirty two lost.
Separate the two numbers carefully. The cycle is fast. There are just a lot of them.
the same loop, with the turns laid side by side
Take the thirty two turns and build them all at once.
what unrolling does
Every turn becomes a row of hardware. There is no counter, no register to shift, and no state at all.
The shifts disappear completely. A shift by k is just wiring row k over by k columns.
Shifts costing nothing in space is worth saying out loud. A shift is a wire, not a gate.
First, every partial product bit at once.
remember
One AND gate for every pair of bits. 1024 of them for a 32 by 32 multiply.
None of them waits for anything, so all 1024 partial product bits exist at t = 1.
That is the entire multiplication part of multiplication. Everything after this is addition.
Same point as last session, but now they are about to see how the additions are physically arranged.
the single most important wire in the design
Each cell makes a sum and a carry. The carry has two places it could go.
send the carry
Same cells, same count, one wire moved. 185 delays against 63. This is the slide of the act.
Follow the longest path a signal can take from input to output.
remember
Down through thirty one rows, and along toward the top end of the product. Two gate delays per cell.
Sixty three gate delays to get the array settled, and the bottom row is still two numbers, not one.
Trace it with a finger on the screen. The diagonal is the shape of the whole delay.
The array never finishes the job. It hands you two numbers.
remember
Saving carries to the next row is quick, but the last row still has a set of sums and a set of carries that were never combined.
So the bottom of the array is a real carry-propagating adder. The one from Class 22, doing the job nothing else can.
This is the first appearance of an idea that dominates next session. Flag it.
Add that up too.
judged the same way
1500 picoseconds is four and a half cycles at 3 GHz. Better than thirty two, and still not one.
Ten times the gates of design one, for about five times the speed. That is not a scandal, but it is not a triumph either.
Resist calling this a win. It is a different point on the same curve, and next session beats both.
The same algorithm, and the bill depends entirely on where you spent it.
the actual skill, again
A microcontroller multiplying a few times a second should run the loop. Seven thousand gates would be silicon it cannot afford to power.
A processor doing signal or matrix work cannot stall for thirty two cycles, and buys the array without hesitating.
They should be able to predict this slide by now. That is the point of repeating the shape.
Six down, three to go.
what you are carrying into next session
A loop can be run or unrolled, and that is a choice between time and area, not between right and wrong.
Shifting by a fixed amount costs nothing in hardware. It is wiring.
And carries can be handed to the next row instead of being resolved. 185 delays became 63 on one wire.
The carry-saving idea is the seed of the entire next session. Plant it, do not spend it.
Thirty two cycles, or seven thousand gates.
Both designs are honest, both are built, and both get slower in exact proportion to how wide the machine is. Double the bits and you double the cycles, or you double the depth of the array.
Next session: stop building the algorithm as written. Make fewer rows to add, and find a cheaper way to add the ones that are left.
Stop here. Send off: write out 0111 in binary and find a way to multiply by it using only two operations instead of three. You are allowed to subtract.