Stohovací stroj - Stack machine

Pro stohovací stroje v teorii automatů viz Pushdown automat .

V informatice , výpočetní techniky a programování implementací jazyka , je zásobníkový počítač je procesor počítače nebo virtuální stroj , ve kterém je primární interakce pohybuje krátkotrvajícím dočasné hodnoty az stlačit stohu . V případě hardwarového procesoru se používá hardwarový zásobník . Použití zásobníku výrazně snižuje požadovaný počet registrů procesoru . Stohovací stroje rozšiřují push-down automat o další operace nakládání/ukládání nebo více stohů, a proto jsou Turing-Complete .

Design

Většina nebo všechny pokyny ke stroji zásobníku předpokládají, že operandy budou ze zásobníku a výsledky budou umístěny do zásobníku. Zásobník snadno pojme více než dva vstupy nebo více než jeden výsledek, takže lze vypočítat bohatou sadu operací. Ve strojovém kódu zásobníku (někdy nazývaném p-kód ) budou mít instrukce často pouze operační kód, který řídí operaci, bez dalších polí identifikujících konstantní, registrovou nebo paměťovou buňku, známou jako formát nulové adresy . To značně zjednodušuje dekódování instrukcí. Větve, načítání immediátů a instrukce načítání/ukládání vyžadují pole argumentů, ale stohovací stroje často zařizují, že jejich časté případy stále zapadají společně s operačním kódem do kompaktní skupiny bitů. Výběr operandů z předchozích výsledků se provádí implicitně objednáním pokynů. Některé sady strojních instrukcí jsou určeny pro interpretační provádění virtuálního počítače, nikoli přímo pro řízení hardwaru.

Celočíselné konstantní operandy jsou tlačeny Pushnebo Load Immediateinstrukcemi. Do paměti se často přistupuje samostatně Loadnebo pomocí Storepokynů obsahujících adresu paměti nebo vypočítáním adresy z hodnot v zásobníku. Všechny praktické stohovací stroje mají varianty operačních kódů load -store pro přístup k lokálním proměnným a formálním parametrům bez explicitních výpočtů adres. To může být pomocí offsetů od aktuální adresy top-of-stack, nebo offsets od stabilního registru frame-base.

Sada instrukcí provádí většinu akcí ALU s operacemi postfix ( reverzní polská notace ), které fungují pouze na zásobníku výrazů, nikoli na datových registrech nebo hlavních paměťových buňkách. To může být velmi výhodné pro spouštění jazyků na vysoké úrovni, protože většina aritmetických výrazů může být snadno přeložena do postfixové notace.

Strom binární syntaxe pro výraz A *( B - C ) + ( D + E )

Zvažte například výraz A * ( B - C ) + ( D + E ), psaný opačným polským zápisem jako A B C - * D E + +. Kompilace a spuštění na jednoduchém imaginárním zásobníku by mělo formu: 

                 # stack contents (leftmost = top = most recent):
 push A          #           A
 push B          #     B     A
 push C          # C   B     A
 subtract        #     B-C   A
 multiply        #           A*(B-C)
 push D          #     D     A*(B-C)
 push E          # E   D     A*(B-C)
 add             #     D+E   A*(B-C)
 add             #           A*(B-C)+(D+E)

Aritmetické operace „odečíst“, „znásobit“ a „přidat“ působí na dva nejvyšší operandy zásobníku. Počítač převezme oba operandy z nejvyšších (nejnovějších) hodnot zásobníku. Počítač nahradí tyto dvě hodnoty vypočteným rozdílem, součtem nebo součinem. Jinými slovy operandy instrukce jsou „vyskočeny“ ze zásobníku a jejich výsledky jsou poté „zasunuty“ zpět do zásobníku, připraveny na další instrukci.

Stohovací stroje mohou mít svůj zásobník výrazů a zásobník zpětného volání oddělené nebo jako jednu integrovanou strukturu. Pokud jsou odděleny, pokyny zásobníku stroje lze pipeline s menším počtem interakcí a menší složitost konstrukce, takže to bude obvykle běží rychleji.

Optimalizace kompilovaného kódu zásobníku je docela možná. Ukázalo se, že back-end optimalizace výstupu kompilátoru výrazně zlepšuje kód a potenciálně výkon, zatímco globální optimalizace v samotném kompilátoru přináší další zisky.

