Programovací jazyk Forth a zásobníkové procesory (14)

Obsah

1. Tři osy technologických vlastností zásobníkových procesorů
2. Jednozásob­níkové procesory
3. Vícezásobníkové procesory
4. Velikost zásobníku či zásobníků
5. Počet adresovatelných operandů v instrukcích
6. Příklady procesorů z jednotlivých kategorií
7. Obsah dalšího pokračování

1. Tři osy technologických vlastností zásobníkových procesorů

Pokud se podíváme na výčet možností různých typů procesorů, kterých je v dnešní době snad již několik tisíc, nezbude nám nic jiného než si procesory roztřídit do různých kategorií a posléze porovnávat jednotlivé kategorie mezi sebou. Z hlediska zásobníkových procesorů se používá třídění podle třech vlastností (toto třídění například používá i Philip Koopman):

1. počtu implementovaných zásobníků (jeden zásobník, nebo více zásobníků)
2. velikosti implementovaných zásobníků (tj. počtu uložitelných hodnot)
3. počtu explicitně adresovatelných operandů v instrukcích, které procesor ve strojovém kódu rozeznává (0, 1, nebo dva operandy)

Třídění podle třech vlastností má výhodu v tom, že jednotlivé vlastnosti lze jednoduše vynést na souřadné osy trojrozměrného diagramu, čímž vznikne dvanáct oblastí. Každý typ procesoru padá právě do jedné z těchto oblastí, bez ohledu na jeho další vlastnosti (rychlost, bitová šířka apod. zde nehrají žádnou roli). Zajímavé je, že každá z dvanácti oblastí je obsazená, to znamená, že každé pojetí zásobníkového procesoru může mít své výhody.

2. Jednozásobníkové procesory

Jednozásobníkové procesory obsahují, jak je patrné již z jejich pojmenování, pouze jeden zásobník. Tento zásobník může být použit pro více účelů – pro výpočty, pro předávání parametrů do volaných funkcí, pro úschovu návratových adres volaných funkcí či pro úschovu lokálních proměnných. Všechny uvedené operace se však na jednom zásobníku provádějí komplikovaným způsobem. Z tohoto důvodu se na zásobníku vytváří takzvaný zásobníkový rámec (stack frame), což je (při běhu programu) přesně definovaná oblast, se kterou se na zásobníku pracuje.

Nejpoužívanější imperativní programovací jazyky (například C, C++, Pascal) vytvářejí při běhu přeložených programů zásobníkový rámec následujícím způsobem (popis je značně zjednodušený a neobsahuje například popis rozdílů mezi volací konvencí C-čka a Pascalu; uvedený postup tvorby zásobníkového rámce je však přibližně stejný):

1. Nejprve se na zásobník uloží parametry volané funkce. Uložení parametrů na zásobník je výhodné, protože je možné použít rekurzi. Jazyky, u kterých se parametry předávají jiným způsobem (například přes registry), většinou rekurzi nepovolují – příkladem jsou starší verze Fortranu. Pořadí parametrů závisí na použitém programovacím jazyce a způsobu deklarace funkce (například C-čko má několik modifikátorů, kterými lze tzv. volací konvenci změnit).
2. Dále se provede skok do funkce, přičemž se použije instrukce typu call, která na zásobník automaticky uloží návratovou adresu z funkce. Tímto způsobem je zajištěn jak jednoduchý návrat z funkce, tak i možnost provedení rekurze.
3. Nyní dochází k uložení ukazatele na vrchol zásobníku (SP – Stack Pointer) do některého adresového registru, jehož původní obsah je rovněž uložen na zásobník (na procesorech Intel x86 je to většinou registr BP). Tento adresový registr bude ve funkci plnit úlohu jakéhosi středobodu při práci se zásobníkovým rámcem, protože bude na jednu stranu ukazovat na parametry právě prováděné funkce, na druhou stranu na lokální proměnné.
4. Lokální proměnné jsou vytvářeny taktéž na zásobníku. Vzhledem k tomu, že adresa ve vybraném adresovém registru je v době běhu celé funkce neměnná, má funkce přístup jak ke svým parametrům (se kterými je volána), tak i k lokálním proměnným. Naproti tomu se ukazatel na vrchol zásobníku samozřejmě mění, například při volání dalších funkcí.
5. Při návratu z funkce je obnoven ukazatel na vrchol zásobníku tak, aby ukazoval na návratovou adresu (ve skutečnosti může ukazovat na buňku ZA nebo PŘED návratovou adresou, to již závisí na typu použitého procesoru). Dále je obnoven vybraný adresový registr (například BP) a proveden návrat z funkce instrukcí typu ret. O „úklid“ parametrů funkce ze zásobníku se podle použitého programovacího jazyka stará buď volající funkce, nebo funkce volaná.

