statnice:bakalar:b4b36pdv

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Modely a architektury paralelních a distribuovaných systémů; prostředky pro jejich implementaci a základní algoritmy. ======
[[https://fel.cvut.cz/cz/education/bk/predmety/47/02/p4702806.html|B4B36PDV]] [[https://cw.fel.cvut.cz/b232/courses/b4b36pdv/lectures/start|Webové stránky předmětu]] [[https://pdv.pages.fel.cvut.cz/lectures/|Nové webové stránky předmětu]]

  * **Paralelní systémy/výpočty**:
    - **Hardwarová podpora pro paralelní výpočty** – (super)skalární architektury, pipelining, spekulativní vyhodnocování, vektorové instrukce, vlákna, procesy, GPGPU. Hierarchie cache pamětí.
    - **Komplikace v paralelním programování** – souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing).
    - **Podpora paralelního programování v C a C++** – pthreads, thread, jthread, atomic, mutex, lock_guard.
    - **Podpora paralelního programování v OpenMP** – sériově-paralelní model uspořádání vláken (fork-join), paralelizovatelná úloha (task region), různé implementace specifikace. Direktivy: parallel, for, section, task, barrier, critical, atomic.
    - **Techniky dekompozice programu** – statické a paralelní rozdělení práce. Threadpool a fronta úkolů. Balancování a závislosti (dependencies).
    - **Techniky dekompozice programu na příkladech**:
      - **Řazení** – quick sort, merge sort.
      - **Numerická lineární algebra a strojové učení** – násobení matice vektorem, násobení dvou matic, řešení systému lineárních rovnic.
  * **Distribuované výpočty/systémy**:
    - **Úvod do distribuovaných systémů (DS)** – charakteristiky DS, čas a typy selhání v DS.
    - **Detekce selhání v DS** – detektory selhání a jejich vlastnosti.
    - **Čas a kauzalita v DS** – uspořádání událostí v DS, fyzické hodiny a jejich synchronizace, logické hodiny a jejich synchronizace.
    - **Globální stav v DS a jeho výpočet** – řez distribuovaného výpočtu, algoritmus pro distribuovaný globální snapshot, stabilní vlastnosti DS.
    - **Vzájemné vyloučení procesů v DS** – algoritmy pro vyloučení procesů a jejich vlastnosti.
    - **Volba lídra v DS** – algoritmy pro volbu lídra a jejich vlastnosti.

===== 1. Hardwarová podpora pro paralelní výpočty =====
V téhle kapitole se zaměříme na to, jak je moderní hardware navržený tak, aby zvládal výpočty paralelně – tedy několik operací současně. Ukážeme si různé úrovně a typy paralelismu, od jednoduchého rozdělení instrukcí na více částí (pipelining), přes využití více výpočetních jader (vlákna, procesy), až po extrémní paralelismus na GPU. Pochopení těchto principů je zásadní pro efektivní vývoj výkonných softwarových systémů.

==== Vektorové instrukce ====
Často nazývané **SIMD** instrukce – *single instruction, multiple data*.

Vektorové instrukce vykonávají jednu danou operaci na velkém množství dat najednou.  
Pracují nad speciálními vektorovými registry – až 512bit.

  * To znamená, že například můžete násobit dvě celé pole čísel "najednou", místo po jednotlivých prvcích.
  * Umožňují značné zrychlení ve výpočetně náročných paralelizovatelných aplikacích, jako např. násobení matic.

Moderní kompilátory jsou schopné automaticky vektorizovat části kódu.  
Pro znatelné zrychlení je ale často nutná manuální implementace.

Na rozdíl od paralelizace mezi jádry se nemusí řešit problémy synchronizace a latence mezi vlákny.  
Nevýhoda je často velmi komplikovaná implementace.

Existuje mnoho standardů, nejznámější jsou x86 standardy:
  * AVX – starší, velmi rozšířený, až 128bit registry
  * AVX2 – novější, přidává nové operace a 256bit registry
  * AVX512 – mnoho dalších operací a 512bit registry, méně rozšířený, většinou jen u high-end CPU

==== Instruction-Level Parallelism (ILP) ====
  * **Definice:** ILP udává, kolik *nezávislých* instrukcí může procesor potenciálně spustit paralelně v rámci *jednoho* programu/vlákna.
  * **Zdroj ILP:** nezávislé aritmetické operace, nezávislé paměťové přístupy, nezávislé větvení.
  * **Využití ILP:** pipelining, superskalární/VLIW architektury, out-of-order execution.

==== Pipelining ====
  * **Princip:** Instrukční cesta se dělí na fáze IF → ID → EX → MEM → WB.  
    To umožňuje, aby různé instrukce byly zpracovávány současně v různých fázích – zvyšuje se **propustnost**, i když latence jednotlivé instrukce zůstává stejná.
  * **Teoretický zisk:** až 1 instrukce / takt (IPC = 1); limitují ho hazardy a větvení.
  * **Superpipelining:** více než 10 stupňů; vyšší frekvence, ale větší penalizace při chybách predikce.
  * **Hazardy:**
    * datové – řeší se forwardingem, stally, přejmenováním registrů
    * řídicí – predikce skoků + branch target buffer (BTB)
    * strukturální – řeší se duplikací jednotek

==== Skalární vs. superskalární procesory ====

=== Skalární procesor ===
  * 1 instrukce za takt (IPC ≤ 1)
  * jednodušší architektura
  * využívá pipelining

=== Superskalární procesor ===
  * více instrukcí za takt (IPC > 1)
  * N-wide architektura (např. 4-wide = až 4 instrukce/takt)
  * využívá ILP pomocí paralelního vykonávání více instrukcí

==== Podtypy superskalární architektury ====
  * **Statická:** paralelně jen instrukce jdoucí v kódu za sebou; při závislostech nastává stall.
  * **Dynamická:** out-of-order execution a přejmenování registrů → lepší využití hardwaru.

==== Shrnutí rozdílu ====
  * **Skalární CPU** ⇒ 1 instrukce/takt, jednoduché, predikovatelné chování.
  * **Superskalární CPU** ⇒ více instrukcí/takt, složitější řízení, vyšší výkon.

==== GPGPU ====
* **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické karty pro obecné výpočty.

* GPU obsahují tisíce jednoduchých jader sdružených do **streaming multiprocessorů (SM)**.  
  Ty spouštějí stovky až tisíce vláken najednou ve skupinách (warp – 32 vláken běžících lock-step).

=== Architektura a omezení ===

  * **Výpočetní hierarchie:** GPC → SM → block → warp → thread
  * **Sdílené prostředky:**
    * shared memory + L1 cache (~128 KB)
    * max 64 warpů / SM (až 2048 vláken)
    * ~255 registrů na vlákno – méně registrů = vyšší obsazenost

  * **Paměťová hierarchie:**
    * L1/shared: ~33 cyklů
    * L2: až 2 TB/s (~200 cyklů)
    * HBM2: 1.5 TB/s (~290 cyklů)
    * Host ↔ GPU: PCIe/NVLink – důležitá je minimalizace přenosů

=== Výpočetní výkon v praxi ===
* Threadripper 3990X + RTX 4090:
  * single-thread: 49 GFLOPS
  * multi-thread CPU: 3.7 TFLOPS
  * CPU + GPGPU: **100 TFLOPS**

=== Programovací modely ===
  * **CUDA C/C++** – pro NVIDIA
  * **OpenCL** – otevřený standard
  * **SYCL** – moderní C++ model
  * **OpenMP target** – direktivy pro GPU

=== Typické úlohy ===
  * lineární algebra, strojové učení, ray-tracing, simulace, video encoding…

=== Výhody ===
  * vysoký výkon (tisíce FP jednotek)
  * efektivita (TFLOPS/W)
  * specializované instrukce (Tensor Cores…)

=== Nevýhody ===
  * paměťová latence
  * omezené registry/shared memory
  * přenosy mezi host ↔ device
  * warp divergence (větvení)
  * vendor lock-in (CUDA)

=== Shrnutí ===
GPGPU nabízí **řádově vyšší výkon** než běžné CPU, ale vývoj je složitější. Správné řízení paměti a vláken, spolu s vhodným programovacím modelem, je klíčem k úspěchu.

==== Vlákna a procesy ====
* **Proces** je samostatná jednotka běhu programu, má vlastní adresní prostor (paměť), popisovače souborů atd.
  * Spuštění nového procesu je relativně nákladné.
  * Vhodné pro více zcela oddělených výpočetních úloh (např. mikroservisy, více programů najednou).

* **Vlákno (thread)** je lehčí jednotka běhu uvnitř procesu.
  * Sdílí paměť a další prostředky s ostatními vlákny procesu.
  * Přepínání mezi vlákny je levnější než mezi procesy.
  * Vhodné pro paralelizaci uvnitř jedné aplikace – více úloh najednou (např. UI, I/O, výpočty).
  * Pozor na **synchronizaci a souběhy (race conditions)** – nutnost použití zámků, mutexů apod.

==== Hierarchie cache pamětí ====
Moderní CPU mají vícestupňovou **hierarchii cache**, která zajišťuje rychlý přístup k často používaným datům:

  * **L1 cache** – nejmenší (např. 32 KB), ale nejrychlejší (~4 cykly), zvlášť pro instrukce a data.
  * **L2 cache** – větší (např. 256 KB), pomalejší (~12 cyklů), většinou sdílena mezi jádry.
  * **L3 cache** – největší (např. 16 MB), ještě pomalejší (~30–40 cyklů), sdílená mezi všemi jádry.
  * **RAM** – mnohem větší, ale o řád(y) pomalejší než cache (~100 ns).
  * **Zásada locality:** data, která byla použita nedávno nebo jsou blízko sobě, mají vyšší šanci být v cache – tím se výrazně snižuje průměrná latence paměťových přístupů.

Efektivní využití cache (např. přístup po řádcích, nikoliv po sloupcích v 2D poli) může mít zásadní vliv na výkon.



===== 2. Komplikace v paralelním programování =====
Když programujeme paralelně – tedy více věcí běží najednou – můžeme narazit na různé složitosti, které se u sekvenčních (jednovláknových) programů vůbec neřeší. Typickými komplikacemi jsou souběh (když dvě vlákna zasahují do stejných dat zároveň), uváznutí (když se navzájem blokují), nebo falešné sdílení (když si vlákna "lezou do cache", i když pracují na různých datech). V téhle kapitole se na tyhle problémy podíváme a vysvětlíme si, jak a proč k nim dochází.

==== Race Condition (souběh) ====
* **Souběh (race condition)** nastává, když dvě nebo více vláken přistupuje ke **stejným datům** a **alespoň jedno z nich je mění**, přičemž jejich pořadí není řízené (např. zámky, mutexy).

* To znamená, že výsledek programu **závisí na načasování** – někdy to „vyjde dobře“, jindy ne.
* Typickým příkladem je inkrementace sdílené proměnné – pokud není chráněná zámkem, může být výsledek menší, než kolik se očekává.

Například:
<code cpp>
// špatně – race condition
for (int i = 0; i < 1000; i++) {
 counter++;
}
</code>

* Řešení:
  * Použít **synchronizační primitiva** – mutexy, atomické operace, semafory apod.
  * Nebo použít **thread-local** kopie a sloučit je až nakonec.

==== Deadlock (uváznutí) ====
* **Uváznutí (deadlock)** nastává, když dvě nebo více vláken čeká na zdroj, který drží to druhé – a žádné se nepohne dál.

* Jednoduše řečeno: vlákno A čeká na zámek, který drží vlákno B, a vlákno B čeká na zámek, který drží vlákno A.

Například:
<code cpp>
// pseudokód s potenciálním deadlockem
thread1:
lock(A)
lock(B)

thread2:
lock(B)
lock(A)
</code>

* Aby deadlock mohl nastat, musí být splněny tyto 4 podmínky (tzv. Coffmanovy podmínky):
  * **Vzájemné vyloučení** – zdroje nejsou sdílené (jen jedno vlákno je může mít).
  * **Zadržení a čekání** – vlákno drží jeden zámek a čeká na další.
  * **Neodnímatelnost** – zdroj (zámek) nemůže být násilně odebrán.
  * **Cyklické čekání** – existuje cyklus závislostí mezi vlákny.

* Prevence:
  * Dodržovat **pevné pořadí zamykání zdrojů**.
  * Používat **timeouty** u zámků.
  * Využít algoritmy pro **deadlock detection** a recovery.

==== False Sharing ====
Nastává, když dvě vlákna přistupují k **různým** proměnným, které se ale nachází ve **stejné cache line**.

* Když jedno vlákno zapíše do své proměnné, CPU invaliduje celou cache line – i když druhé vlákno pracuje na jiné proměnné ve stejné linii.
* Pokud se to děje často, dochází k **velkému zpomalení**, protože cache se neustále synchronizuje mezi jádry.

* Řešení:
  * **Zarovnat proměnné** tak, aby každá byla na vlastní cache line (např. pomocí `alignas(64)`).
  * Přidat „padding“ mezi proměnné, které používají různá vlákna.

==== True Sharing (není komplikace) ====
Nastává, když dvě vlákna přistupují ke **stejné** proměnné.

* Narozdíl od false sharing je to **žádoucí chování**, pokud víme, co děláme – ale musí být správně synchronizované.
* Typicky jde o sdílené čítače, fronty, stavové proměnné atd.


 
===== 3. Podpora paralelního programování v C a C++ =====
 Existuje více úrovní podpory – od nízkoúrovňových knihoven jako `pthreads` v C, až po elegantní moderní rozhraní ve stylu `std::thread`, `std::jthread`, `std::mutex` nebo `std::atomic` v C++. Pokud chceme psát vícevláknové programy efektivně a bezpečně, je důležité pochopit, kdy a jak jednotlivé nástroje použít – a čím se liší.

==== POSIX vlákna (pthreads) ====
* `pthreads` (POSIX Threads) je **standardní rozhraní v jazyku C** pro práci s vlákny.
* Poskytuje funkce pro:
  * **vytváření vláken**: `pthread_create()`
  * **synchronizaci vláken**:
    * **mutexy**: `pthread_mutex_lock()`, `pthread_mutex_unlock()`
    * **podmínkové proměnné**: `pthread_cond_wait()`, `pthread_cond_signal()`
    * **semafory**: `sem_init()`, `sem_wait()`, `sem_post()`

Je to výkonný, ale nízkoúrovňový nástroj – programátor musí vše spravovat ručně. Hodí se pro systémy, kde je důležitá kontrola nad výkonem a kompatibilita se standardem POSIX.

==== std::thread (C++11) ====
* Od C++11 je k dispozici standardní knihovna pro vlákna – `std::thread`.
* Umožňuje jednoduché vytvoření a správu vláken pomocí objektově orientovaného rozhraní.
  * Vlákno spustíme předáním funkce (nebo lambdy) do konstruktoru.
  * Synchronizace se řeší pomocí `std::mutex`, `std::condition_variable` a dalších primitiv.

Výhodou oproti `pthreads` je **vyšší přehlednost, typová bezpečnost a integrace s C++ idiomy** (např. RAII, STL, lambdy).

==== std::jthread (C++20) ====
* Od C++20 přibyla nová třída `std::jthread`, která automaticky spravuje vlákno.
  * Při zničení objektu se vlákno **automaticky ukončí** (`join()` nebo `detach()`).
  * Má vestavěnou podporu pro **zrušení vlákna** pomocí `stop_token`.
  * Výborně se hodí pro práci s **RAII přístupem** a bezpečnější práci s vláknem.

To znamená, že se snižuje riziko zapomenutého `join()` a tím i potencionálních chyb.

==== Mutex a Lock Guard ====
**Mutex** (*mutual exclusion*) je synchronizační nástroj, který **zajišťuje, že jen jedno vlákno přistupuje k určité části kódu najednou** – typicky tzv. *kritické sekci*.

* V C++ se používá `std::mutex` a jeho varianty:
  * `std::recursive_mutex`, `std::timed_mutex`, …

Ukázka (ruční zamykání/odemykání):
<code cpp>
#include <iostream>
#include <thread>
#include <mutex>

int main() {
    std::mutex mtx;

    auto threadFunc = [&mtx]() {
        mtx.lock();
        // Kritická sekce
        std::cout << "Thread is executing critical section." << std::endl;
        mtx.unlock();
    };

    std::thread t1(threadFunc);
    std::thread t2(threadFunc);

    t1.join();
    t2.join();

    return 0;
}
</code>

*Moderní C++* doporučuje použít `std::lock_guard`, který mutex **automaticky zamkne a odemkne** – tím se předejde chybám (např. zapomenutí `unlock()` při výjimce):

<code cpp>
#include <iostream>
#include <thread>
#include <mutex>

int main() {
    std::mutex mtx;

    auto threadFunc = [&mtx]() {
        std::lock_guard<std::mutex> lock(mtx);
        // Kritická sekce
        std::cout << "Thread is executing critical section." << std::endl;
    };

    std::thread t1(threadFunc);
    std::thread t2(threadFunc);

    t1.join();
    t2.join();

    return 0;
}
</code>

==== Atomic ====
**Atomic** proměnné umožňují provádět operace, které jsou **nedělitelné (atomické)** – tím pádem **bezpečné vůči souběhu**, aniž by bylo potřeba používat mutex.

* V C++ se používá `std::atomic<T>` – kde `T` může být např. `int`, `bool`, pointer apod.

  * V pozadí to využívá **atomické instrukce CPU** (pokud jsou dostupné), takže jsou **rychlejší než mutexy**.
  * Pokud HW atomické instrukce neumí, fallback je přes mutex.

V praxi jsou tedy `std::atomic` velmi efektivní pro jednoduché sdílené proměnné – například čítače:

<code cpp>
#include <iostream>
#include <thread>
#include <atomic>

int main() {
    std::atomic<int> counter(0);

    auto increment = [&counter]() {
        for (int i = 0; i < 1000; ++i) {
            ++counter;
        }
    };

    std::thread t1(increment);
    std::thread t2(increment);

    t1.join();
    t2.join();

    std::cout << "Final counter value: " << counter.load() << std::endl;

    return 0;
}
</code>

* Jinými slovy – `std::atomic` je ideální, pokud chceš **rychlou synchronizaci bez složitých zámků**, ale nepotřebuješ složitou logiku jako čekání, notifikace, podmínky apod.


===== 4. Podpora paralelního programování v OpenMP =====
OpenMP je velmi populární knihovna pro paralelizaci v jazycích C, C++ a Fortran. Umožňuje snadno spouštět více vláken pomocí direktiv vkládaných přímo do zdrojového kódu. V této kapitole se podíváme na to, jak funguje základní model *fork-join*, jak se v OpenMP definují úlohy (tasky), a jaké máme k dispozici prostředky pro synchronizaci. Ukážeme si i různé varianty implementací OpenMP a přehled direktiv, které programátorům umožňují jemné řízení paralelismu.

==== Sériově-paralelní model uspořádání vláken (fork-join) ====
Fork-join model je základní exekuční schéma OpenMP. Program začíná jedním *master* vláknem, které po vstupu do direktivy **`parallel`** vytvoří tým dalších vláken (*fork*). Všechna vlákna spolupracují v daném paralelním regionu a na jeho konci se implicitní bariérou zase spojí do jediného vlákna (*join*).

* Výhody:
  * jednoduchá správa vláken
  * sdílená paměť
  * předvídatelné chování a synchronizace

Ukázkový kód:
<code cpp>
#include <omp.h>
#include <stdio.h>

int main(void) {
    #pragma omp parallel
    {
        int id  = omp_get_thread_num();
        int n   = omp_get_num_threads();
        printf("Hello from thread %d of %d\n", id, n);
    }   /* <-- implicit join & barrier */
    return 0;
}
</code>

* Poznámka: OpenMP vytváří **vlákna**, nikoliv procesy – všechna sdílí paměť. Vlákna jsou obvykle implementována pomocí POSIX/pthreads.

Další možnosti a doplňky modelu:
  * `#pragma omp barrier` – ruční synchronizační bod.
  * `single`, `master` – sekci vykoná pouze jedno vlákno.
  * `ordered` – zachování pořadí iterací ve smyčce.
  * `critical`, `atomic` – zajištění sériového přístupu ke sdíleným proměnným.
  * `nowait` – zabrání implicitní bariéře na konci paralelního bloku.
  * `OMP_NESTED=TRUE` nebo `omp_set_max_active_levels()` – aktivuje vnořenou paralelizaci.
  * `task`, `taskgroup`, `depend(...)` – jemné řízení závislostí mezi úlohami (viz níže).

==== Paralelizovatelná úloha (task region) ====
Pomocí direktivy `task` lze definovat úlohy, které mohou být nezávisle spouštěny paralelně. Oproti `parallel for`, které rozděluje smyčku, `task` umožňuje paralelizovat **libovolné části kódu**, včetně rekurze a nepravidelné struktury výpočtu.

* Tasky lze organizovat do `taskgroup`.
* Pomocí `depend(in|out|inout: var)` lze řídit pořadí a závislosti.
* `detach`, `priority` – umožňují pokročilou kontrolu provádění.

Příklad:
<code cpp>
#pragma omp task depend(out: A) {
  // vypočítáme A
}