Úložiště zásobníku

Některé stohovací stroje mají stoh omezené velikosti, implementovaný jako soubor registru. ALU k tomu bude mít přístup pomocí indexu. Velký registrový soubor používá mnoho tranzistorů, a proto je tato metoda vhodná pouze pro malé systémy. Několik počítačů má zásobník výrazů v paměti i samostatný zásobník registrů. V takovém případě může software nebo přerušení přesouvat data mezi nimi. Některé stroje mají hromádku neomezené velikosti, implementovanou jako pole v RAM, které je ukládáno do mezipaměti nějakým počtem adresních registrů „top of stack“, aby se omezil přístup do paměti. Kromě výslovných pokynů „načíst z paměti“ je pořadí použití operandů totožné s pořadím operandů v datovém zásobníku, takže vynikající předběžné načítání lze snadno provést.

Zvažte X+1. Kompiluje do Load X; Load 1; Add. U zásobníku uloženého zcela v RAM to implicitně zapisuje a čte zásobník v paměti:

  • Načtěte X, zatlačte do paměti
  • Načtěte 1, zatlačte do paměti
  • Popadněte 2 hodnoty z paměti, přidejte je a vložte výsledek do paměti

celkem 5 odkazů na mezipaměť dat.

Dalším krokem je stohovací stroj nebo tlumočník s jediným registrem top-of-stack. Výše uvedený kód pak provede:

  • Načíst X do prázdného registru TOS (pokud je to hardwarový stroj) nebo Push TOS registr do paměti, načíst X do registru TOS (pokud je interpret)
  • Zatlačte registr TOS do paměti, načtěte 1 do registru TOS
  • Vyhoďte levý operand z paměti, přidejte do registru TOS a nechte ho tam

pro celkem 5 odkazů na mezipaměť dat, nejhorší případ. Tlumočníci obecně nesledují prázdnotu, protože nemusí-cokoli pod ukazatelem zásobníku je neprázdná hodnota a registr mezipaměti TOS je vždy udržován v chodu. Typické tlumočníky Java však tímto způsobem nevyrovnávají horní část zásobníku, protože program a zásobník obsahují kombinaci krátkých a širokých hodnot dat.

Pokud má stroj s pevným připojením 2 nebo více registrů nejvyšší úrovně nebo soubor registru, pak je v tomto příkladu zabráněn veškerý přístup do paměti a existuje pouze 1 cyklus mezipaměti dat.

Historie a implementace

Popis takové metody, která vyžaduje, aby byly v registrech uchovávány pouze dvě hodnoty současně, s omezenou sadou předdefinovaných operandů, které bylo možné rozšířit definicí dalších operandů, funkcí a podprogramů, poprvé poskytl na konferenci Robert S. Barton v roce 1961.

Komerční stohovací stroje

Viz také: Architektura počítače na vysoké úrovni jazyka

