Can I use Verilog or SystemVerilog to write a state machine

On Thursday, January 10, 2019 at 10:52:13 PM UTC-5, Weng Tianxiang wrote:

On Thursday, January 10, 2019 at 2:02:22 PM UTC-8, dlhe...@gmail.com wrote:
So much wrong.

Any marginally competent cache designer understands that only one cache line is accessed at a time. So the cache is designed as a RAM with data, tags, and state. Each cycle the data, tags and state are read, and a single state machine is used to generate the next state, which is written back into the RAM.

There are plenty of papers on flip flop design that detects whether the new data is different from the present state, and uses that to generate a clock pulse only if necessary.

Congratulation!

Your post is the best and most valuable post in this thread!

Invincible! Marvelous! Smartest!

Your post makes me shameful and speechless!

Hope you join my later post.

I will continue to pursue my next sets of inventions!

Thank you.

Weng

LOL! So can you share your secret comparison using no gates?

Rick C.

--- Get 6 months of free supercharging
--- Tesla referral code - https://ts.la/richard11209

 

[Richard Damon]

On 1/10/19 10:37 AM, gtwrek wrote:

In article <ugHZD.8990$nO2.5464@fx08.iad>,
Richard Damon <Richard@Damon-Family.org> wrote:
On 1/10/19 5:25 AM, Thomas Stanka wrote:
Am Mittwoch, 9. Januar 2019 23:07:47 UTC+1 schrieb gtwrek:
Weng Tianxiang <wtxwtx@gmail.com> wrote:
[0003] Traditionally a deterministic finite state machine is mathematically defined as a set of 6-tuple M = (Σ, Δ, Q, q0, δ, λ), where Σ is a finite
set of input symbols, Δ /= 0 is a finite set of output symbols, Q /= 0 is a finite set of states, q0 є Q is the “reset” state, δ(q, a) : Q x Σ → Q
is the transfer function, and λ(q, a) : Q x Σ → Δ is the output function.
[0004] Conventional state machine theory has following State Machine Axiom:
[0005] State Machine Axiom A state machine has one and only one state being active on any cycle after the state machine is properly initialized.

This definition matches all synchronous digital circuits.

Yes, that's true. A FSM could be a dedicated statemachine written in one HDL module, but each counter is a simple FSM and each complete logic design can
be seen as a statemachine.

Every part of a statemachine containing at least 2 states and 1 input and output is itself a statemachine and every combination of 2 statemachines is one
statemachine. FSM is just a model to describe a digital circuit with at least one sequential element.

best regards Thomas


Perhaps some would call ANY synchronous digital circuit a state-machine,
but the more classical definition would imply that it be a system with a
single clock domain as it is the transformation from one 'State' to
another 'State' on *The* clock edge, with the definition of the Next
State being a function of the Previous State and the Inputs. The concept
of previous and next imply a singular concept of time steps, thus a
single clock domain (though clock gating/enables of that domain would be
allowed).

Yes, exactly. The qualification of a single clock - or as you note -
related clocks is what I was trying to cover with the term SYNCHNRONOUS
digitial circuits. In one of my post up the thread I mentioned a
single clock - Kevin more correctly labeled the requirements as
SYNCHRONOUS which I think summarizes the requirements better so I took
that label.

I'll say again, any SYNCHRONOUS digital circuit meets Weng's definition
of a state machine.

Regards,

Mark

My terminology divided Synchronous (transitions happening on the edge of
some 'global' clock) vs Asynchronous, where some device changes its
state independant of the main clocks, perhaps with an asynchronous
set/clear or being clocks by some input signal that isn't considered a
system clock.

Synchronous system can be divided into single domain and multi-clock
domain systems, for which you seem to want to define 'Synchronous' as
what I would consider 'Single Clock-Domain Synchronous'. Multi-clock
domain synchronous system tend to not be define as *A* FSM, but can be
as a set of FSMs that interact.

Proper multi-clock domain systems need a bit of care at the domain
boarders to avoid meta-stability issues, but this isn't really that hard
to handle.

 

[HT-Lab]

On 11/01/2019 15:12, Richard Damon wrote:

On 1/10/19 10:37 AM, gtwrek wrote:
... snip
I'll say again, any SYNCHRONOUS digital circuit meets Weng's definition
of a state machine.

Regards,

Mark


My terminology divided Synchronous (transitions happening on the edge of
some 'global' clock) vs Asynchronous, where some device changes its
state independant of the main clocks, perhaps with an asynchronous
set/clear or being clocks by some input signal that isn't considered a
system clock.

