Hlavní navigace

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

19. 4. 2005
Doba čtení: 13 minut

Sdílet

V předchozí části seriálu o programovacím jazyce Forth a zásobníkových procesorech jsme si popsali základní vlastnosti těchto procesorů a způsob jejich rozdělení podle několika vlastností. Dnes si podrobněji popíšeme velmi zajímavý zásobníkový procesor, který se jmenuje F21.

Obsah

1. Zevrubná specifikace mikroprocesorů M21 CPU a F21
2. Zásobníky a jejich vlastnosti
3. Sada registrů
4. Šířka sběrnic a zpracovávaného slova
5. Funkční bloky
6. Instrukční soubor
7. Skokové instrukce
8. Obsah dalšího pokračování

1. Zevrubná specifikace mikroprocesorů M21 CPU a F21

San Mateo, CA (November, 1994) – Offete Enterprises announces successful production of the high performance, multiprocessor chip MuP21. MuP21 has a 21-bit CPU core, a memory coprocessor, and a video coprocessor, implemented with 1.2 micron CMOS process. It is targeted for applications in video displays, CAD design, communication, video games, and embedded systems.

M21 CPU (a jeho varianta MuP 21) je, jak již název napovídá, mikroprocesor, tj. elektronická součástka, která v sobě mimo jiné obsahuje aritmeticko-logickou jednotku ALU, sadu registrů a řadič sběrnice. Tento mikroprocesor je založen na virtuálním stroji jazyka Forth. Virtuální stroj je v tomto kontextu značně vzletný pojem, protože se jedná pouze o implementaci základních instrukcí jazyka Forth, žádné další podpůrné prostředky nejsou k dispozici.

Procesor M21 CPU vznikl jako rozšířená varianta mikroprocesoru MuP21 – byl rozšířen zásobník operandů (viz dále), je implementováno více instrukcí včetně nepřímého adresování a podmíněných skoků a v neposlední řadě jsou přímo na mikroprocesoru vytvořeny další podpůrné koprocesory – řadič videa, obvod pro sériový přenos dat a obvod pro paralelní přenos dat. Pokračovatelem tohoto procesoru je čip F21, který dále obsahuje D/A a A/D převodník.

Původní mikroprocesor MuP21 byl vytvořen samotným Chuckem Moorem, vynálezcem Forthu. Chuck Moore pro návrh tohoto čipu použil svůj vlastní CAD systém pro poloautomatizovaný návrh VLSI obvodů – OKAD. Tento systém byl později použit i pro vývoj dalších mikroprocesorů založených na zásobnících.

Ekvivalentní počet tranzistorů, ze kterých je procesor i se všemi koprocesory sestrojen, je roven pouze patnácti tisícům, což je o několik řádů méně než počet tranzistorů v procesorech řady x86. Tak malého počtu tranzistorů bylo dosaženo pouze díky promyšlené koncepci tohoto procesoru – bitové šířce a instrukčnímu souboru.

V dalších kapitolách si popíšeme některé zajímavé části tohoto mikroprocesoru a způsob jeho použití.

2. Zásobníky a jejich vlastnosti

Jak jsem již napsal v předchozím odstavci, je procesor F21 chápán jako virtuální stroj jazyka Forth, což mimo jiné znamená, že veškeré datové přenosy a výpočty se provádějí přes zásobníky. Tento procesor obsahuje dva zásobníky:

První zásobník je určen pro přenos dat a provádění aritmetických výpočtů – jedná se tedy o datový zásobník – Data Stack. Tento zásobník má kapacitu 18 položek a je celý umístěn přímo na mikroprocesoru, čímž nahrazuje sadu registrů, které se používají u klasických mikroprocesorů typu CISC a RISC.

Druhý zásobník je určen především pro úschovu návratových adres z volaných funkcí – jedná se tedy o zásobník Return Stack. Kromě toho lze na tento zásobník ukládat data, ovšem pouze v rámci jedné funkce. Typicky se zde ukládají také počitadla smyček. Tento zásobník má kapacitu 17 položek a je, podobně jako datový zásobník, umístěn přímo na mikroprocesoru.