Mezi příklady sad instrukcí zásobníku přímo provedených v hardwaru patří

  • Architektura F18A 144procesorového čipu GA144 od GreenArrays, Inc.
  • Z4 počítač od Konrad Zuse .
  • Burroughs velké systémy architektury (od roku 1961)
  • Xerox Dandelion představen 27.dubna 1981, využil zásobníku architekturu stroj pro úsporu paměti.
  • English Electric KDF9 stroj. KDF9, který byl poprvé dodán v roce 1964, měl 19-ti hloubkový zásobník aritmetických registrů a 17-hluboký zásobník pro podprogramové návratové adresy
  • Collins Radio Collins Adaptive Processing System minipočítač (CAPS, od roku 1969) a Rockwell Collins Advanced Architecture Mikroprocesor (AAMP od roku 1981).
  • UCSD Pascal p-stroj (jako Pascal MicroEngine a mnoho dalších) podporoval kompletní programovací prostředí studenta na počátku 8-bitových mikroprocesorů se špatnými instrukční sady a malou RAM, kompilací do virtuálního zásobníku stroje.
  • Řady MU5 a ICL 2900 . Hybridní stohovací a akumulátorové stroje. Registr akumulátoru ukládal do vyrovnávací paměti nejvyšší datovou hodnotu zásobníku paměti. Varianty zaváděcích a ukládacích operačních kódů kontrolovaných, když byl tento registr přelit do zásobníku paměti nebo odtud znovu načten.
  • HP 3000 (klasický, nikoli PA-RISC)
  • Tandemové počítače T/16. Podobně jako HP 3000, kromě toho, že kompilátory, nikoli mikrokódy, ovládaly, když se zásobník registrů vysypal do zásobníku paměti nebo byl znovu naplněn ze zásobníku paměti.
  • Atmel MARC4 mikrořadič
  • Několik „Forth čipů“, jako RTX2000, RTX2010 , F21 a PSC1000
  • Počítač Setun Ternary provedl vyvážený ternár pomocí zásobníku.
  • Procesor 4stack od Bernda Paysana má čtyři zásobníky.
  • Stohovací stroj Patriot Scientific Ignite navržený Charlesem H. Moorem má přední měřítko funkční hustoty .
  • Mikroprocesor tvrzený radiací Saab Ericsson Space Thor
  • Inmos transputerech .
  • ZPU Fyzicky malý procesor určený k dohledu nad systémy FPGA .
  • Některé technické ruční kalkulačky používají v rozhraní klávesnice místo polských závorek reverzní polskou notaci. Toto je forma stohovacího stroje. Klíč Plus spoléhá na to, že jeho dva operandy jsou již na správných nejvyšších pozicích zásobníku viditelného uživatelem.

Virtuální stohovací stroje

Příklady virtuálních stohovacích strojů interpretovaných v softwaru:

Hybridní stroje

(Ty by neměly být zaměňovány s hybridními počítači, které kombinují digitální i analogové funkce, např. Jinak digitální počítač, který přistupuje k řešení analogového násobení nebo řešení diferenciálních rovnic mapováním paměti a převodem do a ze vstupů a výstupů analogového zařízení.)

Čistě stohovací stroje jsou docela neefektivní pro procedury, které přistupují k více polím ze stejného objektu. Strojový kód zásobníku musí znovu načíst ukazatel objektu pro každý výpočet+výpočet offsetu. Běžnou opravou je přidání některých funkcí registračního stroje do zásobníku: viditelný soubor registru vyhrazený pro uchovávání adres a pokyny ve stylu registru pro provádění načítání a jednoduché výpočty adres. Je neobvyklé, že registry mají zcela obecný účel, protože pak neexistuje žádný pádný důvod mít instrukční zásobník a pokyny pro postfix.

Dalším běžným hybridem je začít s architekturou registračního stroje a přidat další režim adresy paměti, který emuluje operace push nebo pop stohovacích strojů: 'memaddress = reg; reg += instr.displ '. Tento byl poprvé použit v DEC je PDP-11 minipočítač. Tato funkce byla přenesena do počítačů VAX a do mikroprocesorů Motorola 6800 a M68000 . To umožnilo použití jednodušších metod zásobníku v raných kompilátorech. Efektivně také podporoval virtuální stroje pomocí interpretů zásobníků nebo závitového kódu . Tato funkce však nepomohla tomu, aby se vlastní kód registračního stroje stal tak kompaktním jako čistý strojový kód zásobníku. Rychlost provádění byla také menší než při dobrém překladu do architektury registru. Rychlejší je změnit ukazatel top-of-stack pouze příležitostně (jednou za hovor nebo návrat), než ho neustále šlapat nahoru a dolů v každém příkazu programu, a ještě rychlejší je zcela se vyhnout odkazům na paměť.

V poslední době takzvané zásobníkové stroje druhé generace přijaly vyhrazenou sbírku registrů, které mají sloužit jako registry adres, čímž odkládají úlohu adresování paměti z datového zásobníku. Například MuP21 spoléhá na registr s názvem „A“, zatímco novější procesory GreenArrays se spoléhají na dva registry: A a B.

Rodina mikroprocesorů Intel x86 má pro většinu operací sadu instrukcí ve stylu registru (akumulátoru), ale používá instrukce zásobníku pro svou x87 , aritmetiku s pohyblivou řádovou čárkou Intel 8087 , sahající až ke koprocesoru iAPX87 (8087) pro 8086 a 8088. To to znamená, že neexistují žádné registry s pohyblivou řádovou čárkou přístupné pro programátory, ale pouze 80bitový široký a 8 hluboký zásobník. Asistence při provádění operací x87 do značné míry závisí na procesoru x86.