Jak je z výše uvedeného popisu práce se zásobníkovým rámcem patrné, je zásobník velmi intenzivně používán i v běžných imperativních jazycích. S tím samozřejmě počítají i výrobci procesorů (zejména procesorů typu CISC), protože se v instrukční sadě objevují instrukce jako enter, leave a ret n, které práci se zásobníkovým rámcem poněkud usnadňují. Také je umožněn přístup do libovolné paměťové buňky v zásobníkovém rámci přes adresování s offsetem – to je nutné zejména pro efektivní přístup k parametrům funkce a k lokálním proměnným.

3. Vícezásobníkové procesory

A key conceptual feature of stack machines is their uniformity of interface between high level code and machine instructions. Both procedure calls and opcodes use the stack as a means of passing data. This consistent interface has several positive impacts on software development.
Philip Koopman, Stack Computers: The New Wave

U vícezásobníkových procesorů je pro programátory k dispozici zásobníků více. Typicky to bývají zásobníky dva, kdy první je určen pro předávání parametrů a provádění výpočtů a druhý pro úschovu návratových adres volaných funkcí. Dvouzásobníkové procesory jsou často navrhovány tak, aby na nich bylo možné efektivně provozovat aplikace napsané v programovacím jazyce Forth. V čem však spočívá úprava procesoru pro Forth? Existuje více přístupů, nejpoužívanější jsou následující úpravy:

1. Zásobníky mají různé oblasti použití, a proto pro ně existují i rozdílné instrukce. Jeden zásobník bývá používán pro aritmetické a logické výpočty (to odpovídá forthskému zásobníku operandů), druhý zásobník se používá zejména pro uložení návratových adres volaných funkcí/slov. Procesory, které podporují běh programů napsaných ve Forthu, většinou přímo obsahují instrukce typu DUP, DROP, OVER,ROT, R> či >R.
2. Programy napsané ve Forthu se často vyznačují velkým množstvím skoků do podprogramů a návratů z podprogramů. Je to způsobeno stylem programování, kdy se používají poměrně krátká slova. Z tohoto důvodu obsahují zásobníkové procesory vhodně zakódované instrukce typu CALL a RET (ve Forthu se příslušné slovo značí samozřejmě „;“). Instrukce typu RET bývá typicky párována s ostatními instrukcemi. Například v případě použití instrukčního kódu širokého šestnáct bitů bývá jeden bit (např. nejvyšší) vždy použit pro označení návratu z podprogramu. To znamená, že procesor mohl současně provádět návrat z podprogramu (tj. změnu registru PC) a výpočet – místo uložení výsledku je totiž dopředu známé. Také instrukceCALL spolu s adresou bývá zakódována velmi ekonomickým způsobem, většinou přímo v instrukčním kódu.
3. Pro zásobníkové procesory (s výjimkou některých netypických řešení, například F21 apod.) je typický zvláštní formát instrukcí, kdy lze přímo z operačního kódu instrukce vyčíst prováděné operace. Uvedu příklad: šestnáctibitový kód každé instrukce obsahuje jeden bit pro indikaci návratu z podprogramu (viz předchozí bod), další čtyři bity jsou použity pro specifikaci aritmetické či logické operace, tři bity jsou určeny pro specifikaci operace nad zásobníkem (ROT apod.) a zbývajících osm bitů může být použito například pro uložení literálu na zásobník. Ve skutečnosti se tedy do jedné instrukce dalo zakódovat více forthovských slov, což zhruba (!) odpovídá VLIW procesorům (Very Long Instruction Word).

U některých procesorů je použito i více zásobníků než „pouze“ dva. Pokud jsou použity tři zásobníky, je jeden typicky využíván jako zásobník operandů, druhý pro uložení návratových adres z podprogramů a třetí pro čítače smyček. Samostatné uložení čítačů smyček může zefektivnit překlad některých forthovských programů, protože se omezí použití slov typu R> a >R. Důležité přitom je, že instrukce umožňují práci se všemi zásobníky současně, což výrazným způsobem přispívá k celkové rychlosti aplikace.