#pragma omp task depend(in: A) {
  // použijeme A
}
</code>

==== Různé implementace OpenMP specifikace ====
OpenMP je pouze specifikace – jednotlivé kompilátory ji implementují v různé míře.

*Přehled nejznámějších implementací (stav 2025):*

  * **GCC 14+ (libgomp)** – `-fopenmp`, verze 5.2 (téměř úplná), open-source klasika.
  * **Clang 18+ (libomp)** – `-fopenmp`, verze 5.2 (většina), funguje i na Windows.
  * **Intel oneAPI (icx/icpx + iomp5)** – `-qopenmp`, verze 5.2, velmi výkonný runtime, podpora GPU.
  * **IBM XL (LLVM-based)** – `-qsmp=omp`, verze 5.1, optimalizace pro POWER.
  * **AMD AOCC 4.x** – laděno pro AMD Zen, Clang + libomp.
  * **Cray/ROCm** – zaměřeno na GPU/offload (OpenMP target).

==== Přehled hlavních direktiv OpenMP ====
* **`#pragma omp parallel`**  
  * Vytvoří tým vláken.
  * Podporuje: `num_threads`, `if`, `default`, `shared`, `private`, …

* **`for` / `do`**  
  * Paralelizace smyčky.
  * Možnosti: `schedule(static|dynamic|guided)`, `collapse(n)`, `reduction`, `nowait`.

