Wie viele States sollte ein FSM haben?

[Pepe (Gast)]

Hallo.
Ich stehe vor dem Thema, dass ich ein Frame/Paket mit mehreren Werten 
z.B. per SPI verschicken möchte. Werde 15-20 verschiedene "Werte" in den 
Frame eintragen. Jeder Wert besteht aus einem Header und 2-3 Words.
Würde die ganzen Werte in einen FiFo eintragen und danach per SPI 
verschicken.

Man könnte das Zusammenstellen des Frames ja per FSM lösen. Bei der 
Anzahl an verschiedenen Messwerten würde da aber einige States 
zusammenkommen.

Jetzt frage ich mich, wie viele States denn eine FSM haben sollte?

[Oliver S. (oliverso)]

So wenig wie möglich, so viele wie nötig. Oder halt 42, wenn das besser 
passt.

Oliver

[Andreas S. (Firma: Schweigstill IT) (schweigstill)]

Wie schon von Oliver angedeutet, sollte jede FSM exakt 42 Zustände 
aufweisen.

[Markus (Gast)]

Andreas S. schrieb:

> Wie schon von Oliver angedeutet, sollte jede FSM exakt 42 Zustände
> aufweisen.

Du musst den Grund für die Zahl 42 nennen:

https://www.youtube.com/watch?v=ASoz_NuIvP0

[Fred Funke (Gast)]

Pepe schrieb:
zusammenkommen.
>
> Jetzt frage ich mich, wie viele States denn eine FSM haben sollte?

bei FPGA#s mit 4-LUT höchsten 16; bei denen mit 6 höchtens 64. Das gilt 
nur wenn binarye state encoding wählbar ist.

[Pepe (Gast)]

@Markus
Wenn schon, dann bin ich für 42. ;-)

@Fred
Und was passiert, wenn ich bei einer 4-LUT mehr States einbaue?
Was wird dann (intern) draus gemacht? Weil lauffähig ist die FSM ja dann 
trotzdem.

[Matyas (Gast)]

Pepe schrieb:
> Jetzt frage ich mich, wie viele States denn eine FSM haben sollte?

Da gibt es so keine Regel. Im Grunde ist ein Counter ja auch eine FSM.

Wenn ich n Werte von einem FIFO auslesen müsste, würde ich nicht n 
States dafür schreiben, sondern in einem State sowas wie:

case state is
    when ... => 
       fifo_entries <= 5;
       state <= READ_FIFO;

    when READ_FIFO =>
       if fifo_ptr < fifo_entries then
           frame(some_range_calculation) <= fifo(fifo_ptr);
           fifo_ptr <= fifo_ptr + 1;
       else
           fifo_ptr <= 0;
           state <= next_state;
       end if;

    when ... => ...

[Pepe (Gast)]

@Matyas
Das Auslesen in den Fifo ist nicht mein Thema. Das ist ohne FSM 
realisiert.

Sondern ich habe verschiedene Werte, die zwischen 2-3 Words lang sind 
und aus unterschiedlichen "Quellen" stammen. Und diese Werte möchte ich 
in einen gesamten Frame zusammensetzen und in einen FiFo eintragen.
Und für das Mergen des Frames hätte ich gerne eine FSM eingesetzt.

[A. S. (Gast)]

Pepe schrieb:
> Und diese Werte möchte ich
> in einen gesamten Frame zusammensetzen und in einen FiFo eintragen.
> Und für das Mergen des Frames hätte ich gerne eine FSM eingesetzt.

Was meinst Du damit?

Wenn die werte von Asynchron irgendwo unabhängig reinkommen, dann 
braucht es keine FSM.

Wenn die Werte nacheinander in einen Frame geschrieben werden, dann 
braucht es keine FSM.

Wenn die Werte nacheinander in einer festen Folge reinkommen, und nach 
jedem reinkommen was anderes gemacht werden muss, dann vielleicht, aber 
dazu fehlt mir jede Info zu Deinem Problem.

[Pepe (Gast)]

Grundsätzlich werte ich in Echtzeit das Bild einer Zeilenkamera aus.
D.h. es läuft eine Kantenerkennung gleich im FPGA und ich gebe die 
Koordinaten der Kanten für einige Messbereiche aus. Zusätzlich werden 
noch Positionen von Encodern in den Frame eingetragen.
Der Frame mit den Ergebnissen soll synchron zur Kamera ausgegeben 
werden.

Leider kann es vorkommen, dass "Kante#1" auch mal NACH "Kante#2" kommt, 
weil sich die Polarität der Helligkeiten im Bild ändern kann (SW <> WS).

[Fred Funke (Gast)]

Pepe schrieb:
> @Fred
> Und was passiert, wenn ich bei einer 4-LUT mehr States einbaue?

