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

Obsah

1. Základní charakteristika zásobníkových procesorů
2. Pipelining
3. Velikost zásobníku pro operandy a parametry funkcí
4. Zpracování přerušení a přepnutí kontextu
5. Velikost programového kódu
6. Překladače a optimalizace zásobníkového kódu
7. Porovnání zásobníkových procesorů s procesory typu RISC
8. Porovnání zásobníkových procesorů s procesory typu CISC
9. Obsah dalšího pokračování

1. Základní charakteristika zásobníkových procesorů

V předchozích částech tohoto seriálu – při popisu programovacího jazyka Forth – jsme si ukázali význam zásobníku při zpracování strukturovaného programového kódu, zejména při vyčíslování aritmetických a logických výrazů, předávaní parametrů a řízení programového kódu. Zásobníkové procesory jsou takové procesory, které manipulaci se zásobníkem podporují již ve svých instrukcích a mnohdy dokonce ve svém jádru jeden či více zásobníků obsahují. Nejedná se však pouze o základní manipulaci se zásobníkem (tu zvládají prakticky všechny procesory), ale například o instrukce pro efektivní provádění výpočtů nad hodnotami uloženými v zásobníku, instrukce typu over, dup apod. V praxi se můžeme setkat jak s čistě zásobníkovými procesory, tak i s různými modifikacemi, například s kombinací zásobníkového procesoru a procesoru typu RISC.

Zásobníkové procesory jsou určeny především pro vestavěné systémy, u kterých hrají velkou roli systémové požadavky a cena. Vzhledem k tomu, že programový kód je u zásobníkových procesorů obecně menší než u procesorů typu RISC a CISC, mohou být také použity paměti s menší kapacitou, čímž se může snížit i finální cena výrobku. Samotný zásobníkový procesor je také velmi jednoduchý, protože nemusí obsahovat sadu obecných registrů ani plánovač instrukcí. Další aplikační oblastí zásobníkových procesorů jsou systémy, u nichž je požadována vysoká rychlost zpracování a především rychlé odezvy systému na přerušení. V neposlední řadě jsou zásobníkové procesory použity i v některých družicích, kde provádějí řídicí a měřící činnosti.

Mezi zásobníkové procesory patří například všechny výrobky firem Minimum Instruction Set Computer, Inc., Novix, Harris Semiconductor atd. Ovšem i procesory určené pro běh Javy (UltraJava, MicroJava a PicoJava) jsou ve skutečnosti zásobníkovými procesory.

Procesory můžeme obecně dělit podle různých kritérií. Jedním z těchto kritérií je i počet explicitně zadaných operandů při provádění aritmetických a logických operací. Pokud nebudeme brát v úvahu značně specifické operace, například dělení se zbytkem, lze procesory rozdělit následovně:

• Žádné explicitně zadané operandy se používají zejména u zásobníkových procesorů. Operandy není zapotřebí zadávat, protože je dopředu známo, že se vybírají ze zásobníku. Výsledek operace se taktéž ukládá na zásobník. Výhodou těchto takzvaných bezadresových instrukcí je jejich krátká délka, protože se v instrukčním kódu nemusí vytvářet prostor pro specifikaci zdrojů a cíle dat. Nevýhodou je úzké místo, které zásobník představuje při přípravě dat na výpočet. Zástupcem tohoto typu procesorů je například MISC M17, F21 a RTX 32P.
• Jeden explicitně zadaný operand je použit typicky u akumulátorových procesorů. Tyto procesory jsou charakteristické tím, že obsahují jeden specifický registr nazývaný akumulátor. Tento registr je použit při prakticky všech výpočtech, proto ho není zapotřebí v instrukčním kódu uvádět. Typicky bývá akumulátor použit jako první operand a také jako místo, kam se uloží výsledek operace. Zástupcem tohoto typu procesorů je Intel 8080, Intel 8048 a také MOS 6502. Výhody a nevýhody akumulátorových procesorů jsou stejné (nevýhody jsou však větší) jako v případě procesorů zásobníkových: poměrně krátké instrukce a existence úzkého místa, kterým je nyní akumulátor.
• Dva explicitně zadané operandy jsou použity u takzvaných registrových procesorů, tj. u těch typů procesorů, které obsahují větší množství obecně použitelných registrů. Jedná se o dnes nejpoužívanější procesory typu RISC i CISC. V instrukčním kódu jsou specifikovány dva registry nebo paměťová místa – jeden registr je zdrojový a současně i cílový, druhý registr obsahuje druhý operand, který do instrukce vstupuje (samozřejmě se musí jednat o binární instrukce). Výhodou tohoto typu procesorů je snadná tvorba složitějších výpočtů, nevýhodou dlouhé instrukční kódy a praktická nutnost použití pipeliningu. Známou architekturu Intel x86 lze zařadit do této kategorie, i když vykazuje i některé vlastnosti kategorie předchozí.
• Tři explicitně zadané operandy jsou používány taktéž u registrových procesorů. Rozdíl oproti předchozí skupině je ten, že jsou explicitně specifikovány jak oba zdrojové operandy, tak i operand cílový. Ruční i automatická tvorba strojového kódu je jednoduchá, nevýhodou jsou dlouhé instrukce, složitý dekodér instrukcí a nutnost použití pipeliningu. Tříadresový kód je často použit jako abstraktní mezikód při překladu programu z vyšších programovacích jazyků, protože je nad ním možné provádět různé optimalizace.

