Netværk-Ullman algoritme

Netværk-Ullman algoritme
Opkaldt efter	Ravi Sethi [d] ogJeffrey Ullman
formål	søge efter den optimale oversættelsesrækkefølge for et udtryk
Datastruktur	kurve

Network-Ullman- algoritmen er en algoritme til at oversætte abstrakte syntakstræer til maskinkode, der bruger så få registre som muligt . Algoritmen er opkaldt efter dens udviklere Ravi Seti og Jeffrey Ullman ,

Oversigt

Når der genereres kode til aritmetiske udtryk , skal compileren beslutte, hvilken der er den bedste måde at oversætte udtrykket på i forhold til antallet af brugte instruktioner, samt antallet af registre, der er nødvendige for at evaluere et bestemt undertræ. Især i det tilfælde, hvor antallet af frie registre er lille, kan rækkefølgen af eksekvering være vigtig for længden af den genererede kode, da en anden evalueringsrækkefølge kan resultere i mere eller mindre mellemværdier, der bliver smidt ud i hukommelsen og derefter genoprettet. Network-Ullman-algoritmen (også kendt som Network-Ullmann-nummerering ) har den egenskab, at den producerer kode, der kræver det mindste antal instruktioner såvel som det mindste antal hukommelsesreferencer (forudsat at operationerne i det mindste er kommutative og associative , men distributiv lov , dvs. ikke udføres). Bemærk, at algoritmen lykkes, selvom hverken kommutativitet eller associativitet finder sted i udtrykket, og derfor kan aritmetiske transformationer ikke anvendes. Algoritmen bruger heller ikke almindelig detektering af underudtryk eller eksplicit brug af generelle rettede acykliske grafer i stedet for træer. $a*b+a*c=a*(b+c)$

En simpel Net-Ullman-algoritme

Simple Network-Ullmann-algoritmen fungerer som følger (for load/store -arkitekturen ):

At krydse det abstrakte syntakstræ frem eller tilbage
1. Vi tildeler 1 til enhver ikke-konstant bladknude (det vil sige, vi har brug for 1 register for at gemme en variabel / felt / osv.). Ethvert konstant ark (højre side af operationen - bogstaver, værdier) vil blive tildelt 0.
2. Enhver ikke-bladsknude n tildeles det antal registre, der er nødvendige for at beregne det tilsvarende undertræ n . Hvis antallet af nødvendige registre i det venstre undertræ ( l ) ikke er lig med antallet af nødvendige registre i det højre undertræ ( r ), er antallet af nødvendige registre i det aktuelle knudepunkt n max(l, r). Hvis l == r , så er antallet af registre, der kræves for den aktuelle node . $r+1$
Kodegenerering
1. Hvis antallet af registre, der er nødvendigt for at beregne det venstre undertræ af node n , er større end antallet af registre for det højre undertræ, så beregnes det venstre undertræ først (fordi der kan kræves et ekstra register for at gemme resultatet af det højre undertræ, overlejret af registret i det venstre undertræ). Hvis det højre undertræ kræver flere registre end det venstre, så evalueres det højre træ først. Hvis begge undertræer kræver et lige stort antal registre, betyder rækkefølgen af udførelsen ikke noget.

Eksempel

For et aritmetisk udtryk ser det abstrakte syntakstræ således ud: $a=(b+c+f*g)*(d+3)$

= / \ en* / \ / \ ++ /\/\ /\d3 + * /\/\ bcfg

For at udføre algoritmen skal vi kun tjekke det aritmetiske udtryk , dvs. vi behøver kun at se på det højre undertræ af '=' destinationen: $(b+c+f*g)*(d+3)$

* / \ / \ ++ /\/\ /\d3 + * /\/\ bcfg

Vi starter nu trævandringen ved at tildele antallet af registre, der skal til for at evaluere hvert undertræ (bemærk, at det sidste led i udtrykket er en konstant): $(b+c+f*g)*(d+3)$

* 2 / \ / \ + 2 + 1 /\/\ / \ d 1 3 0 + 1 * 1 /\/\ b 1 c 0 f 1 g 0

Fra dette træ kan du se, at vi har brug for 2 registre for at beregne det venstre undertræ af '*', men kun behøver et register for at beregne det højre undertræ. Noderne 'c' og 'g' behøver ikke registre af følgende årsager: Hvis T er et blad af træet, så er antallet af registre til at evaluere T enten 1 eller 0 afhængigt af om T er i venstre eller højre undertræ (fordi operationer som f.eks. tilføje R1, A kan behandle den rigtige komponent af A direkte uden at registrere den). Derfor bør vi starte med at udføre det venstre undertræ, da vi kan ende med en situation, hvor vi kun har to registre til at evaluere hele udtrykket. Hvis vi først beregner det højre undertræ (som kun kræver et register), skal vi gemme resultatet af det højre undertræ, mens vi beregner det venstre undertræ (som stadig har brug for 2 registre), så 3 registre er nødvendige. Evalueringen af det venstre undertræ kræver to registre, men resultatet kan gemmes i ét register, og da det højre undertræ kræver et register for at evaluere, kan udtrykket evalueres med kun to registre.

Forbedret Net-Ullman-algoritme

I en forbedret version af Network-Ullman-algoritmen konverteres aritmetiske udtryk først ved hjælp af de aritmetiske egenskaber for de anvendte operatorer.

Se også

Strahler-Philosopher number, det mindste antal registre, der kræves for at udføre et udtryk uden at bruge ekstern hukommelse.
Ershov- nummeret er i det væsentlige det samme koncept som Strahler-nummeret.

Noter

Litteratur

Ravi Sethi, Jeffrey D. Ullman . Genereringen af optimal kode for aritmetiske udtryk // Journal of the Association for Computing Machinery . - 1970. - T. 17 , no. 4 . — S. 715–728 . - doi : 10.1145/321607.321620 .