Sethi-Ullmann-Algorithmus, Auswertungsreihenfolge

Aufgabe 10.3: Optimale Registerverw. für Ausdrucksbäume, Sethi-Ullmann-Algorithmus: Lösung

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

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?


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–Ullman_algorithm


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.


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.

Siehe oben, genau das passiert hier auch :wink: Allerdings tritt dieser Fall beim Sethi-Ullman-Algorithmus eben nur dann auf, wenn mehr Register benötigt werden als zur Verfügung stehen.

1 Like