2. Pipelining

Při provádění aritmetických a logických instrukcí nad zásobníkem (tj. pokud jsou všechny operandy umístěny na zásobníku, stejně jako výsledky aritmetických operací) není zapotřebí používat klasický pipelining, protože je předem známé, kde jsou všechny operandy umístěny. To je velký rozdíl oproti registrovým procesorům (RISC, CISC), u kterých se musí nejprve vyčíslit umístění a popřípadě i adresa jednotlivých operandů.

Veškerá režie v přístupu do zásobníku na zásobníkovém procesoru může být pomocí pipeliningu skryta, tj. není zapotřebí provádět zbytečné čekací cykly. Tento přístup byl implementován již u prvních zásobníkových mikroprocesorů, které používaly nekódovaný formát instrukčního slova. Při přístupu do operační paměti se v některých případech čekací cykly mohou vkládat, tyto operace však nejsou (podobně jako u procesorů RISC) příliš časté (pozor, neplést si statickou a dynamickou četnost instrukcí, což je zvláště u vnořených smyček podstatný rozdíl).

Jaký je tedy rozdíl mezi pipeliningem u zásobníkových procesorů a u procesorů typu RISC/CISC? U běžných procesorů se musí v každé instrukci provádět fáze Fetch-Decode-Data read-Execute-Data store, které se samozřejmě mohou díky pipeliningu překrývat s fázemi následujících instrukcí. U zásobníkových procesorů se fáze sdružují na (Fetch + Decode + Data read) – (Execute + Data store), protože se nemusí složitým způsobem dekódovat zdroj a cíl dat – ten je vždy na zásobníku, samozřejmě kromě instrukcí @ a !.

3. Velikost zásobníku pro operandy a parametry funkcí

Při prvním pohledu na zásobníkové počítače se zdá, že velikost zásobníku pro operandy a parametry funkcí (tj. maximální počet paměťových buněk zásobníku, do kterých se mohou vkládat hodnoty) musí být, vzhledem k jeho častému používání, dosti velká, protože se zásobník používá pro mnoho činností, mimo jiné i jako odkládací prostor pro lokální proměnné.

Ve skutečnosti však pro většinu úloh, které jsou psány v programovacím jazyku Forth, postačuje docela malá velikost zásobníku, běžně 16 paměťových buněk. Je to dáno mimo jiné tím, že se ve Forthu vytváří velmi malé funkce (resp. slova), které pro svoji činnost potřebují malé množství parametrů a také používají jen velmi malý počet pomocných proměnných uložených na zásobníku.

Problémy samozřejmě nastávají při příchodu přerušení (interrupt), protože podprogram pro zpracování přerušení samozřejmě vyžaduje další místo na zásobníku. Uvádí se (viz knihu Stack Computers: The new wave), že přetečení zásobníku se šestnácti buňkami nastává vlivem přerušení v jednom procentu případů. Pokud je zásobník zvětšen na 32 buněk, nenastává přetečení prakticky nikdy.

4. Zpracování přerušení a přepnutí kontextu

V případě, že při běhu systému vznikne požadavek na přerušení a/nebo přepnutí kontextu, musí se u registrových procesorů (CISC, RISC) uložit všechny registry na zásobník a po zpracování přerušení obsah registrů opět obnovit. To samozřejmě zabere nějaký čas, což se negativně projevuje například v systémech nasazených v průmyslových aplikacích, ve kterých se musí obsluhovat velké množství přerušení přicházejících od externích zdrojů.

