Close

Fast carry propagation for a new ALU

A project log for The Blinking Computer

An educational 16-bit CPU made from < 1000 transistors with lots of LEDs that anyone can build and learn from

Tony RobinsonTony Robinson 02/23/2017 at 07:195 Comments

I decided to redesign my ALU, the old one worked but it wasn't easy to see how it worked. It was too clever, I think people expect an ALU to compute everything (AND, OR, XOR, ADD/SUB, ASR) in a way they can see and then select the right output - that is much easier to understand.

Minimal ALUs are limited by the ripple-carry propagation time, so the first thing to do was to get my fast carry propagation design working. The slow bit of bipolar junction transistors is switching them off, so I got rid of all of them and used diodes to do all the carry propagation (these will be Schottky diodes for fast switching and low voltage drop). So here it is in it;s simplest form:

Generate, G, is high if both inputs are high. Kill, K, is high if both inputs are low. The carry goes in on the left, if K1 is high then the first NPN is on and the carry is grounded, if G1 is high then the carry out is high else the carry is propagated. That's pretty simple, I feel confident I can both get this implemented in a way that you can see the signal flow (as above) and thus be able to explain how this time-critical bit of a CPU works to all.

There's more detail at http://www.nanocpu.org/alu

Discussions

roelh wrote 05/21/2017 at 20:12 point

Hi Tony, I suspect that with increasing resistors this will only get you perhaps 3 levels, and speed will go down because impedance rises near the end of the chain.

Why dont you built the ALU in units of 3 or 4, each unit will have ripple carry for its own outputs, and a fast carry as output for the whole unit....

Do you already have a design for the ALU ?  I could not find it on your site.

I have a lot of ideas, especially for lowering part count. I can share ideas if you want, but ATOH I can imagine that you prefer your own ideas.

And thanks for liking the Risc relay CPU !

  Are you sure? yes | no

Tony Robinson wrote 05/25/2017 at 07:15 point

Sure the impedance will rise, but you need some impedance to limit the charge flowing onto the base of the last switching transistor (i.e. the output of the last carry).   What matters is the rate at which the impedance rises throughout the chain, I haven't yet worked that out.   It can start low, so there is quite a bit of headroom for it to rise.

But it's a fairly ugly solution.    I don't like the standard 4 way carry lookahead either, I just don't see why everyone designs this way.   All this does is reduce the problem from and O(n) problem to another problem of O(n).   For my last ALU I had a hierarchical carry propagate, it's not symmetric but it's close to optimal - there are details at the end of http://www.nanocpu.org/carry-propagation but the whole page really could do with a reqwite (it's linked from my Outtakes section).

I do have a new ALU design.   The old one is at http://www.nanocpu.org/alu-v1 and the new one, as you rightly point out, isn't written up yet.  I'll make that a high priority so as I can get feedback.   Basically it kills the input to all but the function you want to compute and ORs all teh outputs at the end, so it's quiet shallow.

I'd love to hear your ideas.   I'm old enough to know that there's no way I'm going to get this right first time and so I really want to make this an open design that others can improve upon.   If I make a really good job of it then there will be loads of clones that will get into even more schools.

I love your RISC relay CPU.   I have a whole load of those fast switching relays and for most of the life of this project I really wanted to build my CPU out of relays.   However, it also has to be programmable by school children and cheap enough for everyone to build and I just didn't think I could pull that off with relays.   Good luck and thanks for all your help.

  Are you sure? yes | no

roelh wrote 05/25/2017 at 20:44 point

Hi Tony,

the basic idea for an ALU was also placed in a comment of AYTABTU, ( to be found  here ) so perhaps you know it, but I will repeat it here:

The mentioned comment in AYTABTU gives some explanation of the circuit.

I did some thinking of your carry chain, and I think it will work if we add another 'kill' transistor that operates at the same time as the other one:

(You may have to open it in another window for a better view). In the previous version, the NPN transistor was shorting the previous section. Now, the left side of the resistor is pulled high at the same time, the input diode will block and the previous section is not pulled low.

( I hereby claim to be the inventor of this circuit, until there is proof that it already exists...)

The series resistor can be quite low (to get high speed) at the cost of a little bit more dissipation during 'kill' time. The inverter will be replaced by a transistor circuit, of course.

The carry-out of each section could be connected to the lower half of the previous picture, to provide the complete adder.

For quickly making a simple schematic, you could use the Klunky schematic editor . It works in your browser. However, you can not save, so only suitable for small drawings. After editting, you do a screen save, paste the schematic in 'paint' and place text. My upper drawing was made with it (the lower one was made with a 'real' editor).

  Are you sure? yes | no

roelh wrote 05/20/2017 at 17:06 point

Hi Tony,

I do not understand how this carry chain could work. IMHO, when the 'Kill' is active at let's say K3, it will not only pull C3 low but also the previous C2 and C1.....  

I also have a tip.... A two-input AND gate can be simpler than two diodes and a resistor. Just a single diode and resistor, like this:

Can also be used as OR when the diode is reversed. I use this trick a lot in the https://hackaday.io/project/11012-risc-relay-cpu

  Are you sure? yes | no

Tony Robinson wrote 05/21/2017 at 19:07 point

Yes, you are right.   This is most worrisome as I really need the fast carry propagate or the whole machine will run very much slower.   There is one possible route to save this design, the previous carries won't be pulled right down to ground as each stage has a voltage drop across the diode.   So if I can arrange a transistor to be on without the diode drop and off with it then it'll still work.   I can also move the current limiting resistor to after both diodes, like this:

I have yet to work out how the resistors should increase to make this work.

And thanks for the tip on the AND/OR gates, I'm sure I'll use that one day.

  Are you sure? yes | no