Proč však mají oba zásobníky tak divné kapacity? Osmnáct resp. sedmnáct položek, to je ve výpočetní technice poměrně netypické. Ve skutečnosti má datový zásobník kapacitu „pouze“ 16 položek (to už je zajímavější číslo) a zbývající dvě položky jsou umístěny přímo v aritmeticko-logické jednotce, protože u zásobníkového procesoru je dopředu zřejmé, že se data budou vždy brát ze zásobníku. Tyto dvě položky se označují písmeny T (Top of Stack) a S (Second Item on Stack).

U zásobníku návratových adres je situace podobná – nejvrchnější položka je umístěna ve speciálním registru nazývaném R (Return) a zbývající kapacita zásobníku je rovna opět šestnácti položkám.

3. Sada registrů

Vzhledem k tomu, že tento mikroprocesor je založen na dvojici zásobníků, má programátor k dispozici poměrně omezenou sadu registrů. První tři de-facto registry už známe – jsou to položky na vrcholu obou zásobníků, které jsou implicitně použity k vykonávání většiny aritmetických, logických i řídicích instrukcí. Mezi další registry patří adresový registr a programový čítač, který obsahuje adresu právě vykonávané instrukce a může být programátorem měněn pouze skokovými instrukcemi.

Všechny registry si můžeme přehledně vypsat:

  • A – adresový registr, který je možné použít při práci s pamětí (pole atd.), ale také například při blokových přesunech dat. Existuje totiž instrukce pro čtení či zápis z adresy a současně inkrementaci tohoto registru.
  • PC – programový čítač, který obsahuje adresu právě prováděné instrukce. Obsah tohoto registru je možné měnit pomocí skokových a návratových instrukcí, v opačném případě se jeho hodnota pouze inkrementuje.
  • T – vrchol datového zásobníku. Je použit při všech aritmetických a logických operacích a také při přenosech dat. K dispozici jsou také operace pro přesun dat mezi tímto registrem a vrcholem zásobníku návratových adres.
  • S – druhá položka na datovém zásobníku, která je použita u těch operací, které vyžadují dva operandy.
  • R – vrchol zásobníku návratových adres. Je ho také možné použít pro odkládání mezivýsledků a/nebo čítače smyček.

4. Šířka sběrnic a zpracovávaného slova

Mezi nejzajímavější aspekty popisovaného mikroprocesoru patří zajisté použitá šířka sběrnice. Ta má totiž šířku 20 bitů (ano 20). Je to zejména z toho důvodu, že 16 bitů je pro zakódování některé skupiny instrukcí příliš malá hodnota a naopak 32 bitů je spíše „těžká váha“ pro mikroprocesor, který je určený především pro vestavěná zařízení.

Do jednoho dvacetibitového slova je možné uložit čtyři instrukce, protože počet bitů na jednu instrukci je roven pouze pěti! Maximální počet instrukcí tak dosahuje na první pohled směšné hodnoty 32, instrukcí je však ve skutečnosti ještě méně. To je, zejména v porovnání s procesory typu CISC, například x86, opravdu malé množství, ale na druhou stranu se tato vlastnost může stát velmi výhodnou, především při pečlivém výběru instrukční sady.

Vždy čtyři pětibitové instrukce jsou spojeny tak, že vytvoří jedno dvacetibitové slovo. To znamená, že vlastní procesor může pracovat na čtyřnásobné frekvenci oproti přístupové době použitých pamětí, protože v každém paměťovém taktu je umožněn přístup ke všem dvaceti bitům. Zde je vidět velká výhoda malého instrukčního souboru, který vede k redukci počtu bitů na jednu instrukci, protože procesor může pracovat i na poměrně velkých frekvencích bez použití drahých cache pamětí.