Pro tyto typy průmyslových aplikací je charakteristický poměrně velký datový tok z různých čidel a měřidel spolu s požadavkem na okamžitou odezvu na přerušení – např. okamžitá změna otáček motoru stroje, přepnutí relé atd. Zároveň s těmito požadavky je zapotřebí provádět rychlé přepínání úloh (měření/reakce/výs­tup k uživateli), a to na procesorech, jejichž výpočetní výkon dosahuje pouze zlomku výpočetního výkonu procesorů v dnešních osobních počítačích.

Běžně používané vestavěné systémy reagují na přerušení v časech řádu mikrosekund a jsou v nich použity procesory taktované v desítkách MHz. Porovnání s dnešními PC, která mají frekvence procesorů o dva řády vyšší, není možné, protože běžné operační systémy používané na PC nedokážou na přerušení takto rychle reagovat (samozřejmě s výjimkou real-time systémů).

Některé registrové procesory se nevýhodu pomalé reakce na přerušení snaží řešit například vytvořením více sad registrů, což je sice na první pohled dobrá volba, ale většinou se v praxi (někdy i po delším provozu) projeví její nevýhody: komplikovanější procesor a omezené množství registrových sad při souběhu přerušení.

Nic podobného ovšem na zásobníkových procesorech nenastává. U těchto procesorů se do obsluhy přerušení může skočit okamžitě, protože doba skoku se může překrývat s ještě probíhající aritmetickou operací nad operandy uloženými na zásobníku (návratový kód se ukládá do druhého zásobníku). Zejména z tohoto důvodu jsou zásobníkové procesory využívány v mnoha aplikacích pracujících v reálném čase.

5. Velikost programového kódu

Existuje poměrně velké množství aplikací, u kterých může být kritická i samotná velikost programu, resp. přeloženého programového kódu. Na dnešních osobních počítačích a pracovních stanicích velikost programu (zdánlivě) nehraje tak velkou roli jako například u vestavěných (embedded) systémů. Cena vestavěných systémů totiž nestoupá lineárně s velikostí programového kódu, ale skokově – tehdy, kdy je zapotřebí nainstalovat další paměťový modul nebo modul s větší kapacitou.

To je mimochodem také jeden z hlavních důvodů, proč se po dlouhou dobu nešířily přehrávače pro digitální video uložené podle norem MPEG 2 a MPEG 4 – pro tyto přehrávače bylo zapotřebí nainstalovat alespoň 2 MB, častěji však až 4 MB operační paměti, ale pro přehrávání formátu MPEG 1 se mnohdy vystačilo pouze s 1 MB paměti (velmi zjednodušeně řečeno: není zapotřebí si pamatovat více snímků P a B). U takových vcelku jednoduchých systémů (paměť+čip pro MPEG+IO) hraje cena pamětí velkou roli při prosazování zařízení na trhu.

Velikost výsledného kódu, který byl přeložen z Forthu do mezikódu nebo přímo do strojového kódu, je velmi malá, zejména v porovnání s kódem vzniklým překladači jiných programovacích jazyků. Je to z velké části způsobeno stylem programování (vytváření malých, znovupoužitelných funkcí, aplikace extrémního programování) a také krátkými instrukcemi, které manipulují se zásobníkem bez explicitního uvedení operandů.

Zmenšení kódu mezi CISC procesorem a zásobníkovým procesorem se u běžných aplikací pohybuje v hodnotách od 1:2,5 do 1:8. Při porovnání RISC a zásobníkových procesorů je zmenšení kódu ještě patrnější, o faktor 1:4 až 1:10 (samozřejmě ve prospěch zásobníkových procesorů), protože instrukce u RISC procesorů jsou sice jednoduché, ale vlastní instrukční slovo musí obsahovat adresy či jména operandů/registrů, což u zásobníkového kódu odpadá.

6. Překladače a optimalizace zásobníkového kódu

Kromě překladače/in­terpreteru jazyka Forth samozřejmě existují i další překladače, zejména z jazyků Pascal a C do strojového jazyka zásobníkových procesorů. Tyto překladače však většinou neprodukují příliš efektivní kód, protože jejich optimalizační rutiny jsou zaměřeny především na procesory typu RISC obsahujících co nejvíce všeobecně použitelných registrů.

Jednu z velmi zajímavých optimalizačních metod při práci se zásobníkovými procesory uveřejnil Philip Koopman v časopise Journal of Forth Applications and Research, 6, 1994 (elektronická verze). Na této optimalizační metodě je zajímavý zejména výběr a použití instrukcí pro manipulaci se zásobníkem, protože při překladu jazyků C, Pascal apod. představuje zásobník úzké místo architektury.

