Efficient implementation of logic gates

[netanel]

I was wondering which implementation of Or16 is more efficient.

This one:

CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    Or(a=a[0], b=b[0], out=out[0]);
    Or(a=a[1], b=b[1], out=out[1]);
    Or(a=a[2], b=b[2], out=out[2]);
    Or(a=a[3], b=b[3], out=out[3]);
    Or(a=a[4], b=b[4], out=out[4]);
    Or(a=a[5], b=b[5], out=out[5]);
    Or(a=a[6], b=b[6], out=out[6]);
    Or(a=a[7], b=b[7], out=out[7]);
    Or(a=a[8], b=b[8], out=out[8]);
    Or(a=a[9], b=b[9], out=out[9]);
    Or(a=a[10], b=b[10], out=out[10]);
    Or(a=a[11], b=b[11], out=out[11]);
    Or(a=a[12], b=b[12], out=out[12]);
    Or(a=a[13], b=b[13], out=out[13]);
    Or(a=a[14], b=b[14], out=out[14]);
    Or(a=a[15], b=b[15], out=out[15]);
}

Or this one:

CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    Not16(in=a, out=NOTa);
    Not16(in=b, out=NOTb);
    And16(a=NOTa, b=NOTb, out=NOTaAndNOTb);
    Not16(in=NOTaAndNOTb, out=out);
}

Is it correct to say that since Or is built from 3 gates (not,not,nand), the first implementation has a total of 48 chips (3*16) so it is more efficient than the second, which has 64 chips total (16*4)?

[cadet1620]

You could also build a Nand16 to use in your second version and it would have the same Nand count as the first one.

The thing to realize about gate counting is that 2-input Nand can be used to build any logic circuit, not that it must be used as the basic building block. Modern ICs (CMOS) can easily make Nor gates. Both require 4 transistors for 2-input gates, but for reasons of physics, Nand gates are smaller and therefore preferred. Even smaller, only 2 transistors, is a transmission gate which is like a logic controlled switch. They are very handy for building multiplexors.

CMOS can also make more complex gates with small transistor counts. For instance and-or-invert not(a&b | c&d) is only 8 transistors, as is or-and-invert.

Nand count does make a reasonable first order approximation for circuit complexity, just don't read too much into it.


FWIW, I wrote a quick and dirty preprocessor for HDL. My Or16.hdlx consists of the single line
    Or(a=a[#], b=b[#], out=out[#];
and the preprocessor replicates it 16 times.

--Mark

[netanel]

Thank you for detailed answer. I would like to ask though, on the same note, about an implementation of Mux16, and also a question about HDL in general. Having read and understood your answer that I shouldn't read too much into it, I still have to think that some implementations are much more efficient than others, for example, this Mux16:

CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
    Not(in=sel, out=NOTsel);
    And16(a=a, 
		b[0]=NOTsel,
		b[1]=NOTsel,
		b[2]=NOTsel,
		b[3]=NOTsel,
		b[4]=NOTsel,
		b[5]=NOTsel,
		b[6]=NOTsel,
		b[7]=NOTsel,
		b[8]=NOTsel,
		b[9]=NOTsel,
		b[10]=NOTsel,
		b[11]=NOTsel,
		b[12]=NOTsel,
		b[13]=NOTsel,
		b[14]=NOTsel
		b[15]=NOTsel, out=aAndNOTsel);
    And16(a=b, b[0]=sel,
		b[1]=sel,
		b[2]=sel,
		b[3]=sel,
		b[4]=sel,
		b[5]=sel,
		b[6]=sel,
		b[7]=sel,
		b[8]=sel,
		b[9]=sel,
		b[10]=sel,
		b[11]=sel,
		b[12]=sel,
		b[13]=sel,
		b[14]=sel,
		b[15]=sel, out=bAndSel);
    Or16(a=aAndNOTsel, b=bAndSel, out=out);
}

Versus this Mux16:

CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}

In the second implementation, I had to use 16 Mux gate to deal with the single bit sel input.
However in the first implementation, I just spread that one bit into 15 inputs, basically trading wire count for chip count, am I right?

I also wanted to know if there is a shorter way to spread one bit into multiple bits, like I did in the first implementation with sel, something like:

b[0..15]=sel
or maybe
b[]=sel

[cadet1620]

Yes, in general sharing a part like the Not across several parts used in the implementation is a good idea. This sort of optimization is done by industrial hardware synthesis tools (hardware compilers). This is similar to the way that software compilers identify common sub-expressions and rearrange your code to improve loop efficiency.

For this course, one objective is to learn how to think hierarchically and use abstractions. Teach low-level hardware design is well beyond the course's scope.

Consider your two implementations. If you learn a better way to make Mux, nothing needs to change in the second Mux16, but you may need to substantially rewrite the first implementation. (Think about how to implement Mux using Not and 3 Nands.)

In this HDL, there is no built in way to connect one signal to a bus. You can write two chips, Wire(in=x, out=y) and Wire16(in=x, out=y16), using Ands and ignore their gate count with the understanding that they are logically just wires.

After you have written your Mux16, you can use it to do the same thing:
    Mux16(sel=x, a=false, b=true, out=y16);

[For Mux4Way16, think about how to build it using 3 Mux16.]

--Mark

[netanel]

Thank you again for you answer, definitely gave me some good insights about the whole deal. :)