Počítače využívající zásobníky hovorů a rámce zásobníků

Většina současných počítačů (jakéhokoli stylu sady instrukcí) a většina kompilátorů používá v paměti velký zásobník návratů hovorů k organizaci krátkodobých lokálních proměnných a návratových odkazů pro všechny aktuálně aktivní procedury nebo funkce. Každé vnořené volání vytvoří v paměti nový rámeček zásobníku , který přetrvává, dokud se toto volání nedokončí. Tento zásobník zpětného volání může být zcela spravován hardwarem prostřednictvím specializovaných registrů adres a speciálních režimů adres v pokynech. Nebo to může být pouze sada konvencí, za nimiž následují kompilátory, využívající generické registry a režimy registr+offsetová adresa. Nebo to může být něco mezi tím.

Vzhledem k tomu, že tato technika je nyní téměř univerzální, dokonce i na registračních počítačích, není užitečné označovat všechny tyto stroje jako stohovací stroje. Tento termín je běžně vyhrazen pro počítače, které také používají k vyhodnocení částí jednoho příkazu zásobník výrazů a aritmetické pokyny pouze pro zásobník.

Počítače běžně poskytují přímý a efektivní přístup ke globálním proměnným programu a k lokálním proměnným pouze aktuální nejvnitřnější procedury nebo funkce, nejvyššího rámce zásobníku. „Up level“ adresování obsahu rámců zásobníku volajících obvykle není potřeba a není podporováno přímo hardwarem. V případě potřeby to kompilátory podporují předáváním ukazatelů rámců jako dalších skrytých parametrů.

Některé stohovací stroje Burroughs podporují up-level refs přímo v hardwaru, se specializovanými režimy adres a speciálním registrovým souborem 'display', který obsahuje adresy rámců všech vnějších rozsahů. Žádné další počítačové linky to v hardwaru neudělaly. Když Niklaus Wirth vyvinul první kompilátor Pascal pro CDC 6000 , zjistil, že je celkově rychlejší předávat ukazatele rámců jako řetězec, než neustále aktualizovat kompletní pole ukazatelů rámců. Tato softwarová metoda také nepřináší žádnou režii pro běžné jazyky, jako je C, kterým chybí doporučení na vyšší úrovni.

Stejné stroje Burroughs také podporovaly vnořování úkolů nebo vláken. Úkol a jeho tvůrce sdílejí rámce zásobníků, které existovaly v době vytvoření úkolu, ale nikoli následující rámce tvůrce ani vlastní rámce úkolu. To podpořil kaktusový stoh , jehož schéma rozložení připomínalo kufr a paže kaktusu Saguaro . Každý úkol měl svůj vlastní segment paměti, který držel svůj zásobník a rámce, které vlastní. Základ tohoto zásobníku je spojen se středem zásobníku jeho tvůrce. V počítačích s konvenčním plochým adresním prostorem by zásobník tvůrců a zásobníky úkolů byly samostatné objekty haldy v jedné hromadě.

V některých programovacích jazycích nejsou datová prostředí vnějšího rozsahu vždy vnořena v čase. Tyto jazyky organizují své „aktivační záznamy“ procedury jako samostatné objekty haldy, nikoli jako rámce zásobníku připojené k lineárnímu zásobníku.

V jednoduchých jazycích, jako je Forth, které postrádají lokální proměnné a pojmenovávání parametrů, by rámce zásobníku neobsahovaly nic jiného než návratové adresy větví a režii správy rámců. Jejich návratový zásobník tedy obsahuje spíše holé návratové adresy než rámce. Návratový zásobník je oddělený od zásobníku hodnot dat, aby se zlepšil tok nastavení volání a návratů.

Porovnání s registračními stroji

