Architektura počítače; CPU, paměti, subsystémy

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

• Paměť v počítači si můžeme představit jako vrstvy – od těch nejrychlejších a nejdražších, které jsou přímo v procesoru, až po nejpomalejší a nejlevnější, které slouží k dlouhodobému uložení dat.
• Tento systém je založen na tzv. paměťové hierarchii, kde platí, že čím je paměť blíže procesoru, tím je rychlejší, ale menší a dražší.
• Základním principem, proč hierarchie funguje efektivně, je časová a prostorová lokalita přístupu – programy totiž zpravidla pracují jen s malou částí dat najednou, a často s těmi samými nebo sousedními položkami.
• Paměť je technicky implementovaná jako pole adresovaných buněk (většinou o velikosti jednoho bytu). Každá buňka má přiřazenou adresu a obsahuje hodnotu – data uložená v paměti.
• Velikost dostupné paměti je omezena šířkou adresy – například 16bitový adresní prostor pojme 64 KiB, zatímco 32bitový až 4 GiB.

• Mezi základní parametry, které paměť charakterizují, patří:
  • Vybavovací doba – čas od vzniku požadavku po nalezení dat.
  • Doba přístupu – vybavovací doba + čas nutný k obnovení obsahu nebo zadání dalšího požadavku.
  • Propustnost – kolik dat zvládne paměť obsloužit za jednotku času.

• Paměti dělíme také podle možnosti zápisu:
  • ROM – Read Only Memory, nelze přepisovat za běhu.
  • RAM – Random Access Memory, lze číst i zapisovat v libovolném pořadí.
    • SRAM – statická RAM, rychlá, ale drahá a s větší spotřebou.
    • DRAM – dynamická RAM, levnější, ale pomalejší, nutno pravidelně obnovovat.

• Podle uchování dat po odpojení napájení rozlišujeme:
  • Permanentní paměti – data zůstávají zachována i po výpadku proudu.
  • Volatilní paměti – data jsou ztracena při vypnutí systému.

• Diagram ukazuje klasickou paměťovou hierarchii od nejrychlejších registrů po nejpomalejší diskové úložiště.
• Čím blíže k procesoru, tím je paměť rychlejší, menší a dražší.
• Porovnání parametrů různých typů pamětí:
  • L1 SRAM – 32 kB, velmi rychlá (0.2–2 ns), drahá (10 Kč/kB).
  • Sync SRAM – 1 MB, rychlá (0.5–8 ns/word), velmi drahá (300 Kč/MB).
  • DDR3 (DRAM) – 16 GB, střední propustnost (15 GB/s), běžná RAM (123 Kč/GB).
  • HDD – 3 TB, velmi pomalé (100 MB/s), levné (1 Kč/GB).
• Některá data mohou existovat ve více kopiích (např. L1, L2, RAM).
• Aby nedocházelo k nesrovnalostem, musí být zajištěna koherence cache a konzistence dat – např. při vícejádrovém zpracování (SMP).

• 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ů.
• Registry jsou extrémně rychlé, protože jsou fyzicky integrovány přímo v procesorovém jádru. Přístup do nich trvá jen několik málo taktů.
• Protože jsou velmi omezené kapacitou, používají se pouze pro nejčastěji potřebná data – např. meziproměnné, čítače, ukazatele atd.

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

• RAM (Random Access Memory) umožňuje přístup ke kterékoli buňce ve stejném čase – tedy náhodný přístup. To ji odlišuje například od sekvenčních úložišť jako pásky.
• I když má RAM vysokou propustnost, její latence je výrazně vyšší než u registrů nebo cache. To je důvodem, proč se mezi RAM a procesorem často vkládají cache paměti.
• Systémy s více paměťovými kanály (dual-channel, quad-channel atd.) umožňují zvýšit šířku přenosového pásma mezi RAM a procesorem.

• 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).

• Disky tvoří spodní vrstvu paměťové hierarchie. Jsou nejpomalejší, ale nejlevnější na jednotku velikosti, a mají neomezeně dlouhou dobu uchování dat.
• Pokud dojde RAM, může operační systém část obsahu paměti „odložit“ na disk – to se nazývá swapování nebo použití virtuální paměti. Tento mechanismus je funkční, ale výrazně zpomaluje běh programů.
• SSD disky jsou v současnosti mnohem rychlejší než HDD, protože nemají pohyblivé mechanické části – data se čtou elektronicky, nikoli fyzickým pohybem hlavice jako u HDD.

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ž L1. 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ě není 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 jinak pojmenovaný L1 cache – každé jádro má zde vlastní L0d, L0i, L1, L2 a sdílený L3).

• Cache slouží jako vyrovnávací paměť mezi procesorem a RAM, urychluje přístup k často používaným datům, a tím snižuje latenci a zvyšuje výkon.
• Optimalizace datových struktur programu tak, aby se vešla dobře do cache, může vést k masivnímu nárůstu výkonu.

• Word size (WS) – velikost slova je podle architektury systému 32bit → 32bitová slova, 64bit → 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 lze adresovat jeden řádek.
• Number of sets (SN) – počet řádek v jedné cachovací tabulce, většinou o velikosti $2^n$.
• Index – do řádku cache, odpovídá počtu řádků cache, většinou musí být $2^n$; používá se $n$ bitů z adresy, obvykle nejnižších $b+i \rightarrow n+b+i$ bitů.
• TAG – obsahuje zbytek adresy kromě bitů použitých pro index a offset, tedy $b+n+i \rightarrow$ délka adresy.
• Validity bit – bit platnosti, indikuje, zda jsou data na řádku platná.
• Dirty bit – rozšiřující pole v obsahu paměti. Indikuje, že v cache je jiná hodnota než v hlavní paměti.
• Degree of associativity (N) – počet tabulek.
• Number of blocks (BN) – počet řádků přes všechny tabulky, je roven $N \times \text{Number of sets}$.
• Cache hit – situace, kdy se požadovaná data nachází v cache.
• Cache miss – situace, kdy data v cache nejsou a musí se načíst z pomalejší paměti.
• Cache line nebo Cache block – základní kopírovatelná jednotka mezi hierarchickými úrovněmi (typicky 8B až 1KB).
• Hit rate – počet paměťových přístupů obsloužených danou úrovní cache dělený celkovým počtem přístupů.
• Miss rate – $1 - \text{Hit rate}$.
• Average Memory Access Time (AMAT) – průměrná doba přístupu k paměti: $AMAT = \text{HitTime} + \text{MissRate} \times \text{MissPenalty}$.
  • Pro vícestupňové cache se AMAT počítá rekurzivně podle stejného vztahu.
• Cache replacement policy – pravidla pro výběr, která položka bude z cache odstraněna:
  • Random – náhodná volba.
  • LRU (Least Recently Used) – odstraní nejdéle nepoužitou položku.
  • LFU (Least Frequently Used) – odstraní položku s nejmenší četností použití.
  • ARC (Adaptive Replacement Cache) – adaptivní algoritmus kombinující LRU a LFU.
• Write through (propsání skrz) – při každém zápisu se data uloží do cache i hlavní paměti.
• Write back – data se uloží pouze do cache, a označí se jako “dirty”. Do hlavní paměti se zapíší až při odstranění z cache.

Znamená, že $\text{Degree of associativity} = \text{Number of blocks}$. Každý řádek má svou vlastní tabulku, což znamená, že index má 0 bitů a celá adresa kromě offsetu se ukládá do tagu.

• V plně asociativní cache neexistuje pevné přiřazení adresy do konkrétního řádku. Jakýkoli blok z paměti může být uložen kamkoli do cache. To zajišťuje maximální flexibilitu.
• Díky absenci indexu není třeba řešit kolize způsobené stejnými indexy – všechny bloky soutěží o všechna místa.
• Tag musí obsahovat téměř celou adresu (kromě offsetu), protože není jiný způsob, jak určit, které slovo je právě v cache.

• Vlastnosti:
  • Nemusíme nahrazovat záznamy v cache, dokud není plně zaplněna.
    • To znamená, že cache dokáže efektivněji využít svou kapacitu a zvyšuje se pravděpodobnost cache hitu.
  • Je velmi drahá na implementaci, proto se používá pouze pro malé paměti.
    • Nutnost porovnávat všechny tagy najednou při každém přístupu zvyšuje komplexitu a spotřebu.
  • Používá se např. v TLB (Translation Lookaside Buffer), kde je potřeba extrémní rychlost a malá velikost.
    • TLB je specializovaná cache pro překlad virtuálních adres na fyzické – zde má každá mikrosekunda význam, a malý rozsah přístupů odpovídá malému počtu záznamů.

• 1-cestná cache → stupeň asociace = 1, tedy pouze jedna tabulka.
• $\text{Number of sets} = \text{Number of blocks}$.
• Index má délku $log_2(\text{Number of sets})$ bitů.

• V přímo mapované cache je každý blok z paměti jednoznačně přiřazen právě k jednomu místu (setu) v cache – tedy žádná flexibilita.
• Pokud dva různé bloky z hlavní paměti spadnou na stejné místo, musí si navzájem přepisovat obsah cache – to může vést ke zvýšenému počtu missů.
• Tag je kratší, protože část adresy je vyjádřena indexem.

• Schéma:

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

• Vlastnosti:
  • Hlavní typ cache u mikrokontrolerů a levných procesorů.
    • Důvodem je jednoduchá a levná implementace, která nevyžaduje složité vyhledávání a porovnávání tagů.
  • Má vysokou pravděpodobnost kolizí – může dojít k vyřazení záznamu, i když cache není plná.
    • To je způsobeno tím, že více různých adres může sdílet stejný index.
  • Každou adresu lze zařadit pouze do jednoho místa v cache tabulce.
    • Výsledkem je nižší hit rate oproti flexibilnějším typům cache.

• Obecnější model cache, kde je stupeň asociace $n$ – tzn. že každý set obsahuje $n$ bloků.

