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

>

>

>

# Fwd: Very basic RTL synthesis question by a hobbyist

Started by ●February 4, 2014

Posted by ●February 4, 2014

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/

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/