Stohovací stroje jsou často srovnávány s registračními stroji , které uchovávají hodnoty v řadě registrů . Registrační stroje mohou v tomto poli ukládat struktury podobné hromadám, ale registrační stroj má pokyny, které obcházejí rozhraní zásobníku. Registrační stroje běžně překonávají stohovací stroje a stohovací stroje zůstaly v hardwarových systémech specializovaným hráčem. Ale stohovací stroje se často používají při implementaci virtuálních strojů kvůli jejich jednoduchosti a snadnosti implementace.

Instrukce

Stohovací stroje mají vyšší hustotu kódu . Na rozdíl od běžných instrukcí strojního zásobníku, které se snadno vejdou do 6 bitů nebo méně, vyžadují registrační stroje pro výběr operandů dvě nebo tři pole registračních čísel podle instrukce ALU; nejhustší registrační stroje v průměru asi 16 bitů na instrukci plus operandy. Registrační stroje také používají širší offsetové pole pro operační kódy pro ukládání dat. Kompaktní kód stohovacího stroje přirozeně pojme více instrukcí v mezipaměti, a proto by mohl dosáhnout lepší účinnosti mezipaměti , snížení nákladů na paměť nebo povolení rychlejších paměťových systémů za dané náklady. Navíc je většina instrukcí typu stack-machine velmi jednoduchá a je vytvořena pouze z jednoho pole operačního kódu nebo jednoho pole operandu. Stohovací stroje tedy vyžadují velmi málo elektronických zdrojů k dekódování každé instrukce.

Program musí provést více instrukcí, když je zkompilován do zásobníku, než když je zkompilován do počítače s registrem nebo z paměti do paměti. Každá proměnná zátěž nebo konstanta vyžaduje svou vlastní samostatnou instrukci Load, místo aby byla spojena do instrukce, která tuto hodnotu používá. Oddělené instrukce mohou být jednoduché a běží rychleji, ale celkový počet instrukcí je stále vyšší.

Většina tlumočníků registrů uvádí své registry podle čísla. K registrům hostitelského počítače však nelze přistupovat v indexovaném poli, takže pro virtuální registry je přiděleno paměťové pole. Proto instrukce tlumočníka registru musí používat paměť pro předávání generovaných dat do další instrukce. To nutí registry tlumočníků být mnohem pomalejší u mikroprocesorů vyrobených s pravidlem jemného procesu (tj. Rychlejší tranzistory bez zlepšení rychlosti obvodů, jako je Haswell x86). Ty vyžadují několik hodin pro přístup do paměti, ale pouze jedno pro přístup k registru. V případě zásobníku stroje s obvodem pro předávání dat místo souboru registru mohou tlumočníci zásobníku přidělit registry hostitelského počítače pro několik prvních operandů zásobníku namísto paměti hostitelského počítače

Ve stroji zásobníku jsou operandy použité v pokynech vždy na známém posunu (nastaveném v ukazateli zásobníku), z pevného umístění (spodní část zásobníku, který v hardwarovém provedení může být vždy na nulové pozici paměti), úspora drahocenného úložiště v mezipaměti nebo v CPU před použitím k uložení tak velkého počtu adres paměti nebo indexových čísel. To může zachovat takové registry a mezipaměť pro použití při neprotokolovém výpočtu.

Dočasné / místní hodnoty

Někteří v oboru se domnívají, že stohovací stroje provádějí více cyklů mezipaměti dat pro dočasné hodnoty a lokální proměnné než registrační stroje.

Na strojích typu stack se dočasné hodnoty často dostanou do paměti, zatímco na počítačích s mnoha registry tyto teploty obvykle zůstávají v registrech. (Tyto hodnoty je však často nutné přelít do „aktivačních rámců“ na konci definice procedury, základního bloku nebo přinejmenším do vyrovnávací paměti během zpracování přerušení). Hodnoty přenesené do paměti přidávají další cykly mezipaměti. Tento efekt rozlití závisí na počtu skrytých registrů použitých k ukládání hodnot top-of-stack do vyrovnávací paměti, na frekvenci volání vnořených procedur a na rychlosti zpracování přerušení hostitelského počítače.

Na registračních počítačích využívajících optimalizační kompilátory je velmi běžné, že nejpoužívanější lokální proměnné zůstávají spíše v registrech než v buňkách paměti rámců zásobníku. To eliminuje většinu cyklů mezipaměti dat pro čtení a zápis těchto hodnot. Vývoj „plánování zásobníku“ pro provádění analýzy živých proměnných, a tedy zachování klíčových proměnných v zásobníku po delší dobu, tomuto problému napomáhá.

