The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b0b35apo [2025/06/09 16:31] – [Zápis čísel v různých soustavách] zapleka3
+++ statnice:bakalar:b0b35apo [2025/06/09 21:41] (current) – zapleka3
@@ Line 1: / Line 1: @@
-==== Architektura počítače; CPU, paměti, subsystémy ====
+====== 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]]
@@ Line 106: / Line 106: @@
 </code>
-===== Endianita =====
+=== 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.
@@ Line 134: / Line 134: @@
   * ARM: může být obojí (většinou little endian)
-===== Přehled souvisejících pojmů =====
+=== Přehled souvisejících pojmů ===
   * **bit** – nejmenší jednotka informace, může nabývat hodnoty 0 nebo 1.
@@ Line 146: / Line 146: @@
-==== Celá a reálná čísla ====
-Záporná čísla lze zakódovat různými způsoby:
-- první bit bude znaménko
-nevýhodou je existence +0 a -0 a potřeba nového algoritmu pro sčítání
-- dvojkový doplněk
-pro $X>0$ je reprezentace $X$
-pro $X<0$ je reprezentace $2^k - |X|$
-sčítání je stejné jako pro kladná čísla
--bitová -1 je 11111111
-+(-1) je 101+11111111=100000100, devátý bit se do reprezentace
-čísla nevejde, tedy výsledek je 101+11111111=100
-rozsah čísel reprezentovaných k-bity je $-2^{k-1}$ až $2^{k-1}-1$
-nemusíme navrhovat obvod pro odčítání, jelikož operaci $A-B$ můžeme provést jako $A+(-B)$
-důležité je zjistit opačné číslo $-B$
-záporné $X$ je $2^k - |X|$, pokud znegujeme každý bit, dostaneme $(2^k - 1) - |X|$
-postup:
-  * znegujeme všechny bity čísla X
-  * přičteme 1
-V jazyce C jsou typy:
-| typ | min | max | počet bytů |
-| 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 036 854 775 808 | 9 223 372 036 854 775 807 | 8 |
-Při sčítání čísel může dojít k přetečení:
-<tikzjax>
-\usepackage{tikz}
-\usetikzlibrary{matrix}
-\begin{document}
-\begin{tikzpicture}
-    \matrix (m) [matrix of nodes, nodes={font=\ttfamily}, column sep=0.1cm] {
-& = & & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
-        +120 & = & & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
-        \hline
-  & = & & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
-& = & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
-    };
-\end{tikzpicture}
-\end{document}
-</tikzjax>
-Pro převod celých čísel z dvojkové do desítkové soustavy obecně platí vztah
-$$ \sum_{i=0}^{k-1} b_i \cdot 2^i $$
-kde $k$ je počet cifer a $b_i$ je hodnota cifry na daném indexu.
-Pro příklad
-$$ 0100101_{(2)} = 2^0 + 2^2 + 2^5 = 37_{(10)} $$
-Stejný princip lze aplikovat i na reálná čísla za předpokladu, že posuneme spodní hranici sumy do záporných čísel
-$$ \sum_{i=-j}^{k} b_i \cdot 2^i $$
-Pro příklad
-$$ 0100101,11_{(2)} = 2^{-2} + 2^{-1} + 2^0 + 2^2 + 2^5 = 37,75_{(10)} $$
-Zavádíme též obdobu věděckého zápisu
-$$ 110110000000000,0_{(2)} = 1,1011_{(2)} \cdot 2^{14} = 1,1011E14 = 29696_{(10)} $$
-$$ −0,00000000000000011101_{(2)} = −1,1101_{(2)} \cdot 2^{−16} = −1.1101E − 16 $$
-(Vědecká notace se vyznačuje také tím, že žádné číslo kromě 0 nezačíná 0)
-Obecně užívaný zápis desetinných čísel je standardizován dle IEEE-754.
-Ten definuje způsob zakódování desetinných čísel do 32, resp. 16/64/128, bitů.
-{{:statnice:bakalar:pasted:20250529-101024.png?400|}}
-Pro příklad
-$$ 0,828125_{(10)} = 2^{-1} + 2^{-2} + 2^{-4} + 2^{-6} = 0,110101_{(2)} $$
-Nejprve převedeme číslo do věděcké notace
-$$ 0,110101_{(2)} = 1,10101E-1 $$
-Na první pohled vidíme znaménko (kladné -> 0) a mantisu (10101).
-Exponent se zapisuje v tzv. posunuté formě. Posun lze stanovit jako
-$$ 2^{j-1}-1 $$
-kde $j$ je počet bitů pro vyjádření exponentu. Vždy jde o kladné číslo, pro 8bit jde o posun o 127.
-Exponent v našem příkladu vypočteme tedy jako $$ 2^{8-1}-1 -1 = 127 -1  = 126$$
-Nyní můžeme hledané desetinné číslo zapsat jako
-{{:statnice:bakalar:pasted:20250529-101535.png?400|}}
-Podle hodnoty exponentu rozlišujeme navíc speciální případy
-|Exponent |Mantisa |Hodnota|
-|00000000 | 0 | 0.0 – čistá nula|
-|00000000 |nenulová | Denormalizovaná čísla blízká 0|
-|00000001 |0 | nejmenší normalizované číslo se skrytou 1 v mantise|
-|1 až 254 |cokoliv | normalizovaná čísla, skrytá 1 v mantise|
-|11111111 |0 | nekonečno|
-|11111111 |nenulová | NaN chybná hodnota|
-Pozor... kontrola rovnosti při operacích s desetinnými čísly může [[https://www.cs.unc.edu/~smp/COMP205/LECTURES/ERROR/lec23/node4.html|selhat]]
-=== Denormalizovaná čísla ===
-  * čísla které mají exponent nulový ale mantisu nenulovou.
-  * Umí vyjadřovat extrémně malá čísla
-  * Klasicky mají čísla v mantise "implicitní 1" před desetinou čárkou
-  * denormalizovaná čísla umí zobrazit čísla v mantise typu $0.0001\text{a další rozvoj}$, zatímco u normalizovaných čísel je v mantise vždy $1.000\text{a další rozvo}j$
-  * Většinou o hodně pomalejší výpočet (někdy až o stovky cyklů)
-  * Na některých HW platformách nejsou podporovány (ARM Neon, staré verze CUDA, legacy architektury)
-=== Operace podle rychlosti (nejrychlejší po nejpomalejší, seřazeno jako $\geq$) ===
-  - Sčítání odčítání
-  - Násobení
-  - Dělení
-  - Odmocnina
----------
 ==== Celá a reálná čísla ====
@@ Line 533: / Line 390: @@
 === Výpočet převodu desetinného čísla do IEEE 754 ===
-  - Převeď číslo do binárního zápisu
-  - Převeď desetinnou část opakovaným násobením dvěma
-  - Normalizuj – posuň čárku k první jedničce
-  - Zaznamenej exponent (včetně posunu)
-  - Mantisa = čísla za čárkou (bez úvodní 1)
-Příklad:
+  - 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.
--12.625_{(10)} = -1100.101_{(2)} = -1.100101 \cdot 2^3
+  - 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
-  * Exponent: $3 + 127 = 130 = 10000010$
+  * Binárně: 1100.101 → normalizace: 1.100101 × 2³
-  * Mantisa: `100101` → doplněná na 23 bitů
+  * Exponent: 3 + 127 = 130 → binárně: 10000010
+  * Mantisa: 10010100000000000000000
-Výsledný IEEE zápis: 1 10000010 10010100000000000000000
+Výsledný IEEE 754 zápis: **1 10000010 10010100000000000000000**
 === Výpočetní náročnost základních operací (float/double) ===
@@ Line 569: / Line 422: @@
   * 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 **
+==== RISC vs. CISC architektura ====
-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.
+**RISC (Reduced Instruction Set Computer)** a **CISC (Complex Instruction Set Computer)** jsou dva různé přístupy k návrhu instrukční sady procesoru.
-** Registry **
+  * **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.
-|Registr | Popis|
+  * **CISC** – complex instruction set computer:
-|PC | Program counter - dresa právě prováděné (nebo následující) instrukce|
+    * instrukce mají různou velikost (např. 1–12 bajtů),
-|IR | Instruction register - obsahje kód prováděné instrukce načtený zpaměti |
+    * větší množství komplexních instrukcí,
-|GPR | General purpose registers – obecné uživatelské registry, mohou se dělit na data a adresy do paměti, nebo být univerzální|
+    * mnoho složitých adresních módů,
-|SP | Stack Pointer - kazuje na vrchol zásobníku, slouží k organizaci lokálních dat funkcí|
+    * ALU operuje s registry i pamětí,
-|PSW | Program Status Word – definuje v jakém stavu je procesor |
+    * jednodušší kód, složitější dekódování a provádění,
-|IM | Interrupt Mask – kontrola přerušení |
+    * příkladem je architektura x86.
-|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í **
+=== Registry ===
-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.
+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í.
-** Porovnání jednocyklového procesoru a zřetězeného zpracování instrukcí **
+| Registr | Popis |
+|--------|-------|
+| `PC` | Program Counter – adresa právě prováděné (nebo následující) instrukce |
+| `IR` | Instruction Register – obsahuje kód prováděné instrukce načtený z paměti |
+| `GPR` | General Purpose Registers – obecné uživatelské registry (někdy oddělené na datové a adresové), nebo univerzální |
+| `SP` | Stack Pointer – ukazuje na vrchol zásobníku, využívá se při volání funkcí a správě lokálních dat |
+| `PSW` | Program Status Word – definuje stav procesoru (např. příznaky přetečení, znaménka, nulový výsledek) |
+| `IM` | Interrupt Mask – kontrola přerušení (která přerušení mohou být obsloužena) |
+| `FPR` | Floating Point Registers – rozšíření pro práci s reálnými čísly a často i vektorovými či SIMD operacemi |
-Jednocyklový procesor funguje asi takto
+**Příklad specifických registrů u architektury RISC-V:**
-  - Počáteční nastavení – inicializace PC a PSW
+  * `x0` – `zero`: vždy obsahuje nulu (nelze měnit),
-  - Načtení instrukce z paněti z adresy PC (nastav PC -> Přečti obsah do IR -> uprav PC dle délky instrukce)
+  * `x1` – `ra`: return address (návratová adresa z funkce),
-  - Dekóduj instrukci
+  * `x2` – `sp`: stack pointer,
-  - Proveď instrukci
+  * `x3` – `gp`: global pointer,
-  - Kontrola přerušení nebo výjimky
+  * `x4` – `tp`: thread pointer,
-  - Opakuj od kroku 2
+  * `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).
+=== Formát RISC instrukcí ===
-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.
+{{:statnice:bakalar:pasted:20250609-165038.png}}
-Tomuto procesu se také jinak říká pipelining.
+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
+=== Porovnání: jednocyklový vs. zřetězený procesor ===
+**Jednocyklový procesor (non-pipelined)**
+  - Každá instrukce se provádí samostatně, krok za krokem:
+    - Načtení instrukce,
+    - Dekódování,
+    - Provedení,
+    - Paměťový přístup,
+    - Zápis výsledku.
+  - Nová instrukce může začít až po dokončení předchozí.
+  - Jednoduché řízení, ale nízká propustnost.
+**Zřetězený procesor (pipelined)**
+  - Instrukce se dělí na fáze, které se překrývají.
+  - Umožňuje paralelní zpracování více instrukcí najednou (v různých fázích).
+  - Zvyšuje propustnost bez zvyšování taktovací frekvence.
+**Pětistupňová pipeline:**
+  - **IF** – Instruction Fetch – načtení instrukce z paměti.
+  - **ID** – Instruction Decode – dekódování instrukce, načtení registrů.
+  - **EX** – Execute – výpočet operace (např. sčítání v ALU).
+  - **MEM** – Memory – přístup do paměti (čtení/zápis).
+  - **WB** – Write Back – zápis výsledku do registru.
+Obrázek pipeline:
 {{:statnice:bakalar:pasted:20250529-123852.png|400}}
- Jednotlivé fáze pro pětistupňovou pipeline jsou -
+==== Problémy při zřetězeném zpracování – datové a řídicí hazardy ====
-  - 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ů
+ **Datový hazard** – instrukce potřebuje výsledek, který ještě není zapsán:
-  - EXecution - provedení požadované operace v ALU
-  - MEMory - zápis/čtení z paměti
+  * Např.:
-  - Write Back - zpětný zápis výsledků do pole registrů pro meziregistrové instrukce a paměti
+    - `add x1, x2, x3`
+    - `sub x4, x1, x5` ← závislá na výsledku předchozí
+  * Řešení:
+    - **Stall** – vložení bublin (no-op instrukcí), zpomalení zpracování,
+    - **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í:
+    - **Predikce skoků** – odhad, zda bude skok proveden (např. statická/dynamická),
+    - **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é 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í.
+==== Superskalární paralelismus a větvení ====
+**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.
 ==== 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í.
+Skoky (branch instructions) mění tok řízení programu – buď bezpodmíněně (např. `jmp`) nebo podmíněně (např. `beq`, `bne`).
-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.
+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.
-- 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.
+Ř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**.
-Při skoku na vyšší adresu je pravděpodobnost skoku 40% a při skoku na nižší adresu 99%.
+  * **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žší**.
+    - Skoky na nižší adresu jsou většinou v cyklech (pravděpodobnost T ≈ 99 %),
+    - Skoky na vyšší adresu (větvení) mají pravděpodobnost T ≈ 40 %.
 ==== 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 ===
+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 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 "vždy taken" ===
+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.
+=== Prediktor BTFNT (Backwards Taken, Forwards Not Taken) ===
+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
+$$
-=== Prediktor BTFNT ===
+Tedy přibližně **73% úspěšnost**, což je **výrazně lepší** než u prediktoru „vždy taken“.
-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$.
+Statická predikce je jednoduchá a nezatěžuje hardware, ale neposkytuje dostatečnou flexibilitu při složitějším chování programů.
 ==== 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.
+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ě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.
+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.
 {{https://gitlab.fel.cvut.cz/b35apo/apo-slides/-/raw/db461f7fffea1e00a25346e49a9a27e35f711e7a/06-predictors/prediction_table-cz.svg}}
 === 1-bitový Smithův prediktor ===
+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.
 <tikzjax>
@@ Line 690: / Line 683: @@
 </tikzjax>
-Má stavy:
+Má následující stavy:
-  * 0 - predikce not taken
+  * 0 – predikce: skok se neprovede (not taken)
-  * 1 - predikce 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í.
+=== 2-bitový Smithův prediktor ===
+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.
-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ý.
+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.
-== 2-bitový Smithův prediktor ===
+Má čtyři stavy:
--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.
+  * 00 – silná predikce: skok se neprovede
+  * 01 – slabá predikce: skok se neprovede
+  * 10 – slabá predikce: skok se provede
+  * 11 – silná predikce: skok se provede
-Má 4 stavy:
+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í.
-  * 00 - predikce not taken
-  * 01 - predikce weakly not taken
-  * 10 - predikce weakly taken
-  * 11 - predikce taken
 <tikzjax>
@@ Line 744: / Line 743: @@
 </tikzjax>
+=== 2-bitový prediktor s hysterezí ===
+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ší.
+{{:statnice:bakalar:pasted:20250609-180030.png}}
+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í.
 === 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.
+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í:
-Jediná možnost je statistická analýza různých programů.
+| Typ prediktoru | Úspěšnost predikce |
-% tabulka s úspěšností prediktorů
+|----------------|---------------------|
+| Statický prediktor – vždy skočí | 59.25 % |
+| 1-bitový Smithův prediktor | 68.75 % |
+| 2-bitový prediktor s hysterezí | 83.50 % |
-| Statický prediktor - vždy skočí | 59.25% |
+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ů.
-| 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.
+  * 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.
+  * 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ů.
@@ Line 767: / Line 782: @@
 == 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.
+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).
 {{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.
+Kombinuje více prediktorů (např. 2-bitový Smithův + Gshare) a vybírá ten, který má **v daném kontextu vyšší úspěšnost**.
-Má lepší úspěšnost než korelované prediktory.
+**1-bitový turnajový prediktor** funguje následovně:
+  - Nechá **oba prediktory (P1, P2)** spočítat predikci.
+  - Pokud se **shodují** → použije se jejich predikce.
+  - Pokud se **liší**, zvolí se predikce podle toho, **který byl naposledy úspěšnější** (uloženo v jednom bitu).
+  - 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.
-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}}
@@ Line 796: / Line 820: @@
 ==== 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.
+  * 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.
+{{:statnice:bakalar:pasted:20250609-182543.png}}
+{{/mnt/data/1609b61d-74e8-4463-a3f1-dd677d0047e0.png}}
+  * 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).
 === Registers ===
-Nejrychlejší paměť s nejnižší latancí, která je přímo v jádrech procesoru.
+  * Nejrychlejší paměť s nejnižší latancí, která je přímo v jádrech procesoru.
-Obsahuje data běžícího programu, ale nikoliv instrukce programu.
+  * 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.).
+  * 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ů.
+  * 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.
-=== Cache ===
+=== 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.
+  * **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.
+=== 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).
+  * 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 ====
 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**
+  * **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.
+    * 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).
+    * 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).
+    * 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.
+  * 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.
 === 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.
+  * **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
+  * **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).
+  * **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 musí být o množství $2^n$
+  * **Number of sets (SN)** – počet řádek v jedné cachovací tabulce, většinou o velikosti $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).
+  * **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ě toho co už vyjadřuje index, takže je to rozsah $b+n+i \rightarrow \text{délka adresy}$
+  * **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á.
+  * **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í
+  * **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
+  * **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}$
+  * **Number of blocks (BN)** – počet řádků přes všechny tabulky, je roven $N \times \text{Number of sets}$.
-  * **Cache hit** (zásah) - pojmenování situace, kdy požadovaná hodnota v cache je.
+  * **Cache hit** – situace, kdy se požadovaná data nachází v cache.
-  * **Cache miss** - výpadek, data v cache ješte nejsou
+  * **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$, do $1KB$)
+  * **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ý všemi přístupy
+  * **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 - Hit rate
+  * **Miss rate** – $1 - \text{Hit rate}$.
-  * Average Memory Access Time (AMAT) - $AMAT = \text{HitTime} + \text{MissRate} * \text{MissPenalty}$
+  * **Average Memory Access Time (AMAT)** – průměrná doba přístupu k paměti: $AMAT = \text{HitTime} + \text{MissRate} \times \text{MissPenalty}$.
-  * AMAT pro více urovňovou cache lze spočítat rekurzivní použitím výše uvedeného vztahu
+    * Pro vícestupňové cache se AMAT počítá rekurzivně podle stejné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
+  * **Cache replacement policy** – pravidla pro výběr, která položka bude z cache odstraněna:
-    * Random - vybraná položka je náhodná
+    * **Random** – náhodná volba.
-    * LRU (least recently used) - nejdéle nepoužitá položka
+    * **LRU (Least Recently Used)** – odstraní nejdéle nepoužitou položku.
-    * LFU (least frequently used) - sleduje jak často se k položkám přistupuje
+    * **LFU (Least Frequently Used)** – odstraní položku s nejmenší četností použití.
-    * ARC (Adaptive replacement cache) - kombinace LRU a LFU
+    * **ARC (Adaptive Replacement Cache)** – adaptivní algoritmus kombinující 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 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ží 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.
+  * **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.
 == 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ě.
+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**.
-**vlastnosti:**
+  * 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.
-  * Nemusíme nahrazovat záznamy v cache do té doby než nám kompletně dojde.
+  * Díky absenci indexu není třeba řešit kolize způsobené stejnými indexy – všechny bloky soutěží o všechna místa.
-  * Je velmi drahá na implementaci, takže musí být malá .
+  * 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.
-  * 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}}
+  * **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ů.
+{{:statnice:bakalar:pasted:20250602-114623.png?300}}
 == Přímo mapovaná cache ==
-  * 1 cestná cache $\rightarrow$ stupeň asociace = 1, tedy má jednu tabulku
+  * 1-cestná cache → stupeň asociace = 1, tedy pouze jedna tabulka.
-  * $\text{number of sets} = \text{number of blocks}$
+  * $\text{Number of sets} = \text{Number of blocks}$.
-  * má index o délce bitů $log(\text{number of sets})$
+  * 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**:
+  * **Schéma:**
 {{:statnice:bakalar:pasted:20250602-152014.png?750}}
-**Příklad s většími bloky:**
+  * **Příklad s většími bloky:**
 {{:statnice:bakalar:pasted:20250602-153331.png?750}}
-**Vlastnosti:**
+  * **Vlastnosti:**
-  * Hlavní cache u mikrokontrolerů a levných procesorů
+    * Hlavní typ 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
+      * Důvodem je jednoduchá a levná implementace, která nevyžaduje složité vyhledávání a porovnávání tagů.
-  * Každou adresu můžeme zařadit pouze do jednoho místa v tabulce v cache
+    * 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.
 == N-asociativní cache ==
-  * **Obecnější model cache** - $\text{stupeň asociace} = n$
+  * **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.
 {{:statnice:bakalar:pasted:20250602-153444.png?750}}
-=== RAM ===
+  * 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á.
-Velká volatilní paměť, která fyzicky není v procesoru.
+    * **+** 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í.
-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).
@@ Line 907: / Line 1002: @@
 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í
+==== Periferie mapované do paměti ====
+  * 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.
-velmi jednoduchá konfigurace - periferie při inicializaci získají paměťový rozsah, ten slouží k přesunu dat mezi CPU a periferiemi
+==== Sériová vs paralelní sběrnice ====
+  * **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).
-Adress Decoder rozhoduje kam se data přesměrují
+=== Sériový port (UART) ===
+  * 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
-**Asynchroní sběrnice**
+=== Half-duplex vs Full-duplex ===
-  * USB
+  * **Half-duplex** – data mohou proudit **pouze jedním směrem v daný čas**.
-  * SATA
+    * 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.
-**Synchroní sběrnice**
+=== Asynchronní sběrnice ===
-  * PCI
+  * Data nejsou přenášena podle společného hodinového signálu.
-  * PCIe
+  * 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ů.
-=== Sériová vs paralelní sběrnice ===
+=== Synchronní 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ě
+  * Přenos je řízen společným hodinovým signálem, všechna zařízení se musí synchronizovat.
+    * **PCI**
-Sériová linka
+    * **PCIe**
-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
+  * **Paralelní synchronní sběrnice**, half-duplex.
+  * Počáteční přenos vyžaduje řízení přístupu pomocí arbitra.
-  - přenos začíná tím, že iniciátor pořádá arbitra o přidělení sběrnice
+  * Iniciátor nastaví adresu a příznak **FRAME** – tím začíná rámec přenosu.
-  - 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
+  * Cílové zařízení (**Target**) odpoví signálem **DEVSEL**, že rozpoznalo svou adresu.
-  - periférie, která rozpozná svoji adresu nastaví DevSel na 1
+  * Data se přenášejí, když jsou oba signály **TRDY** (Target Ready) a **IRDY** (Initiator Ready) aktivní.
-  - pokud je cílová periferie (Target) připravena přijmout data, nastaví TRDY na 1.
+  * Přenos končí shozením **FRAME** na 0.
-  - pokud je iniciátor připraven vyslat data, nastaví IRDY na 1
+  * Po přenosu všechny signály přejdou zpět na 0 a sběrnice je opět volná.
-  - 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.
+  * **Nevýhody:**
+    * Half-duplex – nelze komunikovat oběma směry současně.
-PCI je half-duplex, nelze současně posílat data oběma směry.
+    * Sdílená sběrnice – pomalá periferie brzdí všechny ostatní.
+    * Omezená přenosová rychlost – 33 nebo 66 MHz:
-Více zařízení na sběrnici - pomalá periférie brzdí rychlé periférie, zvyšuje latency všech ostatních periférií.
+      * 32bit: 132 MB/s nebo 264 MB/s
+      * 64bit: 264 MB/s nebo 528 MB/s
-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ů
+  * **Sériová sběrnice**, point-to-point (peer-to-peer).
-to je problém pro vysoké frekvence přenosů
+  * **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.
-PCIe te peer-to-peer sběrnice, data se posílají jen mezi dvěma zařízeními
+  * 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.).
-je full-duplex, tedy data mohou být posílána oběma směry současně

Trace: • b0b36dbs

Differences

Search

Navigation

Print/export

Tools

QR Code