Well that was fun!

[dpotter]

I just successfully executed all the tests for the computer at the end of Project 5.  

This has been a really fun project so far, and I've learned so much.  Thank you!

QUESTION:

If I counted the fundamental gates in my Hack platform (NAND, DFF), how many gates were involved in constructing the Hack computer? (not counting the ROM32K, Keyboard and Screen components).  Is it possible to have the hardware simulator report that?

Thanks,
dpotter

[cadet1620]

dpotter wrote

If I counted the fundamental gates in my Hack platform (NAND, DFF), how many gates were involved in constructing the Hack computer? (not counting the ROM32K, Keyboard and Screen components). Is it possible to have the hardware simulator report that?

The hardware simulator can't report this, but I wrote a quick and dirty program to do it.

    int nand = 1;
    int not = nand;
    int not16 = 16*not;
    int and = nand + not;
    int and16 = 16*and;
    int or = 2*not + nand;
    int or16 = 16*or;
    int or8way = 7*or;
    int xor = 4*nand;
    ...
    int dff = 8*nand + not;    // standard implementation of DFF
    ...
    int ram16k = 4*ram4k + dmux4way + mux4way16;
    int cpu = not+13*and + 2*mux+or+2*reg+mux+alu +3*or+3*and+pc;

For my chips, RAM16K = 4 538 299 Nand gates, and CPU = 1 216. Memory decoding logic is 253, so Computer without I/O is 4 540 080 Nand gates.

New and Improved! Now with 60% more Nands for the same low price!
The program was a bit too quick and dirty, it seems. There was a typo causing a severe under count in RAM.

[For a great set of pages on logic and electronics, see http://www.play-hookey.com. The DFF is at http://www.play-hookey.com/digital/d_nand_flip-flop.html.]

--Mark

[dpotter]

cadet1620 wrote

For my chips, RAM16K = 2 834 363 Nand gates, and CPU = 1 216.
Memory decoding logic is 253, so Computer without I/O is 2 835 832 Nand gates.
--Mark

If you had asked me to guesstimate the number of fundamental gates required to make a reasonably functional CPU prior to this exercise, I would have guessed somewhere over 30,000.  (I am envisioning ENIAC and the size of a vacuum tube).  To think that this can be accomplished with only 1200 gates is a real surprise.

On another note, I'd like to understand the math behind your RAM16K calculation.  Mine is significantly higher.  Perhaps I designed one of my fundamentals inefficiently?

int nand = 1;
int not = nand;
int and = nand + not;
int dff = 8*nand + not;
int mux=not+3*nand;
int mux16=16*mux;	    	    
int mux4way16=3*mux16;
int mux8way16=2*mux4way16+mux16;
int bit=mux+dff;
int register=16*bit;
int dmux=not+2*and;
int dmux4way=3*dmux;
int dmux8way=dmux+2*dmux4way;
int ram8=dmux8way+mux8way16+8*register;
int ram64=dmux8way+mux8way16+8*ram8;
int ram512=dmux8way+mux8way16+8*ram64;
int ram4k=dmux8way+mux8way16+8*ram512;
int ram16k=dmux4way+mux4way16+4*ram4k;
System.out.printf("RAM16K: %d\n",ram16k);  // result: RAM16K: 4538299

[cadet1620]

dpotter wrote

cadet1620 wrote

For my chips, RAM16K = 2 834 363 Nand gates, and CPU = 1 216.
Memory decoding logic is 253, so Computer without I/O is 2 835 832 Nand gates.
--Mark

On another note, I'd like to understand the math behind your RAM16K calculation.  Mine is significantly higher.  Perhaps I designed one of my fundamentals inefficiently?

System.out.printf("RAM16K: %d\n",ram16k);  // result: RAM16K: 4538299

My code had a typo -- register was only 8*bit.  When I fix it, I get exactly your number. I'm going to fix my post.

--Mark

[cadet1620]

We can make some intelligent estimates for gate counts for ROM and Screen.

A ROM bit is just a wire to 0 or 1, so it counts as 0 Nands.

int rombit = 0;
int romreg = 16*rombit;
int rom8 	= 8*romreg +  mux8way16;
int rom64 	= 8*rom8 +  mux8way16;
int rom512	= 8*rom64 +  mux8way16;
int rom4k	= 8*rom512 +  mux8way16;
int rom32k	= 8*rom4k +  mux8way16;

ROM32K comes out 2 097 088 Nands

Trickier is Screen. Since the Hack computer has no provision for wait cycles, the Screen buffer needs to be dual port RAM. In this case It can be dual read/single write which is quite a bit simpler than true dual port RAM.

DpRAM8 will look something like:

// DpRAM8.hdl -- dual port 8 byte RAM -- 1 RW port, 1 RO port
CHIP RAM8Dual {
    IN  inA[16], loadA, addressA[3], addressB[3];
    OUT outA[16], outB[16];
    PARTS:
    DMux8Way(sel=addressA, in=loadA, a=ld0, b=ld1, c=ld2, d=ld3, e=ld4,
                f=ld5, g=ld6, h=ld7);
        Register(in=inA, load=ld0, out=d0);
        Register(in=inA, load=ld1, out=d1);
        Register(in=inA, load=ld2, out=d2);
        Register(in=inA, load=ld3, out=d3);
        Register(in=inA, load=ld4, out=d4);
        Register(in=inA, load=ld5, out=d5);
        Register(in=inA, load=ld6, out=d6);
        Register(in=inA, load=ld7, out=d7);
        Mux8Way16(sel=addressA, a=d0, b=d1, c=d2, d=d3, e=d4, f=d5, g=d6, h=d7,
                out=outA);
        Mux8Way16(sel=addressB, a=d0, b=d1, c=d2, d=d3, e=d4, f=d5, g=d6, h=d7,
                out=outB);
}

The same pattern as was used to build up to RAM16K from RAM8 is used to build up to DpRAM8K for the Screen buffer.

int dpram8 = dmux8way + 8*reg + 2*mux8way16;
int dpram64 = dmux8way + 8*dpram8 + 2*mux8way16;
int dpram512 = dmux8way + 8*dpram64 + 2*mux8way16;
int dpram4k = dmux8way + 8*dpram512 + 2*mux8way16;
int dpram8k = dmux + 2*dpram4k + 2*mux16;

The Screen buffer comes out 2 793 339 Nand gates. This does not include any of hardware required to display the screen buffer.

The Keyboard does not require any additional logic in the Hack computer; it's just a bunch of wires coming from the physical keyboard.

CPU	1 528
Memory decoding	253
RAM16K	4 538 299
ROM32K	2 097 088
Screen buffer	2 793 339
Computer	9 430 507

Not a bad little computer for under 10 million Nand gates!

--Mark

[phillustine]

This is a really interesting post. Thanks for it.
Two questions popped into my nugget while reading it:

1) All else remaining equal, is the significantly greater number of gates needs for RAM the reason it's expensive?

2) I recognise two programming languages in this post. One is HDL; what's the other?

[ybakos]

phillustine wrote

2) I recognize two programming languages in this post. One is HDL; what's the other?

It's just for illustration; this could be a few different languages.

[phillustine]

Thanks for the post.

It was mostly this piece of code which I was interested in:

System.out.printf("RAM16K: %d\n",ram16k);

Where might I find something with a similar syntax?

[ybakos]

That's Java, with a format string.

[phillustine]

Aha. I see now. Many thanks.