Na druhou stranu registrační počítače musí přelévat mnoho svých registrů do paměti napříč vnořenými voláními procedur. Rozhodnutí o tom, který registr se má rozlít a kdy, se provádí staticky v době kompilace, nikoli na základě dynamické hloubky hovorů. To může vést k většímu provozu s mezipamětí dat než u pokročilé implementace zásobníku.

Běžné podvýrazy

V registračních strojích lze společný podvýraz (podvýraz, který se používá vícekrát se stejnou hodnotou výsledku) vyhodnotit pouze jednou a jeho výsledek uložit do rychlého registru. Následující opakovaná použití nemají čas ani náklady na kód, pouze odkaz na registr. Tato optimalizace urychluje jednoduché výrazy (například načítání proměnné X nebo ukazatel P) i méně obvyklé složité výrazy.

Naproti tomu u stohovacích strojů lze výsledky ukládat jedním ze dvou způsobů. Za prvé, výsledky lze ukládat pomocí dočasné proměnné do paměti. Ukládání a následné načítání stojí další pokyny a další cykly mezipaměti dat. Dělat to je jen výhra, pokud výpočet subexprese stojí více času než načítání z paměti, což je ve většině procesorů zásobníku téměř vždy. Jednoduché proměnné a načítání ukazatelů se nikdy nevyplatí, protože ty již mají stejné náklady na jeden cyklus mezipaměti dat na přístup. U výrazů jako je to jen okrajově X+1. Tyto jednodušší výrazy tvoří většinu nadbytečných, optimalizovatelných výrazů v programech napsaných v nekonkenativních jazycích. Optimalizující kompilátor může vyhrát pouze nadbytečnost, které se programátor ve zdrojovém kódu mohl vyhnout.

Druhý způsob ponechá vypočítanou hodnotu v datovém zásobníku a podle potřeby ji duplikuje. To používá operace ke kopírování položek zásobníku. Zásobník musí mít dostatečně malou hloubku pro dostupné pokyny ke kopírování CPU. Ručně psaný kód zásobníku často používá tento přístup a dosahuje rychlostí jako obecné registrační stroje. Algoritmy pro optimální „plánování zásobníku“ bohužel programovací jazyky příliš nepoužívají.

Potrubí

V moderních počítačích je doba načítání proměnné z mezipaměti dat často několikrát delší než doba potřebná pro základní operace ALU. Program běží rychleji bez zastavení, pokud lze načíst jeho paměť několik cyklů před instrukcí, která tuto proměnnou potřebuje. Složité stroje to dokážou s hlubokým potrubím a „spuštěním mimo pořadí“, které zkoumá a spouští mnoho instrukcí najednou. Registrační stroje to dokonce dokážou s mnohem jednodušším hardwarem „v pořadí“, mělkým potrubím a o něco chytřejšími kompilátory. Krok načtení se stane samostatnou instrukcí a tato instrukce je staticky naplánována mnohem dříve v sekvenci kódu. Kompilátor mezi tím umístí nezávislé kroky.

Plánování přístupů do paměti vyžaduje explicitní, náhradní registry. Na stohových počítačích to není možné, aniž byste některému aspektu mikroarchitektury vystavili programátora. Pro výraz AB -, B musí být vyhodnocen a tlačen bezprostředně před krokem mínus. Bez permutace zásobníku nebo vícevláknového zpracování hardwaru lze mezi čekání na dokončení načtení B vložit mezi ně relativně málo užitečného kódu. Stohovací stroje mohou obejít zpoždění paměti buď tím, že mají hluboký prováděcí kanál mimo objednávku pokrývající mnoho instrukcí najednou, nebo s větší pravděpodobností mohou permutovat zásobník tak, že mohou pracovat na jiném pracovním zatížení, zatímco se načítání dokončí, nebo může prokládat provádění různých programových vláken, jako v systému Unisys A9. Dnešní stále více paralelní výpočetní zátěž naznačuje, nicméně to nemusí být nevýhoda, kvůli které se v minulosti objevilo.