* **`sections` / `section`**  
  * Spustí nezávislé bloky kódu paralelně (např. různé funkce najednou).

* **`task`**  
  * Vytvoří úlohu; možnost specifikace závislostí přes `depend(...)`.
  * Další klauzule: `priority`, `detach`.

* **`barrier`**  
  * Explicitní synchronizační bod – všechna vlákna musí dojít na toto místo.

* **`critical [(name)]`**  
  * Zamezí více vláknům vstup do stejné sekce kódu najednou.
  * Jméno odděluje různé nezávislé sekce.

* **`atomic`**  
  * Odlehčená synchronizace pro jednoduché operace s proměnnou (inkrementace, zápis, čtení…).

==== Příklad zapojení všeho dohromady ====
<code cpp>
#include <omp.h>
#include <stdio.h>

int main(void) {
    #pragma omp parallel
    #pragma omp single          // jeden thread spouští tasky
    {
        #pragma omp task depend(out: sum)
        {
            int sum = 0;

            #pragma omp parallel for reduction(+ : sum) nowait
            for (int i = 0; i < 1e6; ++i)
                sum += i;

            printf("Sum done: %d\n", sum);
        }

        #pragma omp task depend(in: sum)
        {
            printf("Post-processing...\n");
        }
    }   // implicit taskgroup – čeká se na všechny tasky
    return 0;
}
</code>
 
