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

[glen herrmannsfeldt]

Weng Tianxiang wrote:
(snip)

3. A synchronous or an asynchronous reset signal is vital, either with
clear routing or a hidden within other procedures.

I disagree. Some can synchronize without any reset signal, though
they may have one anyway. The receiver in a UART, if started out
of frame, will synchronize to frame boundaries after not so many
characters come through. That is the purpose for start/stop bits.

There are many systems with a large number of self synchronizing
state machines.

-- glen

 

[glen herrmannsfeldt]

comp.arch.fpga wrote:

(snip)

But to give you the benefit of doubt and return to your orginal
question:
Smith-Waterman hardware implementations instantiate tens of thousands
of identical state machines.

Like the ones that Paracel used to build and sell as real systems?

Oh, wait, the implentation that we used had not reset. Damn.

Which one was that?

-- glen

 

[Jim Granville]

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!

Whoa - hang on there, Syms !!!!

What's this ANDIF, BUTIF ?!?!

You can't use that until there has been a long discussion first ?!

( I like the sound of the BUTIF, you might be onto something there... )

-jg

 

[Weng Tianxiang]

My official guess:
light blue.

Hi John_H,
1. The guessing is missing target.
2. The design falls in every person's blind point who have responded
to the post so far.

Weng

 

[Shannon]

Hi John_H,
1. The guessing is missing target.
2. The design falls in every person's blind point who have responded
to the post so far.

Weng

I guess 28.

 

[John_H]

Hi John_H,
1. The guessing is missing target.
2. The design falls in every person's blind point who have responded
to the post so far.

Weng

To the extent that my guess is as applicable as anyone elses guess, I
stand behind it.

You are asking a seriously senseless question and frankly I'm tired of
watching the thread drone on and on and on so I just added a little to
it because of the absurdity.

Who cares?!

 

[comp.arch.fpga]

Hi,
1. I am talking about GUESSING the largest number of state machines a
current finished design may have. Not ceiling.

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

3. A synchronous or an asynchronous reset signal is vital, either with
clear routing or a hidden within other procedures.

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

 

[Jim Lewis]

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

....

What's this ANDIF, BUTIF ?!?!

And I was hoping for an ORELSE

 

[Weng Tianxiang]

Hi KS, jg,
I answer your questions directly and clearly here:
1. The number of state machines should be much greater than 100k.

2. "Many state machines have no reset signal. "

I have answered your question:
"A synchronous or an asynchronous reset signal is vital, either with
clear routing or a hidden procedure within other initial procedures."

3. "a single FF_CE can be considered a state machine"

No, a single FF_CE is not included in the count. Otherwise my post for
a guessing doesn't make sense.

4. Shifting registers can and should be counted as a state machine
with only one bit set (or only one bit reset) among all its bits.

Please don't delete group names: comp.lang.verilog, comp.lang.vhdl

Because answering this quiz needs knowledge beyond scopes of FPGA and
VHDL.

A quiz beyond FPGA and VHDL may have been the first time since both
groups were set up 10-20 years ago.

I have been wondering why there nobody is asking such a question:
Why is this quiz beyond scope of VHDL?

Any more questions?

Weng

 

[Jeff Cunningham]

...

And I was hoping for an ORELSE

I'm for BUTOUT.

 

[Shannon]

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

 

[Hal Murray]

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

Nonsense. Consider self synchronizing scramblers. They are
just a batch of XOR gates and FFs. From any unspecified state,
they will put out garbage for N clock ticks. After that,
the output is determined by the input.

 

[glen herrmannsfeldt]

comp.arch.fpga wrote:

(snip)

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

If this is the one I remember, then it is wrong:

Smith-Waterman does local alignment which requires finding the
maximum score anywhere in the array. Global alignment only needs
the score at the end. It is interesting, but most DNA research
needs the local alignment.

Paracel and Time Logic make (or made) commercial DNA matching
machines that should qualify as large number of state machines.

-- glen

 

[Weng Tianxiang]

Nonsense. Consider self synchronizing scramblers. They are
just a batch of XOR gates and FFs. From any unspecified state,
they will put out garbage for N clock ticks. After that,
the output is determined by the input.