Vylepšená verze procesoru MuP21, jež se jmenuje F21, dosahuje teoretického výkonu 500 MIPS, protože doba vykonání jedné instrukce trvá dvě nanosekundy. Tento výkon však při použití pamětí ROM klesá na 333 MIPS, s SRAM paměťmi na 200 MIPS a s DRAM paměťmi bez cache dokonce na „pouhých“ 100 MIPS. V praxi je však možné použít novou generaci DRAM pamětí, které nabízejí kratší přístupovou dobu, takže se výkon celého systému může i několikanásobně zvýšit.

Při provádění aritmetických operací se výpočty aplikují v ALU, která má bitovou šířku 21 bitů. Poslední bit slouží jako CARRY, tj. obsahuje jedničku v případě, že došlo k přetečení kapacity registrů. Toho lze využít například při implementaci vícebitové aritmetiky. I adresy jsou reprezentovány 21 bity, skokové instrukce však mohou měnit pouze nižší bity adresy.

5. Funkční bloky

Pro zajištění vysoké rychlosti celého procesoru se v ALU používá velmi jednoduchá sčítačka, která nemusí v jednom taktu zajistit součet všech bitů dvacetibitového slova. Z tohoto důvodu musí být dlouhé instrukce sčítání, při kterých dochází k přenosům, kódovány spolu s instrukcemi NOP, při jejichž zpracování procesor vlastně počká na výsledek sčítání.

Pokud je instrukce sčítání uložena v instrukčním slovu hned v prvním slotu, nemusí se čekací instrukce zadávat, stačí, když v dalších slotech nebude přítomna další sčítací operace.

6. Instrukční soubor

Jak jsem již psal v předchozích odstavcích, je každá instrukce kódována pětibitovým slovem, takže maximální počet instrukcí je roven 32. Ne všechny kódy jsou však obsazeny, proto je instrukcí ve skutečnosti méně než 32. V dalším textu si jednotlivé instrukce podrobněji popíšeme. Je to pouze na ukázku, že velmi záleží na pečlivém výběru opravdu důležitých instrukcí.

JMP – unconditional jump
tato instrukce slouží k provedení nepodmíněného skoku. Pokud je ve dvacetibitovém slově tato instrukce uvedena jako první, je zbylých 14 bitů použito pro adresu (patnáctý bit je vždy nulový). Pokud je uvedena na druhém místě, je pro adresu použito 10 bitů. Poslední možností je uvedení instrukce na třetím místě. V tomto případě na adresu zbývá pouze 5 bitů. Adresa nikdy nepřekročí jedno slovo – je to z důvodu zjednodušení návrhu celého procesoru a také se tím zjednoduší časování. Je na překladači, jakým způsobem provede optimalizaci skoku. Většinou je totiž pro skok dostačujících pouze 10 bitů, čímž mohou být do jednoho slova zakódovány dvě instrukce. Více o skokových instrukcích povím v další podkapitole.

T=0 – branch if TOP of stack =0 (DUP IF)
jedná se také o skokovou instrukci, ale na rozdíl od instrukce JMP zde jde o skok podmíněný. Pokud je na vrcholu zásobníku (tzn. ve skutečnosti v registru T) uložena nulová hodnota, skok se provede. V opačném případě skok proveden nebude a program bude pokračovat dále. Stejně jako u instrukce JMP jsou i zde možné tři typy skoků (5 bitů, 10 bitů, 14 bitů) podle toho, ve které části instrukčního slova se instrukce nachází.

C=0 – branch if CARRY bit not set
jedná se o poslední typ skokové instrukce, která provádí skok v programu pouze v případě, že není nastaven bit CARRY. Tento bit je automaticky nastavován aritmetickými instrukcemi a je pomocí něho možné implementovat například víceslovní aritmetiku nebo testovat výskok z počítaných smyček (zde je ve většině případů výhodnější použití instrukce T0).

CALL – call subroutine
ve Forthu je velmi časté, že se volají podprogramy/funkce, které se zde označují jako slova. Proto také tento procesor obsahuje optimalizovanou instrukci pro zavolání podprogramu. Tato instrukce existuje, stejně jako instrukce skokové, ve třech verzích, které se liší počtem bitů, jimiž je vyjádřena adresa skoku. Vzhledem k tomu, že je instrukce skoku optimalizovaná, může se skok provádět i v době, kdy se dokončuje výpočet předchozí instrukce, protože je zřejmé, že se výsledek bude ukládat na zásobník operandů.

