Guess: what is the largest number of state machines in a current chip design: 1k, 10k, or...

[Uncle Noah]

Another fat-ass discussion invoked by Weng.

Hey Weng, you always turn on the most crapiest and unhealthiest
discussions.

BTW any big-company chief scientists or fat-ass academic professors
want to discuss about YARDstick, my super tool for custom processor
development?

There is a joke about academic bozzos and their capability of
coding...

http://electronics.physics.auth.gr/people/nkavv/yardstick/

 

[Thomas Entner]

IF OP = "Weng Tianxiang" AND group = comp_arch_fpga THEN

be_prepared_for_a_long_thread;
ORIF crossposted = to_comp_lang_vhdl THEN
this_could_go_on_all_week;
ANDIF both_the_above THEN
make_that_a_month;
BUTIF plonk! THEN
blessed_relief;
ELSIF experiences < imagination THEN
OP_question <= not(sense);
ELSE
possibly_on_topic;
END IF;

HTH., Syms. ;-)

p.s. Sorry, couldn't resist it!

p.p.s. I guess one. You can view the whole FPGA as one big state machine.
Do I win £5?

ROFL, how could I have missed this posting for 3 days... LOL

Thomas

 

[Weng Tianxiang]

80B/10B is not a scrambler. It's a coding mechanism used to balance the
DC offset of the encoded stream. It's a straight encode/decode.

Don't be disappointed and frustrated for what you don't know.- Hide quoted text -

- Show quoted text -

Hi John_H,
8b/10b does the same thing as a scambler does: to balance DC offset,
but does a better job than scambler with 20% bandwidth cost.

For higher data rare, 8b/10b is the only choice. It guarantees that DC
offset is balanced between +- 1 during transmission.

Historically, currently satellite communication stations use scambler
not because scambler saves 20% bandwidth, but when satellite station
standard was established, IBM had the patent on 8b/10b that would
expire in 2001, that is the reason why PCI-e uses 8b/10b technology.

I expect 8b/10b technology will be incooperated in any new data
communication standard, but it cannot replace old standards.

Hi Hal,
Scrambler cannot be counted as a state machine in any sense.

The most important factor for a circuit counted as a state machine is
that its states are mutually exclusive and only one state is active in
any cycle.

Scrambler cannot meet the requirements. If it were, every circuit
would be counted as a state machine.

Shift registers can be counted as a state machine only when only one
bit is set or reset among all its bits. Otherwise it cannot be counted
as a state machine.

Weng

 

[Weng Tianxiang]

Hi JTW,
Your response is suggestive and I would like to see your coding to
determine if they are state machines.

I don't exclude RAM used as state machines.

If you can do it, it is better. Xilinx has an application note devoted
to the BRAM used as state machine and I read the note carefully. But I
never use their ideas to use BRAM . I don't have any idea to use the
BRAM as a tool for 10k state machines.

There are 10 millions bits of BRAM, you must also have a legitimate
reason to use so many state machines in a design. There is seldom a
design in FPGA world that would need 100k state machines for a reason.

My answer to my quiz is much larger than 100k state machines in a
finished design that is open to use for any one in the topic groups.

Weng

 

[Shannon]

Hi JTW,
Your response is suggestive and I would like to see your coding to
determine if they are state machines.

I don't exclude RAM used as state machines.

If you can do it, it is better. Xilinx has an application note devoted
to the BRAM used as state machine and I read the note carefully. But I
never use their ideas to use BRAM . I don't have any idea to use the
BRAM as a tool for 10k state machines.

There are 10 millions bits of BRAM, you must also have a legitimate
reason to use so many state machines in a design. There is seldom a
design in FPGA world that would need 100k state machines for a reason.

My answer to my quiz is much larger than 100k state machines in a
finished design that is open to use for any one in the topic groups.

Weng

Thanks Weng. I can sleep better now.

Shannon

 

[glen herrmannsfeldt]

John_H wrote:
(snip)

80B/10B is not a scrambler. It's a coding mechanism used to balance the
DC offset of the encoded stream. It's a straight encode/decode.

You could say it that way, but if you need a modulation method
for clock recovery it can be used in place of a scrambler and
simpler modulation method.

Modulation is used for different reasons:

1) Clock recovery
2a) Band limited channel
2b) AC coupled system

