Network-Ullman-algoritmi

Network-Ullman-algoritmi
Nimetty	Ravi Sethi [d] jaJeffrey Ullman
tarkoitus	etsi lausekkeen optimaalinen käännösjärjestys
Tietorakenne	kaavio

Network-Ullman- algoritmi on algoritmi abstraktien syntaksipuiden kääntämiseksi konekoodiksi , joka käyttää mahdollisimman vähän rekistereitä . Algoritmi on nimetty kehittäjiensä Ravi Seti ja Jeffrey Ullmanin mukaan.

Yleiskatsaus

Luodessaan koodia aritmeettisille lausekkeille kääntäjän on päätettävä, mikä on paras tapa kääntää lauseke käytettyjen käskyjen sekä tietyn alipuun arvioimiseen tarvittavien rekisterien lukumäärän suhteen. Varsinkin jos vapaita rekistereitä on vähän, suoritusjärjestys voi olla tärkeä generoidun koodin pituuden kannalta, koska erilainen arviointijärjestys voi johtaa enemmän tai vähemmän väliarvoihin, jotka häätyvät muistiin ja sitten palautettu. Network-Ullman-algoritmilla (tunnetaan myös nimellä Network-Ullmann-numerointi ) on ominaisuus tuottaa koodia, joka vaatii vähimmäismäärän käskyjä sekä vähimmäismäärän muistiviittauksia (olettaen, että ainakin operaatiot ovat kommutatiivisia ja assosiatiivisia , mutta jakelulakia , eli sitä ei noudateta). Huomaa, että algoritmi onnistuu, vaikka lausekkeessa ei olisi kommutatiivisuutta eikä assosiaatiota , joten aritmeettisia muunnoksia ei voida soveltaa. Algoritmi ei myöskään käytä yleistä osalausekkeen ilmaisua tai yleisten suunnattujen asyklisten graafien käyttöä puiden sijasta. ${\näyttötyyli a*b+a*c=a*(b+c)}$

Yksinkertainen Net-Ullman-algoritmi

Yksinkertainen verkko-Ullmann-algoritmi toimii seuraavasti ( lataus/tallennus arkkitehtuurille ):

Abstraktin syntaksipuun läpikulku eteen- tai taaksepäin
1. Annamme 1:n mille tahansa ei-vakiolle lehtisolmulle (eli tarvitsemme 1 rekisterin tallentaaksemme muuttujan / kentän / jne.). Kaikille vakiosivuille (operaation oikealle puolelle - literaalit, arvot) annetaan 0.
2. Kaikille ei-lehtisolmuille n määrätään tarvittava määrä rekistereitä vastaavan alipuun n laskemiseen . Jos vasemmassa alipuussa ( l ) tarvittavien rekistereiden lukumäärä ei ole yhtä suuri kuin oikean alipuun ( r ) tarvittavien rekisterien lukumäärä, nykyisessä solmussa n tarvittavien rekistereiden lukumäärä on max(l, r). Jos l == r , niin nykyiselle solmulle vaadittavien rekisterien lukumäärä on . $r+1$
Koodin luominen
1. Jos solmun n vasemman alipuun laskemiseen tarvittavien rekisterien määrä on suurempi kuin oikean alipuun rekisterien lukumäärä, lasketaan ensin vasen alipuu (koska yhden ylimääräisen rekisterin tallentamiseen voidaan tarvita oikean alipuun tulos, vasemman alipuun rekisterin päällä) . Jos oikea alipuu vaatii enemmän rekistereitä kuin vasen, oikea puu arvioidaan ensin. Jos molemmat alipuut vaativat saman määrän rekistereitä, suoritusjärjestyksellä ei ole väliä.

Esimerkki

Aritmeettisen lausekkeen abstrakti syntaksipuu näyttää tältä: $a=(b+c+f*g)*(d+3)$

= / \ a* / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfg

Algoritmin suorittamiseksi meidän tarvitsee vain tarkistaa aritmeettinen lauseke ts. meidän tarvitsee vain tarkastella '='-kohteen oikeaa alipuuta: ${\näyttötyyli (b+c+f*g)*(d+3)}$

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

Aloitamme nyt puukävelyn määrittämällä kunkin alipuun arvioimiseen tarvittavan määrän rekistereitä (huomaa, että lausekkeen viimeinen termi on vakio): ${\näyttötyyli (b+c+f*g)*(d+3)}$

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

Tästä puusta näet, että tarvitsemme 2 rekisteriä '*':n vasemman alipuun laskemiseen, mutta tarvitsemme vain yhden rekisterin oikean alipuun laskemiseen. Solmut 'c' ja 'g' eivät tarvitse rekistereitä seuraavista syistä: Jos T on puun lehti, T arvioitavien rekisterien määrä on joko 1 tai 0 riippuen siitä, onko T vasemmassa vai oikeassa alipuussa. (koska toiminnot, kuten lisääminen R1, A, voivat käsitellä A:n oikean komponentin suoraan ilman rekisteröintiä). Siksi meidän pitäisi aloittaa suorittamalla vasen alipuu, koska voimme päätyä tilanteeseen, jossa meillä on vain kaksi rekisteriä arvioimaan koko lauseke. Jos laskemme ensin oikean alipuun (joka vaatii vain yhden rekisterin), meidän olisi tallennettava oikean alipuun tulos samalla kun lasketaan vasenta alipuuta (joka vaatii edelleen 2 rekisteriä), joten tarvitaan 3 rekisteriä. Vasemman alipuun arviointi vaatii kaksi rekisteriä, mutta tulos voidaan tallentaa yhteen rekisteriin, ja koska oikean alipuun arviointi vaatii yhden rekisterin, lauseke voidaan arvioida vain kahdella rekisterillä.

Parannettu Net-Ullman-algoritmi

Network-Ullman-algoritmin parannetussa versiossa aritmeettiset lausekkeet muunnetaan ensin käytettävien operaattoreiden aritmeettisten ominaisuuksien avulla.

Katso myös

Strahler-Filosofin numero, vähimmäismäärä rekistereitä, jotka vaaditaan lausekkeen suorittamiseen ilman ulkoista muistia.
Ershov -luku on pohjimmiltaan sama käsite kuin Strahler-numero.

Muistiinpanot

Kirjallisuus

Ravi Sethi, Jeffrey D. Ullman . Optimaalisen koodin luominen aritmeettisille lausekkeille // Journal of the Association for Computing Machinery . - 1970. - T. 17 , no. 4 . — S. 715–728 . - doi : 10.1145/321607.321620 .

Linkit

Code Generation for Trees Arkistoitu 17. heinäkuuta 2012 Wayback Machinessa