FpgaC developers wanted :)

The open source FpgaC project is looking for a few more developers in
various technology areas and skill levels. One project is updating the
generic LUT only technology mapping code that came with TMCC written a
decade ago, to a newer algorithm that better fits current technology
FPGAs today.
We've started this with several changes, and there is lots more fun
work to go.

The next part of this project, is given a truth table, is to find the
best way to decompose it into LUT's and MUX's. This project is
available for anyone that would like it. Since it's pretty issolated
from the compiler guts, and will be implemented in the device specific
output functions, it's a good project for someone wanting to get their
feet wet as an internals developer.

This isn't exactly easy to do well, but almost any implementation will
be better than the current fitting strategy for LUT only mapping, so
refinement can happen over time as the developers skills build in this
technology area. This is an area of active and competitive research, so
it might make an interesting undergraduate project, or graduate level
thesis.

Interesting reading is related to the Quine-McCluskey algorithm
(implemented in FpgaC) and general logic synthesis algorithms. See:

        http://www.eecs.berkeley.edu/~alanmi/abc/

http://embedded.eecs.berkeley.edu/Respep/Research/mvsis/software.html

http://www.eecg.toronto.edu/~jzhu/releases/fbdd/info_web/index.html
        http://www.ecs.umass.edu/ece/labs/vlsicad/bds/bds.html
        http://service.felk.cvut.cz/vlsi/prj/BOOM/

Good resume builder project for someone interested in EDA software
tools as a job.

http://sourceforge.net/projects/fpgac

Have fun,
John

fpga_toys@yahoo.com wrote:
> The open source FpgaC project is looking for a few more developers in
> various technology areas and skill levels. One project is updating the
> generic LUT only technology mapping code that came with TMCC written a
> decade ago, to a newer algorithm that better fits current technology
> FPGAs today.
> We've started this with several changes, and there is lots more fun
> work to go.
>
> The next part of this project, is given a truth table, is to find the
> best way to decompose it into LUT's and MUX's. This project is
> available for anyone that would like it. Since it's pretty issolated
> from the compiler guts, and will be implemented in the device specific
> output functions, it's a good project for someone wanting to get their
> feet wet as an internals developer.
>
> This isn't exactly easy to do well, but almost any implementation will
> be better than the current fitting strategy for LUT only mapping, so
> refinement can happen over time as the developers skills build in this
> technology area. This is an area of active and competitive research, so
> it might make an interesting undergraduate project, or graduate level
> thesis.
>
> Interesting reading is related to the Quine-McCluskey algorithm
> (implemented in FpgaC) and general logic synthesis algorithms. See:
>
>         http://www.eecs.berkeley.edu/~alanmi/abc/
>
> http://embedded.eecs.berkeley.edu/Respep/Research/mvsis/software.html
>
> http://www.eecg.toronto.edu/~jzhu/releases/fbdd/info_web/index.html
>         http://www.ecs.umass.edu/ece/labs/vlsicad/bds/bds.html
>         http://service.felk.cvut.cz/vlsi/prj/BOOM/
>
> Good resume builder project for someone interested in EDA software
> tools as a job.
>
> http://sourceforge.net/projects/fpgac
>
> Have fun,
> John

Hi John,

I have to ask are you the head developer of this project?

Also I see University of Toronto is heavily involved with your project.
While I do not go to that school, I go to a lesser known University in
the area, do you have any contacts there?

Thanks

-Isaac

Isaac Bosompem wrote:
> I have to ask are you the head developer of this project?

I founded the FpgaC project, and drive it to some extent, but view it
as a group effort.

> Also I see University of Toronto is heavily involved with your project.
> While I do not go to that school, I go to a lesser known University in
> the area, do you have any contacts there?

They have not been active in FpgaC, other than providing BSD licensed
TMCC sources we used as a foundation. I exchange emails with the
original author from time to time, but he is too busy in other projects
to participate at this time.

In article <1143687230.719515.136950@j33g2000cwa.googlegroups.com>,
 <fpga_toys@yahoo.com> wrote:
>
>The next part of this project, is given a truth table, is to find the
>best way to decompose it into LUT's and MUX's. 

What format is the truth table in?  (BLIF, PLA, some other internal data 
structure)

So is this the tech mapping step?  You've already created the truth table that 
represents some part of the design and you need to map it into the underlying 
architecture. Sounds interesting.


