Re: [f-cpu] "Tree"

[Juergen Goeritz <goeritz@oekomm.de>]

On Wed, 9 Jan 2002, Bruno Bougard wrote:
> Hi All,
> 
> I have some remarks about this 'Tree story':
> 
> You give me the feeling that you apply some kind of bottom-up
> methodology. Building your design from the lowest level to the highest.
> Professional IC designers always work top-down, from spec to gate level,
> through different abstraction level.

<snip>

Hi Bruno,

thank you very much for this explanation. Since I am from both
worlds (hardware and software) I do not completely agree to your
statement though. Let me take you (all) onto a short excursion:

The top-down approach reflects the division of the complete
problem into smaller pieces. The bottom-up process means the
implementation and integration of small pieces to build a whole.

Only both parts together will ever be able to produce a result.
I don't know of any development, where the spec wasn't changed
during the development process (or held incomplete) or the
technology was adapted to reach the specified goal. I am not
talking about imitation (re-implement of existing chip) here.

But let's go back to top-down. You have to define the outer
interface and function of your 'whole' system first, then you
can start fill it with something - the division into smaller
parts for which you also define the interfaces and some idea
about their functionality. This is a recursive process until
you end up with trivial entities. In our case - macros or gates.
There a quite a few possibilities to divide the functionality.

The last part of this process is handed over to the synthesizer.
And as you stated above, professional IC designers know how
their synthesizer works and let it do the rest (optimization)
for ease of design description. They adapt their writing to the
synthesizer to get the best result. I see this as symbiosis
with and focusing on the synthesizer.

Why is it such a problem to optimize the design?

This is due to the two-dimensional structure of the problem
(inputs vs. one output). There are ways to reduce such a table
into an AND/OR/NOT representation in a really short time (this
is PLD talking) - optimzers like FACT (single bit) or ESPRESSO
(multi bit) do it very nicely. By the way I also worked with
a multi bit optimizer called BRUNO in those days.

Now come to ASICs and FPGAs:
Since n-input AND(OR) gates are not available (or hard to
implement with a good timing) on the ASIC other algorithms
were developed. These algorithms try to find other patterns
inside the table. XOR detection is one of these. Most very
small gates do have some negated inputs or outputs. When you
can use them in the design the size will be less than with
the other non-inverting gates.

Thus the synthesizer tries (and I mean it!) to find an optimal
solution. But there is a pitty - the gate fanout (the power to
drive other gates). The smallest gates only got low fanout.
Higher fanout costs additional size. AND - the gate delay is
fanout dependent. This multiplies another 2 dimensions into
the problem. And we are still talking about a single output bit.
Similar patterns may be used by multiple output bits though...
Delay and size optimization is the way, but where is the optimum?
And after that you still have to place those gates onto the chip
and wiring does also take size and adds delays and crosstalk...

When I started in 1987 I did most optimization by hand. ;-)
Meanwhile these days are gone.

JG

*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/