statnice:bakalar:b0b35apo

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== Architektura počítače; CPU, paměti, subsystémy ====

[[https://fel.cvut.cz/cz/education/bk/predmety/50/99/p5099306.html|B0B35APO]] [[https://cw.fel.cvut.cz/wiki/courses/b35apo/lectures/start|Webové stránky předmětu]] [[https://comparch.edu.cvut.cz|CompArch]] [[https://eval.comparch.edu.cvut.cz|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.


===== 1. Architektura počítače =====

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

==== Architektura ====
=== Von Neumannova 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čů.

=== Harvardská architektura ===

  * 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ášť.

=== Sběrnice ===

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]

{{:statnice:bakalar:pasted:20250609-153435.png}}

==== Kladná čísla ====

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.

=== Datové typy bez znaménka ===

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.

| typ                  | min  | max                                   | počet bytů |
|----------------------|------|----------------------------------------|-------------|
| `unsigned char`      | 0    | 255                                    | 1           |
| `unsigned short`     | 0    | 65 535                                 | 2           |
| `unsigned long`      | 0    | 4 294 967 295                          | 4           |
| `unsigned long long` | 0    | 18 446 744 073 709 551 615             | 8           |

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í:

<code c>
sizeof(unsigned int)
</code>

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

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

=== Zápis čísel v různých soustavách ===

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

<code c>
252 == 0xfc == 0374 == 0b11111100
</code>

Š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:

<code c>
0x123456 // zabírá 3 byty v paměti
</code>

=== Endianita ===

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

| adresa | big endian | little endian |
|--------|------------|----------------|
| 0x400  | 0x12       | 0x78           |
| 0x401  | 0x34       | 0x56           |
| 0x402  | 0x56       | 0x34           |
| 0x403  | 0x78       | 0x12           |

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)

=== Přehled souvisejících pojmů ===

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





==== Celá a reálná čísla ====

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

=== Celá čísla (signed integers) ===

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:
    - Kladné číslo $X$ se reprezentuje běžným způsobem.
    - 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]
$$

=== Jak vytvořit záporné číslo v two’s complement ===

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

Příklad: $-6$

<code text>
6    = 00000110
~6   = 11111001  (negace bitů)
+1   = 11111010  (přičtení 1)
</code>

=== Typy celých čísel v jazyce C ===

| typ        | min                      | max                      | bajtů |
|------------|--------------------------|---------------------------|--------|
| `char`     | -128                     | 127                      | 1      |
| `short`    | -32 768                  | 32 767                   | 2      |
| `long`     | -2 147 483 648           | 2 147 483 647            | 4      |
| `long long`| -9 223 372 ... 808       | 9 223 372 ... 807        | 8      |

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ý]

<tikzjax>

\usepackage{tikz}
\usetikzlibrary{matrix}

\begin{document}
\begin{tikzpicture}
    \matrix (m) [matrix of nodes, nodes={font=\ttfamily}, column sep=0.1cm] {
        150 & = & & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
        +120 & = & & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
        \hline
        14  & = & & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
        270 & = & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
    };
    
\end{tikzpicture}
\end{document}

</tikzjax>

=== Převod celého čísla z binární do desítkové soustavy ===

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)}
$$

=== Převod do vědeckého zápisu (floating point) ===

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.


=== Reálná čísla (float, double) ===

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 |

{{:statnice:bakalar:pasted:20250529-101024.png?400|}}


=== Binární vědecký zápis (normalizace) ===

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

=== Vzorec pro exponent ===

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

{{:statnice:bakalar:pasted:20250529-101535.png?400|}}

=== Speciální případy v IEEE 754 ===

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.

| Exponent     | Mantisa     | Hodnota / Význam                                              |
|--------------|-------------|----------------------------------------------------------------|
| `00000000`   | `0`         | **0.0** – čistá nula (kladná nebo záporná podle znaménka)     |
| `00000000`   | ≠0          | **Denormalizovaná čísla** – velmi malá čísla blízká nule      |
| `00000001`   | `0`         | **Nejmenší normalizované číslo** se skrytou jedničkou         |
| `00000001`–`11111110` | cokoliv | **Normalizovaná čísla**, skrytá 1 v mantise              |
| `11111111`   | `0`         | **+∞ nebo -∞**, podle hodnoty znaménkového bitu              |
| `11111111`   | ≠0          | **NaN** – „Not a Number“, výsledek nedefinované operace      |