Considering those, 8B/10B is not so different from a scrambler.

-- glen

 

[Hal Murray]

Hi Hal,

Scrambler cannot be counted as a state machine in any sense.

Why not? It has inputs, outputs, and internal state.
Sure looks like a state machine to me.

The most important factor for a circuit counted as a state machine is
that its states are mutually exclusive and only one state is active in
any cycle.

Which part of that does a scrambler not meet? Remember, I'm
talking about a LFSR type scrambler running in bit serial mode,
not a n 8b/10b encoder.

Shift registers can be counted as a state machine only when only one
bit is set or reset among all its bits. Otherwise it cannot be counted
as a state machine.

Huh? A shift register seems like an even simpler example of
a state machine that doesn't need a reset to do useful work.

I'm thinking of a simple serial-in, serial-out shift register,
a delay line. It's "state" is the last N bits shifted in.


If I was explaining a shift register or scrambler to somebody,
I probably wouldn't start by calling it a state machine and drawing
the classic picture of states and transitions, but it might be
handy to use tricks from state machine theory, like if it has
N bits of internal state (aka FFs) it can only have 2^N distinct
states.

 

[John_H]

John_H wrote:
(snip)


You could say it that way, but if you need a modulation method
for clock recovery it can be used in place of a scrambler and
simpler modulation method.

Modulation is used for different reasons:

1) Clock recovery
2a) Band limited channel
2b) AC coupled system

Considering those, 8B/10B is not so different from a scrambler.

-- glen

It's not "so" different, but the advantages of each are different. The
items that strike me the most are that 8B/10B provides better DC balance and
scramblers provide a smoother spread of power across a wider bandwidth.

 

[Amir]

But you do not react if someone answers your question. Can you beat
the
10k+ state machines of a smith-waterman DNA matcher?


Again, you did not read my post. Many state machines have no reset
signal.
For example the reset signal of a JTAG controller is optional. This is
a state machine that is implemented in virtually every complex piece
of silicon out there.

Kolja Sulimma

Hi Weng and all fellow engineers,

I more or less agree with all of you on ur guesses and responses...

I dont quite understand what Weng is up to? If you wanna twist ur
question in any way to mislead us, u could do so forever, and no
answer would SATISFY u, cus there is no real question..

Are u really trying to have an answer/discussion that benefit us all,
OR u r just playing with ur words cus u probably finished clicking as
to test the modules that design engineers handed u in....?

For the sake of every one else, my share of the answer would be:

I would subdivide the question as: 1. How many FSM can fit current
chips? 2. How many FSM is appropriate for a given design? 3. How many
states within each FSM should there be?

My guess/answers:
A.1: twice as much available Registers in the chip (after considering
registers needed for other modules)
A.2: Depending on the complexity of the design, as many as required,
provided that each FSM do not exceed more than 15 states or so...(more
than 15, becomes harder to debug, and follow..)
A.3. Embedded in A.2, hence, max 15-20 states per FSM would be a best
suit based on my experience...Larger than 20, the FSM should be broken
down into 2 FSMs...

But again, as others pointed out, the whole number of FSMs can be
considered as one large FSM, cus they interact with each other through
handshake signals anyways....

Amir,

that it depends on design complexity, however,

 

[Hal Murray]

A.2: Depending on the complexity of the design, as many as required,

provided that each FSM do not exceed more than 15 states or so...(more
than 15, becomes harder to debug, and follow..)
A.3. Embedded in A.2, hence, max 15-20 states per FSM would be a best
suit based on my experience...Larger than 20, the FSM should be broken
down into 2 FSMs...

It's perfectly reasonable to build FSMs with hundreds or even
thousands of states. The trick is to think of it as software
and build yourself an assembler so you can really implement it
that way.

People have been using ROMs for this type of state machine for
a long time. 256x8 ROMs were common back in the old TTL/DIP days.

That style of FSMs usually has clumps of states that don't branch.
If you draw the typical circles and arrows state diagram, you might
want to include each clump in one circle. It just takes several
cycles/states to do the "action" associated with a state transition.

 

[glen herrmannsfeldt]

Weng Tianxiang wrote:

(snip)

Scrambler cannot meet the requirements. If it were, every circuit
would be counted as a state machine.

There is a class of circuits call combinatorial logic. Generally
that means no state, no memory, and so no state machine.