Tento příklad ukazuje vytvoření tasku se závislostí `depend(out: sum)`, paralelní redukci vnitřní smyčky, a následný task, který čeká na výsledek (`depend(in: sum)`).


===== 5. Techniky dekompozice programu =====
Paralelní programy často potřebují být rozděleny na menší části – a to nejen podle funkcí, ale hlavně podle **práce**, kterou je třeba vykonat. Tato kapitola se věnuje technikám, jak takovou práci rozdělit mezi vlákna nebo úlohy (tasky), a jak přitom řešit problémy jako nevyvážená zátěž nebo závislosti mezi úlohami. Pochopení těchto principů ti pomůže psát efektivnější a škálovatelnější paralelní kód.

==== Statické × dynamické rozdělení práce ====
* **Statické rozdělení** – práce (např. iterace smyčky) se rozdělí předem mezi všechna vlákna.
  * Např. pomocí `schedule(static[, chunk])` v OpenMP.
  * Výhodou je **nízký overhead** (prakticky žádná synchronizace).
  * Nevýhodou je, že **u nepravidelných úloh může být některé vlákno přetížené**, zatímco jiné skončí dříve a zahálí.

* **Dynamické rozdělení** – práce se přiděluje **za běhu** podle toho, které vlákno je volné.
  * Používá se `schedule(dynamic[, chunk])`.
  * Výhodou je lepší **vyvážení zátěže**.
  * Nevýhodou je **vyšší režie kvůli synchronizaci**.

* **Guided plánování** – kompromis mezi statickým a dynamickým:
  * `schedule(guided[, chunk])` začíná velkými bloky a postupně zmenšuje chunk velikost.
  * Vhodné pro případy, kdy práce trvá různě dlouho a časem ubývá.

* Další možnosti:
  * `schedule(runtime)` – výběr plánování je ponechán na hodnotě proměnné `OMP_SCHEDULE`.
  * `schedule(auto)` – nechá výběr plánu na implementaci OpenMP.

==== Thread-pool a fronta úkolů (work-stealing) ====
* OpenMP (od verze 3.0) podporuje **tasky**, které jsou plánovány na vlákna z **persistentního thread-poolu**.
  * Vlákna jsou vytvořena v prvním paralelním regionu a **zůstávají aktivní** i pro další úseky programu.

* Každé vlákno má vlastní **lokální deque** (obousměrnou frontu), do které si vkládá nové úkoly.

* **Work-stealing**: pokud vlákno nemá co dělat, zkusí si **„ukrást“ úkol** z cizí fronty.
  * Tento přístup pomáhá **automaticky vyvažovat zátěž**.
  * Push/pop na vlastní frontě jsou většinou **lock-free**; zámky se používají jen při krádeži.

==== Balancování zátěže ====
Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu.

* U **smyček**:
  * Volba správného `schedule(...)` plánu.
  * Velikost `chunku` ovlivňuje granularitu přidělené práce.
  * `collapse(n)` – slučuje více vnořených smyček do jedné, čímž zvyšuje počet iterací pro paralelizaci.

* U **tasků**:
  * Work-stealing pomáhá s dynamickým plánováním.
  * Pomocí `priority(expr)` lze zvýhodnit důležité úkoly.
  * Heuristiky runtime mohou **omezit vznik malých tasků** (např. jejich inline-ing) → lepší škálování.

==== Závislosti (dependencies) ====
Tasky mohou mít mezi sebou **závislosti**, které určují pořadí provádění. V OpenMP se deklarují pomocí `depend(...)`.

* Typy závislostí:
  * `depend(in: X)` – task **potřebuje** data `X`.
  * `depend(out: X)` – task **produkuje** data `X`.
  * `depend(inout: X)` – task `X` čte i zapisuje.
  * Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře.

