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`.

Čí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).

RISC (Reduced Instruction Set Computer) a CISC (Complex Instruction Set Computer) jsou dva různé přístupy k návrhu instrukční sady procesoru.

• RISC – reduced instruction set computer:
  • všechny instrukce mají stejnou délku (např. 32 bitů),
  • menší množství jednoduchých a rychlých instrukcí,
  • méně složitých adresních módů,
  • ALU operuje pouze s registry,
  • vhodné pro optimalizaci na úrovni hardware a pipeliningu,
  • více práce na straně kompilátoru/programátora.

• CISC – complex instruction set computer:
  • instrukce mají různou velikost (např. 1–12 bajtů),
  • větší množství komplexních instrukcí,
  • mnoho složitých adresních módů,
  • ALU operuje s registry i pamětí,
  • jednodušší kód, složitější dekódování a provádění,
  • příkladem je architektura x86.

Registry jsou paměťové buňky uvnitř procesoru, které uchovávají mezivýsledky a stav výpočtu. Hrají klíčovou roli při provádění instrukcí.

Příklad specifických registrů u architektury RISC-V:

• `x0` – `zero`: vždy obsahuje nulu (nelze měnit),
• `x1` – `ra`: return address (návratová adresa z funkce),
• `x2` – `sp`: stack pointer,
• `x3` – `gp`: global pointer,
• `x4` – `tp`: thread pointer,
• `x5–x7` – `t0–t2`: dočasné registry,
• `x10–x17` – `a0–a7`: argumenty funkcí,
• `x18–x27` – `s2–s11`: zachovávané registry (callee-saved),
• `pc` – program counter,
• `f0–f31` – registry pro práci s reálnými čísly (floating point).

RISC instrukce mají typicky pevnou délku, například 32 bitů. Jsou navrženy tak, aby se snadno dekódovaly a zpracovávaly.

• bity 0–7 – operace (opcode),
• následují pole pro specifikaci registrů (zdrojových, cílových),
• případně okamžitá hodnota (immediate).

Příklady RISC-V instrukcí:

• `add rd, rs1, rs2` – [rd] ← [rs1] + [rs2]
• `addi rd, rs1, imm12` – [rd] ← [rs1] + imm12
• `lw rd, imm12(rs1)` – [rd] ← Mem[[rs1] + imm12] – načtení slova z paměti
• `sw rs2, imm12(rs1)` – Mem[[rs1] + imm12] ← [rs2] – uložení slova do paměti
• `beq rs1, rs2, imm12` – [pc] ← [pc] + SignImm – skok pokud jsou rs1 a rs2 rovny

Jednocyklový procesor (non-pipelined)

1. Každá instrukce se provádí samostatně, krok za krokem:
   1. Načtení instrukce,
   2. Dekódování,
   3. Provedení,
   4. Paměťový přístup,
   5. Zápis výsledku.
2. Nová instrukce může začít až po dokončení předchozí.
3. Jednoduché řízení, ale nízká propustnost.

Zřetězený procesor (pipelined)

1. Instrukce se dělí na fáze, které se překrývají.
2. Umožňuje paralelní zpracování více instrukcí najednou (v různých fázích).
3. Zvyšuje propustnost bez zvyšování taktovací frekvence.

Pětistupňová pipeline:

1. IF – Instruction Fetch – načtení instrukce z paměti.
2. ID – Instruction Decode – dekódování instrukce, načtení registrů.
3. EX – Execute – výpočet operace (např. sčítání v ALU).
4. MEM – Memory – přístup do paměti (čtení/zápis).
5. WB – Write Back – zápis výsledku do registru.

Obrázek pipeline:

Datový hazard – instrukce potřebuje výsledek, který ještě není zapsán:

• Např.:
  1. `add x1, x2, x3`
  2. `sub x4, x1, x5` ← závislá na výsledku předchozí

• Řešení:
  1. Stall – vložení bublin (no-op instrukcí), zpomalení zpracování,
  2. Forwarding – předání výsledku přímo z fáze EX/MEM/WB před jeho zápisem do registru (zrychlení toku dat).

Řídicí hazard – nevíme, zda instrukce typu `beq` provede skok, než se spočítá podmínka:

• Řešení:
  1. Predikce skoků – odhad, zda bude skok proveden (např. statická/dynamická),
  2. Brzké vyhodnocení – přesun rozhodnutí do dřívější fáze (např. ID), používá se v architektuře MIPS.

Superskalární architektura – využívá více ALU jednotek a přejmenovávání registrů (register renaming), čímž dále zvyšuje paralelismus a zabraňuje konfliktům v zápisu do registrů.

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

Superskalární procesory mají více výpočetních jednotek (např. více ALU), které umožňují paralelní vykonávání více instrukcí.

Rozlišení architektur:

• Statická superskalární architektura – paralelně mohou být vykonávány pouze instrukce jdoucí za sebou.
• Dynamická superskalární architektura – umožňuje paralelní vykonání libovolných instrukcí (nezávislých), lépe využívá hardwarové prostředky.

Dle typu větví:

• Unifikované větve – všechny větve vykonávají všechny typy instrukcí.
• Specializované větve – každá větev je určena pro konkrétní typ instrukcí (např. ALU, load/store).

Pozor na tzv. interferenci skoku – pokud dvě skokové instrukce mají podobnou adresu (např. stejné poslední bity), může to rozhazovat predikce kvůli sdíleným prediktorovým tabulkám.

Skoky (branch instructions) mění tok řízení programu – buď bezpodmíněně (např. `jmp`) nebo podmíněně (např. `beq`, `bne`).

V moderních procesorech, které používají pipeline a prefetch, je potřeba vědět dopředu, kterou instrukci načíst jako další. Pokud není jasné, zda bude podmínka skoku splněna, může dojít ke zdržení nebo ke špatnému větvení, což způsobuje výkonnostní penalizaci.

Řešením je použití predikce skoků – procesor odhaduje, zda bude skok vykonán (taken, T) nebo ne (not taken, NT), a na základě toho spekulativně vykonává instrukce.

• Predikce správná → pipeline pokračuje bez zdržení.
• Predikce chybná → procesor zruší (flushne) spekulativní instrukce a začne znovu.

Statistiky:

• Skoková je každá 4. až 7. instrukce.
• 80 % skoků je podmíněných.
• Z podmíněných: 66 % je na vyšší adresu, 34 % na nižší.
  1. Skoky na nižší adresu jsou většinou v cyklech (pravděpodobnost T ≈ 99 %),
  2. Skoky na vyšší adresu (větvení) mají pravděpodobnost T ≈ 40 %.

Statické prediktory nemění svou predikci v čase – mají pro každou skokovou instrukci pevně danou předpověď, která nezávisí na tom, jak se daná instrukce chovala v minulosti. Tento přístup je velmi jednoduchý na implementaci a nezatěžuje hardware, ale je omezený v přesnosti, protože nedokáže reagovat na změny v běhu programu.

Tento prediktor vždy předpokládá, že skok bude proveden – tedy že řízení programu skutečně skočí na novou adresu.

Tento přístup je založen na pozorování, že většina zpětných skoků (např. v cyklech) bývá skutečně provedena. Neřeší ale, zda jde o cyklus nebo větvení, zkrátka predikuje vždy stejně.

Výhoda: extrémně jednoduchá implementace – není potřeba žádná analýza ani tabulky.

Nevýhoda: ignoruje skutečné chování programu, a tedy může často chybovat, hlavně u větví, které nejsou často prováděny.

Výpočet úspěšnosti:

Bereme v úvahu:

• 66 % skoků je na vyšší adresu (větvení), s pravděpodobností vykonání 40 %,
• 34 % skoků je na nižší adresu (cykly), s pravděpodobností vykonání 99 %.

Spočítáme tedy vážený průměr:

$$ p_{taken} = 0.66 \cdot 0.4 + 0.34 \cdot 0.99 = 0.264 + 0.3366 = 0.6006 $$

Přibližně 60% úspěšnost – to znamená, že v průměru 6 z 10 predikcí bude správných.

Tento prediktor bere v úvahu směr skoku a předpokládá:

• Zpětný skok (na nižší adresu – např. v těle cyklu) → bude vždy vykonán (taken),
• Skok vpřed (na vyšší adresu – např. větvení) → nebude vykonán (not taken).

Tento prediktor vychází z toho, jak programy typicky vypadají:

• cykly se často opakují (např. for, while),
• větvení má nižší pravděpodobnost vykonání.

Tímto přístupem se snaží prediktor inteligentněji odhadnout chování bez potřeby historie. Oproti prediktoru „vždy taken“ má výrazně lepší výsledky.

Výpočet úspěšnosti:

• zpětné skoky (34 %) → predikce = taken → úspěšnost = 99 %,
• skoky vpřed (66 %) → predikce = not taken → úspěšnost = 60 %.

Opět vážený průměr:

$$ p_{BTFNT} = 0.66 \cdot 0.6 + 0.34 \cdot 0.99 = 0.396 + 0.3366 = 0.7326 $$

Tedy přibližně 73% úspěšnost, což je výrazně lepší než u prediktoru „vždy taken“.

Statická predikce je jednoduchá a nezatěžuje hardware, ale neposkytuje dostatečnou flexibilitu při složitějším chování programů.

Dynamické prediktory se snaží zjistit, zda se skoková instrukce provede, a to na základě jejího předchozího chování. Jinými slovy, sledují minulost konkrétní skokové instrukce a podle toho se snaží odhadnout, zda se tentokrát skočí nebo ne.

Protože počet prediktorů v procesoru je omezený (z důvodů výkonu a velikosti), ne každá skoková instrukce má svůj vlastní prediktor. Místo toho se sdílí mezi více instrukcemi.

V praxi bývá počet prediktorů obvykle $2^n$, protože to umožňuje jednoduše použít $n$ nejnižších bitů z adresy skokové instrukce jako index do tabulky prediktorů. Tento přístup je efektivní z hlediska hardwarové implementace.

Tento prediktor je nejjednodušší formou dynamického prediktoru. Používá pouze 1 bit k uchování stavu, což znamená, že má pouze dva možné stavy. Nejjednodušší prediktor, který má pouze 2 stavy.

Má následující stavy:

• 0 – predikce: skok se neprovede (not taken)
• 1 – predikce: skok se provede (taken)

Ve výchozím stavu bývá predikce nastavena na „taken“, což znamená, že se předpokládá, že se skok vykoná. Pokud je predikce správná (odpovídá skutečnosti), stav se nemění. Pokud je predikce chybná, bit se přepne na opačnou hodnotu. Tento přístup je rychlý, ale citlivý na výkyvy – například při střídavém chování skoku (např. skok se provede jednou ano, jednou ne) může často selhávat.

Tento typ prediktoru je rychlý a jednoduchý, ale také snadno podléhá chybným odhadům, pokud se chování skoku často mění.

Tato varianta Smithova prediktoru používá 2 bity k uchování stavu, což umožňuje rozlišit čtyři různé úrovně „jistoty“ ohledně predikce.

Díky dvěma bitům si prediktor může dovolit „chybu navíc“, než změní svůj názor. To znamená, že je stabilnější a méně přecitlivělý na výjimky.

Má čtyři stavy:

• 00 – silná predikce: skok se neprovede
• 01 – slabá predikce: skok se neprovede
• 10 – slabá predikce: skok se provede
• 11 – silná predikce: skok se provede

Výhoda tohoto prediktoru je, že není tak citlivý na náhodnou odchylku. Například, pokud instrukce většinou skáče, ale jednou neskočí, prediktor se nepřepne hned do opačného režimu – místo toho musí být chyba potvrzena ještě jednou, aby došlo k přepnutí.

Tento prediktor je mírně odlišnou variantou 2-bitového Smithova prediktoru. Podobně jako on má čtyři stavy, ale interpretace těchto stavů je zaměřena na zachování hystereze – tedy odolnosti vůči jednorázovým výkyvům.

Hystereze zde znamená, že prediktor nezmění názor ihned po první chybě, ale až po opakované. Tím se eliminuje „přepínání sem a tam“, které by nastávalo u prediktoru bez hystereze, když se chování skoku často mění.

Prediktor má 4 stavy a pro přechod mezi skupinami „skok“ a „neskok“ je třeba dvou po sobě jdoucích opačných výsledků. Díky tomu se předpověď mění méně často a je stabilnější.

Prediktor s hysterezí je v podstatě standardní 2-bitový prediktor – pokud je ale konkrétní zápis výslovně odlišen jako “s hysterezí”, zdůrazňuje právě tuto schopnost stabilního rozhodování.

Nelze jednoznačně říct, který prediktor je nejlepší, protože jejich výkonnost se liší podle konkrétního programu. Některé prediktory jsou lepší při pravidelném chování skoků, jiné při složitějších vzorcích.

Z tohoto důvodu se kvalita prediktorů hodnotí statisticky – například měřením úspěšnosti predikce na sadě různých programů. Tabulka níže ukazuje typické výsledky takového srovnání:

Z tabulky je patrné, že i jednoduchý 1-bitový prediktor přináší výrazné zlepšení oproti statické predikci. Ještě větší úspěšnost pak poskytuje 2-bitová varianta. Prediktor s hysterezí jde ještě dál a dosahuje nejvyšší úspěšnosti ze všech zde uvedených Smithových typů.

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.

Díky tomu má procesor přehled o tom, jak vypadala nedávná historie větvení a může ji využít k přesnější predikci.

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ů.

Varianta korelovaného prediktoru. Místo přímého spojení adresy skoku a historie využívá XOR (bitovou exkluzivní disjunkci) mezi BHR a adresou skoku.

Výpočet indexu: $index = BHR \oplus PC_{\text{lower bits}}$

Výhoda:

• XOR pomáhá rovnoměrněji rozdělit adresy po predikční tabulce,
• snižuje kolize mezi různými skoky (lepší rozlišitelnost).

Kombinuje více prediktorů (např. 2-bitový Smithův + Gshare) a vybírá ten, který má v daném kontextu vyšší úspěšnost.

1-bitový turnajový prediktor funguje následovně:

1. Nechá oba prediktory (P1, P2) spočítat predikci.
2. Pokud se shodují → použije se jejich predikce.
3. Pokud se liší, zvolí se predikce podle toho, který byl naposledy úspěšnější (uloženo v jednom bitu).
4. Po skutečném vykonání skoku se informace o úspěšnosti aktualizuje.

Výhoda:

• výběr nejlepší predikce pro daný typ kódu (cykly, větvení, vzory),
• vyšší úspěšnost než kterýkoli jednotlivý prediktor.

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ě