Mathematical definition of an FPGA

S

silvio.baccari

Guest
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 am, "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
Click to expand...
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=F(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 pm, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:
On Feb 19, 8:12 am, "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

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=F(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.
Click to expand...
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)
Click to expand...

A mathematical definition for an FPGA??? Is there a mathematical
definition for a CPU or a chalkboard?
Click to expand...
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.
Click to expand...
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 pm, 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???    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
Click to expand...
The fact that the FPGA isn't programmed correspond to the undefined
form of F() function.
Silvio
 
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
Click to expand...
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 Feb 19, 10:04 am, "silvio.baccari" <silvio.bacc...@gmail.com>
wrote:
On Feb 19, 6:14 pm, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:





On Feb 19, 8:12 am, "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

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=F(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.

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 -
Click to expand...
Please explain which part of what I wrote you think is incorrect.

Ed McGettigan
--
Xilinx Inc.
 
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
Click to expand...
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 am, "silvio.baccari" <silvio.bacc...@gmail.com> wrote:

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.
Click to expand...
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) = F(current_state, input)
output_series = 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) = F(current_state, input, configuration)
or
output_series = F(input_series, configuration)

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


Kolja Sulimma
 
On Feb 19, 11:12 am, "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
Click to expand...
Your definition is not complete.
1. There needs to be computation of the next state as a function of
current state and inputs: x(t+1) = g(x(t), u); where x(t) is the
internal state at time 't' and the equation tells you how to map to
the next clock cycle 't+1'
2. Some things are probabilistic: When a signal is generated within
one clock domain but sampled in another clock domain it is not
generally possible to state on exactly which clock cycle in the
sampling clock domain the received signal will arrive. It might
arrive one clock cycle later if the signal violates the setup time.
For whatever your purposes are, maybe you don't care about this but
since it is not clear why you posed the question, I thought I'd point
it out
3. Some things are dependent on things that cannot be predicted
exactly. An example here would be the amount of time it takes a phase-
locked loop to lock on to the input clock. The output of the PLL is
used to clock the state logic, but you can't say exactly when that
clock will be available. Again, I'm suspecting that this is more
detailed than what you're looking for.
4. Since an FPGA can be reprogrammed, the f() and g() functions change
over time (typically only once, but not necessarily just once).

Kevin Jennings
 
On Sat, 19 Feb 2011 21:09:54 -0800 (PST), Ed McGettigan
<ed.mcgettigan@xilinx.com> wrote:

The OP had two inputs to the Function, external inputs and the current
internal state, with the result of the Function being the external
outputs. The OP made no mention of clocks/time factors or that the
next internal state was part of the output function. In this
circumstance a vast majority of the internal states don't matter if
they don't factor directly on the output state.

I find the concept of trying to distill a complex state and time
dependent into a simple mathematical equation versus the HDL that
describes the system of questionable benefit.

Ed McGettigan
Click to expand...
The two equations:
x[k+1] = F(x[k], u[k]) and
y[k] = H(x[k], u[k]) (where x is the state, u is input, y is
output, F is the state transition matrix and H is output matrix)
are called state space equations of a control system and they have a
large body of knowledge behind them. Analysis of such systems have
bewen studied for a long time and a lot of useful theory exists for
such analysis. If an FPGA configuration could be described by such a
set of equations, one could decide observability, controllability,
stability and other features of such a system. The potential benefits
are actually enormous.
--
Muzaffer Kal

DSPIA INC.
ASIC/FPGA Design Services

http://www.dspia.com
 
On Feb 19, 4:07 pm, Kolja Sulimma <ksuli...@googlemail.com> wrote:
On 19 Feb., 18:14, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:

On Feb 19, 8:12 am, "silvio.baccari" <silvio.bacc...@gmail.com> wrote:
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.

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) = F(current_state, input)
output_series = 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) = F(current_state, input, configuration)
or
output_series = F(input_series, configuration)

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

Kolja Sulimma
Click to expand...
The OP had two inputs to the Function, external inputs and the current
internal state, with the result of the Function being the external
outputs. The OP made no mention of clocks/time factors or that the
next internal state was part of the output function. In this
circumstance a vast majority of the internal states don't matter if
they don't factor directly on the output state.

I find the concept of trying to distill a complex state and time
dependent into a simple mathematical equation versus the HDL that
describes the system of questionable benefit.