Der kritische Pfad wird um einen Chiplevel länger was dazu führt, das 
man die FSM und damit den FPGA nicht so schnell takten kann.

[NichtWichtig (Gast)]

Pepe schrieb:
> Und für das Mergen des Frames hätte ich gerne eine FSM eingesetzt.

Wie wäre es mit einem Bitfield?
Wenn es 15-20 Objekte sind langt eine 32 bit Wert, jedes Objekt bekommt 
1 bit und es lassen sich wunderbar und einfach Prüfungen durchführen.

[Matyas (Gast)]

Pepe schrieb:
> Sondern ich habe verschiedene Werte, die zwischen 2-3 Words lang sind
> und aus unterschiedlichen "Quellen" stammen.

Und wie sehen diese Quellen aus?

Ich versuche häufig mir einen Datentyp/LUT zu bauen, der mir die 
Beschreibung vereinfacht.

Wenn jede Quelle die Werte in einen Datentyp* schreibt, könnte man da 
auch einfach drüber iterieren.

* zB:

type t_quelle_entry is record
    byte_buffer(range) : t_byte;
    used_entries       : natural in range xy;
end record;

type t_quellen is array(range_nr_quellen) of t_quelle_entry;

signal quellen : t_quellen;
...

case state is
    when READ_FRAME_FROM_SOURCES => 
       if quell_ptr < NR_QUELLEN then
           if byte_ptr < quellen(quell_ptr).used_entries then
               frame(some_range_calculation) <= quellen(quell_ptr).byte_buffer(byte_ptr);
               byte_ptr <= byte_ptr + 1;
               total_nr_of_bytes <= total_nr_of_bytes + 1;
           else
               byte_ptr <= 0;
               quell_ptr <= quell_ptr + 1;
           end if;
       else
           quell_ptr <= 0;
           state <= WRITE_FIFO;
       end if;

    when WRITE_FIFO =>
       if quell_ptr < total_nr_of_bytes then
           fifo(quell_ptr) <= frame(quell_ptr);
           quell_ptr <= quell_ptr + 1;
       else
           quell_ptr <= 0;
           total_nr_of_bytes <= 0;
           state <= next_state;
       end if;

    when ... => ...

Edit: Vll zu spät, war Mittagspause...

[Pepe (Gast)]

@Matyas
Klingt gut. Macht es auf jeden Fall einfacher.

[-gb- (Gast)]

51 wie die USA.

Aber mal eine ernste Frage: Sollten es immer 2^n States sein? Das wird 
ja intern als binäre Zahl gebaut, wenn man jetzt 7 Zustände hat bleibt 
ein Wert unbelegt aus 2^3. Kann es passieren, dass die Statemachine in 
diesen Zustand spring obwohl er nirgends verwendet wird?

[Michael B. (laberkopp)]

Pepe schrieb:
> Jetzt frage ich mich, wie viele States denn eine FSM haben sollte?

Mindestens 2.

[Matyas (Gast)]

-gb- schrieb:
> Kann es passieren, dass die Statemachine in
> diesen Zustand spring obwohl er nirgends verwendet wird?

Ja, beispielsweise bei einem SEU.

[Blechbieger (Gast)]

-gb- schrieb:
> Sollten es immer 2^n States sein? Das wird
> ja intern als binäre Zahl gebaut, wenn man jetzt 7 Zustände hat bleibt
> ein Wert unbelegt aus 2^3.

Quartus verwendet normalerweise one-hot Kodierung, d.h. pro State ein 
Flipflop (bzw -1, alle FF=0 ist ein weiterer State). Hat vermutlich 
Vorteile für die Überführungs- und Ausgabenetze.

K.A. wie Xilinx das handhabt.

[Christian R. (supachris)]

Bei Xilinx kann man es einstellen, ansonsten wählt er irgendwas aus, was 
seiner Meinung nach passt.
Bisher musste ich das noch nie umgestellen. Ich hab hier eine lange FSM 
zum Auslesen von Daten über das ICAPE2 Interface, z.B. Boot Status. Das 
klappt auch. Wieso auch nicht. Eine FSM hat genau so viele States wie 
benötigt.

[Christophz (Gast)]

Matyas schrieb:
> -gb- schrieb:
>> Kann es passieren, dass die Statemachine in
>> diesen Zustand spring obwohl er nirgends verwendet wird?
>
> Ja, beispielsweise bei einem SEU.

Per Synthesizer Pragma kann man erzwingen, dass für nicht verwendete 
aber mögliche Zustände eine Resetlogik generiert wird. Wird z. B. von 
den mir bekannten Safety Normen jeweils so verlangt.