>This project is
>available for anyone that would like it. Since it's pretty issolated
>from the compiler guts, and will be implemented in the device specific
>output functions, it's a good project for someone wanting to get their
>feet wet as an internals developer.
>
>This isn't exactly easy to do well, but almost any implementation will
>be better than the current fitting strategy for LUT only mapping, so
>refinement can happen over time as the developers skills build in this
>technology area. This is an area of active and competitive research, so
>it might make an interesting undergraduate project, or graduate level
>thesis.
>
>Interesting reading is related to the Quine-McCluskey algorithm
>(implemented in FpgaC) and general logic synthesis algorithms. See:
>
>        http://www.eecs.berkeley.edu/~alanmi/abc/

Ah, yes, Alan is on the cutting edge with this And-Inverter Graph stuff.  He's 
also a very good programmer.
Can you make use of what is already in ABC?  While I would hesitate to use 
code from some other university projects that have appeared in the past, I 
would not hesistate to use Alan's code; it's generally engineered very well.  

Phil

Phil Tomson wrote:
> What format is the truth table in?  (BLIF, PLA, some other internal data
> structure)

Currently just a 2^n bit table, with a linked list for the associated
var's.

> So is this the tech mapping step?  You've already created the truth table that
> represents some part of the design and you need to map it into the underlying
> architecture. Sounds interesting.

Internally, each signal in TMCC/FpgaC has always been a truth table
with var list, limited to 4 inputs, and mapped to LUTs at netlist
output time. Simple optimizations, like don't cares and duplicate
removal have been applied to this 4-lut set to generate a reasonable
netlist, that's a little deeper than can be achieved by allowing the
internal representation to be wider than a 4-LUT. Widening up the
internal representation allows for F5/F6 MUX's to be easily used,
controlling the depth of the LUT tree, and better don't care removal,
at the cost of more effort to decompose the truth table at the
technology mapping step.

> Ah, yes, Alan is on the cutting edge with this And-Inverter Graph stuff.  He's
> also a very good programmer.
> Can you make use of what is already in ABC?  While I would hesitate to use
> code from some other university projects that have appeared in the past, I
> would not hesistate to use Alan's code; it's generally engineered very well.

I've looked at a number of routing and mapping solutions over the last
couple years with conflicting project goals for FpgaC. Both excellent
static map/route and excellent fast dynamic compile load and go or
Just-In-Time styles seem to be needed. Because of frequent larger word
widths, there are some additional twists, like replication to minimize
fan-out which become useful at some point. Where to start has always
been an interesting problem. It seems that maybe just looking at the
technology mapping in a general way for specific devices is a good
start.

The ideas in ABC, and related educational projects, are certainly a
good grounding to start with.

Phil Tomson wrote:
> Can you make use of what is already in ABC?

I should probably note that I didn't want to make an implementation
choice, allowing whoever wants this project to make that choice, which
might include their own research work. This could easily be a one, two
or more person project as it can quickly expand to meet broader needs
... or it could be a class project with a lasting legacy.

fpga_toys@yahoo.com wrote:
> Phil Tomson wrote:
> > What format is the truth table in?  (BLIF, PLA, some other internal data
> > structure)
>
> Currently just a 2^n bit table, with a linked list for the associated
> var's.
>