Synchronous system can be divided into single domain and multi-clock
domain systems, for which you seem to want to define 'Synchronous' as
what I would consider 'Single Clock-Domain Synchronous'. Multi-clock
domain synchronous system tend to not be define as *A* FSM, but can be
as a set of FSMs that interact.

Proper multi-clock domain systems need a bit of care at the domain
boarders to avoid meta-stability issues, but this isn't really that hard
to handle.

what?

the opposite, it is really hard to handle unless you have a single
signal moving from a slow to fast clock domain. Why do you think there
are so many (quite expensive) CDC tools (Bluepearl, Spyglass, Questa
CDC, Conformal, Meridian, ..) Have a look at past ASIC user surveys
(like Wilson research group) and you will find that CDC errors are the
number 2(!) reason for a respin, I would say that qualifies as a hard to
handle issue given the cost of a respin nowadays.

Trying to a find a deep convergence, reset or a CDC glitch problem in a
30 clock domain design (not that unique) is not for the faint-hearted
and that is after identifying that it/they exists in the first place
(simulation won't show you unless you use CDC-FF models from your CDC tool).

Time to power cycle my TV box again as it got stuck yet again....;-)

Hans
www.ht-lab.com

 

[gtwrek]

In article <Jn2_D.15781$375.3997@fx40.iad>,
Richard Damon <Richard@Damon-Family.org> wrote:

My terminology divided Synchronous (transitions happening on the edge of
some 'global' clock) vs Asynchronous, where some device changes its
state independant of the main clocks, perhaps with an asynchronous
set/clear or being clocks by some input signal that isn't considered a
system clock.

Synchronous system can be divided into single domain and multi-clock
domain systems, for which you seem to want to define 'Synchronous' as
what I would consider 'Single Clock-Domain Synchronous'. Multi-clock
domain synchronous system tend to not be define as *A* FSM, but can be
as a set of FSMs that interact.

To be clear here - my definition of a "state machine" matches what I'm
sure most of the other poster's here define it as. A small (less than
5-6 bits) number of states, operating on a single clock domain. Small
enough such that a Synthesis Tools can apply a model to, where as the
"state labels" can be disassociated from the actual bit encodings (and
number of bits). Such a tool can then re-encode these bit encondings
(and number of bits) in order to optimize the circuit, balancing such
metrics as power, timing, area, soft-fault tolerance, and errant state
detection. Such a re-encoding would preserve all state transitions, and
output products - but change the underlying bit-encodings.

Anything more than 5-6 bits (I don't think I've ever designed any with
more than 4) would call (in my opinion) for some re-partitioning and
redesign. In fact, I'd wouldn't be surprised that even with todays
modern tools, a FSM optimizer would start choking when you reach 8-10
bits.

Now, again this is all just a MODEL that we can apply as people to
a digital, synchronous, single-clock domain circuit.

Weng seems to be applying a looser definition of "state machine" that
he's applying to model a CPU Cache circuit (with a ginormous number of
states, or perhaps a ginoromous number of small, indepenent state
machines all interacting). That's fine to model it as such, if there's
some sort of benefit to having this model. (I think it's a silly
model to make, without any benefit, but *shrug*)

My only argument, which I still don't think he understands, is with his
loose of a definition, one can apply his "state machine" model to
ANY digital single-clock domain synchronous circuit. (I just wanted to
avoid that last mouthful and just say "synchronous".)

Weng further goes on and says, with this "state machine" model of a CPU
cache, he can now apply some secret algorithm to optimize something.
My (and other's) points here were that if his algorthim when applied
under his "state machine" model for a CPU cache, would also apply to ANY
other digital single-clock domain synchronous circuit.

Many then would point out, that this would then all fit well within
established prior art. Transformations of Clock Enable circuits to
Gated Clocks are well understood to both the tools and designers.
As per normal, the devil is all in the details of the cost/benefit
metrics of making such transformations.

(And also pointing out, I'm completely unclear as to what Weng's super
snazzy algorithm is, under what conditions it could work, what it's cost
could be, etc.) Some of his post seems to talk about low power and magic
clock gating, but none of it is very clear.)

Regards,

Mark

 

On Friday, January 11, 2019 at 3:04:01 PM UTC-5, HT-Lab wrote:

On 11/01/2019 15:12, Richard Damon wrote:
On 1/10/19 10:37 AM, gtwrek wrote:
.. snip
I'll say again, any SYNCHRONOUS digital circuit meets Weng's definition
of a state machine.

Regards,

Mark


My terminology divided Synchronous (transitions happening on the edge of
some 'global' clock) vs Asynchronous, where some device changes its
state independant of the main clocks, perhaps with an asynchronous
set/clear or being clocks by some input signal that isn't considered a
system clock.

Synchronous system can be divided into single domain and multi-clock
domain systems, for which you seem to want to define 'Synchronous' as
what I would consider 'Single Clock-Domain Synchronous'. Multi-clock
domain synchronous system tend to not be define as *A* FSM, but can be
as a set of FSMs that interact.

Proper multi-clock domain systems need a bit of care at the domain
boarders to avoid meta-stability issues, but this isn't really that hard
to handle.

what?

the opposite, it is really hard to handle unless you have a single
signal moving from a slow to fast clock domain. Why do you think there
are so many (quite expensive) CDC tools (Bluepearl, Spyglass, Questa
CDC, Conformal, Meridian, ..) Have a look at past ASIC user surveys
(like Wilson research group) and you will find that CDC errors are the
number 2(!) reason for a respin, I would say that qualifies as a hard to
handle issue given the cost of a respin nowadays.

Trying to a find a deep convergence, reset or a CDC glitch problem in a
30 clock domain design (not that unique) is not for the faint-hearted
and that is after identifying that it/they exists in the first place
(simulation won't show you unless you use CDC-FF models from your CDC tool).

Time to power cycle my TV box again as it got stuck yet again....;-)

A customer asked me how I handle multiple clock domains and I told him that unless there was reason to perform significant processing in multiple clock domains I transition all I/Os to a single clock domain as quickly as possible so that all interaction between circuits are then in that one clock domain. The resulting domain transitions are limited and well defined making them easy to debug.

Rick C.

--+ Get 6 months of free supercharging
--+ Tesla referral code - https://ts.la/richard11209

 

[Richard Damon]

On 1/11/19 3:03 PM, HT-Lab wrote:

On 11/01/2019 15:12, Richard Damon wrote:
On 1/10/19 10:37 AM, gtwrek wrote:
.. snip
I'll say again, any SYNCHRONOUS digital circuit meets Weng's definition
of a state machine.

Regards,

Mark


My terminology divided Synchronous (transitions happening on the edge of
some 'global' clock) vs Asynchronous, where some device changes its
state independant of the main clocks, perhaps with an asynchronous
set/clear or being clocks by some input signal that isn't considered a
system clock.

Synchronous system can be divided into single domain and multi-clock
domain systems, for which you seem to want to define 'Synchronous' as
what I would consider 'Single Clock-Domain Synchronous'. Multi-clock
domain synchronous system tend to not be define as *A* FSM, but can be
as a set of FSMs that interact.

Proper multi-clock domain systems need a bit of care at the domain
boarders to avoid meta-stability issues, but this isn't really that hard
to handle.

what?

the opposite, it is really hard to handle unless you have a single
signal moving from a slow to fast clock domain. Why do you think there
are so many (quite expensive) CDC tools (Bluepearl, Spyglass, Questa
CDC, Conformal, Meridian, ..)  Have a look at past ASIC user surveys
(like Wilson research group) and you will find that CDC errors are the
number 2(!) reason for a respin, I would say that qualifies as a hard to
handle issue given the cost of a respin nowadays.

Trying to a find a deep convergence,  reset or a CDC glitch problem in a
30 clock domain design (not that unique) is not for the faint-hearted
and that is after identifying that it/they exists in the first place
(simulation won't show you unless you use CDC-FF models from your CDC
tool).

Time to power cycle my TV box again as it got stuck yet again....;-)

Hans
www.ht-lab.com

Solving clock domains issues is fairly straight forward when they are
identified at design time. You do need different strategies depending on
the basic case you are working in, is it a single signal, or is it a
bus, are we going fast to slow and need to make sure the signal gets
across, etc. What is hard is to verify that you have detected all the
cross domain transitions and performed the needed mitigations for it.
They can also get harder if you are trying to squeeze every last drop of
performance out of a cross domain connection.

I suppose some things get mentally hard to shake, like making the
assumption that your synchronous clear terminates simultaneously in all
domains (instead of the idea that simultaneity isn't really a concept in
a multi-clock domain system.)

