Hallo, habe da mal ne Frage an euch Profis (bin noch nicht so bewandert mit dem AVR): Ich habe vor ein Spiel (ist kein komplexes Siel, ist so ne art 3 in einer reihe) mit dem AVR (Mega128) zu realisieren. Dabei soll nach jedem Zug die Spielsituation bewertet werden, anhand der nächsten möglichen Spielmöglichkeiten. Soll so ne art KI werden. Dabei ruft die Funktion die die Spielsituation bewertet sich immer wieder selbst auf (rekursiv). Auf dem PC läuft das Prog schon (Konsole) sind ein paar kB. Jetzt möchte ich das Spiel auf den Mega128 bringen, kann es da Probleme mit dem Rekursiven Funktionsaaufruf geben? Kann ich das im Vorfeld schon mit einem Tool checken, wieviel Speicher im worstcase mit der Rekursion draufgeht? Oder was gibt es da für möglichkeiten? Ich hoffe ihr versteht mein Problem. Danke schon mal für die Antworten.
> kann es da Probleme mit dem Rekursiven Funktionsaaufruf geben? Probleme kann es immer geben :-) Kann, muss aber nicht. > Kann ich das im Vorfeld schon mit einem Tool checken, wieviel > Speicher im worstcase mit der Rekursion draufgeht? Den tatsächlichen Speicherverbrauch kann man nur feststellen indem das Programm läuft. Allerdings könnte man das in einem Simulator machen. > Oder was gibt es da für möglichkeiten? Eine Möglichkeit ist zb. folgende: Du sorgst dafür, dass am Anfang der Speicher in dem der Stack residiert mit einem Bitmuster gefüllt wird, zb 0xAA dann lässt du das Programm laufen und wenn es durchgelaufen ist, schaust du dir den Speicher wieder an. Alles was immer noch 0xAA ist, ist offensichtlich niemals angetascht worden. Zur Sicherheit macht man das dann noch mit einem 2-ten Muster (was ist, wenn zufällig 0xAA auf den Stack geschrieben wurde), zb. 0x55. Damit kannst du feststellen, wieviel Stack in diesem einen Programmlauf verbraucht wurde. Es liegt dann an dir dein Programm so zu bedienen, dass du den Fall 'maximaler Stackverbrauch' vorliegen hast.
Eine Simulation mit vmlab kann da auch weiterhelfen. (Version 3.12 ist freeware). Oliver
Anmerken sollte man noch: Nur mir den Mitteln einer Hochsprache ist das etwas schwierg zu lösen. Du wirst also darauf angewiesen sein, dass die dein Simulator funktionen bereitstellt, mit denen du vor und nach Programmausführung an den simulierten Speicher rankommst.
Der Tipp von Karl Heinz mit dem markierten Stackbereich ist gut und schnell zu implementieren. Das Bitmuster könnte man sogar z.B. im Startup-Code defaultmäßig schreiben lassen. Ich hätte noch weitere Ideen: Hol dein modifiziertes Programm in einen Debugger und schau dir den Stackpointer an den notorischen Stellen an. Modifiziert heisst, dass du nur die Rekursion nicht durchführst, aber sonst den Code unverändert lässt. Du bekommst so den Stackverbrauch für ein Funktionslevel. Für jeden Aufruf in der Rekursion addierst du diesen Wert auf. Die notorischen Stellen sind Stackpointer nach dem Rücksprung der Funktion und an der Stelle mit dem höchsten Stackverbrauch in der Funktion. Der höchste Stackverbrauch ist oft am Funktionsanfang nach dem Anlegen der Autovariablen. Genauer kann man die optimale Prüfposition mit dem Sourcecode festlegen ggf. sogar im Assemblerlisting nachsehen wo SP maximal verändert ist. Ein anderer Weg wäre, dass du eine Stackprüffunktion (Stackpointer per Inline ASM holen) an den Anfang der Rekursionsfunktion stellst. Diese Prüffunktion kann den aktuellen Stackpointer ausgeben und/oder prüfen, ob sich der Stackpointer einer kritischen Grenze nähert. Damit kannst du zur Laufzeit der Rekursion Infos bekommen und experimentell herausfinden, ob Gefahr besteht, dass es knallt.
Rekursionen sind eine spezielle mathematische Schreibweise und daher nicht so effizient, wie andere Lösungen. Sie sind teilweise sogar extrem ineffizient, wenn darin mehrere Vorgänger benötigt werden, da dann Rekursionen exponentiell umsonst berechnet werden müssen. In der Regel lassen sich Rekursionen einfach in Schleifen umformen und laufen dann viel schneller und benötigen viel weniger Speicherplatz. Peter
Also wenn wir hier von KI sprechen, dann sind diese rekursiven Sachen wohl höchstwahrscheinlich Suchoperationen in einem potentiell sehr grossen Zustandsraum - vermutlich eine Art MIN-MAX-Algorithmus. Solche Sachen lassen sich nun wieder in der Regel NICHT in Schleifen umformen (wenn wir mal von speziellen Zustandsräumen absehen). Das einzige was da bleibt ist es "nutzlose" Zweige möglichst früh zu erkennen und nicht abzuarbeiten.
Alternative zur oben geschriebenen Analyse wäre, sich den erzeugten Assemblercode anzusehen und mal zu zählen wie viele push/pop und call/ret (2Byte) bei jeder Rekursion insgesammt ausgeführt werden. Dann diese Zahl mit der Suchtiefe multiplizieren. Bei meiner 4-Gewinnt Routine schafft ein AVR rund 6 Rekursionen bei weniger als 1KB RAM Verbrauch. Für mehr ist der AVR schlicht zu langsam, der Speicher ist aber (zumindest bei mir) kein Problem.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.