With combinatorial logic the outputs will come to a value that
only depends on the inputs after the appropriate propagation delay.

Otherwise, yes, every circuit that has a state memory counts
as a state machine.

Shift registers can be counted as a state machine only when only one
bit is set or reset among all its bits. Otherwise it cannot be counted
as a state machine.

I don't understand this restriction at all.

-- glen

 

[Weng Tianxiang]

"Shift registers can be counted as a state machine only when only one
bit is set or reset among all its bits. Otherwise it cannot be counted
as a state machine."

"I don't understand this restriction at all.

-- glen"

Hi Glen,
For a 4-bit shift register to be counted as a state machine, it must
have data:
"0001", "0010", "0100" and "1000" for an active high state machine, or
"1110", "1101", "1011" and "0111" for an active low state machine.

It must meet state machine requirements:
A state machine can be defined in such a scientific way:
1. All states in a state machine have their own names;
2. All states in a state machine are mutually exclusive;
3. Only one state is active in any cycle;
4. The number of states in a state machine must be 2 or more;
5. There must be clear asynchronous or a synchronous reset signal, or
hidden
procedure for the state machine. After their assertion or
initialization
the state machine must be in known initial state.

For a 4-bit shift register that has data "1100" cannot be counted as
a state machine. Even though they may be used for state machine
functions.
In such cases, they are called shift registers, not state machines.

Roughly speaking, in VHDL, it is used to be declared in the following
way:
type xxx (...);
signal StateMachine, NextState : xxx;

If you use above format to declare a state machine, the statistics
would be shown in Xilinx compilation result. And the declared state
machine would meet all above 5 requirements.

Xilinx compiler does the right thing.

Hi Amir,
My question is very clear:
"What is the largest number of state machines in a current chip
design:
1k, 10k or ... "

If you know, please give the answer and why. If you don't know and are
interested in it, please be quiet and patient, or don't join the
topics discussion if you think it is wasting your time. I will
disclose my answer at appropriate time. It is not a trivial quiz. You
may hear it before, but forget to remember to connect it with the
question.

My question is not how to design a state machine, or how many states a
state machine may have, or how many state machines a FPGA/IC can
construct. Those questions are beyond interest of my topics.

Weng

 

[Hal Murray]

For a 4-bit shift register to be counted as a state machine, it must
have data:
"0001", "0010", "0100" and "1000" for an active high state machine, or
"1110", "1101", "1011" and "0111" for an active low state machine.

That's total nonsense.

Your pattern describes a one-hot state machine. That simplifies
decoding states, but there is nothing in the rules of state
machines that says I have to use that encoding. It's common
to encode states in kludgy ways that make decoding convenient.

 

[Bob Perlman]

Hi,
I would like to pose an interesting guess topics for experienced
engineers:
What is the largest number of state machines in a current chip design:
1k, 10k or ...

I have finished 8 projects and only counted 27 state machines in one
of my biggest designs.

I may know the answer. The final result may surprise everyone who
gives a guess.

Weng

According to a show I just saw on the History Channel, during the last
days of World War II, Adolph Hitler paced up and down the halls of his
bunker, trying to determine the number of state machines you could fit
into a 12AU7.

By the power vested in me by the First Corollary of Godwin's Law, I
declare this thread officially over.

No need to thank me,
Bob Perlman
Cambrian Design Works
http://www.cambriandesign.com

 

[Weng Tianxiang]

Weng Tianxiang wrote:

(snip)


There are many restricted types of state machines, usually named
after the first person to publish the description.

I would say that you have now defined the weng machine, which
is fine. That doesn't have anything to do with the state
machines that others may define and use.

You requirement on naming states reminds me of an old saying:
"If a tree falls in the forest and nobody is around to
hear it does it make any noise?"

Whether the states are named or not has no effect on
the logic. That states are mutually exclusive and
only one state active in each cycle are sort of obvious
requirements. (That doesn't restrict it to one hot
state machines, an active state is any specific
combination of the state variables.)

Also that there must be more than one state is
a reasonable restriction. Many state machines
are self synchronizing so don't need a reset signal.
Others do need one. There are some that can start
in an illegal state and never reach a legal state
without a reset. Most try not to design that way
if it is reasonable not to do so.

-- glen

Hi Glen,
"That doesn't restrict it to one hot
state machines, an active state is any specific
combination of the state variables"