Ukázkový kód:
<code cpp>
#pragma omp task depend(out:A)
build_A();

#pragma omp task depend(in:A) depend(out:B)
build_B();

#pragma omp task depend(in:B)
use_B();
</code>

* OpenMP runtime si z těchto závislostí **sestaví DAG (acyklický graf)**.
* Jakmile jsou všechny vstupní závislosti splněny, task je označen jako **„ready“** a zařadí se do fronty.

Tato metoda umožňuje velmi jemné řízení výpočtu a paralelizace i **nepravidelných nebo stromových struktur** (např. kompilátory, plánovače, grafy).



===== 6. Techniky dekompozice programu na příkladech =====
Abychom lépe pochopili různé způsoby paralelizace, ukážeme si je na konkrétních příkladech z oblasti řazení, lineární algebry a strojového učení. Uvidíme, jak lze algoritmy jako quick sort nebo násobení matic přirozeně rozdělit do paralelních částí a jaké techniky přitom použít – např. tasky, `collapse`, blokové zpracování či závislosti.

==== Řazení ====
**quick sort a merge sort**

=== Quick sort ===
* **Proč „rozděl a panuj“?**  
  * *Divide*: vybereme pivot a jedním průchodem rozdělíme pole na část < pivot a část ≥ pivot.  
  * *Conquer*: obě části rekurzivně řadíme – ideální místo pro vytvoření dvou paralelních úloh (*tasků*).  
  * *Combine*: není třeba – dělení samo zajistí správné pořadí.

* Paralelizace: po operaci `partition` spustíme levé větvení jako `omp task`, pravé běží ve vlákně dál.

<code cpp>
void qs(std::vector<int>& vec, int from, int to) {
    if (to - from <= base_size) {
        std::sort(vec.begin() + from, vec.begin() + to);
        return;
    }

    int pivot = vec[from];
    int mid   = partition(vec, from, to, pivot);      // divide

    if (mid - from > 1) {                             // conquer – left
#pragma omp task shared(vec) firstprivate(from, mid)
        qs(vec, from, mid);
    }
    if (to - mid > 1) {                               // conquer – right
        qs(vec, mid, to);
    }
}
</code>

=== Merge sort ===
* **Proč „rozděl a panuj“?**  
  * *Divide*: rekurzivní dělení pole na půlky.  
  * *Conquer*: každou půlku řadíme paralelně.  
  * *Combine*: dvě seřazené části spojíme lineárním `merge`.

* Paralelizace: obě rekurze běží jako tasky, po jejich dokončení proběhne `inplace_merge`.

<code cpp>
void ms(std::vector<int>& vec, int from, int to) {
    if (to - from <= base_size) {
        std::sort(vec.begin() + from, vec.begin() + to);  // seriál-insert
        return;
    }
    int mid = from + (to - from) / 2;                     // divide

#pragma omp task shared(vec) firstprivate(from, mid)
    ms(vec, from, mid);                                   // conquer – left
    ms(vec, mid, to);                                     // conquer – right

#pragma omp taskwait
    std::inplace_merge(vec.begin() + from,                // combine
                       vec.begin() + mid,
                       vec.begin() + to);
}
</code>

==== Numerická lineární algebra a strojové učení ====
**násobení matice × vektor, násobení dvou matic, řešení systému lineárních rovnic**

=== Paralelní násobení matice × vektor (SpMV/Dense MV) ===
* **Princip:** každý prvek $y_i$ je skalární součin řádku $A_i$ a vektoru $x$.  
  * *Divide*: rozdělíme po řádcích.  
  * *Conquer*: každý řádek počítá vlákno nezávisle.  
  * *Combine*: nepotřebujeme – každý výstupní `y[i]` je unikátní.

* U husté matice: nejlepší přístup po řádcích (row-major).  
* U řídké: paralelizace přes nenulové řádky (např. CSR formát).

<code cpp>
void matvec_dense(const std::vector<double>& A,   // ROWS × COLS, row-major
                  const std::vector<double>& x,
                  std::vector<double>&       y) {
    #pragma omp parallel for
    for (int i = 0; i < ROWS; ++i) {
        double sum = 0.0;
        for (int j = 0; j < COLS; ++j)
            sum += A[i * COLS + j] * x[j];   // dot product
        y[i] = sum;
    }
}
</code>

=== Paralelní násobení dvou matic ===
* **Naivní přístup**: každý prvek $c_{ij}$ samostatně – špatná cache-lokalita.

* **Blokové (tiling) násobení**:
  * *Divide*: rozdělíme výstupní matici $C$ na bloky $B_{pq}$.
  * *Conquer*: každý blok počítá vlákno/task – např. pomocí `collapse(2)`.
  * *Combine*: není třeba – bloky jsou oddělené.

<code cpp>
#pragma omp parallel for collapse(2) schedule(dynamic)
for (int bi = 0; bi < N; bi += BS)
  for (int bj = 0; bj < N; bj += BS)
    for (int bk = 0; bk < N; bk += BS)
      multiply_block(A, B, C, bi, bj, bk, BS);
</code>

* Pro vysoký výkon: používat BLAS knihovny (OpenBLAS, MKL…) se SIMD a tilingem.

=== Paralelní řešení systému lineárních rovnic (Gaussova eliminace) ===
* **Gaussova eliminace (LU)**: v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$.
  * Paralelizujeme řádky $i = k+1..n-1$.
  * Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti.

<code cpp>
void gauss_elim(std::vector<double>& A) {         // ROWS × COLS, row-major
    for (int k = 0; k < ROWS - 1; ++k) {
        #pragma omp parallel for
        for (int i = k + 1; i < ROWS; ++i) {
            double c = -A[i * COLS + k] / A[k * COLS + k];
            for (int j = k; j < COLS; ++j)
                A[i * COLS + j] += c * A[k * COLS + j];
        }
    }
}
</code>

* **Iterativní metody (Jacobi, CG, GMRES)**:
  * Lépe paralelizovatelné než Gauss – hlavně `matvec`, vektorové operace, redukce.
  * OpenMP poskytuje `reduction(+:)` a `atomic` pro synchronizaci.

* **Off-load na GPU (OpenMP 5.x)**:
  * Pomocí `target teams distribute parallel for` lze výpočet přenést na GPU.
  * Host kontroluje synchronizaci, ale výpočet běží plně na zařízení.


===== Úvod do distribuovaných systémů (DS) ====
**charakteristiky DS, čas a typy selhání v DS**

DS je soubor nezávislých, autonomních výpočetních jednotek propojených komunikační sítí. Výpočetní jednotky mezi sebou komunikují formou posílání zpráv za účelem určité formy spolupráce.

Výpočetní jednotky nemají sdílenou paměť, nesdílejí globální hodiny a selhávají na sobě nezávisle.

Kadý proces má své lokální hodiny, které nemusí ukazovat přesný čas (synchronizace je možná pouze s určitou přesností).

Je obtížné uvažovat o čase nejen kvůli absenci globálních hodin ale obecně nelze dát limit na komunikaci a délku výpočtu.

