Ershovovo číslo - Ershov Number

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Ershovovo číslo“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Dubna 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Ershovova čísla jsou používány v optimalizace kódu minimalizovat množství přidělení registrů. Ershovova čísla lze v metodách použít k optimálnímu výběru registrů, když je v bloku kódu pouze jeden výraz. Vzhledem k výrazu E = E₁ op E₂ cílem je vygenerovat kód tak, aby buď minimalizoval počet použitých registrů, nebo, pokud je k dispozici nedostatečný počet registrů, minimalizoval počet požadovaných neregistrovaných dočasných položek.

Ershovovo číslo n daného uzlu strom výrazů je definována takto:

1. Každý list má n = 1.
2. U uzlu s jedním dítětem n je stejný jako dětský.
3. U uzlu se dvěma dětmi n je definován jako:

${ displaystyle n = { begin {cases} max (dítě_ {1}, dítě_ {2}) & dítě_ {1} neq dítě_ {2} dítě_ {1} + 1 & dítě_ {1} = dítě_ {2} konec {případů}}}$

Ershovovo číslo a uzel představuje minimální počet registrů potřebných k vyhodnocení podvýrazu, jehož kořenem je tento uzel. Myšlenka je, že nejprve vyhodnotíme dítě s větším Ershovovým číslem, potom druhé dítě a poté provedeme operaci v kořenu.

Příklad

Předpokládejme, že máme strom výrazů s operací '+' v kořenovém adresáři a vlevo a vpravo podstromy mají Ershovova čísla 3, respektive 4. Ershovovo číslo tohoto uzlu je 4, takže bychom měli být schopni generovat kód pro výraz pomocí 4 registrů.

1. Vygenerujte kód k vyhodnocení správného dítěte pomocí registrů r1, r2, r3 a r4. Výsledek umístěte do r1.
2. Generujte kód pro vyhodnocení levého dítěte pomocí registrů r2, r3 a r4. Výsledek umístěte do r2.
3. Vydejte instrukci „PŘIDAT r1, r2, r1“.

Pokud není k dispozici dostatek registrů?

Pokud je číslo Ershov kořene stromu výrazu větší než počet registrů, lze čísla Ershov použít ke generování kódu pomocí minimálního počtu načtení a uložení, a to následovně:

1. generovat kód pro dítě s větším Ershovovým číslem
2. vydat pokyn k dočasnému uložení výsledku
3. generovat kód pro dítě s menším Ershovovým číslem
4. vydat pokyn k načtení dočasného do registru
5. vydat pokyn k provedení operace v kořenovém adresáři

Viz také

• Strahlerovo číslo, minimální počet registrů potřebných k vyhodnocení výrazu bez jakéhokoli externího úložiště
• Sethi – Ullmanův algoritmus, v podstatě stejný koncept

externí odkazy

• Stránka Carleton University o generování optimálního kódu a používání čísel Ershov