Simple way to generate random netlists of ALU cells

Hello,

I'm looking for a way to generate somewhat random netlists of upto 25
ALU-like cells.  As an illustration of the cells' level of
abstraction, please see http://www.doe.carleton.ca/~fma/RCHW/Cell.png.
The blue boxes are word-oriented computing/boolean logic.

I know that pure random netlists are not realistic, so I'm looking for
a more realistic scheme.  Related material that I've google so far
are:

   Mentor Graphics's Generator "PartGen":
   "Generation of Very Large Circuits to Benchmark the Partitioning of
   FPGAs"
   J. Pistorius   E. Legai   M. Minoux
   ISPD?99 : April 12 - April 14, 1999

   "Design of Experiments for Evaluation of BDD Packages Using
   Controlled Circuit Mutations"
   Justin E. Harlow III & Franc Brglez

PartGen assumes fine-grain logic elements, so interconnection
statistics may differ from my word-oriented ALU-like elements.  In
particular, my cells can take alot of inputs, each net representing a
multi-bit word.  Because PartGen deals with fine-grain, I assume that
many more levels of hierarchy are assumed.  I haven't yet inquired
about whether the program is available, or how quickly one can ramp up
on it to generate simple random netlists.

I am ploughing through the 2nd reference right now.

Can anyone suggest references, approaches, or ideas/considerations for
generating a somewhat random netlist at level of abstraction of my
cells?  I'm not necessarily looking for a program.  In fact, it would
probably be more convenient to code up the generator myself using
matlab, given some guiding constraints.

Thanks for any suggestions.

Fred
-- 
Fred Ma
Dept. of Electronics, Carleton University
1125 Colonel By Drive, Ottawa, Ontario
Canada, K1S 5B6

Fred Ma <fma@doe.carleton.ca> wrote in message news:<40A4605E.256F58DA@doe.carleton.ca>...
> Hello,
> 
> I'm looking for a way to generate somewhat random netlists of upto 25
> ALU-like cells.  As an illustration of the cells' level of
> abstraction, please see http://www.doe.carleton.ca/~fma/RCHW/Cell.png.
> The blue boxes are word-oriented computing/boolean logic.
> 

snipping

Looks like a datapath to me, and a piece of cake.

Why wouldn't you use a HDL, either one can describe bit twiddly ops. 

Verilog is esp suitable for that being very wire low level oriented.

You can almost as easily describe this in C by converting the HDL for
simulation purposes.

But I think I am missing your main point too.

regards

johnjakson_usa_com

john jakson wrote:
> 
> Fred Ma <fma@doe.carleton.ca> wrote in message news:<40A4605E.256F58DA@doe.carleton.ca>...
> > Hello,
> >
> > I'm looking for a way to generate somewhat random netlists of upto 25
> > ALU-like cells.  As an illustration of the cells' level of
> > abstraction, please see http://www.doe.carleton.ca/~fma/RCHW/Cell.png.
> > The blue boxes are word-oriented computing/boolean logic.
> >
> 
> snipping
> 
> Looks like a datapath to me, and a piece of cake.
> 
> Why wouldn't you use a HDL, either one can describe bit twiddly ops.
> 
> Verilog is esp suitable for that being very wire low level oriented.
> 
> You can almost as easily describe this in C by converting the HDL for
> simulation purposes.
> 
> But I think I am missing your main point too.

I'm actually not trying to model the ALU-like cell.  I'm trying to
generate random netlist of those cells.  However, a completely
random net list is not realistic.

Fred
-- 
Fred Ma
Dept. of Electronics, Carleton University
1125 Colonel By Drive, Ottawa, Ontario
Canada, K1S 5B6

Why?

Fred Ma wrote:

>
> I'm actually not trying to model the ALU-like cell.  I'm trying to
> generate random netlist of those cells.  However, a completely
> random net list is not realistic.
>
> Fred
> --
> Fred Ma
> Dept. of Electronics, Carleton University
> 1125 Colonel By Drive, Ottawa, Ontario
> Canada, K1S 5B6

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