Občas se setkáme i s procesory, které obsahují více zásobníků – například se jedná o procesor SF 1: Stack Frame computer number 1, který obsahuje pět zásobníků. Využití těchto procesorů vypadá lákavě, například možnost využití dvou zásobníků pro operandy instrukcí. Zde se však dostavují komplikace, protože instrukce již musí být složitější (je nutné jednotlivé zásobníky „adresovat“) a více zásobníků se ve Forthu již prakticky nedá rozumným způsobem obsloužit (možná s využitím jiné sady základních slov a odlišné struktury programů).

Vícezásobníkové procesory se z tohoto důvodu více uplatňují při běhu funkcionálních jazyků, zejména LISPu. Požadavkem ovšem je, aby bylo možné spustit kód, který je na zásobníku uložen.

4. Velikost zásobníku či zásobníků

Velikost zásobníku či zásobníků úzce souvisí s technologií implementace zásobníků. V zásadě jsou možné tři strategie při vytváření zásobníků:

1. Celý zásobník je vytvořen v operační paměti počítače, kromě minimálně dvou položek na vrcholu zásobníku, které jsou prakticky vždy mapovány do speciálních registrů procesoru. Tento přístup k vytváření zásobníku patří mezi nejjednodušší a přitom prakticky neomezuje velikost zásobníků. Nevýhodou je pomalejší přístup k jednotlivým položkám, protože rychlost pamětí tvoří v současné době úzké hrdlo mikroprocesorových systémů.
2. Větší část zásobníku (blízko jeho vrcholu) je uložena ve speciálních registrech mikroprocesoru, zbytek zásobníku je uložen v operační paměti počítače. Výhodou tohoto přístupu je větší rychlost zpracování programu, zejména v porovnání s předchozí strategií. Problém představují vyšší nároky na počet hradel, ze kterých je procesor sestaven, a nutnost přesouvat větší množství dat při přepínání kontextu (pokud samozřejmě daný systém pracuje s multitaskingem).
3. Celý zásobník je tvořen speciální HW strukturou, například dlouhým posuvným registrem či podobným číslicovým obvodem. Tento přístup se uplatňuje především u specializovaných procesorů se známými nároky běžících procesů na zdroje. Výhodou může být velká rychlost zpracování, protože přístup do zásobníků může být v jednom cyklu kombinován s přístupem do operační paměti. Nevýhodami jsou značná režie při přepnutí kontextu, problémy při překročení kapacity zásobníku a v neposlední řadě také vyšší nároky na HW řešení celého systému (opět stoupá počet hradel, stejně jako počet vývodů procesoru).

5. Počet adresovatelných operandů v instrukcích

Důležitou vlastností všech procesorů je jejich schopnost adresovat jednotlivé operandy, se kterými se mají provádět výpočty. Tuto skutečnost jsme si ostatně uvedli již v předchozí části tohoto seriálu. Zásobníkové procesory používají prakticky vždy implicitní adresování, proto se v operačním kódu instrukce nenachází pole (rezervované bity), které by bylo použito pro specifikaci operandů. Naproti tomu se u RISC a CISC procesorů objevují instrukce s jedním operandem, dvěma operandy a v některých případech i se třemi operandy.

Při použití implicitně adresovaných operandů je dopředu známo, že se operandy vybírají ze zásobníku a výsledek operace se taktéž ukládá na zásobník. Jeden explicitně zadaný operand se typicky používá u procesorů s akumulátorem, protože ten vždy uchovává první operand i výsledek výpočtu. Dva či tři explicitně zadané operandy nacházejí své uplatnění v registrových procesorech, ať už typu CISC či RISC.

6. Příklady procesorů z jednotlivých kategorií

Jak již bylo řečeno v předchozích kapitolách, v každé ze dvanácti kategorií vynesených na trojrozměrném grafu se nachází nějaký typ procesoru. To znamená, že tvůrci procesorů po zvážení všech kladů a záporů museli jednu z kategorií upřednostnit, každá z kategorií má tedy svůj smysl. Pokusme se vypsat nejznámější procesory z každé kategorie.

Každou kategorii přitom budeme značit třemi znaky. Prvním znakem je řečeno, zda je použit jeden zásobník (Single), či více zásobníků (Multiple). Druhým znakem je naznačena velikost zásobníku -Small, nebo Large. Třetí znak je číslo 0–2, kterým je uveden počet operandů adresovatelných v jedné instrukci.