Ed McGettigan
--
Xilinx Inc.
 
On Feb 19, 8:03 pm, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:
On Feb 19, 10:04 am, "silvio.baccari" <silvio.bacc...@gmail.com
wrote:









On Feb 19, 6:14 pm, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:

On Feb 19, 8:12 am, "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

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=F(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.

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.
Click to expand...
Sorry, the second part of you message ... this part:
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.
Click to expand...
 
On Feb 19, 9:02 pm, Tim Wescott <t...@seemywebsite.com> wrote:
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
Click to expand...
I'm interested only to the logical behavior of an FPGA; not the
complex (transitory) phenomenons between two steady states and the way
to implement the logic core and the memory ones.
Thanks,
Silvio
 
On Feb 20, 2:10 am, KJ <kkjenni...@sbcglobal.net> wrote:
On Feb 19, 11:12 am, "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

Your definition is not complete.
1. There needs to be computation of the next state as a function of
current state and inputs:  x(t+1) = g(x(t), u); where x(t) is the
internal state at time 't' and the equation tells you how to map to
the next clock cycle 't+1'
2. Some things are probabilistic:  When a signal is generated within
one clock domain but sampled in another clock domain it is not
generally possible to state on exactly which clock cycle in the
sampling clock domain the received signal will arrive.  It might
arrive one clock cycle later if the signal violates the setup time.
For whatever your purposes are, maybe you don't care about this but
since it is not clear why you posed the question, I thought I'd point
it out
3. Some things are dependent on things that cannot be predicted
exactly.  An example here would be the amount of time it takes a phase-
locked loop to lock on to the input clock.  The output of the PLL is
used to clock the state logic, but you can't say exactly when that
clock will be available.  Again, I'm suspecting that this is more
detailed than what you're looking for.
4. Since an FPGA can be reprogrammed, the f() and g() functions change
over time (typically only once, but not necessarily just once).

Kevin Jennings
Click to expand...
Hi Kevin,
the definition of next states is essential for a correct definition
(first point).
The second and third point is relative to the simulation of the model
and I think it is a valid consideration, but it is off topic.
The fourth point is a good consideration ... so the functions F and G
are time variant.
Silvio
 
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
Click to expand...
Sure. You don't have any state changes, except for outputs. At least make
it a FSM

You also only allow determistic functions, omitting a large class of
timing errors

The real question might be - what do you hope to do with this definition.
What you have isn't specific to FPGAs.

Maybe something that composes functions from states, routing, and LUTs?

--
mac the naĂŻf
 
On 20 Feb., 06:09, Ed McGettigan <ed.mcgetti...@xilinx.com> wrote:

I find the concept of trying to distill a complex state and time
dependent into a simple mathematical equation versus the HDL that
describes the system of questionable benefit.
Click to expand...

The HDL is a representation of the circuit that is extremely
unsuitable for pretty much anything
except for presenting the circuit to humans. I guess this is the
reason
why any tool chain (including ISE) gets rid of the HDL as quicky as
possible to replace it by
- netlists
- state graphs
- decision diagrams (ROBDDs for example)
- boolean equations
- function tables
Whatever might suit the task that needs to be performed. (placement,
logic optimization, retiming, equivalence checking, etc.)

When analysing algorithms or proving properties of a circuits
notations like that of the OP
or mine are very commonly used and useful.
For example in bounded model checking one iteratively builds a circuit
derived from the
original circuit and needs to no when this process reaches a
functional fixed point. e.g. you want to
know when Fn(x)=Fn+1(x).
Try reasoning about such an algorithm without a formalism.

By the way:
Are there any plans by xilinx of making model checking available to
the FPGA world for a price less
then 120k$ per seat and year for the products by OneSpin?

Regards,

Kolja
 
"silvio.baccari" <silvio.baccari@gmail.com> wrote in message
news:404f9d57-bb4d-4f3d-a4b0-186971ba71ae@x3g2000yqj.googlegroups.com...
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?
Click to expand...
I guess a general [boring] mathematical definition could be:
for all IO pins in i:
IOpin(i)=F(all_other_IOpins,all_internal_memory_states,config_data)

But for this to be valid, a "value" of "undriven/nothing" must be part of
the valid return union.
 
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
Click to expand...
What an incredibly daft idea!


---------------------------------------
Posted through http://www.FPGARelated.com
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top