Stohovací stroje mohou vynechat fázi načítání operandů registračního stroje. Například v mikroprocesoru JOP ( Java Optimized Processor ) horní 2 operandy zásobníku přímo vstupují do obvodu pro předávání dat, který je rychlejší než soubor registru.

Provedení mimo objednávku

Tomasulo algoritmus nalezne na úrovni instrukcí paralelismus vydávání pokynů, jak budou k dispozici jejich data. Koncepčně se adresy pozic v zásobníku neliší od registrových rejstříků souboru registru. Toto zobrazení umožňuje , aby bylo provádění algoritmu Tomasulo mimo pořadí použito se stroji stacků.

Zdá se, že provádění mimo pořadí ve stohových strojích snižuje nebo se vyhýbá mnoha teoretickým a praktickým obtížím. Citovaný výzkum ukazuje, že takový stohovací stroj může využívat paralelismus na úrovni instrukcí a výsledný hardware musí ukládat data do mezipaměti pro pokyny. Takové stroje efektivně obcházejí většinu přístupů k paměti do zásobníku. Výsledkem je propustnost (instrukce za hodiny ) srovnatelná s registračními stroji RISC s mnohem vyšší hustotou kódu (protože adresy operandů jsou implicitní).

Jeden problém nastolený ve výzkumu spočíval v tom, že práce instrukce RISC registračního stroje vyžaduje přibližně 1,88 instrukce stohovacího stroje. Konkurenční stohovací stroje mimo pořadí proto ke sledování pokynů („výdejní stanice“) vyžadují zhruba dvakrát tolik elektronických zdrojů. To může být kompenzováno úsporami v mezipaměti instrukcí a v obvodech dekódování paměti a instrukcí.

Skryje uvnitř rychlejší stroj na registraci

Některé jednoduché stohovací stroje mají čipový design, který je plně přizpůsoben až na úroveň jednotlivých registrů. Horní část adresního registru zásobníku a N horní část datových vyrovnávacích pamětí zásobníku jsou postaveny ze samostatných jednotlivých obvodů registru se samostatnými sčítači a připojeními ad hoc.

Většina stohovacích strojů je však postavena z větších obvodových komponent, kde jsou N datové vyrovnávací paměti uloženy společně v souboru registru a sdílejí sběrnice čtení/zápisu. Dekódované instrukce zásobníku jsou mapovány do jedné nebo více sekvenčních akcí v tomto skrytém souboru registru. Zatížení a operace ALU působí na několika nejvyšších registrech a implicitní úniky a výplně působí na nejspodnějších registrech. Dekodér umožňuje kompaktní tok instrukcí. Pokud by ale stream kódu místo toho měl explicitní pole pro výběr registru, která přímo manipulovala se základním souborem registru, kompilátor by mohl lépe využít všechny registry a program by běžel rychleji.

Mikroprogramované stohovací stroje jsou toho příkladem. Vnitřní modul mikrokódu je nějaký registrační stroj podobný RISC nebo stroj podobný VLIW využívající více registračních souborů. Když je tento motor řízen přímo mikrokódem specifickým pro daný úkol, získá mnohem více práce za cyklus, než když je ovládán nepřímo ekvivalentním kódem zásobníku pro stejný úkol.

Dalším příkladem jsou překladače objektových kódů pro HP 3000 a Tandem T/16. Přeložili sekvence kódu zásobníku do ekvivalentních sekvencí kódu RISC. Drobné „lokální“ optimalizace odstranily velkou část režie architektury zásobníku. K vyloučení opakovaných výpočtů adres byly použity náhradní registry. Přeložený kód si stále zachoval spoustu emulačních režií z nesouladu mezi původními a cílovými počítači. Navzdory této zátěži se účinnost cyklu přeloženého kódu shodovala s účinností cyklu původního kódu zásobníku. A když byl zdrojový kód překompilován přímo do registračního stroje pomocí optimalizačních překladačů, účinnost se zdvojnásobila. To ukazuje, že architektura zásobníku a jeho neoptimalizující kompilátory ztrácely více než polovinu výkonu základního hardwaru.