I agree with your opinion.

Weng

 

[glen herrmannsfeldt]

Weng Tianxiang wrote:
(snip)

For a 4-bit shift register to be counted as a state machine, it must
have data:
"0001", "0010", "0100" and "1000" for an active high state machine, or
"1110", "1101", "1011" and "0111" for an active low state machine.

It must meet state machine requirements:
A state machine can be defined in such a scientific way:
1. All states in a state machine have their own names;
2. All states in a state machine are mutually exclusive;
3. Only one state is active in any cycle;
4. The number of states in a state machine must be 2 or more;
5. There must be clear asynchronous or a synchronous reset signal, or
hidden
procedure for the state machine. After their assertion or
initialization
the state machine must be in known initial state.

There are many restricted types of state machines, usually named
after the first person to publish the description.

I would say that you have now defined the weng machine, which
is fine. That doesn't have anything to do with the state
machines that others may define and use.

You requirement on naming states reminds me of an old saying:
"If a tree falls in the forest and nobody is around to
hear it does it make any noise?"

Whether the states are named or not has no effect on
the logic. That states are mutually exclusive and
only one state active in each cycle are sort of obvious
requirements. (That doesn't restrict it to one hot
state machines, an active state is any specific
combination of the state variables.)

Also that there must be more than one state is
a reasonable restriction. Many state machines
are self synchronizing so don't need a reset signal.
Others do need one. There are some that can start
in an illegal state and never reach a legal state
without a reset. Most try not to design that way
if it is reasonable not to do so.

-- glen

 

[Daniel S.]

And I was hoping for an ORELSE

Coming soon to a thread near you: ELSEMAYBEIF, ELSECONFUSEDIF,
ELSERANDOMIF, etc.

I wonder if Weng will ever quit creating and feeding these very much
pointless threads. Maybe he's just a bad comedian.

 

[Weng Tianxiang]

I gave my guess. Why haven't you responded? You told me you would
tell me the answer after I guessed. Now tell me.

Shannon

Hi Sannon,
1. It is L2 cache that uses a lot of state machines;
http://en.wikipedia.org/wiki/Cache_coherence

2. IBM/Intel uses MESI protocol (Modified, Eclusive, Shared and
Invalid);
http://en.wikipedia.org/wiki/MESI_protocol

3. Please visit Intel product website to get the latest http://download.intel.com/products/processor/xeon/7300_prodbrief.pdf

4. "with up to 8 MB of L2 cache per processor" and 4 cores.
It means 4*8MB = 32MB L2 cache;

5. Each 32Bytes is a cache line;

6. 32MB/32 = 1M cache lines and 1M state machines.

The final answer is:
There is at least 1M state machines in Intel chip.

a. It is available to every users in the topics groups;
b. They are written in Verilog, not in VHDL;
c. FPGA has never had a design using L2 cache.

Any more questions?

Weng

 

[comp.arch.fpga]

Hi KS, jg,
"A synchronous or an asynchronous reset signal is vital, either with
clear routing or a hidden procedure within other initial procedures."

No, it is not.
See entries 2 and 3 on this page:
http://www.ics.uci.edu/~eppstein/pubs/misc.html

Kolja Sulimma

 

[comp.arch.fpga]

Scrambler cannot be counted as a state machine in any sense.

Wrong. Again.

The most important factor for a circuit counted as a state machine is
that its states are mutually exclusive and only one state is active in
any cycle.

Hmm. Any deterministic system can only be in one state. That is the
whole
meaning of "state". Of course there are non deterministic systems. And
also
non deterministic state machines. Just because you cannot code them in
VHDL
does not mean they do not exist. But I am sure you can provide an
extension to
VHDL that supports quantum computing. My suggestion:
if (condition) maybe
dosomething;
anyways
do somethin
beginning of the end;

Scrambler cannot meet the requirements. If it were, every circuit
would be counted as a state machine.

No, just any sequential circuit. Any circuit with state. Wait, maybe
that's
what the name comes from?
http://en.wikipedia.org/wiki/Finite_state_machine

Shift registers can be counted as a state machine only when only one
bit is set or reset among all its bits. Otherwise it cannot be counted
as a state machine.

You still insist on your reset? Read the JTAG specification for gods
sake.

Kolja Sulimma