Not logged in. · Lost password · Register

Forum: Master / Vertiefung LS 2: Programmiersysteme RSS
Aufgabe 10.3: Optimale Registerverw. für Ausdrucksbäume, Sethi-Ullmann-Algorithmus: Lösung
luisgerh
Member since Nov 2016
32 posts
Subject: Sethi-Ullmann-Algorithmus, Auswertungsreihenfolge
In den Uebungsfolien (tut10_slides_handout.pdf) wird auf Folie 11/14 mit dem Title "Aufgabe 10.3: Optimale Registerverw. für Ausdrucksbäume, Sethi-Ullmann-Algorithmus: Lösung" die Auswertungsreihenfolge beispielhaft angezeigt.

Wenn ich die vorherige Folie richtig verstehe gitb tes beim S.U.A. keine Vorschrift welches Kind zuerst ausgewertet wird wenn beide Kinder den gleichen Registerverbrauch haben. Daher wuerde ich in solchen Faellen immer eine bevorzugung des rechten/linken Kindes erwarten.

Im Beispiel wird jedoch auf hoeherer Ebene zunaechst das rechte Kind gewaehlt und dann auf niedriger Ebene das linke Kind, obwohl in beiden Faellen die Kinder den gleichen Registerverbrauch haben.

Handelt es sich hier um eine inkonsistenz oder gibt es doch eine Vorschrift zur Auswertungsreihenfolge?
luisgerh
Member since Nov 2016
32 posts
Wikipedia sagt "If both subtrees need equal as much registers, then the order of evaluation is irrelevant." [1].

Ich bin aber z.B. der Meinung das es sinn macht erst den rechten Teilbaum auszuwerten weil man dann spaeter eventuell direkt eine "Register = Register OP Memory" verwenden kann (bei kommutativen Operationen kann man das natuerlich auch wenn man den linken zuerst macht, z.B. bei Minus macht es aber einen Unterschied wenn ich das richtig sehe).

[1] https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm
luisgerh
Member since Nov 2016
32 posts
Ausserdem in den Vorlesungsfolien zu finden: "Bei kommutativen Operationen Operanden so vertauschen, dass möglichst viele Variablen direkt aus Speicher gelesen werden können".

Den Fall mit dem Minus deckt das aber nicht ab, ist ja nicht kommutativ.
pkr
The Compiler Guy
Member since Oct 2016
19 posts
In reply to post #1
+1 luisgerh
Quote by luisgerh on 2020-06-20, 10:15:
Handelt es sich hier um eine inkonsistenz oder gibt es doch eine Vorschrift zur Auswertungsreihenfolge?

Grundsätzlich ist es bei Kindern mit gleichem Registerverbrauch egal, in welcher Reihenfolge diese bearbeitet werden. Der Grund, warum der rechte "+"-Teilbaum vor dem linken "-"-Teilbaum bearbeitet wird (und an anderer Stelle stattdessen zuerst das linke Kind bearbeitet wird), ist hier aber ein anderer: Der gemeinsame Elternknoten bräuchte mehr Register als zur Verfügung stehen, deshalb muss das rechte Kind "herausgeschnitten" und vor der Bearbeitung des restlichen Baums in den Speicher ausgewertet werden (vgl. VL 10-40) => hier gibt es gar keine andere Wahl, als zuerst den "+"-Teilbaum auszuwerten.

Ich bin aber z.B. der Meinung das es sinn macht erst den rechten Teilbaum auszuwerten weil man dann spaeter eventuell direkt eine "Register = Register OP Memory" verwenden kann

Siehe oben, genau das passiert hier auch ;) Allerdings tritt dieser Fall beim Sethi-Ullman-Algorithmus eben nur dann auf, wenn mehr Register benötigt werden als zur Verfügung stehen.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen