B0B35APO Webové stránky předmětu CompArch WebEval

• Architektura počítače – jak jsou v počítači uložena kladná čísla, celá čísla a reálná čísla, příklady používaných přístupů. Nejmenší a největší reálná čísla a jejich přesnosti.
• CPU – RISC/CISC architektura, registry, formát RISC CPU instrukcí, porovnání jednocyklového procesoru a zřetězeného zpracování instrukcí. Jaké problémy přináší zřetězené zpracování instrukcí a jak je lze řešit – stall/forwarding.
• Predikce skoků – jak lze predikovat skoky v programu, jak se přiřadí prediktor k instrukci, co je to spekulativní vykonávání instrukcí.
• Paměti – hierarchie pamětí, porovnání ceny, velikosti a rychlosti. Cache – organizace cache a její velikost, plně asociativní cache oproti n-cestné cache – výhody, nevýhody, rychlost a velikost.
• Vstupně výstupní periferie – periferie mapované do paměti, sériový port, sběrnice – sériová/paralelní, half-duplex/full-duplex, sběrnice PCI.

Architektura počítače popisuje způsob, jakým je organizován a propojen hardware – zejména paměť, procesor a sběrnice. Dvě nejčastější architektury používané pro návrh počítačových systémů jsou von Neumannova architektura a Harvardská architektura.

• V této architektuře je společná paměť pro instrukce i data.
• Instrukce i data jsou ukládány do jedné paměťové oblasti a jsou přenášeny přes stejnou sběrnici.
• To způsobuje tzv. von Neumannův bottleneck – úzké hrdlo, kdy CPU musí čekat, než se dokončí přenos dat, protože nelze paralelně číst instrukci a pracovat s daty.
• Výhodou je jednodušší návrh, menší složitost a nižší výrobní náklady.
• Používá se i dnes, např. ve většině běžných osobních počítačů.

• Instrukce a data jsou ukládány ve fyzicky oddělených paměťových oblastech.
• CPU může paralelně číst instrukci i přistupovat k datům, protože pro instrukce a data jsou použity oddělené sběrnice.
• Díky tomu je systém rychlejší a efektivnější, zejména vhodný pro vestavěné systémy, DSP apod.
• Návrh je složitější, ale umožňuje optimalizaci instrukční a datové části zvlášť.

V obou architekturách jsou paměťové jednotky spojeny se zbytkem systému pomocí tří základních typů sběrnic:

• Adresová sběrnice – určuje, kam (na jakou adresu) se CPU připojuje.
• Datová sběrnice – přenáší samotná data mezi komponentami.
• Řídicí sběrnice – přenáší signály řízení přenosu (např. čtení/zápis).

[obrázek: porovnání von Neumannovy a Harvardské architektury – ukazuje společnou paměť/sběrnici vs. oddělené části]

Počítače interně ukládají a zpracovávají všechna čísla v binární (dvojkové) soustavě. To znamená, že i běžná desítková čísla, se kterými pracujeme, musí být uvnitř reprezentována jako posloupnost bitů — tedy nul a jedniček.

Každý bit odpovídá určité mocnině čísla 2. Čím je bit „více vlevo“, tím větší mocninu reprezentuje. Například číslo `101011` znamená:

$$ 1 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 32 + 8 + 2 + 1 = 43 $$

Tento princip je základním kamenem všech výpočtů a práce s daty uvnitř počítače.

V jazyce C a dalších systémech se s kladnými čísly pracuje pomocí tzv. unsigned datových typů. Ty nezaznamenávají znaménko a využívají všechny své bity pouze k reprezentaci kladných hodnot — díky tomu mají větší maximální hodnotu než jejich „signed“ (se znaménkem) ekvivalenty.

Každý z těchto typů je implementován jako pevný počet bitů, které určují možný rozsah hodnot.

Poznámka: Standard C určuje minimální rozsah jednotlivých typů, ale konkrétní implementace může použít i širší. Například `unsigned int` bývá téměř vždy 4 byty.

Velikost konkrétní proměnné nebo typu zjistíš v C pomocí:

sizeof(unsigned int)

Přesnější (a přenositelné) typy se dají zavést pomocí hlavičkového souboru `stdint.h`:

#include <stdint.h>
uint8_t x;
uint16_t y;
uint32_t z;
uint64_t w;

Číselné konstanty můžeš v jazyce C zapsat v několika formátech podle toho, jakým prefixem začínají:

• desítkově: běžné zápisy bez prefixu (např. `123`)
• osmičkově: začínají `0` (např. `0374`)
• šestnáctkově: začínají `0x` (např. `0xfc`)
• binárně: začínají `0b` (např. `0b11111100`) – pouze v GCC nebo jako rozšíření

252 == 0xfc == 0374 == 0b11111100

Šestnáctkový (hexadecimální) zápis je čitelnější, protože každý hexadecimální znak odpovídá přesně 4 bitům. Díky tomu je rychlé převádění mezi hex a binární reprezentací.

