16 input 'AND' operation in ASIC

[Weng Tianxiang]

Hi,
I would like to know which logic is best in ASIC implementation for
following equation in schematics entry:

B <= not (A1 and A2 and ... and A16);

The best solution for speed is using one large NAND with 16 inputs or
anything else?

Thank you.

Weng

 

[Pieter Hulshoff]

I would like to know which logic is best in ASIC implementation for
following equation in schematics entry:

B <= not (A1 and A2 and ... and A16);

The best solution for speed is using one large NAND with 16 inputs or
anything else?

Don't worry too much about such things. In general Synopsys is more than
capable of making that decision for you. You can help Synopsys a tad
though, by creating a bit of an AND tree using (). It's most likely
Synopsys will use 2 or 4 input ANDs, so something like
B <= not ((((A1 and A2) and (A3 and A4) and ((A5 and A6) and (A7 and A8)))
and (((A9 and A10) and (A11 and A12)) and ((A13 and A14) and (A15 and
A16))))

Regards,

Pieter Hulshoff

 

[Weng Tianxiang]

Don't worry too much about such things. In general Synopsys is more than
capable of making that decision for you. You can help Synopsys a tad
though, by creating a bit of an AND tree using (). It's most likely
Synopsys will use 2 or 4 input ANDs, so something like
B <= not ((((A1 and A2) and (A3 and A4) and ((A5 and A6) and (A7 and A8)))
and (((A9 and A10) and (A11 and A12)) and ((A13 and A14) and (A15 and
A16))))

Regards,

Pieter Hulshoff

Hi Pieter,
Thank you for your suggestion.

I want to know why 16 input NAND is inferior to 2 levels of 4 input
equivalent logic in terms of speed.

Could you please give me an explanation.

Weng

 

[Pieter Hulshoff]

I want to know why 16 input NAND is inferior to 2 levels of 4 input
equivalent logic in terms of speed.
Could you please give me an explanation.

It'll depend on your ASIC technology most likely. Look in the databook of
the technology you're planning to use, and see what the delays of 2, 4, and
16 input ANDs will be. I don't even know how many technology companies
would offer a 16 input AND. Synopsys should know which one to take though,
though we've seen situations in the past where Synopsys would refuse to use
muxes, even if they were clearly the best choice for the job.

Regards,

Pieter Hulshoff

 

[David Bishop]

Hi,
I would like to know which logic is best in ASIC implementation for
following equation in schematics entry:

B <= not (A1 and A2 and ... and A16);

The best solution for speed is using one large NAND with 16 inputs or
anything else?

Once again, recursion is the answer:

-- done in a recursively called function.
function and_reduce (arg : std_logic_vector )
return std_logic is
variable Upper, Lower : std_logic;
variable Half : integer;
variable BUS_int : std_logic_vector ( arg'length - 1 downto 0 );
variable Result : std_logic;
begin
if (arg'LENGTH < 1) then -- In the case of a NULL range
Result := '1'; -- Change for version 1.3
else
BUS_int := to_ux01 (arg);
if ( BUS_int'length = 1 ) then
Result := BUS_int ( BUS_int'left );
elsif ( BUS_int'length = 2 ) then
Result := BUS_int ( BUS_int'right ) and BUS_int ( BUS_int'left );
else
Half := ( BUS_int'length + 1 ) / 2 + BUS_int'right;
Upper := and_reduce ( BUS_int ( BUS_int'left downto Half ));
Lower := and_reduce ( BUS_int ( Half - 1 downto BUS_int'right ));
Result := Upper and Lower;
end if;
end if;
return Result;
end;

function nand_reduce (arg : std_logic_vector )
return std_logic is
begin
return not and_reduce (arg);
end;

This will give you the most efficient possible synthesis.
Most tools will make an efficent synthesis of this, but if you
are using one of the "built in" synthesis tools you are best
holding it's hand.

 

[Sylvain Munaut]

I want to know why 16 input NAND is inferior to 2 levels of 4 input
equivalent logic in terms of speed.

Could you please give me an explanation.

A first guess would be :

Look at the N-Mos tree

__|
--||__
|
__|
--||__
|

 

[Tom Verbeure]

I want to know why 16 input NAND is inferior to 2 levels of 4 input
equivalent logic in terms of speed.

Could you please give me an explanation.

As other have said, it purely depends on your standard cell library.
For each cell, a trade-off has to be made between speed and area. A lot
of libraries will only focus on area for cells that have a high number
of inputs. As a result, it's faster to use multiple smaller cells than
one bigger cell.

In the past, I have seen libraries where a cell with a simple 4-to-1
mux was significantly slower than the version built with multiple
smaller cells.

If you're using schematic entry, you're only way to find the best
implmentation is to consult the databook of your library. The problem
there is that you'll also have to estimate the loading on the nets to
make the comparison accurate. Obviously, A synthesis tool is usually
(!) much better at this.

Tom

 

[Weng Tianxiang]

A first guess would be :

Look at the N-Mos tree

__|
--||__
|
__|
--||__
|
.
.
.
__|
--||__
|
__|
--||__
|


Each MOS gate threshold is relative to it's source potential.
Now, the potential difference between source and drain of all
theses MOS is not zero ...
Let's say they are 0.1v.
The sixteenth MOS will have a threshold voltage 1.5v above the
first one ...

(totally arbitrary numbers ...)


Sylvain

Hi Sylvain,
Your answer is reasonable.

I want to know normally what a suggested max number of inputs for a NAND device is.

Weng

 

[Sylvain Munaut]

I want to know normally what a suggested max number of inputs for a NAND device is.

I'd look at what your ASIC manufacturer is offering you.

Theorically, it doesn't offers you interconnected MOS, but a NAND gate and you
don't know about the non-symetry or whatever caracteristics the in/out have.
All you know is that they are "good enough" so that it effectivly behave like
a NAND.

If you manufacturer offers you a 16 NAND gate guaranted for the same delay as a
2 NAND gate, I'd go for it ...

As all others told, you must look at what they offer you.


Sylvain

 

[Weng Tianxiang]

Once again, recursion is the answer:

-- done in a recursively called function.
function and_reduce (arg : std_logic_vector )
return std_logic is
variable Upper, Lower : std_logic;
variable Half : integer;
variable BUS_int : std_logic_vector ( arg'length - 1 downto 0 );
variable Result : std_logic;
begin
if (arg'LENGTH < 1) then -- In the case of a NULL range
Result := '1'; -- Change for version 1.3
else
BUS_int := to_ux01 (arg);
if ( BUS_int'length = 1 ) then
Result := BUS_int ( BUS_int'left );
elsif ( BUS_int'length = 2 ) then
Result := BUS_int ( BUS_int'right ) and BUS_int ( BUS_int'left );
else
Half := ( BUS_int'length + 1 ) / 2 + BUS_int'right;
Upper := and_reduce ( BUS_int ( BUS_int'left downto Half ));
Lower := and_reduce ( BUS_int ( Half - 1 downto BUS_int'right ));
Result := Upper and Lower;
end if;
end if;
return Result;
end;

function nand_reduce (arg : std_logic_vector )
return std_logic is
begin
return not and_reduce (arg);
end;

This will give you the most efficient possible synthesis.
Most tools will make an efficent synthesis of this, but if you
are using one of the "built in" synthesis tools you are best
holding it's hand.

Tom,
Thank you and others.

What I really want to do is to write 2 patents, one of which needs a
NAND of 19 inputs, another of N inputs. What should I correctly draw
in schematics entry without leaving any legal loopholes in the future?
In 19 input case, there are several combinations of optimized logics:
first level: 2*9, 3*5+4, 4*4+3, 5*3+4, 6*3.

Any suggestions are welcome.

Weng

 

[Sylvain Munaut]

What I really want to do is to write 2 patents, one of which needs a
NAND of 19 inputs, another of N inputs. What should I correctly draw
in schematics entry without leaving any legal loopholes in the future?
In 19 input case, there are several combinations of optimized logics:
first level: 2*9, 3*5+4, 4*4+3, 5*3+4, 6*3.

Any suggestions are welcome.

Well, I guess that you can just note a 19 input black box implementing a NAND.

I don't have any legal competence except common sense, but if implementing
the NAND as 2 9 inputs ones allows a competitor to copy your whole design
just changing that, that's just plain stupid !



Sylvain

 

[rickman]

Tom,
Thank you and others.

What I really want to do is to write 2 patents, one of which needs a
NAND of 19 inputs, another of N inputs. What should I correctly draw
in schematics entry without leaving any legal loopholes in the future?
In 19 input case, there are several combinations of optimized logics:
first level: 2*9, 3*5+4, 4*4+3, 5*3+4, 6*3.

Any suggestions are welcome.

For something as important as a patent, you need to consult a patent
expert. If you want my limited knowledge on the matter, you want to
make a patent as general as possible. If the implimentation of the NAND
function is not important to the patent, then just make it a box
implementing a NAND function without specifying the details. The more
you spec, the easier it will be to work around the patent.

--

Rick "rickman" Collins

(e-mail address removed)
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX

 

[Ralf Hildebrandt]

I want to know normally what a suggested max number of inputs for a NAND device is.

Your synthesis tool will decide, what fits best. Even if you have a 100
bit NAND, it will create a bunch of combinational logic, that just
computes this operation - but, as easily can be seen, not with a single
NAND.

In typical ASIC libraries bigger gates have a higher delay than smaller
ones (have a look at the vital description of you library). Therefore
even if you describe a 8 bit NAND the compiler may say "no way" and
infer a block of smaller and faster gates for the desired function.

Ralf