Popsaný optimalizační proces je založen na zpracování mezikódu (intermediate kódu) produkovaného překladačem GCC. Tento mezikód je zapsán v jazyce podobném LISPu a jsou v něm vyjádřeny prováděné operace nad imaginární soustavou registrů. Z tohoto mezikódu lze vytvořit program pro zásobníkový počítač, který registry umisťuje do zásobníku a vykonává nad nimi potřebné operace. Tento přímý převod do výsledného kódu není z mnoha důvodů optimální, a to ani na registrových procesorech, zejména těch, které nejsou ortogonální – odstrašujícím příkladem je celá architektura x86.

Optimalizace nastává až nad tímto zásobníkovým/re­gistrovým mezikódem, ve kterém jsou nalezeny často používané registry (ty jsou uloženy hlouběji v zásobníku pro pozdější použití) a naopak registry, které spolu nekolidují – potom je lze sloučit. Nakonec se ještě sloučí popř. odstraní některé instrukce, které se nemusejí použít (DUP SWAP → DUP, SWAP TUCK → OVER apod.).

Optimalizace popsané ve výše uvedeném článku však zdaleka nejsou dokonalé, protože se týkají pouze optimalizací na úrovni základních bloků, tj. uvnitř funkcí v místech, kde se neprovádějí rozskoky (tj. podmínky). Překladač GCC optimalizuje kód pro RISC a CISC procesory mnohem lépe, to je však dáno především lepší znalostí a rozšířeností těchto typů procesorů. Základní optimalizace nad mezikódem jsou však pro všechny procesory stejné a lze je dělat bez znalosti cílového procesoru. Týká se to zejména nalezení „mrtvého“ kódu, prohození mezí u počítaných smyček, eliminace výrazů uvnitř smyček, zjednodušení výrazů apod.

7. Porovnání zásobníkových procesorů s procesory typu RISC

Největším rozdílem mezi zásobníkovými procesory a procesory typu RISC je fakt, že zásobníkové procesory používají instrukce bez explicitního adresování operandů. U RISC procesorů se typicky používají instrukce se dvěma operandy, kterými bývají registry. Jedinou výjimku tvoří instrukce typu LOAD a STORE, které načítají obsah registru z operační paměti nebo naopak ukládají obsah registru do operační paměti.

Celková velikost programového kódu je u zásobníkových procesorů obecně menší než u RISC procesorů. RISC procesory totiž mají velké množství registrů, pro jejichž specifikaci je nutné použít většího množství bitů v kódu instrukce. Dokonce se uvádí vtip, že velikost cache u RISC procesoru musí být větší než kapacita CELÉ operační paměti u zásobníkového procesoru, přičemž na obou procesorech běží programy stejnou rychlostí.

U RISC procesorů také nastávají problémy při volání podprogramů a návratech z podprogramů, protože se přeruší plynulý tok instrukcí, a tím pádem je zapotřebí vyprázdnit polozpracované instrukce z fronty instrukcí – viz kapitolu o pipeliningu.

8. Porovnání zásobníkových procesorů s procesory typu CISC

CISC procesory se vyznačují velmi obsáhlou instrukční sadou. Před několika lety se zdálo, že celá architektura CISC bude opuštěna a nahrazena architekturou RISC. Opak je pravdou – dnes nejpopulárnější procesory jsou sice interně vytvořeny jako RISCové (což je samo o sobě dosti diskutabilní), ale jejich instrukční sada je CISCová. V této kombinaci se ukazují výhody obou architektur: rychlost a jednoduchost RISCů a současně kratší kód instrukcí u CISC procesorů.

Naproti tomu skok do podprogramu, návrat z podprogramu i podmíněný skok jsou pro CISC procesor takovou malou tragédií, protože musí zapomenout všechny rozpracované instrukce a začít plnit pipeline pěkně od začátku. Z tohoto důvodu se u CISC procesorů začínají objevovat různé technologie umožňující predikovat podmíněný skok (jednobitové a dvoubitové prediktory skoků), překladače na požádání rozbalují smyčky, využívají inline funkce apod. Žádnou z těchto technologií není zapotřebí u zásobníkových procesorů používat, což dále přispívá k jejich konstrukční jednoduchosti.

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

V příštím pokračování tohoto seriálu si povíme, jakým způsobem je možné roztřídit všechny typy zásobníkových procesorů (a prakticky všech procesorů obecně) do několika kategorií. Ukážeme si také, že každá kategorie má své přednosti a samozřejmě i některé záporné vlastnosti.