Například:

0x123456 // zabírá 3 byty v paměti

Když počítač pracuje s víc než jedním bytem (např. `uint32_t`, `uint64_t`), musí nějak určit, v jakém pořadí budou jednotlivé bajty uloženy do paměti.

Tato vlastnost se nazývá endianita.

Zjednodušeně:

• big endian = zápis „zleva“ (nejvýznamnější byte první)
• little endian = zápis „odzadu“ (nejméně významný byte první)

Little endian si snadno zapamatuješ tak, že se číslo rozebere po bajtech odzadu – první přijde ten „nejmenší“.

Například hodnota `0x12345678` se v little endian uloží jako `0x78 0x56 0x34 0x12`.

Pro komunikaci přes síť se čísla často převádějí na network byte order, což je forma big endian. Překlady do/z této formy se v C provádějí pomocí funkcí jako `htons()` nebo `ntohl()`.

Platformy a endianita:

• RISC-V: little endian
• MIPS: big endian
• ARM: může být obojí (většinou little endian)

• bit – nejmenší jednotka informace, může nabývat hodnoty 0 nebo 1.
• nibble – skupina 4 bitů, reprezentuje 1 hexadecimální číslici.
• byte – 8 bitů; základní adresovatelná jednotka v paměti počítače.
• hexadecimální zápis – zápis binárních hodnot ve formě 0–9, A–F. Každý znak odpovídá právě jednomu nibblu.

Binární zápis je přirozený pro počítače, ale pro lidi je často čitelnější hexadecimální forma. Například 8bitové číslo `11110000` lze rychle přepsat jako `0xF0`.

Záporná čísla lze zakódovat různými způsoby:

- první bit bude znaménko

nevýhodou je existence +0 a -0 a potřeba nového algoritmu pro sčítání

- dvojkový doplněk

pro $X>0$ je reprezentace $X$ pro $X<0$ je reprezentace $2^k - |X|$

sčítání je stejné jako pro kladná čísla

8-bitová -1 je 11111111

5+(-1) je 101+11111111=100000100, devátý bit se do reprezentace čísla nevejde, tedy výsledek je 101+11111111=100

rozsah čísel reprezentovaných k-bity je $-2^{k-1}$ až $2^{k-1}-1$

nemusíme navrhovat obvod pro odčítání, jelikož operaci $A-B$ můžeme provést jako $A+(-B)$

důležité je zjistit opačné číslo $-B$

záporné $X$ je $2^k - |X|$, pokud znegujeme každý bit, dostaneme $(2^k - 1) - |X|$

postup:

• znegujeme všechny bity čísla X
• přičteme 1

V jazyce C jsou typy:

Při sčítání čísel může dojít k přetečení:

Pro převod celých čísel z dvojkové do desítkové soustavy obecně platí vztah

$$ \sum_{i=0}^{k-1} b_i \cdot 2^i $$

kde $k$ je počet cifer a $b_i$ je hodnota cifry na daném indexu.

Pro příklad

$$ 0100101_{(2)} = 2^0 + 2^2 + 2^5 = 37_{(10)} $$

Stejný princip lze aplikovat i na reálná čísla za předpokladu, že posuneme spodní hranici sumy do záporných čísel

$$ \sum_{i=-j}^{k} b_i \cdot 2^i $$

Pro příklad

$$ 0100101,11_{(2)} = 2^{-2} + 2^{-1} + 2^0 + 2^2 + 2^5 = 37,75_{(10)} $$

Zavádíme též obdobu věděckého zápisu

$$ 110110000000000,0_{(2)} = 1,1011_{(2)} \cdot 2^{14} = 1,1011E14 = 29696_{(10)} $$ $$ −0,00000000000000011101_{(2)} = −1,1101_{(2)} \cdot 2^{−16} = −1.1101E − 16 $$

(Vědecká notace se vyznačuje také tím, že žádné číslo kromě 0 nezačíná 0)

Obecně užívaný zápis desetinných čísel je standardizován dle IEEE-754. Ten definuje způsob zakódování desetinných čísel do 32, resp. 16/64/128, bitů.

Pro příklad

$$ 0,828125_{(10)} = 2^{-1} + 2^{-2} + 2^{-4} + 2^{-6} = 0,110101_{(2)} $$

Nejprve převedeme číslo do věděcké notace

$$ 0,110101_{(2)} = 1,10101E-1 $$

Na první pohled vidíme znaménko (kladné → 0) a mantisu (10101). Exponent se zapisuje v tzv. posunuté formě. Posun lze stanovit jako

$$ 2^{j-1}-1 $$

kde $j$ je počet bitů pro vyjádření exponentu. Vždy jde o kladné číslo, pro 8bit jde o posun o 127.

Exponent v našem příkladu vypočteme tedy jako $$ 2^{8-1}-1 -1 = 127 -1 = 126$$

Nyní můžeme hledané desetinné číslo zapsat jako

