Why we like abstraction

[cadet1620]

On a whim a couple nights ago I implemented the ALU using nothing but Nand gates. One pot of coffee and 466 gates later, at 3:30 in the morning, I have a working ALU.

New and improved: Koen found a couple optimizations I missed. The ALU is now down to 440 Nand gates.

Here's the schematic on 3 size C sheets: ALU-440-Armbrust-Simons-2.1.pdf

Cheers!
--Mark

WOW! See this post by dgramsey for a 403 Nand ALU.

[ybakos]

That is totally rad.

[myles]

I envy you sir.

[GustavoB]

Mark, how did you get that schematic?

[cadet1620]

I drew the schematic with ExpressSCH, a part of ExpressPCB which is a free circuit board design tool for Windows.

Basically, I designed and drew a 1-bit ALU, then cut and pasted it into a 16-bit ALU, and then added the circuitry for the status bits.

--Mark

[knarf_navillus]

That is brilliant. I'm somewhat surprised that it's "only" 466 gates.

[Koen_Be3840]

DSC_0002.JPG
 cut and paste!

[cadet1620]

It's great to see somebody thinking along the same lines as I was.

You might want to try implementing it in Logisim. Logisim will count your gates for you. I hope you can find a clever way to better my 466 Nands.

Here's a Logisim file that shows a trick that's handy when putting an ALU together from bit slices. ALU-1bit-1.circ (Hint: use Save Link As in your browser or you'll get to see a bunch of XML.)

--Mark

[Koen_Be3840]

ALU_462_NAnd.pdf

no comment

[Koen_Be3840]

Sorry 463 +1 because when zero zr=true

[Koen_Be3840]

463



I should be sleeping, realy!!

[cadet1620]

Koen_Be3840 wrote

ALU_462_NAnd.pdf

no comment

This ALU has a bug in it. It does not properly compute the AND operation because of a bad optimization in the implementation of bits 1..15. Carry out from the full adder is used as the input to the "f" multiplexor. 15 additional Nand gates will be required to invert the half adder carry out to get the correct multiplexor input.

This image shows the effect of this bug on bits 0 and 1 when computing
    x=0
    y=1
    zx = nx =1
    zy = ny = f = no = 0
The result is
    out = 0xFFFF should be 0!

--Mark

(Note: trailing "-" on a signal name means inverted signal.)
 

[cadet1620]

Awesome job by Koen

While fixing the AND bug he figured out how to apply one of my tricks to the X and Y input channels, reducing each to a single Mux (4 Nands). He also saw that it's much cheaper to detect -1 with Ands than to detect 0 with Ors.

The net result is an ALU with 441 Nands! Proving yet again that two minds are better than one.

I'll get the original schematic updated in a couple days.

--Mark

[Koen_Be3840]

What comes to mind is this:

What is the usefulness of this exercise. As Mark pointed out to me earlier on this forum this ALU wouldn't hold up in the real world due to race and hazard glitches.Simplifying chips
The most important lesson:
By rewiring the ALU to its minimal Nand implementation you will rewire your brain. You start recognizing the importance of analyzing of what is asked and what is given. What information can I compute before even processing i/O values. Most astonishing was that X and Y value could act as selection bit for the Mux handling nx,ny and zx,zy.

Seeing the patterns:

In this table out doesn't reveal much

nx zx  x | out
0   0   0 |  0
0   0   1 |  1
0   1   0 |  0
0   1   1 |  0
1   0   0 |  1
1   0   1 |  0
1   1   0 |  1
1   1   1 |  1

but if you re-arrange the table

nx zx  x | out
0   0   0 |  0
0   1   0 |  0
1   0   0 |  1
1   1   0 |  1
0   0   1 |  1
0   1   1 |  0
1   0   1 |  0
1   1   1 |  1

you see when x=0 out=nx
when x=1 out=Not(nx Xor zx)

So before going to the next chapters keep in mind, stay open minded!

Koen

[cadet1620]

Koen_Be3840 wrote

As Mark pointed out to me earlier on this forum this ALU wouldn't hold up in the real world due to race and hazard glitches.Simplifying chips

Actually, since the Hack computer architecture is fully synchronous, the glitches are not a problem. They occur after the data changes in response to the clock.  The real word implication of the glitches, along with other propagation delay effects, is to limit the maximum clock rate.

This is one of the reasons that PALs and FPGAs are usually synchronous.  The individual cells in these devices usually implement their logic with tiny ROMs used as lookup tables.

--Mark

[monsonite]

Mark

Thankyou for pointing me in the direction of Logisim.  

I've tinkered with it for about an hour, and already got most of an ALU slice put together. I'm hoping to simulate the timing delays of the proposed ALU and possibly look at Carry Look ahead logic to speed up the arithmetic.

If any hardware enthusiasts are looking for a challenge... I've come up with a proposal for a bitslice version all in TTL - called Nandroid

I've also done an eagleCAD schematic for a more complete bitslice, which includes the D Register, the A register, the PC (and associated incrementer), and the two multiplexers.

The first iteration is intended to be made entirely from 74xx00 nands and 74xx74 for the registers.

There are a total of 18 chips in each slice,  and it looks like it would fit easily onto a 4" x 2" pcb using soic packages of the ICs. The slice would also include LEDs to show the status of the register bits (using the /Q output of the 74xx74) and a toggle switch register to allow simple programs/data to be toggled in - just like the old PDP8s.

The 16 slices connect together using double ended header pins, making an Arduino "shield like" construction.  This would leave a RAM/ROM pcb to include, and some sort of a PC interface - such as an Arduino MEGA, which has enough I/O pins to dump data directly into a 64K x 16 RAM. (To emulate  the ROM).

I may never get around to building this HCTTL implementation - as I think I would be better to concentrate on moving on to FPGAs, but it would be a great nostalgia piece.


Ken