Fwd: Very basic RTL synthesis question by a hobbyist

Started by Aidan Keady February 4, 2014
Hi,

This has ended up being quite rambling - hope it's of some use! - the short
version is look at the espresso logic optimiser [1] and book [2] and
possibly see how the priority comes down to just combinational logic like
the other examples.

I think you're right that optimisation usually happens before the logic is
mapped to a particular target library.

Something like the espresso [1] logic minimiser will see that both your
original logic cases are identical and they should synthesise to the same
logic. The order of the expressions doesn't matter in your first example,
as the inputs are fully defined for each term - there's no overlap between
s="00" and the other possibilities.

For the final example, there is a priority - however, the logic is still
combinational.

When I was doing a masters in '89, I wrote a C program for logic
minimisation which did something like espresso (I don't know if espresso
was available then, I started from scratch with by reading [2] by the guys
behind espresso) but also further optimised the logic to 2-input functions,
because that's what we wanted at the time. It was for a DRC program - it
generated layers and check layers by ANDing, ORing etc. the drawn layers -
the software ran very slowly on a VAX - it was an overnight job for very
small circuits, so there was considerable benefit in optimising the number
of operations required to run the checks - I think we never used it as we
got some commercial DRC software and new machines too! Eventually, I made
the program write out logic gates in netlist formats and taped out a
digital filter part-generated using 2-input logic gates from this (on
MIETEC 2.4um technology).

I don't have my old logic optimiser to hand now (I think I can still dig it
up, given about a month), but I remember the input format. Your first
example becomes:

2 - no. of inputs
4 - no. of outputs
4 - no. of p-terms
003334 - inputs outputs - I used 3 & 4 for 0 and 1 in the outputs, to
distinguish them from the inputs! It may actually be more confusing :D
013343
103433
114333

By crunching away using the operations in [2], you should get the optimised
logic.

Your priority-encoded logic is expressible in the same terms, introducing
the digit 2, for "don't care" inputs.

Those functions become:

4 - no. of inputs
2 - no. of outputs
4 - no. of p-terms
122244
012243
001234
000233

In fact, the 2 is only a short-hand; one could also write out the p-terms
explicitly (e.g. 100044, 100144, 101044, 101144, 110044, 110144, 111044,
11144 instead of 122244), the optimiser will quickly realise that for line
1, all inputs are "don't care" apart from r(3).

Maybe the trick in seeing how the priority encoder maps to a normal
optimisation problem is seeing that for the second case to be reached, r(3)
must be 0 and so on and writing the p-terms in this way. Once this is
done, the logic minimisation proceeds as normal.

ATB,
Aidan.

[1] http://diamond.gem.valpo.edu/~dhart/ece110/espresso/tutorial.html
[2] Robert K. Brayton, Gary Hachtel, Curtis McMullen, and Alberto
Sangiovanni-Vincentelli, *Logic Minimization Algorithms for VLSI Synthesis*,
Kluwer Academic Publishers, Boston/Dordrecht/London, 1984.
On 5 February 2014 00:45, Jon Kirwan wrote:

> On Wed, 5 Feb 2014 01:21:02 +0100, you wrote:
>
> > Most FPGAs are LUT based. As long as the number of inputs to
> > a function is lower than the number of inputs to a LUT it
> > does not matter what the function is, it will always have
> > the same cost.
> > Thanks. This answers the question in some cases. I have an
> old Xilinx 4000 series board. What about that?
>
> But the actual question I'm asking is more broadly about
> synthesis generally. I might be synthesizing an ASIC. Or it
> may target some specific FPGA with various cell types I can
> only imagine.
>
> The question I'm foundering on is whether or not synthesis
> tools will see the two ways of expressing the goal
> identically, internally within their intermediate analysis
> structures, before targeting some specific device -- whether
> standard cell ASIC or modern FPGA. (I guess I'm currently
> imagining this as a "back end" process. I could be wrong
> about that, though.)
>
> Thanks,
> Jon
>
>
>
Okay!!! THANKS!! This was the kind of thinking I was/am
looking for. I need to re-read this a few times and work
things out by hand on paper in order to (a) see if I follow
and have no more questions or (b) see if it's not all there
for me and have some questions.