Das erhöht den Ressourcenverbrauch etwas und verlangsamt die FSM, darum 
wird das per default nicht gemacht.

[Burkhard K. (buks)]

Pepe schrieb:
> Und was passiert, wenn ich bei einer 4-LUT mehr States einbaue?
Nicht viel, sofern fsm-style "BRAM" eingestellt ist. :-)

Christophz schrieb:
> Per Synthesizer Pragma kann man erzwingen, dass für nicht verwendete
> aber mögliche Zustände eine Resetlogik generiert wird.
Bei Xilinx nennt sich das "-safe_implementation = yes".

-gb- schrieb:
> Aber mal eine ernste Frage: Sollten es immer 2^n States sein?

Nö - wieso denn?

Blechbieger schrieb:
> K.A. wie Xilinx das handhabt.

Da hast Du die Qual der Wahl. Mit im Angebot: Auto, One-Hot, Gray, 
Johnson, Compact, Sequential, Speed, User - und witzigerweise "None" 
(noch nicht ausprobiert).

[C. A. Rotwang (Gast)]

Burkhard K. schrieb:
>> Aber mal eine ernste Frage: Sollten es immer 2^n States sein?
>
> Nö - wieso denn?

Komplettes ausdecodieren aller möglichen Zustände damit die FSM nicht 
festhängt.

Kann man auch anders erreichen ('when others').
Aber man sollte sich schon mal drüber nachdenken wie die Zustände der 
FSM realisiert werden und wie sich die FSM verhält wenn mal eine 
FSM-Zustand eintritt (beispielsweise durch unbeabsichtigtes 
"Übertakten") der so nicht vorgesehen war.

[Andreas S. (Firma: Schweigstill IT) (schweigstill)]

NichtWichtig schrieb:
> Wie wäre es mit einem Bitfield?
> Wenn es 15-20 Objekte sind langt eine 32 bit Wert, jedes Objekt bekommt
> 1 bit und es lassen sich wunderbar und einfach Prüfungen durchführen.

Es geht hier um programmierbare Logik bzw. deren Beschreibungssprachen. 
Da ist man nicht auf 8/16/32/64 Bit breite Datentypen eingeschränkt. 
Ganz im Gegenteil nöhlt der Synthesizer herum, wenn Bits nicht verwendet 
werden und dampft dann ein Konfigurationsregister auf die tatsächlich 
benötigten z.B. 27 Bit ein. Und eine One-Hot-FSM mit 17 Zuständen wird 
dann intern durch 17 Bit repräsentiert. Bei der anschließenden 
Implementierung des synthetisierten Designs muss das ganze natürlich 
wieder auf die tatsächlichen Hardwareressoucen abgebildet werden, d.h 
Register, LUTs usw., so dass es hierbei natürlich wieder zu Verschnitt 
kommen kann. Insgesamt erfolgt die ganze Optimierung aber deutlich 
rigoroser als beim Kompilieren und Linken von Software.

[StefG (Gast)]

FSM = Fliegendes Spaghetti Monster (gemäss Wikipedia)

[Christophz (Gast)]

C. A. Rotwang schrieb:
> Burkhard K. schrieb:
>>> Aber mal eine ernste Frage: Sollten es immer 2^n States sein?
>>
>> Nö - wieso denn?
>
> Komplettes ausdecodieren aller möglichen Zustände damit die FSM nicht
> festhängt.

Geht theoretisch ist aber schwierig zu erreichen, wenn der Synthesizer 
freie Hand hat bei der Wahl der FSM codierung.

Tönt auch eher nach Verilog Stil, wo es keinen Enumerationstyp gibt und 
FSM dann mit Bitvektoren beschrieben werden, die dann der Synthesizer 
wieder komplett anders implementiert.

> Kann man auch anders erreichen ('when others').

Synthesizer ignorieren den 'when others' Pfad (kann ich definitiv 
bestätigen für Synplify). Ist auch so dokumentiert bzw. wird als Warnung 
ausgegeben.

Um das gewünschte Ziel zu erreichen, stehen die schon weiter oben 
erwähnten Pragmas zur Verfügung.

[Matjos (Gast)]

Christophz schrieb:
> Synthesizer ignorieren den 'when others' Pfad (kann ich definitiv
> bestätigen für Synplify). Ist auch so dokumentiert bzw. wird als Warnung
> ausgegeben.
>
> Um das gewünschte Ziel zu erreichen, stehen die schon weiter oben
> erwähnten Pragmas zur Verfügung.

Ja stimmt, wenn der 'when others state' als nicht erreichbar erkannt 
wird und keine Attribute für die Synthese gesetzt sind.

Ich habe auch schon gesehen, dass der 'when others state' im Reset 
gesetzt wird, um die Erreichbarkeit der Synthese zu zeigen.