Does this bit table represent two or three states per bit?
(i.e. True, False, or True, False, Don't Care)

While on a sequential processor it might not make sense to worry about
the don't care state and simply enumerate the table, in logic it can
make a very big difference.  You have probably already thought of this.
 The use of "bit" just threw up a red-flag for me, as the bit type in C
generally has only two states.


Regards,
Erik.

---
Erik Widding
President
Birger Engineering, Inc.

 (mail) 100 Boylston St #1070; Boston, MA 02116
(voice) 617.695.9233
  (fax) 617.695.9234
  (web) http://www.birger.com

Erik Widding wrote:
> fpga_toys@yahoo.com wrote:
> > Currently just a 2^n bit table, with a linked list for the associated
> > var's.
> Does this bit table represent two or three states per bit?
> (i.e. True, False, or True, False, Don't Care)

It's bivalued, since that is the only defined number set for C boolean
operations, logicals, and arithmetics used by C. Multivalued sets have
little value otherwise for FpgaC.

> While on a sequential processor it might not make sense to worry about
> the don't care state and simply enumerate the table, in logic it can
> make a very big difference.  You have probably already thought of this.

Because the boolean and arithmentic operations are defined as bivalue
operations, nothing else is necessary for FpgaC

>  The use of "bit" just threw up a red-flag for me, as the bit type in C
> generally has only two states.

Which, is enough. Even for boolean and arithmetics for other HDL and
HLL's RTL generation. Extended sets for simulation, fuzzy logic,
tristate busses, and other domains is a completely different problem.

fpga_toys@yahoo.com wrote:
> Erik Widding wrote:
> > fpga_toys@yahoo.com wrote:
> > > Currently just a 2^n bit table, with a linked list for the associated
> > > var's.
> > Does this bit table represent two or three states per bit?
> > (i.e. True, False, or True, False, Don't Care)
>
> It's bivalued, since that is the only defined number set for C boolean
> operations, logicals, and arithmetics used by C. Multivalued sets have
> little value otherwise for FpgaC.
>
> > While on a sequential processor it might not make sense to worry about
> > the don't care state and simply enumerate the table, in logic it can
> > make a very big difference.  You have probably already thought of this.
>
> Because the boolean and arithmentic operations are defined as bivalue
> operations, nothing else is necessary for FpgaC
>
> >  The use of "bit" just threw up a red-flag for me, as the bit type in C
> > generally has only two states.
>
> Which, is enough. Even for boolean and arithmetics for other HDL and
> HLL's RTL generation. Extended sets for simulation, fuzzy logic,
> tristate busses, and other domains is a completely different problem.

John,

I think I may have done a poor job communicating the issue.  So I will
offer a little more detail.

It is common occurance in code to have a series of independent "if"
statements with no correponding "else" all operating on the same set of
variables.  Atleast this is common in code that I have written.  In
VHDL and C this can be a very efficient way to code.  In either
language the last assignment wins.  And in many such instances, the
truth table is then only populated with a very small subset of answers.
 The remainder of the table can be assumed to have a value of "don't
care", in many languages this requires a first (or default) assignment
to the state of "don't care" that may or may not be overridden.

When minimizing logic into anything other than a fully populated truth
table the ability to manipulate the "don't cares" can allow for the
drastic reduction in logic at mapping.  Any first year digital design
course teaches a technique called "Karnaugh Mapping" as an analysis
tool and visual means for exploring this.

If a default value is placed into the table, it artificially over
specifies the logic, and will result in a suboptimal result.  There is
no problem with equations of no more than four terms as your basic unit
is a 4-lut.  But when you start getting into complex state machines
with dozens of terms, this can result in being an order of magnitude
off in utilization in specific areas of a design.  I bring this up now,
as the early test cases are going to be simpler, so it may be some time
before you see that there is really a problem.

So I am not disagreeing with you that FPGAC may not care about this for
now.  I am suggesting that you should allow for this future
optimization that you will almost certainly need, by considering that
you should specify your fitter to take as input the additional state of
"don't care".  All of the work out of Berkely (espresso, etc) supports
this addional state as it is crucial to quality of result.

This is me trying to constructively offer an example to the earlier
suggestion I made that  "what you want to do [in the area of
reconfigurable computing] is a whole lot more similar to the current
use of the devices than you realize."

This post is intended to be supportive.  If you have taken it any other
way, please simply ignore it.


Regards,
Erik.


---
Erik Widding
President
Birger Engineering, Inc.


 (mail) 100 Boylston St #1070; Boston, MA 02116
(voice) 617.695.9233
  (fax) 617.695.9234 
  (web) http://www.birger.com

Erik Widding wrote:
<snip>
> If a default value is placed into the table, it artificially over
> specifies the logic, and will result in a suboptimal result.  There is
> no problem with equations of no more than four terms as your basic unit
> is a 4-lut.  But when you start getting into complex state machines
> with dozens of terms, this can result in being an order of magnitude
> off in utilization in specific areas of a design.  I bring this up now,
> as the early test cases are going to be simpler, so it may be some time
> before you see that there is really a problem.
> 
> So I am not disagreeing with you that FPGAC may not care about this for
> now.  I am suggesting that you should allow for this future
> optimization that you will almost certainly need, by considering that
> you should specify your fitter to take as input the additional state of
> "don't care".  All of the work out of Berkely (espresso, etc) supports
> this addional state as it is crucial to quality of result.
<snip>

  I'll expand this a little, by adding that there can also be
an 'inferred else' operation, that depends on the register used.

  Thus a .D ff state engine, will tend to 00000 state, if
it hits a non-covered instance, whilst a .T ff state engine
will stay where it was.
  If you want to include glitch/noise recovery, that can
matter...

-jg