=== Denormalizovaná čísla ===

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.

=== Přehled přesností a rozsahů ===

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.

| Typ      | Bitů | Přesnost (cca)     | Rozsah hodnot (přibližně)     |
|----------|------|--------------------|--------------------------------|
| `float`  | 32   | ~7 desetinných míst | ±3,4 · 10³⁸                    |
| `double` | 64   | ~15–17 číslic       | ±1,8 · 10³⁰⁸                   |

**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í.

=== Výpočet převodu desetinného čísla do IEEE 754 ===

  - Urči znaménko (0 = kladné, 1 = záporné).
  - Převeď číslo do binární soustavy (celou i desetinnou část).
  - Normalizuj číslo do tvaru 1.xxxx × 2^e.
  - Exponent ulož jako e + bias (např. +127 pro float).
  - 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**

=== Výpočetní náročnost základních operací (float/double) ===

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

=== Shrnutí ===

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

===== 2. 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.

** 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 **

|Registr | Popis|
|PC | Program counter - dresa právě prováděné (nebo následující) instrukce|
|IR | Instruction register - obsahje kód prováděné instrukce načtený zpaměti |
|GPR | General purpose registers – obecné uživatelské registry, mohou se dělit na data a adresy do paměti, nebo být univerzální|
|SP | Stack Pointer - kazuje na vrchol zásobníku, slouží k organizaci lokálních dat funkcí|
|PSW | Program Status Word – definuje v jakém stavu je procesor |
|IM | Interrupt Mask – kontrola přerušení |
|FPR | Floating point registers – rozšíření procesoru pro práci s reálnými čísly, případně i vektorové/multimediální 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

  - Počáteční nastavení – inicializace PC a PSW
  - Načtení instrukce z paněti z adresy PC (nastav PC -> Přečti obsah do IR -> uprav PC dle délky instrukce)
  - Dekóduj instrukci
  - Proveď instrukci
  - Kontrola přerušení nebo výjimky
  - 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. 

{{:statnice:bakalar:pasted:20250529-123852.png|400}}

 Jednotlivé fáze pro pětistupňovou pipeline jsou -
  - Instruction Fetch - přivedení PC na adreosvý vstup paměti, načtení instrukce
  - Instruction Decode - dokódování opcode (bity 0-7), přímého operandu a načtení registrů
  - EXecution - provedení požadované operace v ALU
  - MEMory - zápis/čtení z paměti
  - 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). 
===== 3. Predikce skoků =====
jak lze predikovat skoky v programu, jak se přiřadí prediktor k instrukci, co je to spekulativní vykonávání instrukcí.

==== Přehled predikce skoků ====
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 ====
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). 

=== Prediktor který vždy předpokládá, že skok bude vykonán ===
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 ===
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 ====
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. 

