Algorytm Sethi-Ullmana

Z Wikipedii

Algorytm Sethi-Ullmana – 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.

Jego autorami są Ravi Sethi oraz Jeffrey Ullman (stąd nazwa).

[edytuj] 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 = t3 + 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ć.

[edytuj] 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.