==== Asynchronní x Synchronní DS ====
Popisují model světa ve kterém DS existuje. rozdělení synchroní a asynchroní popisuje množinu předpokladů, které budeme používat při psaní distribuovaného algoritmu. 
=== Synchronní model ===
  * **Známe horní hranice**
    * maximální zpoždění zprávy
    * maximální čas mezi dvěma kroky procesu
    * maximální drift lokálních hodin
  * Algoritmy můžeme psách v **fázích/kolech** a spolehlivě používat timeouty
  * V praxi čistě synchroní sétě skoro neexistují
=== Asynchronní model ===
  * **Žádné limity** – zpráva může bloudit libovolně dlouho, proces může
    běžet tak pomalu, jak chce, hodiny se mohou rozejít.
  * Timeout tedy **nemůže spolehlivě rozlišit** „zpomalení“ od „pádu“.
  * V tomto modelu je např. prokázáno (FLP), že deterministický konsensus
    s možností jediného pádu procesu **nelze** vyřešit.
=== Částečně synchronní model (real-world kompromis) ===
  * Systém se může chovat asynchronně, ale po nejpozději neznámém čase **stabilně** do režimu, kdy už limity platí.
  * Většina produkčních protokolů (Raft, PBFT …) předpokládá právě tenhle model – jsou robustní vůči výkyvům, ale nakonec se „chytí“. 
  


  - Selhání procesu
    * crash / fail-stop - proces přestane vykonávatz algoritmus
    * libovolné (byzantské) selhání - proces může pracovat déle a odpovídat na zprávy, ale vykonává chybný algoritmus
  - Selhání kanálu
    * ztráta zprávy - zpráva se ztratí a nedorazí do cílového procesu
    * partitioning - procesy jsou rozdělené do disjunktních množin, komunikace v nich je možná, ale mezi nimi ne
  - Selhání časování - doba odezvy procesu nebo přenosu zprávy vybočila z dohodnutého časového rozmezí

Předpoklady na komunikační kanál:
Spolehlivé doručování, žádná duplikace, žádné vytváření, garantované pořadí doručování

===== Detekce selhání v DS =====
**detektory selhání a jejich vlastnosti**

**úplnost** - každé selhání je časem detekováno alespoň jedním bezvadným procesem

**přesnost** - nedochází k mylné detekci

nelze dosáhnout obou vlastností současně, je vyžadována  100% úplnost a $\lt$ 100% přesnost.



Frekvence selhání roste lineárně s počtem procesů ve skupině (selhání jsou běžná)

Dva podprotokoly - detekce selhání a šíření informace o selhání

Průběh detekce:
  - havárie procesu $p_j$
  - detekce selhání procesu $p_j$ nějakým procesem $p_k$
  - proces $p_k$ rozšiřuje informaci o selhání procesu $p_j$ do ostatních procesů

Základní protokoly pro detekci selhání:

=== Centralizovaný heartbeat ===
Heartbeat jsou odesílány periodicky, každých $\mathcal{T}$ jednotek času jednomu vybranému procesu $p_j$

Heartbeat má pořadové číslo, to odeslání heartbeatu je inkrementován lokální čítač pro každý proces

Pokud není heartbeat od $p_i$ přijat v $p_j$ v časovém limitu $\tau$, je $p_i$ označen jako havarovaný

Je úplný pro všechny uzly kromě $p_j$, selhání $p_j$ není detekováno a při velkém počtu uzlů může být $p_j$ přetížen.


=== Kruhový heartbeat ===
Heartbeats jsou odesílány periodicky sousedům každého procesu (jednostranně nebo oboustranně).

  * není centrální uzel
  * není úplné při selhání více procesů (stačí jeden u jednosměrného, 2 u obousměrného)
  * je třeba udržovat kruhovou hierarchii

=== All to all heartbeat ===
každý proces periodicky odesílá heartbeat všem ostatním procesům
  * rovnoměrná zátěž uzlů
  * je úplný
  * vysoké zatížení uzlů
  * nízká přesnost (může dojít k označení více uzlů za havarované při zpoždění zprávy)

=== SWIM ===
**Scalable weakly consistent infection-style proces group membership protocol**

  * proces $p_i$ periodicky odesílá zprávu $\texttt{ping}$ náhodně vybranému uzlu $p_j$ a čeká na odpověď $\texttt{ack}$
  * pokud ji nedostance, odešle zprávu $\texttt{ping\_req}$ $\mathcal{K}$ náhodně vybraným uzlům
  * tyto uzly se zeptají $p_j$ pomocí zprávy $\texttt{ping}$ a pokud dostanou odpověď, odešlou ji $p_i$ jako $\texttt{ping\_ack}$
  * pokud ani jeden z $\mathcal{K}$ uzlů nedostane odpověď, označí $p_i$ $p_j$ jako havarovaný

přesnost lze nastavit volbou $\mathcal{K}$, klesá exponenciálně s rostoucím $\mathcal{K}$

úplnost je zaručena, průměrný čas detekce je $\frac{e}{e - 1}\mathcal{T}$

===== Čas a kauzalita v DS =====
**uspořádání událostí v DS, fyzické hodiny a jejich synchronizace, logické hodiny a jejich synchronizace**

clock slew - rozdíl v času hodin dvou procesů, mají li dvoje hodiny nenulovou mimoběžnost, jsou nesynchronizované

clock drift - rozdíl v rychlosti hodin dvou procesů

synchronizace
  * externí
    * čas $\mathcal{C}_i$ hodin každého procesu $p_i$ je udržován v rozmezí $\delta$ od času $\mathcal{S}$ externích referenčních hodin (tj. $|\mathcal{C}_i - \mathcal{S}| \leq \delta$)
    * externí hodiny mohou být napojeny na UTC nebo atomové hodiny
    * například NTP
  * interní
    * každý pár procesů $(p_i, p_j)$ má hodnoty času svých hodin v rozmezí $\delta$, v každém okamžiku (tj. $|\mathcal{C}_i - \mathcal{C}_j| \leq \delta$)
    * například Berkeley algoritmus

Externí synchronizace typu Kolik je hodin? -> odešle odpověď -> nastaví čas, má chybu nastavení špatného času kvůli komunikační prodlevě (latenci)

