mikrocontroller.net

Forum: FPGA, VHDL & Co. Automat -> FPGA/CPLD


Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ein Freund (der nicht wusste, das ich nur Desktop-Entwicklung mache) 
fragte mich:

"Ich interessiere mich gerade für Code-Generatoren für Automaten und 
interessiere mich auch für die Frage, wie man endliche Automaten in 
FPGAs und CPLDs programmiert. Hast Du da Hinweise auf Hard- und 
Software?"

Er habe einen effizienten Algorithmus auf der Basis von sog. 
failure-Automaten entwickelt und einen Generaten geschrieben, der aus 
den Automaten gleich C++-Code macht.
Da das Ergebnis aber wenig performant sei, will er als nächstes 
Automaten gleich in Assembler übersetzen oder eben in FPGAs speichern 
lassen.

Kann ihm da jemand weiterhelfen?

Grüße!

Autor: Weingut Pfalz (weinbauer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
asm in FPGA? ... Mit Kanonen auf Spatzen schießen

FPGA als Speicher? ... naja

würde sagen erklär dem Jungen das mit der Stromspannung nochmal

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich kenne mich damit gar nicht aus (Desktop-Entwickler)...

Jedenfalls geht es darum, dass er Automaten hat, die nun möglichst 
schnell ausgeführt werden sollen.
Im Moment lässt er automatisch C++-Code erzeugen, aber der Compiler ist 
ihm zu langsam und das Ergebnis zu groß.

Daher würde er lieber gleich automatisch Assembler-Code erzeugen lassen.
Oder alternativ das ganze in einem FPGA/CPLD speichern.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> dass er Automaten hat, die nun möglichst
> schnell ausgeführt werden sollen.
Bei Automaten geht es doch gar nicht darum, dass sie möglichst schnell 
ausgeführt werden, sondern dass sie die richtigen Transitionen zum 
richtigen Zeitpunkt machen...

> wie man endliche Automaten in FPGAs und CPLDs programmiert.
Ich mache das in VHDL.
Du kannst auch ein Bildchen malen und dann VHDL-Code daraus erzeugen.

Was sind das eigentlich für Automaten?
Und warum müssen die schneller gemacht werden?

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das sind Parser-Automaten, die natürlich schon schnell laufen sollen.

Die Geschwindigkeit der Automaten selbst ist wohl auch OK, das Problem 
ist eher, dass diese (zigtausend Zustände) vielen Millionen Zeilen 
C++-Code entsprechen und der C++-Compiler so lange braucht.
Zudem ist das Kompilat eben relativ groß.

Schöner wäre ein schlankes Programm, das sich schnell erstellen lässt, 
so wie ich ihn verstanden habe.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Das sind Parser-Automaten
Ich glaube nicht, dass man sowas in vertretbarer Zeit in ein FPGA 
bekommt.

> Schöner wäre ein schlankes Programm, das sich schnell erstellen lässt,
> so wie ich ihn verstanden habe.
Dann müsste man auch genau dort anfangen zu optimieren (optimale 
Speicherzugriffe...), und nicht einfach die Verarbeitung 
beschleunigen...

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der C++-Code ist ja wohl schon performant genug.
Es sind eben nur zu viele Zeilen Code (einige Millionen), sodass der 
Compiler zu lange braucht und eben eine große EXE ausspuckt.

Verstehe ich das also richtig, dass niemand Erfahrung hat, wie man aus 
einem Automaten Assembler o.ä. erzeugt?

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Verstehe ich das also richtig, dass niemand Erfahrung hat, wie man aus
> einem Automaten Assembler o.ä. erzeugt?
Das macht doch der Compiler  :-/

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Habe das Gefühl, wir reden aneinander vorbei.

Ich weiß nicht, wie der Automat aktuell repräsentiert ist.

Mein Freund erzeugt daraus jedenfalls aktuell C++-Code mit Hilfe eines 
eigenen Code-Generators.
Der entstehende Code ist zu umfangreich (langer Compilerlauf, großes 
Kompilat).

Er möchte stattdessen nun keinen C++-Code mehr generiert bekommen (und 
auch keinen ASM-Code aus dem C++-Code, da der ja auch wieder zu 
umfangreich wäre), sondern eben direkt ASM aus dem Automaten, weil das 
vermutlich kleiner wäre und sich bedeutend schneller in Binärcode 
übersetzen ließe.

Nun wäre es für ihn aber natürlich enorm viel Arbeit, einen eigenen 
ASM-Codegenerator zu schreiben.
Deshalb die Frage, ob es da nicht schon etwas Fertiges gibt.

Klarer?

Autor: Duke Scarring (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Marvin M. schrieb:
> Ich weiß nicht, wie der Automat aktuell repräsentiert ist.

Also ein C++-Generator existiert.

Dein Freund will einen ASM und/oder VHDL-Generator. Und jetzt sollen die 
Forumsteilnehmer raten ob das gehen kann?

Ja, es geht, aber ohne die Automatenrepresentation zu kennen, wird sich 
hier keiner zu konkreten Aussagen bewegen lassen. Wie auch?

Duke

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es geht darum, ob jemand irgendein Tool kennt, das Automaten in ASM 
o.ä. überführen kann.

Es ist sicherlich erheblich einfacher, seinen Automaten in ein anderes 
Automaten-Format zu überführen, als selbst einen neuen Codegenerator zu 
schreiben, der ähnlich performant und ausgereift wie ein kommerzielles 
Produkt wäre.

Autor: Schizo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Mein Freund

Damals war ich noch schizophren, heute geht es uns besser ;O)

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Es geht darum, ob jemand irgendein Tool kennt, das Automaten in ASM
> o.ä. überführen kann.
Hier beißt sich die Katze in den Schwanz...

Ein Compiler kann das. Und wenn die Umsetzung des Automaten in C++ Code 
effizient gelungen ist, dann gelingt auch die Umsetzung von C++ nach C 
nach ASM effizient. Wenns vorn schon klemmt, dann wirds hinten raus 
nicht signifikant besser werden...

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, deshalb geht es ja darum, die Generierung des C++-Codes komplett zu 
vermeiden und direkt ein erprobtes Tool einzusetzen, das aus einem 
Automaten gleich sinnvoll schlanken o.ä. erzeugt.

Außerdem geht es ja vor allem darum, die Kompilierzeit einzusparen.
Das Kompilat ist ja schon ausreichend schnell.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da meckern die Softwerker wenn der Compiler mal ein paar Minuten 
braucht...
Was sollen wir VHDL'er sagen :P

Ne aber ernsthaft, wenns zu langsam ist würde ich ne dickere Maschine 
für diesen Fall hinstellen.
Das Problem ist warum will man sowas? Wenn mans direkt in ASM übersetzt 
dann bin ich auf eine Architektur festgenagelt.

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Na ja, das Kompilat ist ja auch recht groß.
Ich schätze, es soll ohnehin nur auf x86 laufen, deshalb wäre die 
Festlegung auf eine Architektur in Ordnung.

Autor: mac4ever (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jetzt mal eine ganz dumme Frage: Wie schnell sollte ein Automat, der in 
C++ Millionen von Codezeilen erzeugt, denn kompiliert werden? Wie groß 
sollte das Kompilat sein (Nebenrechnung: 1M Zeilen -> 1M Zeilenumrüche 
-> 1MB allein dafür ... ich bin mir bewusst, dass die CR nicht im 
Kompilat enthalten sind, geht nur ums Prinzip)? Und warum ist die 
Compile-Time so wichtig? Werden die Automaten mit tausenden von 
Zuständen denn im Minutentakt zusammengefrickelt?

<spaß>Logisch, bei tausenden von Zuständen stößt die Methodik namens 
"Trail&Error" an ihre Grenzen ... ;)</spaß>

Wenn dein Freund bereits einen Code-Generator für C++ geschrieben hat, 
was hindert ihn daran einen Generator für ASM zu schreiben? Optimaler 
als per Hand wird es wohl kaum gehen (wenn man weiß was man tut).

Zum Thema FPGA/CPLD:
Die zweite Klasse (CPLD) kannst du bei der genannten Anzahl von 
Zuständen gleich wieder vergessen. Dafür reichen die FlipFlops nicht 
aus.
Einen solcher Automat wird wohl ganz gut in ein FPGA passen, je nachdem 
was außer dem Zustandswechsel noch bewerkstelligt werden soll. Aber egal 
ob C++ oder VHDL: Je komplexer, desto länger braucht auch der 
Compiler/Synthesizer. Prinzipiell ist der Synthesevorgang eines FPGAs 
deutlich langsamer als die Kompilierung eines Programms. Jedenfalls sind 
das meine bisherigen Erfahrungen.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja 1000e von Zuständen können mit ca 14 Bits kodiert werden, das passt 
schon noch ins CPLD rein, wies mit dem Übergangsnetzwerk aussieht ist 
allerdings wieder eine andere Frage :)