Hi Hal,
Can you please put more information on scramblers and their state
machines?

I don't know scramblers.

Weng

 

[Hal Murray]

Can you please put more information on scramblers and their state

machines?

I don't know scramblers.

The idea is to generate a random bit stream that you can XOR
with a data stream for a serial link to make sure there are
no long strings of 0s or 1s.

It's a pile of FFs and XORs. The same logic as CRCs.
LFSR, Linear Feedback Shift Register is another buzzword.

The "self synchronizing" part means that the output
doesn't need to be reset. It will get to a known state
after N cycles. A single bit error on the link
will produce a multi-bit error after the descrambler.
That pattern of bits is the polynomial used by the scrambler.

The wiki article is pretty good.
http://en.wikipedia.org/wiki/Scrambler_(randomizer)
A digital communications text might be better.

 

[Weng Tianxiang]

The idea is to generate a random bit stream that you can XOR
with a data stream for a serial link to make sure there are
no long strings of 0s or 1s.

It's a pile of FFs and XORs. The same logic as CRCs.
LFSR, Linear Feedback Shift Register is another buzzword.

The "self synchronizing" part means that the output
doesn't need to be reset. It will get to a known state
after N cycles. A single bit error on the link
will produce a multi-bit error after the descrambler.
That pattern of bits is the polynomial used by the scrambler.

The wiki article is pretty good.
http://en.wikipedia.org/wiki/Scrambler_(randomizer)
A digital communications text might be better.

Hi Hal,
Thank you very much for your information.

Weng

 

[Weng Tianxiang]

Hi Hal,
8b/10b is perfect for scrambling function. PCI-e uses 8b/10b
technology.

Scramble technology still uses randomized serial and XOR now? After 8b/
10b technology, I think other randomized XOR scramble technology is
dying out, is it right?

IBM got one patent for 8b/10b technology in 1981, Xilinx filed for 23
patents on 8b/10b implementation in FPGA on one day in 2004.

I think that IBM is really a technology leader in almost all respects
in computer industry. Xilinx is the leader of FPGA.

Weng

 

[jtw]

Far too restrictive. In a TDMA architecture I implemented, one RAM contains
512 locations of N bits each: 512 individual state machines. Each 'virtual
process' was identical, but had different inputs. For this particular
design, a lower bound on the number of states would be 4*512 = 2048, since I
had four instances of that particular module. Probably double that, due to
similar logic structures downstream. If it were appropriate for the
application, scale it up appropriately.

Depending on required processing speed, state machine complexity, target
device capabilities, etc., an internal (or external) RAM could contain
thousands -- or millions -- of individal state machines.

For my particular case, the next states were defined by equations, the last
states were the outputs of the RAMs, and the particular state machine was
selected by the RAMs address. (I instantiated the RAMs, but they could have
been generated by a process. However, the tools aren't always that good at
properly inferring dual-port RAMs, so if you need a particular
structure... )

So, what are the limiting factors? Available logic, available storage
(registers and memory), creativity, and objectives.

What is the value of the answer?

JTW

 

[Hal Murray]

Scramble technology still uses randomized serial and XOR now? After 8b/
10b technology, I think other randomized XOR scramble technology is
dying out, is it right?

8b/10b has a 20% bandwidth hit. That may be reasonable on short
links where the cost of the link is small relative to the cost
of the end points. But change hats from a computer room
to a Telco. Their costs are mostly the fibers in the ground.
Using scramblers is a no-brainer for 20% cost reduction.

 

[John_H]

Hi Hal,
8b/10b is perfect for scrambling function. PCI-e uses 8b/10b
technology.

Scramble technology still uses randomized serial and XOR now? After 8b/
10b technology, I think other randomized XOR scramble technology is
dying out, is it right?

IBM got one patent for 8b/10b technology in 1981, Xilinx filed for 23
patents on 8b/10b implementation in FPGA on one day in 2004.

I think that IBM is really a technology leader in almost all respects
in computer industry. Xilinx is the leader of FPGA.

Weng

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.