6.1 Kategorie SS0

Transputery – některé transputery spadají právě do kategorie SS0, tj. instrukce nemají explicitně zadaný žádný operand a je použit pouze jeden zásobník malého rozsahu.

6.2 Kategorie SS1

V této kategorii se nachází procesory, které obsahují jeden zásobník a v instrukcích se používá pouze jeden explicitně zadaný operand. Typicky se jedná o procesory s akumulátorem, mezi něž patří například známý Intel 8080 a dále velké množství mikrořadičů, zejména Intel 8048 a jeho následovníci.

6.3 Kategorie SS2

Intel x86 – známá procesorová řada, jejíž procesory podporují práci s jedním zásobníkem (přes registry SS aSP). V instrukcích se adresují dva operandy, první operand je zároveň i operandem cílovým. Existují samozřejmě i výjimečné instrukce (například MUL a DIV), ale vcelku tento procesor patří do kategorie SS2.

6.4 Kategorie SL0

Procesory spadající do kategorie SL0 nejsou příliš rozšířené, neboť se práce pouze s jedním zásobníkem komplikuje, zejména při skocích do podprogramů. Z tohoto důvodu se v této kategorii vyskytují zejména vývojové typy, například G Machine apod.

6.5 Kategorie SL1

Tato kategorie obsahuje procesory s jedním zásobníkem o velké kapacitě, přičemž instrukce mohly explicitně používat jeden operand (samozřejmě v součinnosti s jedním operandem implicitním). Do této kategorie spadají některé méně známé CISC a RISC procesory. Najdeme zde například procesor Micro-3L.

6.6 Kategorie SL2

V této kategorii se nachází mnoho procesorů typu RISC. Možnost explicitního adresování dvou operandů je využita při práci s obecně použitelnými registry, jediný zásobník se používá pro vytváření výše popsaného zásobníkového rámce. Do této kategorie patří například procesory RISC I, CRISP a Dragon.

6.7 Kategorie MS0

V této kategorii se nachází velké množství zásobníkových procesorů určených pro běh aplikací napsaných v programovacím jazyce Forth. Mezi tyto procesory patří například dále popisovaný MISC M17. Některé další zásobníkové procesory spadají do kategorie ML0, která aplikacím nabízí větší prostor na zásobníku.

6.8 Kategorie MS1

Některé akumulátorové procesory obsahují více zásobníků. Částečně sem spadá i známý procesor Motorola 6809, která obsahuje dva nezávislé ukazatele vrcholu zásobníku.

6.9 Kategorie MS2

Procesory, které obsahují více zásobníků a současně mohou v instrukci adresovat dva operandy, jsou velmi flexibilní, zejména pro programátory v assembleru (překladače mají raději jednodušší instrukční sadu). Takovým procesorem je známá Motorola 68000, která byla použita v mnoha počítačových systémech. Zásobníky se na tomto procesoru vytvářely přímo v operační paměti, do níž se přistupovalo pomocí instrukcí s post-inkrementací nebo naopak pre-dekrementací adresy.

6.10 Kategorie ML0

Prakticky všechny moderní zásobníkové procesory spadají do této kategorie; jedná se například o procesor RTX 32P, RTX 2000 a WISC CPU/32. Oproti podobné kategorii MS0 je u procesorů z této kategorie použit větší zásobník, což přináší některé výhody, ale i problémy (přepínání kontextu apod.).

6.11 Kategorie ML1

V této kategorii se nacházejí jak procesory určené pro běh programů napsaných ve Forthu (procesor SF1), tak i procesory pro rychlý běh aplikací napsaných v programovacím jazyku LISP. Použití většího množství zásobníků společně s jednoadresovými instrukcemi může skutečně běh LISPovských programů podstatným způsobem urychlit.

6.12 Kategorie ML2

Opět se jedná o kategorii vyhrazenou zejména vývojovým typům procesorů, například Socrates apod.

7. Obsah dalšího pokračování

V následujících pokračováních tohoto seriálu si uvedeme popis několika známých a typických zásobníkových procesorů. Bude se jednat jak o starší šestnáctibitové procesory, tak i o novou generaci třicetidvoubitových procesorů. Určitě také nezapomeneme na mikroprocesor F21, který navrhl Chuck Moore (vynálezce Forthu).