Efficiency - Is it 'better' to minimize the total NAND gates in a complex gate?

[ppfvy]

For example, it looks like I can make Or8Way using 15 Nand gates or 7 Or gates. The version with Or gates looks cleaner and has fewer gates, but each Or gate is built from 3 Nand gates so it has more (21) total Nand gates than the 15 Nand version. Since we're building everything from Nand, should I consider the solution with the fewest Nands to be the 'best'?

[cadet1620]

ppfvy wrote

For example, it looks like I can make Or8Way using 15 Nand gates or 7 Or gates. The version with Or gates looks cleaner and has fewer gates, but each Or gate is built from 3 Nand gates so it has more (21) total Nand gates than the 15 Nand version. Since we're building everything from Nand, should I consider the solution with the fewest Nands to be the 'best'?

Optimization in the hardware world is a speed/size/power tradeoff that depends on the underlying IC technology. For this course, where the object is to learn abstraction/encapsulation, I'd consider the 7 Or gate version as better than the all Nand version.

The optimization in the 7 Or version is in the topology of the Or gates. If each Or gate has one unit delay time, can your Or8Way produce its output in 3 unit delays worst case form any input?

--Mark

[ivant]

I just want to add some more info to what Mark already said. In the real world, each gate needs some time to "settle" its outputs after the inputs are changed. That is, this is the minimum amount of time you need to wait before you're sure that the gate outputs will contain the correct values. This is called propagation time.

When you combine multiple gates in more complex ones, you need to compute the resulting propagation time. You go from simple NAND gates, up to CPUs and the whole computer in the end. This propagation time determines the maximum clock speed that you can use. If go above that (overclocking) you'll end up with a computer that doesn't compute correctly[1].

If you want a faster chip, you need to minimize the propagation time. In many cases this is done by adding more gates in it, rather than by using less. For example, the adder described the book is very simple, but a bit slow. There are various schemes to make a significantly faster ones, but they add more gates and complexity.

Also, gates consume power, so the more gates you have, the more power you'll need, right? But modern processors may switch off entire subsystems (e.g. whole cores), so they don't consume any power if they aren't needed. Again, it's not obvious that just by having less gates you'll consume less power.

In the end, it's like Mark said: go for the clarity with this course.

[1] The propagation time depends on many things. Even two chips from the same silicon waffle can have different propagation times. The manufacturers test and remove the buggy ones and the ones which are slower than their specs. What's left vary still vary, but within the specs.

The propagation time also depends on outside conditions, like temperature. So if you have a good chip and you have good cooling, you can overclock above what the provider specified.

--
Ivan

[ppfvy]

Thanks to both of you - I was thinking in terms of fewer gates being more efficient and an Or just being 3 Nands in disguise, but of course what actually matters for efficiency is how many gates a signal has to pass through to compute the value of the chip's output, which is easier to optimize from the 7-Or-gate implementation.

I imagine in the real world of hardware design, chips are not actually built by stringing together NAND gates to make everything else - surely it makes more sense to have all of the basic building block gates implemented directly from the metal (silicon?), even if NAND is sufficient to make everything in theory.

[ivant]

ppfvy wrote

I imagine in the real world of hardware design, chips are not actually built by stringing together NAND gates to make everything else - surely it makes more sense to have all of the basic building block gates implemented directly from the metal (silicon?), even if NAND is sufficient to make everything in theory.

It depends on the underlying technology really. With CMOS at least, you can't directly make the "positive" gates. That is, to make an AND(x, y), you'll need to have NOT(NAND(x, y)). The reason for this is, that using the P and N transistors, you can reinforce the signal in negative (reverse?, i'm not sure about the terminology) gates, but not in the "positive" ones.

This is what I mean by "reinforce" here: Say you treat input between 0V and 2V as logical zero, and input between 4V and 6V as logical one. Everything else is undefined. With CMOS you can build your gates in such a way, that the output is even more restricted, e.g. 0V - 1V for a logical 0 and 5V - 6V for logical 1. This is very important, because you have some losses and if you produced 4V as the output of one of the gates, it may be less than 4V when it reaches the input of the next gate. That would make the output of the second gate unpredictable.

With CMOS positive thinking won't get you far and double negation is your friend :)

Now, do they create everything from NANDs (or NORs?) or do they have separate NANDs, NOTs and NORs? I don't know. But I suspect, that at least some producers are using NANDs exclusively.