Cristianův algoritmus
$$ \mathcal{C}_i \coloneq t + \frac{\mathcal{T}_\text{RT}-l_{\text{min}+l'_{min}}}{2}$$
chyba je omezena, tj maximálně $\frac{\mathcal{T}_\text{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$

lokální čas lze posunou libovolně dopředu, ale ne dozadu, je možné zvýšit nebo snížit rychlost hodin

NTP
  * servery uspořádány do hierarchie stromu, uzly synchronizují čas se svými rodiči a někdy s dalšími servery na stejné úrovni
  * mezi zprávami se spočte offset, který se použije pro výpočet komunikační latence
  * $o = \frac{(t_1^{r} - t_2^{r}+t_2^{s} - t_1^{s})}{2}$

Logické hodiny

nepoužívají přímo aktuální čas ale časovou značku

kauzální vztah - první událost může ovlivnit druhou

Relace stalo se před
  - Jsou-li $\mathcal{A}$ a $\mathcal{B}$ události ve stejném procesu $p$ a pokud $\mathcal{A}$ nastala před $\mathcal{B}$, pak $\mathcal{A} \rightarrow \mathcal{B}$
  - Je-li $\mathcal{A}$ odeslání zprávy a $\mathcal{B}$ je přijetí této zprávy, pak $\mathcal{A} \rightarrow \mathcal{B}$
  - Je-li $\mathcal{A} \rightarrow \mathcal{B}$ a $\mathcal{B} \rightarrow \mathcal{C}$, pak $\mathcal{A} \rightarrow \mathcal{C}$ (tranzitivita)

Kauzální nezávislost
  * relace stalo se před zavádí částečné uspořádání událostí, potenciální kauzální závislosti
  * $e_1$ -> $e_2$: potenciálně kauzálně závislé události ($e_2$ mohlo být ovlivněno $e_1$, ale nemuselo)
  * $e_1$ || $e_2$: současné události (kauzální vztah určitě není)

Lamportovy logické hodiny - každý proces má své logické hodiny, které se aktualizují podle přijímání zpráv

Synchronizace logických hodin
  - po každé události která se odehraje v $p_i$ se hodiny $\mathcal{C}_i$ inkrementují o 1
  - každé zprávě $m$ odeslané procesem $p_i$ je přiřazená časová značka $ts(m) = \mathcal{C}_i$
  - kdykoliv proces $p_j$ přijme zprávu $m$, tak:
    - upraví své lokální hodiny $\mathcal{C}_j$ na $max\{\mathcal{C}_j, ts(m)\}$ a poté
    - provede krok 1 předtím než předá $m$ aplikaci (<= přijetí zprávy je událost) 

Lamportovy hodiny neimplikují kauzalitu!
  * Platí: jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$
  * Neplatí: jestliže $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$, pak $e_1 → e_2$

Vektorové hodiny - každý proces si udržuje vektor celočíselných hodin ostatních procesů

===== Globální stav v DS a jeho výpočet =====
**řez distribuovaného výpočtu, algoritmus pro distribuovaný globální snapshot, stabilní vlastnosti DS**

globální stav je množina lokálních stavů procesů v DS a stavu všech komunikačních kanálů v jednom okamžiku

globální snapshot je záznam globálního stavu

například
  * garbage collection
  * deadlock detection
  * detekce ukončení výpočtu
  * checkpointing

Řez - časová hranice v každém procesu a v každém komunikačním kanále
  * události které nastanou před řezem jsou v řezu
  * události které nastanou po něm jsoui mimo řez

Konzistentní řez - řez $\mathcal{Ř}$ je konzistentní pokud splňuje kauzalitu, tj. pokud pro každý pár událostí $e$, $f$ v systému platí:
$$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř}$$
tj. pokud řez obsahuje nějakoiu událost, obsahuje i všechny, které ji předcházejí dle relace **stalo se před** (tj. nelze aby v řezu byl důsledek a nebyla tam příčina)

konzistentní řez = logický okamžik

{{statnice:bakalar:rezy.png?500}}

Konzistentní globální snapshot odpovídá konzistentnímu řezu.
  * Globální snapshot je konzistentní, pokud by mohl (ale nikoliv musel) být zpozorován externím pozorovatelem daného distribuovaného výpočtu.
  * Nekonzistentní řez by nemohl nikdy být zpozorován externím pozorovatelem daného distribuovaného výpočtu.

{{statnice:bakalar:rezy2.png?500}}

Chamdy-Lamport algoritmus pro distribuovaný globální snapshot
  - (Vytváření snapshotu je distribuované.)
  - Speciální zpráva: ZNAČKA ▪
  - Jeden (libovolný) z procesů iniciuje vytvoření snapshotů.
  - Procesy reagují na příjem zprávy ZNAČKA ▪
  - výsledkem je konzistentní řez

{{statnice:bakalar:03_globalni_snapshot_2023.pdf|ilustrace algoritmu slide 15-21}}

stabilní vlastnost je taková vlastnost, že jakmile je ve výpočtu jednou splněna, zůtává splněna navždy
  * například výpočet skončil, nastalo uváznutí, objekt je sirotek

 nestabilní vlastnost je například //ve výpočtu není žádný havarovaný proces//

Chandy-Lamport snapshotů algoritmus lze použít pro detekci stabilních globálních vlastností:
  * Je daná stabilní vlastnost V splněna v globálním snapshotu zachyceným snapshot algoritmem?
    - ANO - Vlastnost $\mathcal{V}$ bude ve výpočtu splněna i ve fyzickém okamžiku doběhnutí snapshot algoritmu.
    - NE - Vlastnost $\mathcal{V}$ nemohla být ve výpočtu splněna ani ve fyzickém okamžiku zahájení snapshot algoritmu.

===== Vzájemné vyloučení procesů v DS =====
**algoritmy pro vyloučení procesů a jejich vlastnosti**

==== Problém vzájemného vyloučení ====
<markdown>
- *Kritická sekce* je část kódu u které potřebujeme zaručit, že ji v každém okamžiku vykonává maximálně jeden proces
- Definujeme funkce *enter()* a *exit()* pro vstup a výstup do kritické sekce
- Na úrovni operačního systému umíme problém řešit pomocí synchronizačních nástrojů, v distribuovaném systému potřebuje algoritmus
</markdown>
==== Požadavky na algoritmus pro vyloučení procesů ====
<markdown>

- *Bezpečnost* - Nejvýše jeden proces v kritické sekci
- *Živost* - Každý požadavek na vstup kritické sekce je časem uspokojen
- *Uspořádání* (není nutné) - Předchází-li žádost jednoho procesu do kritické sekce kauzálně žádosti jiného procesu, tento proces by se měl do kritické sekce dostat dříve
- Uvažujeme navíc, že procesy neselhávají a komunikační kanály jsou perfektní (FIFO, zprávy se neduplikují, nevznikají, neztrácejí) a uvažujeme asynchronní systém s konečnou latencí
</markdown>

==== Analýza výkonnosti algoritmů pro vzájemné vyloučení ====
<markdown>

- *Komunikační zátěž* = počet zpráv poslaných při každém vstupu a výstupu do KS
- *Zpoždění klienta* = zpoždění procesu při vstupu do KS za předpokladu, že jiné procesy na vstup nečekají
- *Synchronizační zpoždění* = interval mezi vystoupením jednoho procesu z KS a vstoupením dalšího
</markdown>

==== Centralizovaný algoritmus ====
<markdown>

- Je zvolen jeden koordinátor
- Ten spravuje speciální token, který držiteli umožní vstup do KS a frontu požadavků na vstup do KS
- Před vstupem do KS je poslán požadavek na token koordinátorovi, po přijetí tokenu algoritmus vstupuje do kritické sekce
- Po výstupu je token vrácen koordinátorovi
- Koordinátor po přijetí požadavku na token předá token pokud jej drží, pokud jej nedrží, tak tento požadavek přidá do fronty
- Ve chvíli kdy koordinátor obdrží token tak zkontroluje frontu zda tam není žádný požadavek a případně jej obslouží
- Bezpečnost je zaručena, a živost za našich předpokladů také
- Komunikační zátěž - 2 zprávy vstup, 1 výstup
- Zpoždění klienta - 2 latence
- Synchronizační zpoždění - 2 latence
</markdown>

==== Kruhový algoritmus ====
<markdown>

- N procesů v kruhu
- Proces může poslat zprávu následníkovi
- Mezi procesy koluje jeden token
- Před vstupem proces čeká dokud neobdrží token
- Po vstupu proces pošle token následníkovi
- Pokud proces obdrží token a nečeká na vstup, tak jej hned předá dále
- Komunikační zátěž - $N$ vstup, $1$ výstup
- Zpoždění klienta - $0$ až $N$ zpráv
- Synchronizační zpoždění - $1$ až $N-1$ komunikačních latencí
</markdown>

==== Ricart-Agrawalův algoritmus ====
<markdown>
- Nepoužívá token, ale kauzalitu a multicast
- Nižší synchronizační zpoždění než kruhový algoritmus a nepoužívá centrální proces
- Každý proces si udržuje stav, který může nabývat 3 hodnot: WANTED, HELD, RELEASED (u všech procesů je inicializován na RELEASED)
1. identifikátor kritické sekce, kterou zamyká,
1. stav: *RELEASED*, *HELD* nebo *WANTED*, a
1. frontu odložených požadavků.

Na začátku je stav každého zámku každého procesu nastaven na *RELEASED*. V systému kolují pro každou kritickou sekci dva typy zpráv: `REQUEST` a `OK`

1. Pokud chce proces `P[i]` požádat o vstup do kritické sekce `K`, zaznamená čas `T[i]` kdy o zdroj žádá a pošle zprávu `REQUEST(K)` s tímto časem všem procesům, které do `K` přistupují. Nastaví stav svého zámku `K` na *WANTED*.
1. Zámek `K` procesu je ve stavu *WANTED* dokud neobdrží zprávu `OK(K)` od každého dalšího přistupujícího procesu. Poté se nastaví na *HELD*.
1. Pokud procesu `P[j]` přijde zpráva `REQUEST(K)` od procesu `P[i]` s časem `T[i]`, tak 
	- pokud je zámek `K` ve stavu *HELD*, pak zprávu `REQUEST(K)` zařadí mezi odložené požadavky a neodpoví
	- pokud je ve stavu *WANTED* a o vstup do kritické sekce žádal v čase `T[j] < T[i]`, případně `T[j] = T[i]` a `j < i`, pak zprávu `REQUEST(K)` zařadí mezi odložené požadavky a neodpoví,
	- jinak pošle zprávu `OK(K)` procesu `P[i]`.
1. Pokud proces `P[i]` dokončí práci v kritické sekci `K`, nastaví stav zámku `K` na *RELEASED*, odpoví na všechny zprávy ve frontě zámku a frontu vyprázdní.

- V nejhorším případě je nutno čekat než všech $(N-1)$ pošle OK
- Je zachováno pořadí, požadavky s nižší lamportovou značkou mají přednost
- Komunikační zátěž – $2(N-1)$ při vstupu, až $(N-1)$ při výstupu
- Zpoždění klienta – **2** latence
- Synchronizační zpoždění – 1 latence
</markdown>

===== Volba lídra v DS =====
**algoritmy pro volbu lídra a jejich vlastnosti**
<markdown>
- Cílem je, aby se všechny procesy shodly na jednom „koordinátorovi“ (lídrovi).  
- Předpokládáme možnost selhání (crash) procesů nebo spojení; zprávy se ale doručují spolehlivě.  
- Výsledek nesmí záviset na tom, kdo volbu odstartoval, a více souběžných voleb se musí slít do jedné (konvergence).
</markdown>

==== Kruhový algoritmus (Ring) ====
<markdown>
- Procesy tvoří logický kruh uspořádaný podle ID. Každý zná svého **následníka** a umí zjistit, zda soused žije.  
- **Start**: proces $P_i$ detekuje pád lídra a pošle zprávu `ELECTION(i)` svému následníkovi.  
- **Přijetí `ELECTION(j)`** u $P_i$  
  - pokud $j > i$: předá zprávu dál beze změny;  
  - pokud $j < i$: nahradí $j$ svým ID a pošle `ELECTION(i)`;  
  - pokud $j = i$: zpráva oběhla kruh ⇒ $P_i$ má nejvyšší ID ⇒ je vítěz.
- $P_i$ vyšle `ELECTED(i)` kolem kruhu; všichni si uloží, že koordinátor je $i$ a předají dál, dokud zpráva neoběhne kruh.
- **Komplexita**: $\mathcal{O}(n)$ zpráv a čas, kde $n$ je počet živých procesů. Funguje i s více paralelními volbami, protože nejvyšší ID zvítězí.
</markdown>

==== Algoritmus Bully ====
<markdown>
- **Assumpce**: úplná síť (každý zná všechny), procesy se dají porovnat dle ID; detekce pádu je „rychlá“ (time-outs).  
- **Kroky (z pohledu procesu $P_i$)**  
  1. $P_i$ zjistí, že koordinátor neodpovídá.  
  2. Pošle `ELECTION` *všem* procesům s **vyšším** ID.  
  3. Pokud **nikdo** neodpoví během timeoutu → $P_i$ se prohlásí koordinátorem, odešle `COORDINATOR(i)` všem procesům s nižším ID a volba končí.  
  4. Pokud přijde **alespoň jedno** `OK` od vyššího ID → $P_i$ čeká na zprávu `COORDINATOR(k)`; pokud po čase nedorazí, restartuje volby.  
  5. Po přijetí `COORDINATOR(k)` si každý proces uloží $k$ jako nového lídra.

- **Typy zpráv**  
  - `ELECTION` – „vyhlašuji volby, reaguj, pokud žiješ a máš vyšší ID“.  
  - `OK` – potvrzení, že vyšší proces existuje; potlačí menší ID.  
  - `COORDINATOR(k)` – oznámení výsledku všem.  

- **Vlastnosti**  
  - Garantuje, že zvítězí **nejvyšší živé ID** (“bully” přetlačí ostatní).  
  - Nejhorší případ $\mathcal{O}(n^2)$ zpráv (kaskáda voleb, když padá více procesů).  
  - Rychlejší konvergence než kruh, pokud selže jen koordinátor a vyšší ID je blízko.  
  - Netoleruje síťové rozdělení (“split brain”) – vyžaduje spolehlivé detekce crashů.
</markdown>
Trace: • b0b36pjv • b4b01jag • exams • b6b36ts1 • be4b39vgo • b4b39hry • b4b35osy
Search

Navigation

Print/export

Tools

QR Code
