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


von Marvin M. (xyz)


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!

von Weingut P. (weinbauer)


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

von Marvin M. (xyz)


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.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


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?

von Marvin M. (xyz)


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.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


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...

von Marvin M. (xyz)


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?

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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

von Marvin M. (xyz)


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?

von Duke Scarring (Gast)


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

von Marvin M. (xyz)


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.

von Schizo (Gast)


Lesenswert?

>Mein Freund

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

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


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...

von Marvin M. (xyz)


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.

von D. I. (Gast)


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.

von Marvin M. (xyz)


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.

von mac4ever (Gast)


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.

von D. I. (Gast)


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 :)

von Michael H. (overthere)


Lesenswert?

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

von Marvin M. (xyz)


Lesenswert?

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

von mac4ever (Gast)


Lesenswert?

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

von Christian Leber (Gast)


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=projects&id=fsmdes4

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

von Bernhard R. (barnyhh)


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

von Marvin M. (xyz)


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.

von D. I. (Gast)


Lesenswert?

Bei solchen Art Parsern ist das durchaus üblich

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.