Number of NAND gates in the HACK computer

[Renslay]

Hi all,

I was wandering: how many NAND gates/chips would you need if you want to build the entire HACK computer, chip by chip? How many NAND gates does each chip require?

For that I wrote a Python script where each function is responsible for calculating the needs of a single chip. The numbers follow my implementation of the HACK computer: they might not be optimal, but I tried to aim for low number of sub-chips.

The only "optimization" I used is I defined the XOR gate with 2 NOT and 3 NAND chips; and the DFF can be constructed with 1 AND chip and 6 NAND chips (thanks, wiki). Otherwise I followed the chip hierarchy of the nand2teris lecture.

I did not define the ROM chip; the complexity of that can vary, depending on your interpretation of what can be considered as ROM (it can be just a couple of demuxers with hard-coded constant signals - or an entire programmable RAM with tons of DFFs).

This can be a bit of a spoiler for those who have not yet finished the hardware course, as you can see what sub-chips I used for each individual chip.

This is the result I got:

chip_nand       ->       1 NAND gates.
chip_not        ->       1 NAND gates.
chip_and        ->       2 NAND gates.
chip_or         ->       3 NAND gates.
chip_xor        ->       5 NAND gates.
chip_mux        ->       8 NAND gates.
chip_dmux       ->       5 NAND gates.
chip_not16      ->      16 NAND gates.
chip_and16      ->      32 NAND gates.
chip_or16       ->      48 NAND gates.
chip_mux16      ->     128 NAND gates.
chip_or8way     ->      21 NAND gates.
chip_mux4way16  ->     384 NAND gates.
chip_mux8way16  ->     896 NAND gates.
chip_dmux4way   ->      15 NAND gates.
chip_dmux8way   ->      20 NAND gates.
chip_half_adder ->       7 NAND gates.
chip_full_adder ->      17 NAND gates.
chip_add16      ->     272 NAND gates.
chip_inc16      ->     272 NAND gates.
chip_ALU        ->    1181 NAND gates.
chip_dff        ->       8 NAND gates.
chip_bit        ->      16 NAND gates.
chip_register   ->     256 NAND gates.
chip_ram8       ->    2964 NAND gates.
chip_ram64      ->   24628 NAND gates.
chip_ram512     ->  197940 NAND gates.
chip_ram4k      -> 1584436 NAND gates.
chip_ram16k     -> 6338143 NAND gates.
chip_screen     -> 3169005 NAND gates.
chip_memory     -> 9507670 NAND gates.
chip_PC         ->     790 NAND gates.
chip_CPU        ->    2887 NAND gates.

==========================================
And here is the Python code (spoiler!)
==========================================

def chip_nand(): return 1
def chip_not(): return chip_nand()
def chip_and(): return chip_nand() + chip_not()
def chip_or(): return 2*chip_not() + chip_nand()
def chip_xor(): return 2*chip_not() + 3*chip_nand()
def chip_mux(): return chip_not() + 2*chip_and() + chip_or()
def chip_dmux(): return chip_not() + 2*chip_and()
def chip_not16(): return 16*chip_not()
def chip_and16(): return 16*chip_and()
def chip_or16(): return 16*chip_or()
def chip_mux16(): return 16*chip_mux()
def chip_or8way(): return 7*chip_or()
def chip_mux4way16(): return 3*chip_mux16()
def chip_mux8way16(): return 2*chip_mux4way16() + chip_mux16()
def chip_dmux4way(): return 3*chip_dmux()
def chip_dmux8way(): return chip_dmux() + chip_dmux4way()

def chip_half_adder(): return chip_and() + chip_xor()
def chip_full_adder(): return 2*chip_half_adder() + chip_or()
def chip_add16(): return 16*chip_full_adder()
def chip_inc16(): return chip_add16()
def chip_ALU(): return 6*chip_mux16() + 4*chip_not16() + chip_and16() + chip_add16() + 2*chip_or8way() + chip_or()

def chip_dff(): return chip_and() + 6*chip_nand()
def chip_bit(): return chip_mux() + chip_dff()
def chip_register(): return 16*chip_bit()
def chip_ram8(): return chip_dmux8way() + 8*chip_register() + chip_mux8way16()
def chip_ram64(): return chip_dmux8way() + 8*chip_ram8() + chip_mux8way16()
def chip_ram512(): return chip_dmux8way() + 8*chip_ram64() + chip_mux8way16()
def chip_ram4k(): return chip_dmux8way() + 8*chip_ram512() + chip_mux8way16()
def chip_ram16k(): return chip_dmux4way() + 4*chip_ram4k() + chip_mux4way16()

def chip_screen(): return chip_dmux() + 2*chip_ram4k() + chip_mux16()
def chip_memory(): return chip_dmux() + chip_not() + 2*chip_and() + chip_ram16k() + chip_screen() + chip_register() + 2*chip_mux16()
def chip_PC(): return 2*chip_mux16() + 2*chip_or() + chip_register() + chip_inc16()
def chip_CPU(): return 3*chip_mux16() + 2*chip_register() + chip_ALU() + chip_PC() + 3*chip_not() + 4*chip_and() + 3*chip_or()
# def chip_computer(): return chip_rom32k() + chip_CPU() + chip_memory()

# Create a copy of globals() to iterate over
global_objects = globals().copy()

for name, obj in global_objects.items():
    # Check if the object is a callable function and not a built-in function
    if callable(obj) and not name.startswith("__"):
        # Call the function and print its name and return value
        print(f"{name:<15} -> {obj():>7} NAND gates.")

[Renslay]

I was surprised to see that the memory requires almost 10 million NAND gates (the CPU is less than 3,000). In the age of vacuum tubes, they managed to build computers with a couple of thousands, maybe 10s of thousands of vacuum tubes (and I'm not sure a nand gate would require 1 or more tubes to implement!)

Sure, the HACK computer has a lot of memory compared to those, and it's a 16 bit architecture. Still, I wonder how would they approach the implementation of the HACK computer in the early days of computers.

Also, is there any chip that can be built more efficiently directly, without entering a crazy optimization territory?

[dolomiti7]

Yes, memory is expensive in terms of gates/transistors. A significant amount of transistors in modern CPUs is actually related to the embedded cache memory. However, real life memory (DRAM) is implemented more efficiently in terms of transistors (not based on gates).

But your list is far from optimal. A full adder can be done with 9 NAND gates for example, a XOR and 2x1 MUX with 4 NAND gates each. That will be cascading through to the more complex chips. Not even considering more sophisticated (global) optimizations that are applied by EDA tools. Effectively you would need much less gates. That is however out of the scope of nand2tetris.

[pm100]

A few things. First here is a video by a guy building a tube based cpu. Right at the start you see his circuit diagram for a NOR gate https://www.youtube.com/watch?v=o0ZmcvvznTY&t=959s

Second, in the tube and early transistor days memory was ferrite core. https://en.wikipedia.org/wiki/Magnetic-core_memory . not implemented as logic gates at all

Then came static ram chips(this is where intel got their start) https://en.wikipedia.org/wiki/Random-access_memory#SRAM I started in 74 and 1k (bit) chips were just being replaced by 4k chips on the machine I worked on (cpu was implemented using TTL)

Then came dram. DRAM is much, much denser but slower. This is what enabled large RAMS (gigs)

We then come full circle. To overcome the slowness of DRAM on chip SRAM caches were implemented. These basically work the same way the original SRAM chips worked, JK flip flops. Lots of them, maybe > 50% of transistors in a modern CPU