{{https://gitlab.fel.cvut.cz/b35apo/apo-slides/-/raw/db461f7fffea1e00a25346e49a9a27e35f711e7a/06-predictors/prediction_table-cz.svg}}

=== 1-bitový Smithův prediktor ===
Nejjednodušší prediktor, který má pouze 2 stavy.
<tikzjax>
\usetikzlibrary{arrows.meta,positioning}
\begin{document}

\begin{tikzpicture}[
  >=Stealth,
  every node/.style={font=\sffamily\small},  
  state/.style={circle,draw,thick,
                align=center,
                minimum size=3cm,
                text width=2.8cm},
]
\definecolor{stategreen}{RGB}{144,238,144}
\definecolor{statered}{RGB}{255,182,182}

\node[state,fill=stategreen] (taken)
      {Prediction\\Jump\\\textbf{Taken}\\\textbf{1}};
\node[state,fill=statered,right=4cm of taken] (nottaken)
      {Prediction\\Not jump\\\textbf{Not Taken}\\\textbf{0}};

\path[->,red,thick]
      (taken) edge[bend left=35] node[above]{not taken} (nottaken);
\path[->,green!60!black,thick]
      (nottaken) edge[bend left=35] node[below]{taken} (taken);

\path[->,green!60!black,thick]
      (taken) edge[loop left] node[left]{taken} (taken);
\path[->,red,thick]
      (nottaken) edge[loop right] node[right]{not taken} (nottaken);
\end{tikzpicture}
\end{document}

</tikzjax>

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 ===
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

<tikzjax>
\usepackage{tikz}

\usetikzlibrary{arrows.meta,positioning}
\begin{document}

\begin{tikzpicture}[
    >=Stealth,
    every node/.style={font=\sffamily\small},
    state/.style={circle,draw,thick,
                   align=center,
                   minimum size=3cm,
                   text width=2.8cm},
]
  % colours
  \definecolor{stategreen}{RGB}{144,238,144}
  \definecolor{statered}{RGB}{255,182,182}

  % nodes
  \node[state,fill=stategreen]           (st11) {Prediction\\Jump\\Strongly Taken\\11};
  \node[state,fill=stategreen,right=4cm of st11] (st10) {Prediction\\Jump\\Weakly Taken\\10};
  \node[state,fill=statered,right=4cm of st10] (st01) {Prediction\\Not jump\\Weakly Not Taken\\01};
  \node[state,fill=statered,right=4cm of st01] (st00) {Prediction\\Not jump\\Strongly Not Taken\\00};

  \path[->,green!60!black,thick]
    (st11) edge[loop left]    node[left]{taken}       (st11)
    (st10) edge[bend left=35] node[above]{taken}      (st11)
    (st01) edge[bend left=35] node[above]{taken}      (st10)
    (st00) edge[bend left=35] node[above]{taken}      (st01);

  \path[->,red,thick]
    (st11) edge[bend left=35] node[below]{not taken}  (st10)
    (st10) edge[bend left=35] node[below]{not taken}  (st01)
    (st01) edge[bend left=35] node[below]{not taken}  (st00)
    (st00) edge[loop right]   node[right]{not taken}  (st00);
\end{tikzpicture}
\end{document}

</tikzjax>

=== Hodnocení prediktorů ===
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ů

| Statický prediktor - vždy skočí | 59.25% |
| 1-bitový Smithův prediktor | 68.75% |
| 2-bitový Smithův prediktor | 81.75% |

=== Historie skoků - korelované prediktory ===
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ů. 

{{https://gitlab.fel.cvut.cz/b35apo/apo-slides/-/raw/db461f7fffea1e00a25346e49a9a27e35f711e7a/06-predictors/prediction_BHR-cz.svg}}

== Gshare ==

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.

{{https://gitlab.fel.cvut.cz/b35apo/apo-slides/-/raw/db461f7fffea1e00a25346e49a9a27e35f711e7a/06-predictors/prediction_GShare-cz.svg}}

=== Turnajový prediktor ===
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í:
  - 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.
  - Podle skutečnosti vyber prediktor P1, nebo P2 pro příští predikci.
{{https://gitlab.fel.cvut.cz/b35apo/apo-slides/-/raw/db461f7fffea1e00a25346e49a9a27e35f711e7a/06-predictors/prediction_tournament-cz.svg}}

=== Moderní neuronové prediktory ===
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.

{{https://gitlab.fel.cvut.cz/b35apo/apo-slides/-/raw/db461f7fffea1e00a25346e49a9a27e35f711e7a/06-predictors/prediction_amd-cz.svg}}



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

==== Hiearchie ====
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.

=== Registers ===
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 ===
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.
=== Organizace Cache ===
  * **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.
== Plně asociativní cache ==
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á.
{{:statnice:bakalar:pasted:20250602-114623.png?300}}


== Přímo mapovaná cache ==
  * 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**:

{{:statnice:bakalar:pasted:20250602-152014.png?750}}

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

{{:statnice:bakalar:pasted:20250602-153331.png?750}}

**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 
== N-asociativní cache ==
  * **Obecnější model cache** - $\text{stupeň asociace} = n$

{{:statnice:bakalar:pasted:20250602-153444.png?750}}

=== RAM ===

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.

=== Disk ===

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



===== 5. Vstupně výstupní periferie =====
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á vs paralelní sběrnice ===
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)

=== UART ===
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

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

  - přenos začíná tím, že iniciátor pořádá arbitra o přidělení sběrnice
  - 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
  - periférie, která rozpozná svoji adresu nastaví DevSel na 1
  - pokud je cílová periferie (Target) připravena přijmout data, nastaví TRDY na 1.
  - pokud je iniciátor připraven vyslat data, nastaví IRDY na 1
  - pyslání posledních dat je indikováno shozením příznaku FRAME na 0.
  - 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

=== PCIe ===
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ě
Trace: • b4b36zui • b0b35lsp • b0b01pst • be4b39vgo • b0b01lgr • b0b35apo • b4b35psr • b4b32pks • b0b01ma1
Search

Navigation

Print/export

Tools

QR Code