Podle hodnoty exponentu rozlišujeme navíc speciální případy

Pozor… kontrola rovnosti při operacích s desetinnými čísly může selhat

• čísla které mají exponent nulový ale mantisu nenulovou.
• Umí vyjadřovat extrémně malá čísla
• Klasicky mají čísla v mantise “implicitní 1” před desetinou čárkou
• denormalizovaná čísla umí zobrazit čísla v mantise typu $0.0001\text{a další rozvoj}$, zatímco u normalizovaných čísel je v mantise vždy $1.000\text{a další rozvo}j$
• Většinou o hodně pomalejší výpočet (někdy až o stovky cyklů)
• Na některých HW platformách nejsou podporovány (ARM Neon, staré verze CUDA, legacy architektury)

1. Sčítání odčítání
2. Násobení
3. Dělení
4. Odmocnina

Čísla v počítači můžeme rozdělit na celá čísla (integer) a reálná čísla (floating-point). Každý z těchto typů má svá specifika, jak jsou uložena, reprezentována a zpracovávána na úrovni binární reprezentace.

Pro reprezentaci záporných celých čísel se historicky používaly různé způsoby:

• Znaménkový bit: nejvyšší bit určuje znaménko (0 = kladné, 1 = záporné). Výhoda – jednoduché, ale nevýhoda: dvě různé nuly (+0 a -0), složité obvody pro aritmetiku.

