FPGA Central

Here is a question:
"Given a combinational circuit, for each primary output, find the
number of primary inputs that this output depends on."

It is easy to do structual analysis for a small-size circuit. But for a
circuit with million gates, we need to find a effecient way.

Now assume a gate-level Verilog code for this circuit is given, I plan
to write a script (e.g., Perl) to scan this Verilog code, then for each
output, trace back to find the primary input on which it depends. But I
am new to both Perl and Verilog.
So could you please give me any suggestion or any script example for
references? or is there other way to address this problem effeceintly?

Thanks very much!
Fei

And also, can Verilog PLI deal with this problem?


Please give me a hint... Thanks!
Fei

Fei wrote:
> Here is a question:
> "Given a combinational circuit, for each primary output, find the
> number of primary inputs that this output depends on."
>
> It is easy to do structual analysis for a small-size circuit. But for a
> circuit with million gates, we need to find a effecient way.
>
> Now assume a gate-level Verilog code for this circuit is given, I plan
> to write a script (e.g., Perl) to scan this Verilog code, then for each
> output, trace back to find the primary input on which it depends. But I
> am new to both Perl and Verilog.
> So could you please give me any suggestion or any script example for
> references? or is there other way to address this problem effeceintly?

Look up "Boolean Decision Diagrams" (aka BDDs) on your
favorite search engine; I even saw a web page once which compared
several BDD packages (I don't have the URL handy).

If I were trying to solve this problem, I would use Perl (or
a C lexer/parser package) to scan the Verilog and pipe the output
to a BDD package, asking it to build BDDs for each of the module
output ports. From there, it shouldn't be too hard to write code
to "walk the BDD" for each output to see if an input is ignored
or if it "matters" to the output. The BDD package does most of
the hard work of reducing the Boolean logic so -- if an input
doesn't affect the output -- the BDD package should either
eliminate it from the BDD or figure out that the '0' & '1'
pointers of that input's node in the BDD tree point to the same
place.

I haven't worked with BDDs for several years; early BDD
packages created very large BDDs (running out of memory) for
parity trees & other circuits which generated a lot of XOR
gates/functions. If your Verilog has large parity trees, adders,
etc. -- anything which generates a lot of XOR functions, you may
wish to benchmark different BDD packages with large XOR circuits
to see which ones make the most sense for your application.

"Fei" <[email protected]> wrote in message
news:[email protected] oups.com...
> "Given a combinational circuit, for each primary output, find the
> number of primary inputs that this output depends on."
>
> It is easy to do structual analysis for a small-size circuit.

You mean by visual inspection.

>But for a circuit with million gates, we need to find a effecient way.
>
> Now assume a gate-level Verilog code for this circuit is given, I plan
> to write a script (e.g., Perl) to scan this Verilog code, then for each
> output, trace back to find the primary input on which it depends. But I
> am new to both Perl and Verilog.
> So could you please give me any suggestion or any script example for
> references? or is there other way to address this problem effeceintly?

A PERL script "parse" Verilog will likely be unreliable. In a million
lines of code, "everything happens", which means you will
very likely will need a full Verilog parser just to make sure
that you don't misinterpret the source text.

Ideally, you'd have a Verilog parser, and could walk over the syntax
tree representing the expression for each output to enumerate the inputs.
Of course, symbols in that expression may represent other combinational
outputs,
thus you'll have to through a fixpoint procedure to arrive at just
the inputs values.

A full Verilog parser (including SystemVerilog ) that will build
you the trees is commercially available from:
http://www.semdesigns.com/Products/F...gFrontEnd.html.

--
Ira D. Baxter, Ph.D., CTO 512-250-1018
Semantic Designs, Inc. www.semdesigns.com

A million gates of gate-level Verilog is likely to be the output of
some synthesis tool, and probably only uses a very small subset of the
language, e.g. instantiations of library components and nothing else.
The OP only needs to identify combinatorial logic, and storage elements
(ffs, latches and rams).

Someone experienced in both Perl and Verilog (and the library used)
could probably implement the parser for the required subset of the
language from scratch in about a day. (Well, that's how long it took
the last time I wrote one.)

Regards,
Allan