RET – return from subroutine
Po zavolání této instrukce se provede výběr adresy ze zásobníku návratových adres a běh programu bude pokračovat od právě vybrané adresy – provede se návrat z podprogramu. Jedná se tedy o opak instrukce CALL. I návrat z podprogramu je optimalizovaný, takže se v jeho průběhu mohou dokončit probíhající výpočty.

# – literal
jedna z nejjednodušších instrukcí, pomocí níž se na zásobník operandů vloží konstanta, která následuje ihned za instrukčním slovem. Konstanta má bitovou šířku stejnou jako zásobník, tj. 20 bitů.

@A – fetch
jedná se o instrukci určenou pro práci s pamětí. Z adresy, kterou obsahuje registr A, se přečte hodnota, jež se uloží na zásobník operandů.

@A+
také se jedná o instrukci určenou pro práci s pamětí. Z adresy, kterou obsahuje registr A, se přečte hodnota, jež se uloží na zásobník. Současně je zvýšena hodnota v registru A. S pomocí této instrukce lze velmi efektivně realizovat blokový přenos dat nebo průchod polem se čtením hodnot.

@R+
poslední instrukce pro čtení obsahu paměti. Z adresy, kterou obsahuje registr R, se přečte hodnota, jež se uloží na zásobník. Současně se inkrementuje hodnota uložená v registru R. Při provádění smyček je v registru R uložen čítač, proto lze tuto instrukci použít také pro blokový přenos dat.

!A – store
instrukce pro zápis do paměti. Na adresu, kterou obsahuje registr A, se zapíše hodnota z vrcholu zásobníku operandů.

!A+
tato instrukce provádí stejnou činnost jako instrukce předchozí s tím rozdílem, že po zápisu hodnoty do paměti se inkrementuje hodnota uložená v registru A.

!R+
i tato instrukce provádí zápis do paměti, tentokrát však na adresu uloženou v registru R. Po provedení zápisu se zvýší hodnota v registru R o jednotku.

COM
jedná se o unární operaci, která vypočte doplněk hodnoty uložené na vrcholu zásobníku operandů – v registru T. Nová hodnota nahradí na zásobníku hodnotu původní.

AND
binární operace, která přečte dvě hodnoty uložené na vrcholu zásobníku T a ve druhé pozici S a následně vypočte jejich bitový součin. Výsledek přepíše hodnotu uloženou na vrcholu zásobníku.

-OR
binární operace, která taktéž přečte dvě hodnoty uložené na vrcholu zásobníku T a ve druhé pozici S a provede s nimi bitovou nonekvivalenci. Výsledek přepíše hodnotu uloženou na vrcholu zásobníku.

+
binární operace, která sečte hodnoty uložené na vrcholu zásobníku T a na druhé pozici S. Výsledek přepíše hodnotu uloženou na vrcholu zásobníku.

2*
unární operace, při níž se provádí bitový posun doleva s hodnotou uloženou na vrcholu zásobníku. Bitovým posunem doleva se vlastně provádí vynásobení hodnoty na vrcholu zásobníku dvojkou.

2/
unární operace, při níž se provádí bitový posun doprava s hodnotou uloženou na vrcholu zásobníku. Touto bitovou operací se provádí dělení hodnoty dvěma.

+*
podobná operace, jakou je operace +, s tím rozdílem, že se součet provede pouze v případě, že nejnižší bit hodnoty na vrcholu zásobníku má hodnotu 1.

A@
při této operaci se hodnota uložená v registru A zkopíruje na vrchol zásobníku. Jedná se o jedinou operaci, při niž lze zjistit obsah registru A.

A!

tato operace slouží k přesunu hodnoty uložené na vrcholu zásobníku do registru A. Jedná se o jedinou operaci, kterou lze přímo změnit obsah registru A, nepřímá změna je možná pomocí operací

