Algorytm Sethi-Ullmana: Różnice pomiędzy wersjami

Usunięta treść Dodana treść
Nie podano opisu zmian
(Brak różnic)

Wersja z 22:46, 24 maj 2003

Algorytm Sethi-Ullmana to algorytm konwersji drzewa na taki szereg prostych instrukcji w którym zostanie użyta minimalna liczba rejestrów (lub zmiennych tymczasowych jeśli rejestry się wyczerpią).

Jest to bardzo ważne, ponieważ większość współczesnych komputerów ma relatywnie niewielką ilość rejestrów

Przykład problemu

Kod:

x = a + (b + (c + (d + x)))

Można przekształcić zgodnie z zasadą "wyliczaj najpierw lewą stronę" na:

t1 = a
t2 = b
t3 = c
t4 = d + x
t3 = t1 + t4
t2 = t2 + t3
t1 = t1 + t2
x = t1

Lub też zgodnie z zasadą "wyliczaj najpierw prawą stronę" na:

t1 = d + x
t1 = c + t1
t1 = b + t1
t1 = a + t1
x = t1

Dla tego wyrażenia korzystniejsza jest ta druga postać.

Algorytm

Algorytm Sethi-Ullmana pozwala nam zawsze znaleźć optymalną postać. Krok pierwszy polega na wyliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do wyliczenia poddrzewa:

  • każdy liść otrzymuje wartość 0
  • jeśli węzeł ma 2 podwęzły o różnych wartościach, otrzymuje wartość większego z nich
  • jeśli węzeł ma 2 podwęzły o takich samych wartościach, otrzymuje tą wartość plus 1

Takie ponumerowanie da nam dla przykładowego wyrażenia:

x = a + (b + (c + (d + x)))
    0    0    0    0   0
                  [  1  ]
             [     1     ]
        [        1        ]
   [           1           ]

Teraz generujemy kod w następujący sposób:

  • Jeśli mają taki sam numer:
    • Generujemy kod dla jednego poddrzewa
    • Alokujemy dodatkowy rejestr do którego wstawiamy rezultat dotychczasowych obliczeń
    • Generujemy kod dla drugiego poddrzewa
    • Scalamy wynik
  • W przeciwnym razie:
    • Generujemy kod dla poddrzewa o większym numerze
    • Wykorzystujemy jeden z rejestrów które zaalokowaliśmy na potrzeby wyliczania pierwszego poddrzewa.
    • Generujemy kod dla drugiego poddrzewa
    • Scalamy wynik

Algorytm ten ustali "optymalną" kolejność wykonywania obliczeń. Oczywiście w praktyce możliwe są inne optymalizacje - możemy przekształcić drzewo korzystając z praw łączności i przemienności działań, wyliczyć w trakcie kompilacji stałe części drzewa, oddzielić wyliczanie wspólnych podwyrażeń itd.