• Dvojkový doplněk (two's complement) – moderní a dnes univerzálně používaná metoda:

1. Kladné číslo $X$ se reprezentuje běžným způsobem.
2. Záporné číslo $X$ se reprezentuje jako $2^k - |X|$, kde $k$ je počet bitů.

Výhoda: není třeba speciální obvod pro odčítání — záporná čísla lze přičítat jako kladná.

Např. pro 8bitové číslo:

• $-1$ = `11111111`
• $5 + (-1)$: `00000101 + 11111111 = 00000100` (pozorujeme přenos mimo rozsah, který zahodíme)

Rozsah čísel, která lze zapsat pomocí $k$ bitů:

$$ [-2^{k-1}, 2^{k-1} - 1] $$

Např. 8bitový typ `char` má rozsah:

$$ [-128, 127] $$

1. Převeď číslo $X$ na binární tvar.
2. Zneguj (invertuj) všechny bity – získáš 1’s complement.
3. Přičti 1 – tím získáš 2’s complement.

Příklad: $-6$

6    = 00000110
~6   = 11111001  (negace bitů)
+1   = 11111010  (přičtení 1)

Při sčítání může dojít k přetečení, pokud výsledek přesáhne možný rozsah typu. Například:

[příklad binárního přetečení dvou čísel, např. 150 + 120 → přetečení na 14, protože nejvyšší bit je znaménkový]

Pro libovolné binární číslo platí:

$$ \sum_{i=0}^{k-1} b_i \cdot 2^i $$

kde $k$ je počet cifer a $b_i$ je hodnota cifry (0 nebo 1) na daném indexu zleva zprava (od nejméně významného bitu).

Příklad:

$$ 0100101_{(2)} = 2^0 + 2^2 + 2^5 = 1 + 4 + 32 = 37_{(10)} $$

Stejný princip lze aplikovat i na reálná čísla, kde za desetinou čárkou používáme záporné exponenty:

$$ \sum_{i=-j}^{k} b_i \cdot 2^i $$

Příklad:

$$ 0100101,11_{(2)} = 2^0 + 2^2 + 2^5 + 2^{-1} + 2^{-2} = 1 + 4 + 32 + 0.5 + 0.25 = 37.75_{(10)} $$

Podobně jako v desítkové soustavě zapisujeme čísla ve vědeckém tvaru, lze to udělat i binárně:

$$ 110110000000000,0_{(2)} = 1,1011_{(2)} \cdot 2^{14} = 1.1011E14 = 29696_{(10)} $$

Záporný příklad:

$$ −0,00000000000000011101_{(2)} = −1,1101_{(2)} \cdot 2^{−16} = −1.1101E − 16 $$

Poznámka: Vědecká notace se vyznačuje tím, že žádné číslo (kromě nuly) nezačíná nulou. Mantisa má vždy tvar $1.xxxx$, což odpovídá normalizovanému binárnímu číslu.

Počítače reprezentují desetinná čísla podle standardu IEEE 754, který definuje:

• Znaménko – 1 bit (0 = kladné, 1 = záporné)
• Exponent – zakódovaný v tzv. aditivním (excess) kódu
• Mantisa – zlomková část, normalizovaná (skrytá 1)

Například pro 32bitový float:

• 1 bit: znaménko $s$
• 8 bitů: exponent $g$ (posunutý o 127)
• 23 bitů: mantisa $f$

IEEE zápis: | s | gggggggg | fffffffffffffffffffffff |

Každé desetinné číslo se převede do vědeckého binárního zápisu. Tento zápis je obdobou vědeckého zápisu v desítkové soustavě, kde číslo zapisujeme ve tvaru:

$$ x = m \cdot 2^e $$

kde:

• $m$ je mantisa (zlomková část),
• $e$ je exponent (celé číslo).

Například:

$$ 0{,}828125_{(10)} = 2^{-1} + 2^{-2} + 2^{-4} + 2^{-6} = 0{,}110101_{(2)} $$

Následně převedeme binární číslo do normalizované (vědecké) formy:

$$ 0{,}110101_{(2)} = 1{,}10101 \cdot 2^{-1} $$

Z této podoby lze přímo získat:

• Znaménko = 0 (kladné číslo),
• Exponent = $-1$ → zakóduje se jako $-1 + 127 = 126$ (v 8bitovém excess-k kódu),
• Mantisa = $10101\ldots$ (začínáme za první jedničkou, doplníme na 23 bitů).

Exponent se ve formátu IEEE 754 neukládá přímo, ale v tzv. posunuté (excess-K) formě, kde:

$$ E_{\text{uložený}} = E_{\text{skutečný}} + 2^{j-1} - 1 $$

kde:

• $j$ je počet bitů vyhrazených pro exponent (např. 8 bitů → posun je $2^7 - 1 = 127$),
• $E_{\text{skutečný}}$ je skutečný exponent, který jsme vypočetli z normalizace,
• $E_{\text{uložený}}$ je hodnota, která se uloží do paměti.

V našem příkladu:

$$ E_{\text{skutečný}} = -1 \Rightarrow E_{\text{uložený}} = -1 + 127 = 126 $$

Tato hodnota (126) je to, co se ve skutečnosti uloží do příslušných 8 bitů exponentu v IEEE formátu pro 32bitové float.

Nyní můžeme hledané desetinné číslo zapsat jako

Podle hodnoty exponentu a mantisy lze ve formátu IEEE 754 rozeznat několik speciálních hodnot. To je důležité pro detekci výjimek, extrémních hodnot nebo výpočtových chyb.

Denormalizovaná čísla (někdy také subnormální) vznikají tehdy, když je exponent nulový (`00000000`), ale mantisa není nulová. Liší se od běžných normalizovaných čísel tím, že:

• nemají implicitní skrytou jedničku před desetinnou čárkou – např. místo `1,xxxx` mají `0,xxxx`,
• umožňují reprezentovat velmi malá čísla blízká nule (tzv. „underflow“ oblast),
• výpočty s nimi bývají výrazně pomalejší (až stovky cyklů),
• některé starší nebo nízkonákladové platformy (např. starší ARM Neon, CUDA, embedded systémy) je nepodporují.

Příklad:

• Normalizované číslo: mantisa `1.000001…`, exponent ≠ 0
• Denormalizované číslo: mantisa `0.000001…`, exponent = 0

Denormalizace tak tvoří jakýsi „most“ mezi nulou a nejmenší normalizovanou hodnotou.

Formát IEEE 754 existuje v několika variantách podle bitové šířky. Čím více bitů, tím větší rozsah a vyšší přesnost.

Nejmenší kladná hodnota pro `float` (normalizovaná):

$$ \approx 1{,}17 \cdot 10^{-38} $$

Tato hodnota odpovídá nejnižšímu možnému exponentu `00000001` a mantise `000…0`, tedy normalizovanému číslu s minimální velikostí.

1. Urči znaménko (0 = kladné, 1 = záporné).
2. Převeď číslo do binární soustavy (celou i desetinnou část).
3. Normalizuj číslo do tvaru 1.xxxx × 2^e.
4. Exponent ulož jako e + bias (např. +127 pro float).
5. Mantisa = binární čísla za desetinnou čárkou (bez úvodní 1), doplň na 23 bitů.

Příklad pro číslo: -12.625

• Znaménko: 1
• Binárně: 1100.101 → normalizace: 1.100101 × 2³
• Exponent: 3 + 127 = 130 → binárně: 10000010
• Mantisa: 10010100000000000000000

Výsledný IEEE 754 zápis: 1 10000010 10010100000000000000000

Pořadí podle rychlosti (od nejrychlejšího):

• Sčítání / odčítání
• Násobení
• Dělení
• Odmocnina

Důvodem je složitost a potřeba normalizace/denormalizace během výpočtů.

• Celá čísla se ukládají pomocí two's complement – efektivní, jednoduchá aritmetika, jeden způsob reprezentace nuly.
• Reálná čísla využívají normovaný zápis dle IEEE 754, který umožňuje široký rozsah, ale je méně přesný v určitých oblastech.
• Binární reprezentace má své specifické chování, včetně přetečení, podtečení a zaokrouhlovacích chyb.
• Na rovnost dvou desetinných čísel nelze spoléhat — i malá aritmetická chyba způsobí rozdíl.

RISC/CISC architektura, registry, formát RISC CPU instrukcí, porovnání jednocyklového procesoru a zřetězeného zpracování instrukcí. Jaké problémy přináší zřetězené zpracování instrukcí a jak je lze řešit – stall/forwarding.

RISC/CISC

Reduced Instruction Set Computing vs. Complex Instruction Set Computing referuje o přístupu k návrhu procesorů. Jak název napovídá první z přístupů disponuje tzv. redukovanou instrukční sadou a druhý komplexní instrukční sadou. V redukované sadě mají standardně všechny instrukce stejnou délku a jejich sada není příliš početná. V komplexní nemusí mít instrukce konstantní délku, a jejich množství je větší. Redukovaná sada představuje většinou více práce pro programátora, kdežto komplexní sada často umožňuje provedení několika operací zavoláním jedné instrukce.

Registry

Formát RISC CPU instrukcí

Obecně – instrukce mají 32bit, kde bity 0-7 (LSb, little endian → “zprava doleva”) definují operaci, následně zbytek obsahuje registry cíle a zdrojů, případně konstant, či další specifikaci operace.

Porovnání jednocyklového procesoru a zřetězeného zpracování instrukcí

Jednocyklový procesor funguje asi takto

1. Počáteční nastavení – inicializace PC a PSW
2. Načtení instrukce z paněti z adresy PC (nastav PC → Přečti obsah do IR → uprav PC dle délky instrukce)
3. Dekóduj instrukci
4. Proveď instrukci
5. Kontrola přerušení nebo výjimky
6. Opakuj od kroku 2

Zřetězení přináší rozdělení vykonání jednotlivých úkonů instrukce. Tj. mezitím co dochází k faktickému vykonání instrukce, již se připravuje vykonání další, či dalších několika. Tomuto procesu se také jinak říká pipelining.

Jednotlivé fáze pro pětistupňovou pipeline jsou -

1. Instruction Fetch - přivedení PC na adreosvý vstup paměti, načtení instrukce
2. Instruction Decode - dokódování opcode (bity 0-7), přímého operandu a načtení registrů
3. EXecution - provedení požadované operace v ALU
4. MEMory - zápis/čtení z paměti
5. Write Back - zpětný zápis výsledků do pole registrů pro meziregistrové instrukce a paměti

Jaké problémy přináší zřetězené zpracování instrukcí a jak je lze řešit – stall/forwarding

Za předpokladu, že výsledek předchozí instrukce potřebujeme využít v další instrukci, došlo by bez ošetření k “datovému hazardu”. Ten lze vyřešit pomocí zpoždění vykonání následující operace (stall), či doplněním procesoru o tzv. forwarding, při kterém jsou nově vypočítané hodnoty přímo předány instrukci následující.

Další možné hazardy, které mohou vzniknout, jsou tzv. “control hazardy” (tj. řídící). Ty nastávají v případě, kdy je vyhodnocován skok. Pokud dojde ke skoku, může tak dojít na stav, kdy instrukce nejsou předpočítané a dochází tak k významnému zpomalení. Toto lze omezit efektivní predikcí skoků, či přesunutím rozhodování o skocích do kroku ID (jako například u architektury MIPS).

jak lze predikovat skoky v programu, jak se přiřadí prediktor k instrukci, co je to spekulativní vykonávání instrukcí.

Skoky v programu jsou instrukce, které mění tok programu. Většina skoků je podmíněná, což znamená, že se vykonají pouze pokud je splněna určitá podmínka.

Moderní procesory prefetchují instrukce dopředu, aby mohl mít zaplněnou pipeline a případně měnit pořadí instrukcí. Pokud narazí na podmíněný skok tak procesor neví, jestli má další instrukce načíst za skokem nebo za instrukcí následující po skoku. Toto se dá vyřešit tak, že procesor počká než se vyhodnotí podmínka skoku a pak se rozhodne, co udělat. To ale způsobuje zpoždění, které je nežádoucí. Proto se používají prediktory skoků, které se snaží odhadnout, zda bude skok vykonán nebo ne a spekulativně načítá a vykonává instrukce podle toho. Pokud je predikce správná, procesor může pokračovat v načítání instrukcí bez zpoždění. Pokud je predikce špatná, procesor musí zrušit všechny instrukce, které byly načteny po špatném skoku a začít znovu.

- podmínka skočila = taken. - podmínka neskočila = not taken.

Cca každá 4. až 7. instrukce je skoková, z nich 20% je nepodmíněných a 80% podmíněných. Z toho 66% podmíněných skoků je na vyšší adresu a 34% na nižší adresu. Při skoku na vyšší adresu je pravděpodobnost skoku 40% a při skoku na nižší adresu 99%.

Statické prediktory mají pro danou skokovou instrukci vždy stejnou predikci (to neznamená že například vždycky skok bude vykonán, jen to že pokud máme nějaký podmíněný skok, tak je buď vždy vykonán nebo nikdy).

Tento prediktor vychází ze statistiky, že většina skoků je vykonána a proto vždy předpovídá taken. Má uspěšnost stejnou jako je pravděpodobnost vykonání skoku, což je $p_{taken} = 0.66 \times 0.4 + 0.34 \times 0.99 = 0.6$.

Prediktor BTFNT (Backwards Taken, Forwards Not Taken) predikuje taken, pokud se jedná o skok na nižší adresu tak předpovídá taken a pokud se jedná o skok na vyšší adresu tak předpovídá not taken. Tento prediktor má úspěšnost $p_{\text{BTFNT}} = 0.66 \times 0.6 + 0.34 \times 0.99 = 0.73$.

Dynamické prediktory se snaží zjistit, zda se skočí na základě minulého chování dané instrukce skoku. Protože prediktorů je omezeně mnoho ne každá skoková instrukce má svůj prediktor.

Většinou procesor má $2^n$ prediktorů, protože díky tomu je možné použít $n$ nejnižších bitů z adresy skokové instrukce pro adresaci prediktoru.

Nejjednodušší prediktor, který má pouze 2 stavy.

Má stavy:

• 0 - predikce not taken
• 1 - predikce taken

Ve výchozím stavu je většinou predikce taken. Pokud je predikce správná, tak se nic neděje. Pokud je predikce špatná, tak se změní stav na opačný.

2-bitový Smithův prediktor má 4 stavy. 2 stavy předpovídají skok a 2 stavy předpovídají neskok. Předpověď závisí na minulém chování, ale toleruje jednu odchilku od pravidelnosti.

Má 4 stavy:

• 00 - predikce not taken
• 01 - predikce weakly not taken
• 10 - predikce weakly taken
• 11 - predikce taken

Je nemožné rozhodnout obecně, který prediktor je nejlepší. Vždy lze najít protipříklady, kdy se každý z uvedených prediktorů chová nejlépe.

Jediná možnost je statistická analýza různých programů. % tabulka s úspěšností prediktorů

Registr BHR (Branch History Register) uchovává historii posledních $n$ skoků. Na základě této historie se určuje, jaký prediktor se použije pro danou skokovou instrukci. - Pokud se skočilo pak obsahuje BHR 1, pokud se neskákalo pak obsahuje 0. - Nová informace se vloží do BHR na nejnižší bit a ostatní bity se posunou.

Vybíráme prediktor podle BHR a adresy skokové instrukce. Takže místo toho abychom prediktor vybírali jen podle adresy skokové instrukce, tak vybíráme prediktor podle adresy skokové instrukce a historie posledních skoků.

Je téměř stejný jako BHR, ale místo toho aby se bral prediktor podle adresy skokové instrukce a BHR, tak se bere prediktor podle XOR adresy skokové instrukce a BHR.

Turnajový prediktor je složený z několika prediktorů. Vybírá se podle toho, který prediktor měl v minulosti nejlepší úspěšnost.

Má lepší úspěšnost než korelované prediktory.

Jak funguje 1-bitový turnajový prediktor - Vypočti predikci prediktory P1 a P2. - Pokud se predikce shodují je výsledkem tato predikce. - Pokud se predikce neshodují:

1. Výsledná predikce je podle toho, který prediktor byl v minulosti úspěšný. Tato informace je uložena v 1-bitovém stavovém automatu.
2. Podle skutečnosti vyber prediktor P1, nebo P2 pro příští predikci.

Moderní prediktory používají neuronové sítě k určení toho, zda se skok vykoná nebo ne. Například Zen 2 používá neuronovou síť kde pro $2^k$ skokových instrukcích existuje pro každou sada vah pro neuronovou síť. Neuronová síť používá jako vstup BHR.

Paměť je jedna ze základních částí počítače. Do paměti se ukládají všechna data zpracovávaná procesorem, včetně instrukcí programů.

Každý moderní počítač má několik úrovní paměti, které se liší svou velikostí, rychlostí, latencí a funkcí. Hiearchie pamětí se může trochu lišit napříč architekturami a konkrétními sestavami.

Nejrychlejší paměť s nejnižší latancí, která je přímo v jádrech procesoru. Obsahuje data běžícího programu, ale nikoliv instrukce programu. Procesor provádí většinu operací nad registery (např. sčítání, odčítání atd.). Konkrétní počet registerů závisí na konkrétní architektuře (x86, extensions atd.), většinou v řádu desítek registerů, sčítající na stovky bytů.

Cache je rychlá volatilní paměť přímo v procesoru, která se snaží snížit dopad relativně velmi pomalých pamětí RAM. Historicky rostl výpočetní výkon procesorů mnohem rychleji než rychlost pamětí RAM a proto je cache stále více a více důležitý, aby nebyl procesor omezován (bottleneck). Moderní procesory mají několik úrovní cache pro optimální výkon:

• L1
  • Nejrychlejší cache s nejnižší latencí. Rychlost přes 2000 GB/s, latence pod 1ns.
  • Každé jádro má svůj vlastní L1 cache. U x86 je rozdělen na L1i (pro instrukce) a L1d (pro data), u ARM záleží na konkrétní architektuře.
  • Velmi malý, velikost kolem 40KB na jádro.
• L2
  • Větší ale pomalejší než L2. Rychlost kolem 1000GB/s, latence kolem 2.5ns.
  • U x86 většinou samostatný pro každé jádro, na arm většinou sdílený napříč jádry (unified).
  • Velikost v řádu MB na jádro.
• L3
  • Zdaleka největší a taky nejpomalejší. Rychlost kolem 500GB/s, latence kolem 10ns.
  • Většinou pouze u x86.
  • Sdílený napříč jádry nebo bloky jáder (např amd epyc).
  • Velikost v řádu desítek až stovek MB.

Toto rozložení samozřejmě neni univerzální, ale je typické. Intel např. dříve experimentoval s velkým L4 cache a nové intel procesory obsahují L0 cache (což je jen debilně pojmenovaný L1 cache - každé jádro má zde vlastní L0d, L0i, L1, L2 a sdílený L3).

Optimalizace datových struktur programu tak, aby se vešla dobře do cache, může vést k masivnímu nárustu výkonu.

• Word size (WS) - velikost slova je podle architektury systému 32bit $\rightarrow$ 32bitová slova, 64bit $\rightarrow$ 64bitová slova, má většinou velikost $2^i$, kde i je počet bitů potřeba na adresaci bytů uvnitř slova.
• Capacity (C) - kapacita cache v bytech nebo ve slovech
• Block size (BS) - velikost prostoru pro data v jednom řádku cache, měří se ve slovech, bývá o velikosti $2^b$, kde b je počet bitů kterými jde adresovat jeden řádek (např, pokud má řádek 128bitů, tak jde adresovat 7 bity $\arrowright$ $2^7$, kde b=7).
• Number of sets (SN) - počet řádek v jedné cachovací tabulce, většinou musí být o množství $2^n$
• Index - do řádku cache, odpovída počtu řádků (SN) cache která většinou musí být $2^n$, Index má poté $n$ bitů. Většinou se bere do Indexu nejnižích $b+i \rightarrow n+b+i$ bitů adresy z paměti (prvních $b$ bitů, adresuje obsah jednoho řádku).
• TAG - Obsahuje zbytek adresy kromě toho co už vyjadřuje index, takže je to rozsah $b+n+i \rightarrow \text{délka adresy}$
• Validity bit - bit platnosti, indikuje zda jsou data na řádku platná.
• Dirty bit - rošiřující pole v obsahu paměti. Indikuje že v cache je jiná hodnota, než v paměti hlavní
• Degree of associativity (N) - Počet tabulek
• Number of blocks (BN) - počet řádků přes všechny tabulky, je roven $\text{Degree of associativity} * \text{Number of sets}$
• Cache hit (zásah) - pojmenování situace, kdy požadovaná hodnota v cache je.
• Cache miss - výpadek, data v cache ješte nejsou
• Cache line nebo Cache block - základní kopírovatelná jednotka mezi hierarchickými ůrovněmi (typicky, $8B$, do $1KB$)
• Hit rate - počet paměťových přístupů obsloužených danou úrovní cache dělený všemi přístupy
• Miss rate 1 - Hit rate
• Average Memory Access Time (AMAT) - $AMAT = \text{HitTime} + \text{MissRate} * \text{MissPenalty}$
• AMAT pro více urovňovou cache lze spočítat rekurzivní použitím výše uvedeného vztahu
• Cache replacement policy - pravidla pro výběr položky vyřazení z cache, když potřebujeme nahrát novou hodnotu do cache
  • Random - vybraná položka je náhodná
  • LRU (least recently used) - nejdéle nepoužitá položka
  • LFU (least frequently used) - sleduje jak často se k položkám přistupuje
  • ARC (Adaptive replacement cache) - kombinace LRU a LFU
• Write through (zápis, propsání skrz) cache - Při každém zápisu se data hned propíšou i do hlavní paměti, takže cache má vždy čistou kopii, ale každý zápis stojí čas.
• Write back - Data se uloží jen do cache a blok se označí jako „dirty“; do hlavní paměti se pošlou až při vytlačení bloku, čímž šetříš počet zápisů, ale musíš hlídat dirty bity.

Znamená že $\text{Degree of associativity} = text{Number of blocks}$, pro každý řádek tímpádem existuje tabulka, to znamená že index má $0$ bitů (tedy neexistuje) a tag má velikost $\text{TAG} = $\text{délka adresy} - b+i$, kde b je počet bitů potřeba na adresaci jednoho slova v bloku a i je počet bitů na adresaci bytů ve slově.

vlastnosti:

• Nemusíme nahrazovat záznamy v cache do té doby než nám kompletně dojde.
• Je velmi drahá na implementaci, takže musí být malá .
• Používá se v aplikacích kde je potřeba extrémní rychlost, takže třeba TLB (translation lookaside buffer, pro překlad virtulní na fyzickou paměť), potřebuje být velmi malá.

• 1 cestná cache $\rightarrow$ stupeň asociace = 1, tedy má jednu tabulku
• $\text{number of sets} = \text{number of blocks}$
• má index o délce bitů $log(\text{number of sets})$

Schéma:

Příklad s většími bloky:

Vlastnosti:

• Hlavní cache u mikrokontrolerů a levných procesorů
• Má velkou pravděpodobnost kolizí $\rightarrow$ budeme muset vyřadit záznam z cache bez toho aniž bychom celou cache zaplnili
• Každou adresu můžeme zařadit pouze do jednoho místa v tabulce v cache

• Obecnější model cache - $\text{stupeň asociace} = n$

Velká volatilní paměť, která fyzicky není v procesoru.

Technologie DDR, DDR2, DDR3, DDR4.

Celkový bandwidth záleží na frekvenci pamětí a počtu kanálů. Běžné procesory většinou podporují kanály pouze 2, serverové až 12, díky čemuž dosahují velké propustnosti - stovky GB/s.

Největší problém je spíše latence, která je většinou přes 75ns. Někteří výrobci se proto snaží dát paměť co fyzicky nejblíže k procesoru, aby se minimalizovala latence.

Velmi pomalé, nevolatilní úložiště. Slouží k dlouhodobému ukládání dat. Data se z něj načítají do paměti. Při nedostatku paměti je možné jej využít jako virtuální paměť - pagefile - může vézt k problémům s výkonem.

• HDD - levné, ale pomalejší úložiště (stovky MB/s).
• SSD - drahé, ale mnohem rychlejší úložiště (až desítky GB/s).

periferie mapované do paměti, sériový port, sběrnice – sériová/paralelní, half-duplex/full-duplex, sběrnice PCI.

RISC-V nemá speciální instrukce pro komunikaci s periferiemi, místo toho se zapisuje do určené oblasti paměti, to vede k zápisu / čtení z periferií

velmi jednoduchá konfigurace - periferie při inicializaci získají paměťový rozsah, ten slouží k přesunu dat mezi CPU a periferiemi

Adress Decoder rozhoduje kam se data přesměrují

Asynchroní sběrnice

• USB
• SATA

Synchroní sběrnice

• PCI
• PCIe

Sériová sběrnice přenáší data po jedné datové lince, paralelní sběrnice přenáší data po více datových linkách současně

Sériová linka

jeden z nejstarších způsobů komunikace, asynchronní přenos bez hodin obě strany jsou nastaveny na stejnou rychlost která definuje délku vysílání jednoho bitu (baud rate, dříve např 9600 - 115200 Bd, nově až 921600 Bd, Bd = 1bit/s)

Universal Asychronous Receiver Transmitter

speciální zařízení které přijímá a vysílá byty po sériové lince (dva dráty RX a TX)

RX_ST - stav přijímání dat

• bit 0 ready - byla přijata data

RX_DATA - přijatá data

• Čtení z adresy RX_DATA současně odstraní čtená data z UARTu a vymaže příznak ready (pokud nejsou další data)

TX_ST - stav odesílání dat

• bit 0 ready - můžeme zadávat data k odeslání

TX_DATA - data k odeslání

• Zápis do TX_DATA vede rovnou k odesílání data

sběrnice PCI je řízena hodinami, pro správnou činnost je nutná co nejpřesnější synchronizace hodin

1. přenos začíná tím, že iniciátor pořádá arbitra o přidělení sběrnice
2. iniciátor začne vysílání nastavením adresy cílové periferie na AD sběrnici a nastavením příznaku FRAME - rámec přenosu a bitů cmd
3. periférie, která rozpozná svoji adresu nastaví DevSel na 1
4. pokud je cílová periferie (Target) připravena přijmout data, nastaví TRDY na 1.
5. pokud je iniciátor připraven vyslat data, nastaví IRDY na 1
6. pyslání posledních dat je indikováno shozením příznaku FRAME na 0.
7. po ukončení přenosu se signály IRDY, TRDY a DEVSEL vrátí na 0 a sběrnice se uvolní pro další přenos.

PCI je half-duplex, nelze současně posílat data oběma směry.

Více zařízení na sběrnici - pomalá periférie brzdí rychlé periférie, zvyšuje latency všech ostatních periférií.

PCI sběrnice umožňuje pouze hodiny s 33 MHz, nebo 66 MHz.

• To odpovídá 132MB/s nebo 264 MB/s pro 32 bitovou variantu
• To odpovídá 264MB/s nebo 528 MB/s pro 64 bitovou variantu

i malé nepřesnosti v délce vodičů, kvalitě spojů vedou k rozdílným rychlostem šíření signálů to je problém pro vysoké frekvence přenosů

PCIe te peer-to-peer sběrnice, data se posílají jen mezi dvěma zařízeními

je full-duplex, tedy data mohou být posílána oběma směry současně