Mathematical definition of an FPGA

Hi guys,
I'm searching for a general mathematical definition of an FPGA.
I propose this y=F(x,u) where y is a vector of output , u is a vector
of input and x is a vector of internal state and F is a certain
function of x,u. Have you some idea to generalize more this
definition?
Thank you,
Silvio

On Feb 19, 8:12=A0am, "silvio.baccari" <silvio.bacc...@gmail.com> wrote:
> Hi guys,
> I'm searching for a general mathematical definition of an FPGA.
> I propose this y=3DF(x,u) where y is a vector of output , u is a vector
> of input and x is a vector of internal state and F is a certain
> function of x,u. Have you some idea to generalize more this
> definition?
> Thank you,
> Silvio

A mathematical definition for an FPGA???    Is there a mathematical
definition for a CPU or a chalkboard?

If the design that was implemented in a FPGA included no states
(registers, latches, RAMs, etc) it would be possible define the
function of the combinatorial function that was implemented in the
FPGA as y=3DF(u) using your definitions.

But with states what would be the point?  The Function could only
describe a portion of the design with that portion including only the
last state point to outputs and the time based nature of logic states
would not be described.

Ed McGettigan
--
Xilinx Inc.

On Feb 19, 6:14=A0pm, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:
> On Feb 19, 8:12=A0am, "silvio.baccari" <silvio.bacc...@gmail.com> wrote:
>
> > Hi guys,
> > I'm searching for a general mathematical definition of an FPGA.
> > I propose this y=3DF(x,u) where y is a vector of output , u is a vector
> > of input and x is a vector of internal state and F is a certain
> > function of x,u. Have you some idea to generalize more this
> > definition?
> > Thank you,
> > Silvio
>
> A mathematical definition for an FPGA??? =A0 =A0Is there a mathematical
> definition for a CPU or a chalkboard?
>
> If the design that was implemented in a FPGA included no states
> (registers, latches, RAMs, etc) it would be possible define the
> function of the combinatorial function that was implemented in the
> FPGA as y=3DF(u) using your definitions.
>
> But with states what would be the point? =A0The Function could only
> describe a portion of the design with that portion including only the
> last state point to outputs and the time based nature of logic states
> would not be described.
>
> Ed McGettigan
> --
> Xilinx Inc.

I think, it's not correct, the internal state variables x are the
smallest possible subset of system variables that can represent the
entire state of the system at any given time.
Silvio

You need x (vector of internal state) to also be the output of a
function of u and x.

Once you have that, you've got a mathematical model of a hybrid Mealy/
Moore state machine.  I don't think you can generalize it much more
than that.

Ed McGettigan <ed.mcgettigan@xilinx.com> wrote:
(someone wrote)
>> I'm searching for a general mathematical definition of an FPGA.
(snip)

> A mathematical definition for an FPGA???    Is there a mathematical
> definition for a CPU or a chalkboard?

The APL programming language was originally designed to write
a mathematical expression for the IBM 360 system.  I suppose
one could rewrite the microcode for a CPU in a mathematical
form, and call it a mathematical definition of that CPU.
 
> If the design that was implemented in a FPGA included no states
> (registers, latches, RAMs, etc) it would be possible define the
> function of the combinatorial function that was implemented in the
> FPGA as y=F(u) using your definitions.

I can believe in writing a mathematical definition for a 
programmed FPGA, but not for an unprogrammed one.  Might just
as well write one for a silicon crystal.

-- glen

On Feb 19, 7:42=A0pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:
>
> (someone wrote)>> I'm searching for a general mathematical definition of =
an FPGA.
>
> (snip)
>
> > A mathematical definition for an FPGA??? =A0 =A0Is there a mathematical
> > definition for a CPU or a chalkboard?
>
> The APL programming language was originally designed to write
> a mathematical expression for the IBM 360 system. =A0I suppose
> one could rewrite the microcode for a CPU in a mathematical
> form, and call it a mathematical definition of that CPU.
>
> > If the design that was implemented in a FPGA included no states
> > (registers, latches, RAMs, etc) it would be possible define the
> > function of the combinatorial function that was implemented in the
> > FPGA as y=3DF(u) using your definitions.
>
> I can believe in writing a mathematical definition for a
> programmed FPGA, but not for an unprogrammed one. =A0Might just
> as well write one for a silicon crystal.
>
> -- glen

The fact that the FPGA isn't programmed correspond to the undefined
form of F() function.
Silvio

On Feb 19, 10:04=A0am, "silvio.baccari" <silvio.bacc...@gmail.com>
wrote:
> On Feb 19, 6:14=A0pm, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:
>
>
>
>
>
> > On Feb 19, 8:12=A0am, "silvio.baccari" <silvio.bacc...@gmail.com> wrote=
:
>
> > > Hi guys,
> > > I'm searching for a general mathematical definition of an FPGA.
> > > I propose this y=3DF(x,u) where y is a vector of output , u is a vect=
or
> > > of input and x is a vector of internal state and F is a certain
> > > function of x,u. Have you some idea to generalize more this
> > > definition?
> > > Thank you,
> > > Silvio
>
> > A mathematical definition for an FPGA??? =A0 =A0Is there a mathematical
> > definition for a CPU or a chalkboard?
>
> > If the design that was implemented in a FPGA included no states
> > (registers, latches, RAMs, etc) it would be possible define the
> > function of the combinatorial function that was implemented in the
> > FPGA as y=3DF(u) using your definitions.
>
> > But with states what would be the point? =A0The Function could only
> > describe a portion of the design with that portion including only the
> > last state point to outputs and the time based nature of logic states
> > would not be described.
>
> > Ed McGettigan
> > --
> > Xilinx Inc.
>
> I think, it's not correct, the internal state variables x are the
> smallest possible subset of system variables that can represent the
> entire state of the system at any given time.
> Silvio- Hide quoted text -
>
> - Show quoted text -

Please explain which part of what I wrote you think is incorrect.

Ed McGettigan
--
Xilinx Inc.

On Sat, 19 Feb 2011 08:12:29 -0800, silvio.baccari wrote:

> Hi guys,
> I'm searching for a general mathematical definition of an FPGA. I
> propose this y=F(x,u) where y is a vector of output , u is a vector of
> input and x is a vector of internal state and F is a certain function of
> x,u. Have you some idea to generalize more this definition?
> Thank you,
> Silvio

By the time you captured all of the "FPGA-ness" you would have a 
mathematical description that would be so complex it would be useless.

In general the art of mathematical modeling lies not in capturing 
everything there is to capture about a thing that you want to model.  
Rather, it lies in capturing _just enough_ information about the thing so 
that you can get a _representative_ answer for your _immediate problem_.  
Capture too much information, and at best your model will be confusing, 
and at worst it'll be so unwieldy that you can't do anything useful with 
it.

So -- tell us what you want to do, and maybe we can help you model 
whatever subset of FPGA behavior it is that you really need modeled.

-- 
http://www.wescottdesign.com

On 19 Feb., 17:12, "silvio.baccari" <silvio.bacc...@gmail.com> wrote:
> Hi guys,
> I'm searching for a general mathematical definition of an FPGA.
> I propose this y=F(x,u) where y is a vector of output , u is a vector
> of input and x is a vector of internal state and F is a certain
> function of x,u. Have you some idea to generalize more this
> definition?
> Thank you,
> Silvio

Andre DeHon developed a taxonomy that views an FPGA as a processor
that executes one very complex instruction word.
The theoretical portions of that work might be a good starting point
for you:
http://www.seas.upenn.edu/~andre/abstracts/dehon_phd.html

Kolja Sulimma

On 19 Feb., 18:14, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:
> On Feb 19, 8:12=A0am, "silvio.baccari" <silvio.bacc...@gmail.com> wrote:

> But with states what would be the point? =A0The Function could only
> describe a portion of the design with that portion including only the
> last state point to outputs and the time based nature of logic states
> would not be described.

Actually, no, it is pretty common thing to reason about state machines
in an abstract way exactly in the way the OP did.
For example in model checking. But also in synthesis.

A programmed FPGA is just a digital circuit, so one can simple look up
the definitions that are used for these.
Depending on what you want to do, essentially there are to views on
the problem. Either the state transfer funktion:
(next_state, output) =3D F(current_state, input)
output_series =3D F(input_series)

In general the FPGA of course is included in these views, as the
configuration is state, and the config pins are inputs.
But in many cases it might make sende to capture the notion that the
configuration is different from the state captured in the DFFs and
BRAMs.
So one might write:
(next_state, output) =3D F(current_state, input, configuration)
or
output_series =3D F(input_series, configuration)

Of course this does ignore dynamic reconfiguration, so you might end
up with:
(next_state, output, next_configuration) =3D F(current_state, input,
current_configuration)
output_series =3D F(input_series, initial_configuration)


Kolja Sulimma