@A+ a !A+.

DUP
tato operace jednoduše zduplikuje hodnotu na vrcholu zásobníku. Instrukce tedy dělá to samé co slovo DUP ve Forthu.

DROP
tato operace odstraní hodnotu z vrcholu zásobníku. Instrukce odpovídá slovu DROP ve Forthu.

OVER
podobně jako slovo OVER ve Forthu, i tato instrukce přečte hodnotu z druhé položky zásobníku a vloží ji na vrchol zásobníku.

PUSH
tato instrukce vezme hodnotu z vrcholu zásobníku operandů a vloží ji na vrchol zásobníku návratových adres. Jde o jediný způsob přímé manipulace se zásobníkem adres.

POP
tato instrukce vezme hodnotu z vrcholu zásobníku adres a vloží ji na vrchol zásobníku operandů. Pomocí instrukcí PUSH a POP lze ukládat mezivýsledky výpočtů na zásobník návratových adres, čímž se minimalizují pomalé přístupy do paměti.

NOP
tato instrukce neprovádí žádnou operaci. Její význam tkví především v tom, že může sloužit jako výplň v instrukčním slově (které obsahuje čtyři instrukce). Používá se například v případě, že je potřeba zakódovat „dlouhou“ instrukci skoku, která zabere celé instrukční slovo.

7. Skokové instrukce

Nejprve si schematicky ukažme instrukční slovo, ve kterém mohou být uloženy až čtyři instrukce, každá s délkou pět bitů:

bit  20 ...15  ...10  ....5  ....0
        slot0  slot1  slot2  slot3

Vidíme, že celé instrukční slovo je rozděleno do čtyř slotů, v každém slotu může být uložena jedna krátká instrukce. Jak se však kódují skokové instrukce, u kterých je zapotřebí specifikovat i adresu skoku? Jednoduše, tato instrukce zabere více slotů, jejichž počet je implicitně určen pozicí instrukce v instrukčním slo­vě.

Zakódování instrukce skoku, při kterém je v instrukčním slově uloženo deset bitů adresy, vypadá následovně:

bit  20 ...15  ...10  ....5  ....0
        slot0   jump  aaaaa  aaaaa
                      v   v   v
adresa p pppp pppp ppaa aaaa aaaa (p je z registru PC)

Vidíme, že pouze nejnižších deset bitů adresy je ovlivněno instrukcí skoku, dalších jedenáct bitů zůstává nezměněno.

Dalším typem skokové instrukce je skok, kdy je zadáno čtrnáct bitů adresy:

bit  20 ...15  ...10  ....5  ....0
         jump  0aaaa  aaaaa  aaaaa
                      v   v   v
adresa p pppp ppaa aaaa aaaa aaaa (p je z registru PC)

Při použití tohoto typu skoku zůstává neovlivněno pouze nejvyšších sedm bitů. Tuto instrukci lze modifikovat tak, že se nultý patnáctý bit nastaví na jedničku – v tom případě se jedná o skok mezi adresou v rozsahu paměti DRAM na adresu, jež leží v rozsahu paměti SRAM. Z tohoto důvodu se takto modifikovaná instrukce nazývá home page jump, protože ve SRAM je uložen počáteční bootovací program.

Jakým způsobem je však možné zajistit skok na libovolnou adresu? Taková instrukce není přímo povolena, protože by ve slotu instrukčního slova nezůstaly žádné volné bity na zakódování skokové instrukce. Řešení je však velmi jednoduché: adresa se uloží na zásobník návratových adres a provede se instrukce ret, která ze zásobníku adresu vyzvedne a provede skok.

Jak je z předchozích řádků patrné, má procesor MuP21, M21 a F21 opravdu velmi zajímavý návrh a na mnoha jeho vlastnostech je patrný typický Moorův minimalistický přístup k řešení problémů.

root_podpora

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

V dalším pokračování tohoto seriálu si popíšeme poněkud odlišné zásobníkové procesory – WISC CPU/16 a MISC M17.

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.