Autor: Michael H. (overthere)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich glaube ASTADE (oder wie das hieß) war mal so ein Projekt, aber das 
hat den Code auch nur in C umgewandelt.

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank für diesen Hinweis!
Das sieht doch schon mal immerhin sehr viel interessanter aus!
Dankeschön!

Autor: mac4ever (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ D.I.
Da hast du natürlich recht ... ich hatte gerade One-Hot-Encoding im Kopf 
:)

Autor: Christian Leber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Fuer die Erzeugung von C/C++ state machines gibt es diverse Programme, 
wie man leicht auf freshmeat.net finden kann. (z.B. Regel)

Fuer Verilog (und dieses VHDL) gibt es den FSMDesigner, aber tausende 
states gehen nicht und machen auch keinen Sinn.
http://ra.ziti.uni-heidelberg.de/index.php?page=pr...

Wenn jmd. tausende states braucht... dann ist wahrscheinlich am Design 
etwas falsch.

Autor: Bernhard R. (barnyhh)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Wenn jmd. tausende states braucht... dann ist wahrscheinlich am Design
>> etwas falsch.

So etwas nannte einer meiner Kollegen einmal "(Objekt)Orientierungsloses 
Nichtdesign".

Das konnte ich mir jetzt nicht mehr "verkneifen".

Bernhard

Autor: Marvin M. (xyz)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mein Freund ist Informatik-Prof., ich denke schon, dass er weiß, was er 
da tut...
Die Zustände sind notwendig, da es sich um Parser handelt.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei solchen Art Parsern ist das durchaus üblich

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.