Fred Ma wrote:
> I'm actually not trying to model the ALU-like cell.  I'm trying to
> generate random netlist of those cells.  However, a completely
> random net list is not realistic.

Ray Andraka wrote:
> Why?

Hi, Ray,

Not sure if you remember, but we met (I think at FCCM) a few
years back.  Hope things are going well with you.

Why am I trying to generate pseudorandom netlists?  I'm testing out a
placement algorithm for ALU arrays.

Why is a random netlist not realistic?  Designs usually have some kind
of hierarchy (effective hierarchy, even if not explicit).  I'm not an
expert in this area, but I've looked at a few papers on graph
clustering algorithms.  Hierarchical information is often captured as
a rooted tree, where each internal node represents a subgraph of the
netlist with a somewhat minimal cutset (compared to an arbitrarcy cut
at the same level of clustering).  A truly random graph will probably
not have the same degree of hierarchical structure.  You can still
force-feed it into a clustering algorthm to impose hierarchy, but the
criteria for choosing subgraphs will probably not be that distinct
between candidate subgraphs.

Intuitively, I don't expect a totally random graph to be easily
placable because there's too much random interdepedence between
arbitrary nodes.  A real netlist has more localization of
interconnect.

I'm currently looking through some papers on the topic of random graph
generation by Hutton & Pistorius (upon their recommendation).
However, they are meant for FPGAs, whereas the cell I mentioned in my
original post is quite different.  There are far fewer of them in a
circuit, and there are many more inputs.  I'm trying to get some
guiding considerations to cobble my own quick-and-dirty code in
matlab.

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
*|  If I don't reply to your email, please sent it again.  I may  |*
*|  have erased along with the deluge of post-filter spam.        |*

Fred Ma wrote:
> 
> Hierarchical information is often captured as
> a rooted tree, where each internal node represents a subgraph of the
> netlist with a somewhat minimal cutset (compared to an arbitrarcy cut
> at the same level of clustering).  A truly random graph will probably
> not have the same degree of hierarchical structure.  You can still
> force-feed it into a clustering algorthm to impose hierarchy, but the
> criteria for choosing subgraphs will probably not be that distinct
> between candidate subgraphs.

I just read what I wrote -- it's clear to someone who has seen it
before, but confusing otherwise.  The rooted tree is different from
graph for the netlist.  The tree just captures subsumption information
(a parent node subsumes a child node, thus forming a more aggregate
node, or "supernode").  If you travel down a path on the rooted tree,
you are travelling deeper and deeper into the nested supernodes.  When
you reach the leaf nodes at the bottom of the tree, you reached the
actual nodes in the circuit graph.  The physical interconnect doesn't
show up in the rooted tree at all.

Actually, maybe that picture isn't so obscure.  I think it might be
commoon placed for graph partitioning algorithms.

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
*|  If I don't reply to your email, please sent it again.  I may  |*
*|  have erased along with the deluge of post-filter spam.        |*

Fred Ma <fma@doe.carleton.ca> wrote in message news:<40A5873B.DC4721CA@doe.carleton.ca>...
> Fred Ma wrote:

 snipping

> Actually, maybe that picture isn't so obscure.  I think it might be
> commoon placed for graph partitioning algorithms.
> 
> Fred

Ok so you are doing P/R work, sort of guessed.

Why not hand design a reasonable datapath with lots of options that
can be parameterised.

Atleast in verilog (& probably VHDL) you can 'define just like in C,
and in verilog2000 use generate (VHDL does that too).

With that, 1 good datapath can now spawn possibly 100s of variations
small & large. For instance design a hierarchy of cells with specific
ports. Now create alternates for a no of these, a good candidate would
be the alu adder. You can have a dumb ripple adder, carry save added,
carry lookahead and so on, all pin compatible but using wildy
different amounts of logic, some regular & some not.

If your datapath has half a dozen widgets, you could make 2,3 ^6
versions in no time and they would be plausible. We end up doing that
anyway but chucking the slower ones along the way. You could do same
in a toy meta HDL if you add a define or generate primitive to it.

