Where can my NAND count be improved?

[Christer Nilsson]

I've tried to count the number of NAND gates in the different chips.
The numbers reflect my unoptimized solutions.

While the cpu takes 3578 nands,
the ram8_16, (8x16=128 bits), takes 2618 nands.

I would like to get some feedback about where my nand count could improve.

_not 1
nand 1
_and 2
_or 3
dmux 5
_xor 6
dff 6
halfAdder 8
mux 8
dmux4way 15
nand_16 16
not_16 16
fullAdder 22
dmux8way 35
dmux8way 35
or16Way 45
mux_16 113
register_16 224
mux4way_16 339
add_16 352
inc_16 352
mux8way_16 791
pc 1373
alu_16 1476
ram8_16 2618
cpu 3578
ram64_16 21770
ram512_16 174986
ram4k_16 1400714
ram16k_16 5603210
memory 5603559
computer 5607137

Ruby code used:

nand = 1
dff = 6 * nand
_not = nand
_or = 2 * _not + nand
_and = _not + nand
_xor = nand + _or + _and

.. deleted lines ...

computer = cpu + memory + rom32k_16

list = %w"_xor _not _and _or nand not_16 nand_16 or16Way mux mux_16 add_16 fullAdder halfAdder cpu pc inc_16 register_16 dff mux8way_16 ram8_16 ram64_16 ram512_16 ram4k_16 ram16k_16 dmux dmux4way dmux8way rom32k_16 mux4way_16 alu_16 dmux8way memory computer"

sorted = list.map { |name| [eval(name),name]}.sort
sorted.each do |pair|
  count,name=pair
  puts "#{name} #{count}"
end

[cadet1620]

Christer Nilsson wrote

I've tried to count the number of NAND gates in the different chips.
The numbers reflect my unoptimized solutions.

While the cpu takes 3578 nands,
the ram8_16, (8x16=128 bits), takes 2618 nands.

I would like to get some feedback about where my nand count could improve.

_not 1
nand 1
_and 2
_or 3
dmux 5
...

Counting the number of 2-input Nand gates used in a nested implementation like the one done for N2T only gives an indication of how quickly the complexity grows as higher level parts are built. It's not something that would be optimized.

Real world implementation is not done with just 2-input Nands.  For instance CMOS, which is the most common logic family these days, can implement Nor for exactly the same cost as Nand, as well as a transmission gate which is like a controlled switch. Signals can flow either direction in a transmission gate which allows for some very strange optimizations.

For example, a Mux can be made in CMOS with a Not and 2 transmission gates.

Also, under the digital logic level, all this is implemented using transistors which are analog devices. Some circuits can take advantage of this to do optimizations that are "magic" as far as the digital world is concerned. This is particularly true of memory devices. Only the smallest and fastest memories (like registers) are made from DFFs.

--Mark

[monsonite]

Christer,

I also kept a count of nands.

I think the pc and the alu are the devices which could benefit most from optimisation.

I have just completed the cpu with a nand count of 1084 nand gates and 48 DFF.

ALU   530 gates
PC     340 gates   +  16FF

However, with some optimisation I believe that I could reduce the ALU to 498 gates and the PC to 161 gates.  This would reduce the total cpu nand count to about 873.

These are preliminary figures, and very much a work in progress. I'll let you know how I get on.


Ken

London UK

[monsonite]

Christer

I had a quick look at your Nand count.

The half adder should be 5 Nands and the full adder 9 Nands per bit

mux16 should be 49   - 3 to select each bit, and one as a Not to drive the select pin

inc16 can be as few as 80 Nands if you base it on half adders  (5 x 16)


I think the ALU can be 530 or fewer (498) and the pc  340 or fewer (161)

There are further optimisations possible within the cpu when you look at the interaction of the whole design


Ken