Registrační soubory jsou dobré nástroje pro výpočet, protože mají velkou šířku pásma a velmi nízkou latenci ve srovnání s odkazy na paměť prostřednictvím datových mezipamětí. V jednoduchém stroji umožňuje soubor registru čtení dvou nezávislých registrů a zápis třetího, vše v jednom cyklu ALU s jednocyklem nebo menší latencí. Zatímco odpovídající mezipaměť dat může spustit pouze jedno čtení nebo jeden zápis (ne obojí) za cyklus a čtení má obvykle latenci dvou ALU cyklů. To je jedna třetina propustnosti při dvojnásobku zpoždění potrubí. Ve složitém stroji, jako je Athlon, který dokončí dvě nebo více instrukcí za cyklus, umožňuje soubor registru čtení čtyř nebo více nezávislých registrů a zápis dalších dvou, vše v jednom cyklu ALU s latencí jednoho cyklu. Zatímco odpovídající mezipaměť dat s dvěma porty může spustit pouze dvě čtení nebo zápisy za cyklus s více cykly latence. Opět je to jedna třetina propustnosti registrů. Vybudování mezipaměti s dalšími porty je velmi nákladné.

Vzhledem k tomu, že zásobník je součástí většiny softwarových programů, i když použitý software není striktně stohovací stroj, stroj s hardwarovým zásobníkem může více napodobovat vnitřní fungování svých programů. Registry procesorů mají vysoké tepelné náklady a stohovací stroj může požadovat vyšší energetickou účinnost.

Přerušení

Odpověď na přerušení zahrnuje uložení registrů do zásobníku a následné větvení na kód obsluhy přerušení. Stohovací stroje často reagují na přerušení rychleji, protože většina parametrů je již na zásobníku a není potřeba je tam tlačit. Některé registrační stroje to řeší tím, že mají více registračních souborů, které lze okamžitě prohodit, ale to zvyšuje náklady a zpomaluje soubor registru.

Tlumočníci

Tlumočníky pro virtuální stohovací stroje lze stavět snáze než tlumočníky pro registrační stroje; logika zpracování režimů adres paměti je pouze na jednom místě, než aby se opakovala v mnoha instrukcích. Stohovací stroje také mívají méně variací operačního kódu; jeden generalizovaný operační kód zvládne jak časté případy, tak nejasné rohové případy referencí paměti nebo nastavení volání funkcí. (Hustota kódu se však často zlepšuje přidáním krátkých a dlouhých formulářů pro stejnou operaci.)

Tlumočníci pro virtuální stohovací stroje jsou často pomalejší než tlumočníci pro jiné styly virtuálních strojů. Toto zpomalení je nejhorší, když běží na hostitelských počítačích s hlubokým prováděcím kanálem, jako jsou aktuální čipy x86.

U některých tlumočníků musí tlumočník provést skok N-way switch, aby dekódoval další operační kód a větev na jeho kroky pro konkrétní operační kód. Další metodou pro výběr operačních kódů je závitový kód . Mechanismy předběžného načtení hostitelského počítače nejsou schopny předpovědět a načíst cíl tohoto indexovaného nebo nepřímého skoku. Spouštěcí kanál hostitelského počítače se tedy musí restartovat pokaždé, když hostovaný interpret dekóduje jinou virtuální instrukci. K tomu dochází častěji u virtuálních zásobníků než u jiných stylů virtuálních počítačů.

Jedním z příkladů je programovací jazyk Java . Jeho kanonický virtuální stroj je určen jako 8bitový zásobník. Nicméně, Dalvik Virtual Machine for Java používá na Android smartphony je 16bitové virtuální registr stroj - výběr vyrobený z důvodů účinnosti. Aritmetické instrukce přímo načítají nebo ukládají lokální proměnné prostřednictvím 4bitových (nebo větších) instrukčních polí. Podobně verze 5.0 Lua nahradila svůj virtuální stack stroj rychlejším virtuálním registračním strojem.

Vzhledem k tomu, že se virtuální stroj Java stal populárním, používají mikroprocesory pokročilé prediktory větví pro nepřímé skoky. Tento postup zabrání většině restartů potrubí z N-way skoků a eliminuje většinu nákladů na počet instrukcí, které ovlivňují tlumočníky zásobníku.

Viz také

Reference

externí odkazy