regards

johnjakson_usa_com

john jakson wrote:
> 
> Why not hand design a reasonable datapath with lots of options that
> can be parameterised.
> 
> Atleast in verilog (& probably VHDL) you can 'define just like in C,
> and in verilog2000 use generate (VHDL does that too).
> 
> With that, 1 good datapath can now spawn possibly 100s of variations
> small & large. For instance design a hierarchy of cells with specific
> ports. Now create alternates for a no of these, a good candidate would
> be the alu adder. You can have a dumb ripple adder, carry save added,
> carry lookahead and so on, all pin compatible but using wildy
> different amounts of logic, some regular & some not.
> 
> If your datapath has half a dozen widgets, you could make 2,3 ^6
> versions in no time and they would be plausible. We end up doing that
> anyway but chucking the slower ones along the way. You could do same
> in a toy meta HDL if you add a define or generate primitive to it.

I can't really change the design of the cell (which is already at a high
level).   I can only interconnect them in different ways.  The exact
behaviour of the cells are determined by control signals (not shown).
So I have to create random netlists of identical cells i.e. the cells
are the same throughout each netlist, as well as between netlists.

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
*|  If I don't reply to your email, please sent it again.  I may  |*
*|  have erased along with the deluge of post-filter spam.        |*

Fred,

Yes, I do remember you.  We hit a couple of the wineries that Friday
afternoon with you.  I realize now that I was also ambiguous.  I meant why
generate a random netlist.  I guessed it was for something with doing
studies with PAR, but wasn't sure.


Fred Ma wrote:

> Fred Ma wrote:
> > I'm actually not trying to model the ALU-like cell.  I'm trying to
> > generate random netlist of those cells.  However, a completely
> > random net list is not realistic.
>
> Ray Andraka wrote:
> > Why?
>
> Hi, Ray,
>
> Not sure if you remember, but we met (I think at FCCM) a few
> years back.  Hope things are going well with you.
>
> Why am I trying to generate pseudorandom netlists?  I'm testing out a
> placement algorithm for ALU arrays.
>
> Why is a random netlist not realistic?  Designs usually have some kind
> of hierarchy (effective hierarchy, even if not explicit).  I'm not an
> expert in this area, but I've looked at a few papers on graph
> clustering algorithms.  Hierarchical information is often captured as
> a rooted tree, where each internal node represents a subgraph of the
> netlist with a somewhat minimal cutset (compared to an arbitrarcy cut
> at the same level of clustering).  A truly random graph will probably
> not have the same degree of hierarchical structure.  You can still
> force-feed it into a clustering algorthm to impose hierarchy, but the
> criteria for choosing subgraphs will probably not be that distinct
> between candidate subgraphs.
>
> Intuitively, I don't expect a totally random graph to be easily
> placable because there's too much random interdepedence between
> arbitrary nodes.  A real netlist has more localization of
> interconnect.
>
> I'm currently looking through some papers on the topic of random graph
> generation by Hutton & Pistorius (upon their recommendation).
> However, they are meant for FPGAs, whereas the cell I mentioned in my
> original post is quite different.  There are far fewer of them in a
> circuit, and there are many more inputs.  I'm trying to get some
> guiding considerations to cobble my own quick-and-dirty code in
> matlab.
>
> Fred
> --
> Fred Ma, fma@doe.carleton.ca
> Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada
> *|  If I don't reply to your email, please sent it again.  I may  |*
> *|  have erased along with the deluge of post-filter spam.        |*

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

Ray Andraka wrote:
> 
> Fred,
> 
> Yes, I do remember you.  We hit a couple of the wineries that Friday
> afternoon with you.  I realize now that I was also ambiguous.  I meant why
> generate a random netlist.  I guessed it was for something with doing
> studies with PAR, but wasn't sure.

Yeah, it was cool (the wineries).

So is the PAR world.  Who'da ever thunk that generating random
circuits was such a deep topic.

Fred
-- 
Fred Ma, fma@doe.carleton.ca
Dept. of Electronics, Carleton University, Ottawa, Ontario, Canada