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!
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
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.
> 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?
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.
> 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...
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?
> Verstehe ich das also richtig, dass niemand Erfahrung hat, wie man aus > einem Automaten Assembler o.ä. erzeugt? Das macht doch der Compiler :-/
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?
Gast
#1672469
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
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.
Gast
#1672550
>Mein Freund
Damals war ich noch schizophren, heute geht es uns besser ;O)
> 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...
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.
Gast
#1673068
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.
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.
Gast
#1673173
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.
Gast
#1673185
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 :)
Ich glaube ASTADE (oder wie das hieß) war mal so ein Projekt, aber das hat den Code auch nur in C umgewandelt.
Vielen Dank für diesen Hinweis! Das sieht doch schon mal immerhin sehr viel interessanter aus! Dankeschön!
Gast
#1673283
@ D.I. Da hast du natürlich recht ... ich hatte gerade One-Hot-Encoding im Kopf :)
Gast
#1673496
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.
>> 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
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.
Gast
#1673837
Bei solchen Art Parsern ist das durchaus üblich
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.