The other issue is that when you start to move to higher level
abstractions the real RTL code, it becomes easier to miss the cross
clock domain transfers or to miss some of the interactions between
multiple instances of a given cross-domain transfer (Two signals that
are together in clock domain 1 will not necessarily be together in clock
domain 2 after transitioning, unless care is taken to keep them together).

 

On Friday, January 11, 2019 at 5:03:35 PM UTC-5, gtwrek wrote:

(And also pointing out, I'm completely unclear as to what Weng's super
snazzy algorithm is, under what conditions it could work, what it's cost
could be, etc.) Some of his post seems to talk about low power and magic
clock gating, but none of it is very clear.)

This seems to be par for the course with patent seeking. The typical patent seeker is not proficient or even familiar with a given area of expertise, has ill-conceived ideas of what the tools can do or how the tools work and proposes poor solutions to issues no one else sees as problems.

I would be interested in learning of such a patent seeker's background and what sorts of work they have done in the past.

Rick C.

-+- Get 6 months of free supercharging
-+- Tesla referral code - https://ts.la/richard11209

 

[Weng Tianxiang]

Hi Mark,

Is there anywhere I said that
"Weng seems to be applying a looser definition of "state machine" that
he's applying to model a CPU Cache circuit (with a ginormous number of
states, or perhaps a ginoromous number of small, indepenent state
machines all interacting)."

I only said that one L2 cache line has a state machine, and 6M L2 cache would need 100,000 state machines.

And dlhe...@gmail.com resolved my problem accurately and excellently.

Invincible! Marvelous! Smartest!

Thank you, dlhe...@gmail.com.

Weng

 

[Richard Damon]

On 1/11/19 5:03 PM, gtwrek wrote:

In article <Jn2_D.15781$375.3997@fx40.iad>,
Richard Damon <Richard@Damon-Family.org> wrote:
My terminology divided Synchronous (transitions happening on the edge of
some 'global' clock) vs Asynchronous, where some device changes its
state independant of the main clocks, perhaps with an asynchronous
set/clear or being clocks by some input signal that isn't considered a
system clock.

Synchronous system can be divided into single domain and multi-clock
domain systems, for which you seem to want to define 'Synchronous' as
what I would consider 'Single Clock-Domain Synchronous'. Multi-clock
domain synchronous system tend to not be define as *A* FSM, but can be
as a set of FSMs that interact.

To be clear here - my definition of a "state machine" matches what I'm
sure most of the other poster's here define it as. A small (less than
5-6 bits) number of states, operating on a single clock domain. Small
enough such that a Synthesis Tools can apply a model to, where as the
"state labels" can be disassociated from the actual bit encodings (and
number of bits). Such a tool can then re-encode these bit encondings
(and number of bits) in order to optimize the circuit, balancing such
metrics as power, timing, area, soft-fault tolerance, and errant state
detection. Such a re-encoding would preserve all state transitions, and
output products - but change the underlying bit-encodings.

Anything more than 5-6 bits (I don't think I've ever designed any with
more than 4) would call (in my opinion) for some re-partitioning and
redesign. In fact, I'd wouldn't be surprised that even with todays
modern tools, a FSM optimizer would start choking when you reach 8-10
bits.

Now, again this is all just a MODEL that we can apply as people to
a digital, synchronous, single-clock domain circuit.

Weng seems to be applying a looser definition of "state machine" that
he's applying to model a CPU Cache circuit (with a ginormous number of
states, or perhaps a ginoromous number of small, indepenent state
machines all interacting). That's fine to model it as such, if there's
some sort of benefit to having this model. (I think it's a silly
model to make, without any benefit, but *shrug*)



Regards,

Mark

The basic concept of a state machine is that given a state variable S
(implemented with some number of bits and representing states like S0,
S1, S2, ... Sn), and a set of inputs I, then we can say that we have the
logic that at the clock signal

S <= F(S, I)

where F is a pure combinatorial function if its inputs.

Technically, most single clock domain sychronous systems qualify by this
definition, but I agree that 'arithmetic' and other data-path type
structures are really state machines.

I have designed state machines with perhaps as high as 100 state
(slightly above your limit), and machines of that size that I have done
tend to have a number of legs where once you get to state Sn, you
automatically progress to state Sn+1, Sn+2 ... Sm and you could perhaps
factor out a smaller state machine coupled to a counter.

Based on the papers Weng pointed to, he is dealing with this sort of
state machine, as they are presents as perhaps a dozen circles with
conditions and outputs on the arrows between them, and a very large
number of these in the system.