• Tento typ cache kombinuje výhody předchozích dvou přístupů:
  • Každá paměťová adresa směřuje do konkrétního setu (jako u přímo mapované), ale v rámci tohoto setu může být uložena v libovolném z $n$ bloků.
  • Tím se snižuje pravděpodobnost kolizí, protože více položek může sdílet jeden set bez vzájemného přepisování.
  • Implementace je jednodušší než u plně asociativní cache, protože se porovnávají tagy jen v rámci jednoho setu, ne celé cache.

• Tento typ organizace nabízí kompromis mezi plně asociativní a přímo mapovanou cache:
  • + Lepší využití paměti a vyšší hit rate než přímo mapovaná.
  • + Nižší složitost a režie než plně asociativní.
  • − Může docházet ke konfliktům, ale méně často než u přímého mapování.

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 čtení a zápis do periferií provádí zápisem do vyhrazené oblasti v paměťovém prostoru.
• Periferie při inicializaci získají svůj vlastní paměťový rozsah, přes který komunikují s CPU.
• Address Decoder rozhoduje, ke které periferii daný paměťový přístup patří.
  • Asynchroní sběrnice: USB, SATA
  • Synchroní sběrnice: PCI, PCIe
• Tento způsob je jednoduchý na implementaci, přehledný a často používaný v embedded systémech.
• Komunikace přes paměťovou mapu je vhodná pro zařízení, která nepotřebují složité řízení přenosu.

• Paralelní sběrnice přenáší více bitů najednou, každým vodičem jeden bit.
  • Vyšší propustnost, ale více vodičů = vyšší nároky na prostor a synchronizaci.
• Sériová sběrnice přenáší data bit po bitu jedním vodičem.
  • Nižší náklady a menší fyzické rozměry – dnes preferovaná varianta i pro vysokorychlostní přenosy.
• Paralelní sběrnice se používaly u starších zařízení (např. ATA), sériové dnes dominují (např. USB, PCIe).

• Jeden z nejstarších a nejjednodušších způsobů komunikace.
• Asynchronní přenos bez hodin – vysílač a přijímač musejí být nastaveny na stejnou přenosovou rychlost (baud rate).
  • Např. 9600 Bd, 115200 Bd, nově až 921600 Bd (Bd = 1 bit/s).
• UART (Universal Asynchronous Receiver/Transmitter) – obvod pro obousměrný sériový přenos:
  • Využívá dvě linky: TX (transmit) a RX (receive).

• Paměťově mapované registry UARTu:
• RX_ST – stav přijímání dat
  • bit 0: ready – byla přijata data
• RX_DATA – čtení přijatých dat
  • čtením z této adresy se data přečtou a příznak ready se smaže
• TX_ST – stav vysílání
  • bit 0: ready – UART je připraven k odeslání
• TX_DATA – zápis dat k odeslání
  • zápis do registru rovnou spouští odeslání po TX

• Half-duplex – data mohou proudit pouze jedním směrem v daný čas.
  • Např. klasický PCI – nelze současně odesílat i přijímat.
• Full-duplex – data mohou proudit oběma směry současně.
  • Např. PCIe – vyšší efektivita přenosu.

• Data nejsou přenášena podle společného hodinového signálu.
• Používají se tam, kde nelze garantovat přesnou synchronizaci nebo to není potřeba.
  • USB – univerzální rozhraní pro připojení periferií.
  • SATA – rozhraní pro připojení disků.

• Přenos je řízen společným hodinovým signálem, všechna zařízení se musí synchronizovat.
  • PCI
  • PCIe

• Paralelní synchronní sběrnice, half-duplex.
• Počáteční přenos vyžaduje řízení přístupu pomocí arbitra.
• Iniciátor nastaví adresu a příznak FRAME – tím začíná rámec přenosu.
• Cílové zařízení (Target) odpoví signálem DEVSEL, že rozpoznalo svou adresu.
• Data se přenášejí, když jsou oba signály TRDY (Target Ready) a IRDY (Initiator Ready) aktivní.
• Přenos končí shozením FRAME na 0.
• Po přenosu všechny signály přejdou zpět na 0 a sběrnice je opět volná.

• Nevýhody:
• Half-duplex – nelze komunikovat oběma směry současně.
• Sdílená sběrnice – pomalá periferie brzdí všechny ostatní.
• Omezená přenosová rychlost – 33 nebo 66 MHz:
  • 32bit: 132 MB/s nebo 264 MB/s
  • 64bit: 264 MB/s nebo 528 MB/s

• Sériová sběrnice, point-to-point (peer-to-peer).
• Full-duplex – data mohou proudit současně v obou směrech.
• Každé spojení je realizováno jako samostatný link – nedochází ke sdílení přenosového pásma.
• Velmi vysoké rychlosti, ale vyžaduje kvalitní spoje – i drobné rozdíly v délce vodičů nebo kvalitě mohou narušit komunikaci.
• Nahrazuje klasické PCI u moderních zařízení (grafické karty, SSD, síťové adaptéry apod.).