But this reads about like what I hoped to see!

Thanks so much,
Jon
On Wed, 5 Feb 2014 02:31:54 +0000, you wrote:

>Hi,
>
>This has ended up being quite rambling - hope it's of some use! - the short
>version is look at the espresso logic optimiser [1] and book [2] and
>possibly see how the priority comes down to just combinational logic like
>the other examples.
>
>I think you're right that optimisation usually happens before the logic is
>mapped to a particular target library.
>
>Something like the espresso [1] logic minimiser will see that both your
>original logic cases are identical and they should synthesise to the same
>logic. The order of the expressions doesn't matter in your first example,
>as the inputs are fully defined for each term - there's no overlap between
>s="00" and the other possibilities.
>
>For the final example, there is a priority - however, the logic is still
>combinational.
>
>When I was doing a masters in '89, I wrote a C program for logic
>minimisation which did something like espresso (I don't know if espresso
>was available then, I started from scratch with by reading [2] by the guys
>behind espresso) but also further optimised the logic to 2-input functions,
>because that's what we wanted at the time. It was for a DRC program - it
>generated layers and check layers by ANDing, ORing etc. the drawn layers -
>the software ran very slowly on a VAX - it was an overnight job for very
>small circuits, so there was considerable benefit in optimising the number
>of operations required to run the checks - I think we never used it as we
>got some commercial DRC software and new machines too! Eventually, I made
>the program write out logic gates in netlist formats and taped out a
>digital filter part-generated using 2-input logic gates from this (on
>MIETEC 2.4um technology).
>
>I don't have my old logic optimiser to hand now (I think I can still dig it
>up, given about a month), but I remember the input format. Your first
>example becomes:
>
>2 - no. of inputs
>4 - no. of outputs
>4 - no. of p-terms
>003334 - inputs outputs - I used 3 & 4 for 0 and 1 in the outputs, to
>distinguish them from the inputs! It may actually be more confusing :D
>013343
>103433
>114333
>
>By crunching away using the operations in [2], you should get the optimised
>logic.
>
>Your priority-encoded logic is expressible in the same terms, introducing
>the digit 2, for "don't care" inputs.
>
>Those functions become:
>
>4 - no. of inputs
>2 - no. of outputs
>4 - no. of p-terms
>122244
>012243
>001234
>000233
>
>In fact, the 2 is only a short-hand; one could also write out the p-terms
>explicitly (e.g. 100044, 100144, 101044, 101144, 110044, 110144, 111044,
>11144 instead of 122244), the optimiser will quickly realise that for line
>1, all inputs are "don't care" apart from r(3).
>
>Maybe the trick in seeing how the priority encoder maps to a normal
>optimisation problem is seeing that for the second case to be reached, r(3)
>must be 0 and so on and writing the p-terms in this way. Once this is
>done, the logic minimisation proceeds as normal.
>
>ATB,
>Aidan.
>
>[1] http://diamond.gem.valpo.edu/~dhart/ece110/espresso/tutorial.html
>[2] Robert K. Brayton, Gary Hachtel, Curtis McMullen, and Alberto
>Sangiovanni-Vincentelli, *Logic Minimization Algorithms for VLSI Synthesis*,
>Kluwer Academic Publishers, Boston/Dordrecht/London, 1984.


To post a message, send it to: f...
To unsubscribe, send a blank message to: f...Yahoo Groups Links

<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/fpga-cpu/

<*> Your email settings:
Individual Email | Traditional

<*> To change settings online go to:
http://groups.yahoo.com/group/fpga-cpu/join
(Yahoo! ID required)

<*> To change settings via email:
f...
f...

<*> To unsubscribe from this group, send an email to:
f...

<*> Your use of Yahoo Groups is subject to:
http://info.yahoo.com/legal/us/yahoo/utos/terms/