Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b36pdv [2025/05/31 13:27] – [GPGPU] mistrjirka | statnice:bakalar:b4b36pdv [2025/06/04 22:52] (current) – [Logické hodiny a kauzalita] zapleka3 | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ===== Modely a architektury paralelních a distribuovaných systémů; prostředky pro jejich implementaci a základní algoritmy. ===== | + | ====== Modely a architektury paralelních a distribuovaných systémů; prostředky pro jejich implementaci a základní algoritmy. |
| [[https:// | [[https:// | ||
| Line 19: | Line 19: | ||
| - **Volba lídra v DS** – algoritmy pro volbu lídra a jejich vlastnosti. | - **Volba lídra v DS** – algoritmy pro volbu lídra a jejich vlastnosti. | ||
| - | /* | + | ===== Paralelní systémy/výpočty ===== |
| - | ################################################################################################################################################################################### | + | |
| - | ################################################################################################################################################################################### | + | ===== 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í |
| - | */ | + | |
| - | ===== Hardwarová podpora pro paralelní výpočty ===== | + | |
| - | **(super)skalární architektury, pipelining, spekulativní vyhodnocování, | + | |
| - | * (super)skalární architektury, pipelining, spekulativní vyhodnocování, | + | |
| - | * vlákna, procesy: (statnice: | + | |
| ==== Vektorové instrukce ==== | ==== Vektorové instrukce ==== | ||
| - | Často nazývané **SIMD** instrukce | + | Často nazývané **SIMD** instrukce |
| + | |||
| + | Vektorové instrukce vykonávají jednu danou operaci na velkém množství dat najednou. | ||
| + | Pracují nad speciálními vektorovými registry – až 512bit. | ||
| - | ektorové instrukce vykonávají jednu danou operaci na velkém množství dat najednou. | + | * To znamená, |
| - | Pracují nad specielními vektorovými registery - až 512bit. | + | * Umožňují značné zrychlení ve výpočetně náročných paralelizovatelných aplikacích, |
| - | Umožňují značné zrychlení ve výpočetně náročných paralelizovatelných aplikacích, | + | Moderní kompilátory jsou schopné automaticky vektorizovat části kódu. |
| - | Moderní kompilátory jsou schopné automaticky vektorizovat části kódu. | + | Pro znatelné zrychlení je ale často |
| - | Pro znatelné zrychlení je ale nutná manuální implementace. | + | |
| - | Narozdíl | + | Na rozdíl |
| Nevýhoda je často velmi komplikovaná implementace. | Nevýhoda je často velmi komplikovaná implementace. | ||
| Existuje mnoho standardů, nejznámější jsou x86 standardy: | Existuje mnoho standardů, nejznámější jsou x86 standardy: | ||
| - | * AVX | + | * AVX – starší, velmi rozšířený, |
| - | * AVX2 - novější, | + | * AVX2 – novější, přidává nové operace a 256bit |
| - | * AVX512 | + | * AVX512 |
| - | ==== GPGPU ==== | + | |
| - | * **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické akcelerátory jako masivně paralelní výpočetní jednotky. | + | ==== Instruction-Level Parallelism (ILP) ==== |
| - | * Typický desktopový GPU (např. NVIDIA Ampere) má tisíce jednoduchých jader sdružených do **streaming multiprocessorů (SM)**, které spouštějí stovky až tisíce vláken | + | |
| + | * **Zdroj ILP:** nezávislé aritmetické operace, nezávislé paměťové přístupy, nezávislé | ||
| + | | ||
| - | === Architektura a omezení | + | ==== Pipelining |
| + | * **Princip: | ||
| + | To umožňuje, aby různé instrukce byly zpracovávány současně v různých fázích – zvyšuje se **propustnost**, | ||
| + | * **Teoretický zisk:** až 1 instrukce / takt (IPC = 1); limitují ho hazardy a větvení. | ||
| + | * **Superpipelining: | ||
| + | * **Hazardy: | ||
| + | * datové – řeší se forwardingem, | ||
| + | * řídicí – predikce skoků + branch target buffer (BTB) | ||
| + | * strukturální – řeší se duplikací jednotek | ||
| - | * **Hierarchie výpočetních bloků:** GPC $\rightarrow$ SM $\rightarrow$ processing block $\rightarrow$ warp $\rightarrow$ thread. | + | ==== Skalární vs. superskalární procesory ==== |
| - | * **Sdílené prostředky SM:** | + | |
| - | * 128 KB *shared memory* + L1 cache | + | === Skalární procesor === |
| - | * max 64 warpů ≈ 2048 vláken na SM | + | * 1 instrukce za takt (IPC ≤ 1) |
| - | * 64 k 32-bit registrů; limit ≈ 255 registrů na vlákno (nižší počet registrů = vyšší | + | * jednodušší |
| - | * **Paměťová hierarchie GPU:** | + | * využívá pipelining |
| - | * L1/shared: ~33 cyklů | + | === Superskalární procesor === |
| - | * L2: až 2 TB/s (~200 cyklů) | + | * více instrukcí za takt (IPC > 1) |
| - | * HBM2: 1.5 TB/s (~290 cyklů) | + | * N-wide architektura (např. 4-wide = až 4 instrukce/takt) |
| - | * Host ↔ GPU: PCIe Gen4 ~32 GB/s, NVLink ~50 Gb/s pár signálů | + | * využívá ILP pomocí paralelního vykonávání více instrukcí |
| - | * ⇒ minimalizovat a slučovat přenosy mezi CPU ↔ GPU, i za cenu většího lokálního výpočtu.&# | + | |
| - | === Výpočetní výkon v praxi === | + | ==== Podtypy superskalární architektury |
| + | * **Statická: | ||
| + | * **Dynamická: | ||
| - | | Konfigurace | + | ==== Shrnutí rozdílu ==== |
| - | | Threadripper 3990X + RTX 4090 | 49 GFLOPS | + | * **Skalární CPU** ⇒ 1 instrukce/ |
| + | | ||
| - | *Na stejném stroji | + | ==== GPGPU ==== |
| + | * **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické karty pro obecné výpočty. | ||
| + | | ||
| + | * Ty spouštějí stovky až tisíce vláken najednou ve skupinách (warp – 32 vláken běžících lock-step). | ||
| - | === Programovací modely | + | === Architektura a omezení |
| + | * **Výpočetní hierarchie: | ||
| + | * **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ů | ||
| - | * **CUDA C/C++** – proprietární, | + | === Výpočetní výkon v praxi === |
| - | * **OpenCL | + | * Threadripper 3990X + RTX 4090: |
| - | * **SYCL | + | * single-thread: |
| - | * **OpenMP | + | * multi-thread CPU: 3.7 TFLOPS |
| - | * Další možnosti: Vulkan Compute, DirectX 12 Compute, Thrust (C++ algoritmy nad CUDA). | + | * CPU + GPGPU: **100 TFLOPS** |
| + | |||
| + | === Programovací modely === | ||
| + | | ||
| + | * **OpenCL** – otevřený standard | ||
| + | * **SYCL** – moderní C++ model | ||
| + | * **OpenMP target** – direktivy | ||
| === Typické úlohy === | === Typické úlohy === | ||
| - | + | | |
| - | * lineární algebra | + | |
| === Výhody === | === Výhody === | ||
| - | + | | |
| - | * **Obrovský teoretický throughput** (tisíce FP jednotek). | + | * efektivita |
| - | * **Energetická | + | * specializované |
| - | * **Specializované | + | |
| === Nevýhody === | === Nevýhody === | ||
| - | + | | |
| - | * **Paměťová latence** mimo L1/shared, nutnost koalesovaného přístupu. | + | |
| - | * **Omezená velikost registrů a shared memory** $\rightarrow$ ladění obsazenosti. | + | * přenosy |
| - | * **Drahé | + | * warp divergence |
| - | * **Divergence | + | * vendor |
| - | * **Vendor | + | |
| === Shrnutí === | === Shrnutí === | ||
| - | GPGPU nabízí **řádově vyšší | + | GPGPU nabízí **řádově vyšší výkon** než běžné |
| - | /* | + | |
| - | ################################################################################################################################################################################### | + | ==== Vlákna |
| - | ################################################################################################################################################################################### | + | * **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, |
| - | ===== Komplikace v paralelním programování ===== | + | * **Vlákno (thread)** je lehčí jednotka běhu uvnitř procesu. |
| - | **souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing)** | + | * Sdílí paměť a další prostředky s ostatními vlákny procesu. |
| - | * souběh (race condition), uváznutí (deadlock): (statnice:bakalar:b4b35osy) | + | * Přepínání mezi vlákny je levnější než mezi procesy. |
| + | * Vhodné pro paralelizaci uvnitř jedné aplikace – více úloh najednou | ||
| + | * 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ý | ||
| + | * **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, | ||
| + | |||
| + | ==== 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++) { | ||
| + | | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | * Ř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í | ||
| + | * 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) | ||
| + | </ | ||
| + | |||
| + | * 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 ==== | ==== False Sharing ==== | ||
| - | Nastává když dvě vlákna přistupují k **různým** | + | Nastává, když dvě vlákna přistupují k **různým** |
| - | Když jedno vlákno zapíše do cache svojí variable, tak se automaticky invalidují všechna data na stejné | + | |
| - | Pokud tedy tyto dvě vlákna konstantně tyto dvě promněné mění, dochází ke značnému poklesu výkonu. | + | * Pokud se to děje často, dochází k **velkému zpomalení**, |
| + | * Řešení: | ||
| + | * **Zarovnat proměnné** tak, aby každá byla na vlastní | ||
| + | * Přidat „padding“ mezi proměnné, které používají různá vlákna. | ||
| ==== True Sharing (není komplikace) ==== | ==== True Sharing (není komplikace) ==== | ||
| - | Nastává když dvě vlákna přistupují | + | Nastává, když dvě vlákna přistupují |
| - | + | | |
| - | Narozdíl od false sharing | + | * Typicky jde o sdílené čítače, fronty, stavové proměnné atd. |
| - | /* | ||
| - | ################################################################################################################################################################################### | ||
| - | ################################################################################################################################################################################### | ||
| - | ################################################################################################################################################################################### | ||
| - | */ | ||
| - | ===== Podpora paralelního programování v C a C++ ===== | + | ===== 3. Podpora paralelního programování v C a C++ ===== |
| - | **pthreads, thread, jthread, atomic, | + | 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:: |
| - | * pthreads: | + | ==== POSIX vlákna (pthreads) |
| - | * thread: | + | * `pthreads` (POSIX Threads) je **standardní rozhraní |
| - | * jthread: C++20 přidává | + | * Poskytuje funkce pro: |
| + | * **vytváření vláken**: `pthread_create()` | ||
| + | * **synchronizaci | ||
| + | * **mutexy**: `pthread_mutex_lock()`, `pthread_mutex_unlock()` | ||
| + | * **podmínkové | ||
| + | * **semafory**: | ||
| + | |||
| + | 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 | ||
| + | * Umožňuje jednoduché vytvoření a správu vláken | ||
| + | * Vlákno spustíme předáním funkce (nebo lambdy) do konstruktoru. | ||
| + | * Synchronizace se řeší | ||
| + | |||
| + | Výhodou oproti `pthreads` je **vyšší přehlednost, | ||
| + | |||
| + | ==== std::jthread (C++20) ==== | ||
| + | * Od C++20 přibyla nová třída `std:: | ||
| + | * Při zničení objektu se vlákno **automaticky ukončí** (`join()` nebo `detach()`). | ||
| + | * Má vestavěnou podporu pro **zrušení | ||
| + | * Výborně se hodí pro práci s **RAII přístupem** | ||
| + | |||
| + | To znamená, že se snižuje riziko zapomenutého `join()` a tím i potencionálních chyb. | ||
| ==== Mutex a Lock Guard ==== | ==== Mutex a Lock Guard ==== | ||
| - | Mutex (mutual exclusion) je synchronizační | + | **Mutex** (*mutual exclusion*) je synchronizační |
| + | * V C++ se používá `std::mutex` a jeho varianty: | ||
| + | * `std:: | ||
| - | Ukázkový kód: | + | Ukázka (ruční zamykání/ |
| <code cpp> | <code cpp> | ||
| #include < | #include < | ||
| Line 149: | Line 253: | ||
| mtx.lock(); | mtx.lock(); | ||
| // Kritická sekce | // Kritická sekce | ||
| - | std::cout << " | + | std::cout << " |
| mtx.unlock(); | mtx.unlock(); | ||
| }; | }; | ||
| Line 163: | Line 267: | ||
| </ | </ | ||
| - | Moderní | + | *Moderní |
| - | <code cpp> | + | |
| + | <code cpp> | ||
| #include < | #include < | ||
| #include < | #include < | ||
| Line 187: | Line 291: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | |||
| </ | </ | ||
| ==== Atomic ==== | ==== Atomic ==== | ||
| - | 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 podstatě je to jako mutex, ale bez zamykání a odemykání. Atomic proměnné | + | * V C++ se používá `std::atomic<T>` – kde `T` může být např. `int`, `bool`, pointer apod. |
| + | | ||
| + | * Pokud HW atomické | ||
| + | |||
| + | V praxi jsou tedy `std:: | ||
| <code cpp> | <code cpp> | ||
| Line 220: | Line 327: | ||
| </ | </ | ||
| + | * Jinými slovy – `std:: | ||
| - | + | ===== 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í |
| - | ################################################################################################################################################################################### | + | |
| - | ################################################################################################################################################################################### | + | |
| - | ################################################################################################################################################################################### | + | |
| - | */ | + | |
| - | ===== Podpora paralelního programování v OpenMP ===== | + | |
| - | **sériově-paralelní | + | |
| ==== Sériově-paralelní model uspořádání vláken (fork-join) ==== | ==== 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 | + | 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 |
| - | Výhody: jednoduchá správa vláken, sdílená paměť | + | |
| + | * jednoduchá správa vláken | ||
| + | * sdílená paměť | ||
| + | * předvídatelné chování a synchronizace | ||
| - | < | + | Ukázkový kód: |
| - | - **Explicitní synchronizace uvnitř regionu** | + | <code cpp> |
| - | - `#pragma omp barrier` – ruční bariéra. | + | |
| - | - `single` / `master` – sekci vykoná pouze jedno vlákno. | + | |
| - | - `ordered` – zachování pořadí iterací ve smyčce. | + | |
| - | - `critical(name)` nebo `atomic` – sériový přístup k proměnné či úseku. | + | |
| - | + | ||
| - | - **Omezení serializace** | + | |
| - | Přidej klauzuli `nowait`, pokud bariéru na konci *work-sharing* konstrukce nepotřebuješ. | + | |
| - | + | ||
| - | - **Vnořená paralelizace** | + | |
| - | Výchozí stav je vypnutý (`OMP_NESTED=TRUE` nebo `omp_set_max_active_levels()` ji zapne). | + | |
| - | + | ||
| - | - **Tasky a datové závislosti** | + | |
| - | `task`, `taskgroup`, | + | |
| - | + | ||
| - | + | ||
| - | Ukázkový kód (C): | + | |
| - | + | ||
| - | ```c | + | |
| #include < | #include < | ||
| #include < | #include < | ||
| Line 266: | Line 353: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | ```` | + | </code> |
| - | </markdown> | + | |
| - | Poznámka: **Fork-join v OpenMP vytváří vlákna, nikoli samostatné procesy**. Implementace obvykle stojí na POSIX/ | + | |
| - | ===== Různé implementace | + | * Poznámka: |
| - | Běžně používané kompilátory a knihovny OpenMP (stav jaro 2025): | + | |
| - | < | + | Další možnosti a doplňky modelu: |
| - | | Implementace | Kompilátor / knihovna | Úroveň podpory | Poznámky | | + | * `#pragma omp barrier` – ruční synchronizační bod. |
| - | |--------------|----------------------|----------------|----------| | + | * `single`, `master` – sekci vykoná pouze jedno vlákno. |
| - | | **GCC 14+ (libgomp)** | `-fopenmp` | 5.2 (téměř úplná) | Dlouhodobá open-source volba. | | + | |
| - | | **LLVM/Clang 18+ (libomp)** | `-fopenmp` | 5.2 (většina) | Dobrá diagnostika, | + | * `critical`, `atomic` – zajištění sériového přístupu ke sdíleným proměnným. |
| - | | **Intel oneAPI (icx/icpx + iomp5)** | `-qopenmp` | 5.2 | Vysoce optimalizovaný runtime, podporuje offload | + | * `nowait` – zabrání implicitní bariéře |
| - | | **IBM XL / LLVM-based** | `-qsmp=omp` | 5.1 | Optimalizace pro POWER. | | + | * `OMP_NESTED=TRUE` nebo `omp_set_max_active_levels()` – aktivuje vnořenou paralelizaci. |
| - | | **AMD AOCC 4.x** | Clang + libomp | 5.1 | Laděno pro Zen architekturu. | | + | * `task`, `taskgroup`, |
| - | | **Cray/AMD ROCm (OpenMP Offload)** | Clang | 5.2 | Zaměřeno na akcelerátory a HPC. | | + | |
| - | </ | + | |
| - | ==== Přehled hlavních direktiv OpenMP | + | ==== 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: | ||
| + | * `detach`, `priority` – umožňují pokročilou kontrolu provádění. | ||
| - | * **`parallel`** – vytvoří tým vláken; podporuje klauzule `if`, `num_threads`, | + | Příklad: |
| - | * **`for` / `do`** – paralelizuje smyčku; plánování (`schedule(static|dynamic|guided)`), | + | <code cpp> |
| - | * **`sections` / `section`** – spustí nezávislé bloky kódu souběžně. | + | #pragma omp task depend(out: A) { |
| - | * **`task`** – vytvoří paralelizovatelnou úlohu, volitelně s `depend`, `priority`, `detach`. | + | // vypočítáme A |
| - | * **`barrier`** – explicitní synchronizační bod všech vláken týmu. | + | } |
| - | * **`critical [ (name) ]`** – sekce, do které může současně vstoupit jen jedno vlákno; pojmenování odděluje nezávislé kritické sekce. | + | |
| - | * **`atomic`** – nejlehčí synchronizace pro jednoduché operace na sdílené proměnné (`update`, `read`, `write`, …). | + | |
| - | </markdown> | + | #pragma omp task depend(in: A) { |
| + | // použijeme A | ||
| + | } | ||
| + | </code> | ||
| - | ==== Příklad zapojení všeho dohromady | + | ==== Různé implementace OpenMP specifikace |
| - | Ukázka kombinuje `parallel`, `for`, tasky a závislosti: | + | 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), | ||
| + | * **Intel oneAPI (icx/icpx + iomp5)** – `-qopenmp`, verze 5.2, velmi výkonný runtime, podpora GPU. | ||
| + | * **IBM XL (LLVM-based)** – `-qsmp=omp`, | ||
| + | * **AMD AOCC 4.x** – laděno pro AMD Zen, Clang + libomp. | ||
| + | * **Cray/ | ||
| + | |||
| + | ==== Přehled hlavních direktiv OpenMP ==== | ||
| + | **`#pragma omp parallel`** | ||
| + | * Vytvoří tým vláken. | ||
| + | * Podporuje: `num_threads`, | ||
| + | **`for` / `do`** | ||
| + | * Paralelizace smyčky. | ||
| + | * Možnosti: `schedule(static|dynamic|guided)`, | ||
| + | **`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, | ||
| + | |||
| + | ==== Příklad zapojení všeho dohromady ==== | ||
| + | < | ||
| #include < | #include < | ||
| #include < | #include < | ||
| Line 311: | Line 426: | ||
| { | { | ||
| int sum = 0; | int sum = 0; | ||
| - | | + | |
| - | #pragma omp parallel for reduction(+\:sum) nowait | + | #pragma omp parallel for reduction(+ : sum) nowait |
| for (int i = 0; i < 1e6; ++i) | for (int i = 0; i < 1e6; ++i) | ||
| sum += i; | sum += i; | ||
| - | | + | |
| printf(" | printf(" | ||
| } | } | ||
| Line 323: | Line 438: | ||
| printf(" | printf(" | ||
| } | } | ||
| - | } // implicit taskgroup | + | } // implicit taskgroup |
| return 0; | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | Tento příklad ukazuje vytvoření tasku se závislostí `depend(out: | ||
| - | } </ | ||
| + | ===== 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 ==== |
| - | ################################################################################################################################################################################### | + | |
| - | ################################################################################################################################################################################### | + | * Např. pomocí `schedule(static[, |
| - | ################################################################################################################################################################################### | + | * 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é**, |
| + | * **Dynamické rozdělení** – práce se přiděluje **za běhu** podle toho, které vlákno je volné. | ||
| + | * Používá se `schedule(dynamic[, | ||
| + | * 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[, | ||
| + | * 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. | ||
| - | ===== Techniky dekompozice programu ===== | + | ==== Thread-pool a fronta úkolů (work-stealing) |
| - | **statické a dynamické rozdělení práce. Thread-pool a fronta úkolů. Balancování a závislosti | + | * 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 | ||
| + | * Každé vlákno má vlastní **lokální deque** | ||
| + | | ||
| + | * Tento přístup pomáhá **automaticky vyvažovat zátěž**. | ||
| + | * Push/pop na vlastní frontě jsou většinou **lock-free**; | ||
| - | < | + | ==== Balancování zátěže ==== |
| - | ### Statické × dynamické | + | Vyrovnané |
| - | - **Statické rozdělení** (`schedule(static[, | + | * U **smyček**: |
| - | - **Dynamické rozdělení** (`schedule(dynamic[, | + | * Volba správného |
| - | - **Guided** (`schedule(guided[, | + | * Velikost |
| - | - Další volby: `runtime` (čte z `OMP_SCHEDULE`), `auto` (nechá výběr na runtime). | + | * `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í | ||
| + | * Heuristiky runtime mohou **omezit vznik malých tasků** | ||
| - | ### Thread-pool a fronta úkolů | + | ==== Závislosti |
| - | - První paralelní region vytvoří | + | Tasky mohou mít mezi sebou **závislosti**, které určují pořadí provádění. V OpenMP |
| - | - Každé vlákno udržuje | + | * Typy závislostí: |
| - | - Fronty se většinou zamykají jen při krádeži, takže běžné push/pop jsou lock-free a škálují. | + | * `depend(in: X)` – task **potřebuje** data `X`. |
| + | | ||
| + | * `depend(inout: X)` – task `X` čte i zapisuje. | ||
| + | * Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře. | ||
| - | ### Balancování zátěže | + | Ukázkový kód: |
| - | - **Smyčky**: volba plánu (`static`, `dynamic`, `guided`), velikost chunku, případně `collapse(n)` pro součtové smyčky. | + | <code cpp> |
| - | - **Tasky**: work-stealing, | + | #pragma omp task depend(out:A) |
| + | build_A(); | ||
| - | ### Závislosti (dependencies) | + | #pragma omp task depend(in: |
| - | - Tasks mohou deklarovat závislosti pomocí `depend` – `in`, `out`, `inout`, `mutexinoutset`, | + | build_B(); |
| - | ```c | + | |
| - | #pragma omp task depend(out: | + | |
| - | build_A(); | + | |
| - | | + | |
| - | build_B(); | + | |
| - | #pragma omp task depend(in: | + | |
| - | use_B(); | + | |
| - | ```` | + | |
| - | * Runtime tvoří orientovaný acyklický graf; když jsou všechny závislosti splněné, | + | #pragma omp task depend(in: |
| + | use_B(); | ||
| + | </ | ||
| - | | + | |
| + | * 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, | ||
| + | |||
| + | ===== 6. Techniky dekompozice programu na příkladech ===== | ||
| + | Abychom lépe pochopili různé způsoby paralelizace, | ||
| - | ===== Techniky dekompozice programu na příkladech ===== | ||
| ==== Řazení ==== | ==== Řazení ==== | ||
| **quick sort a merge sort** | **quick sort a merge sort** | ||
| === Quick sort === | === Quick sort === | ||
| - | < | + | * **Proč „rozděl a panuj“? |
| - | - **Proč „rozděl a panuj“? | + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | - Paralelizace: | + | |
| - | - Zdrojový kód: | + | < |
| - | ```cpp | + | |
| void qs(std:: | void qs(std:: | ||
| if (to - from <= base_size) { | if (to - from <= base_size) { | ||
| Line 399: | Line 540: | ||
| } | } | ||
| } | } | ||
| - | ```` | + | </ |
| - | </ | + | === 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: | ||
| - | === Merge sort === | + | <code cpp> |
| - | <markdown> | + | |
| - | + | ||
| - | * **Proč „rozděl a panuj“? | + | |
| - | + | ||
| - | * *Divide*: pole se **rozpůlí** na levé a pravé podpole, dokud nedojdeme k malému úseku. | + | |
| - | * *Conquer*: každé z půlek se **třídí rekurzivně**, | + | |
| - | * *Combine*: dvě seřazené půlky se **slijí** lineárním `merge`, čímž vznikne seřazené pole větší velikosti. | + | |
| - | * Paralelizace: | + | |
| - | * Zdrojový kód: | + | |
| - | + | ||
| - | ```cpp | + | |
| void ms(std:: | void ms(std:: | ||
| if (to - from <= base_size) { | if (to - from <= base_size) { | ||
| Line 431: | Line 566: | ||
| | | ||
| } | } | ||
| - | ``` | + | </code> |
| - | + | ||
| - | </markdown> | + | |
| ==== Numerická lineární algebra a strojové učení ==== | ==== Numerická lineární algebra a strojové učení ==== | ||
| Line 439: | Line 572: | ||
| === Paralelní násobení matice × vektor (SpMV/Dense MV) === | === Paralelní násobení matice × vektor (SpMV/Dense MV) === | ||
| - | < | + | * **Princip: |
| - | - **Princip: | + | |
| - | | + | |
| - | | + | |
| - | | + | * U husté matice: nejlepší přístup po řádcích (row-major). |
| + | * U řídké: paralelizace přes nenulové řádky (např. CSR formát). | ||
| - | - **Paměťové locality: | + | < |
| - | - U husté matice je nejvýhodnější iterovat *po řádcích* (souvislý přístup k paměti). | + | |
| - | - U řídké (CSR) se iteruje přes neprázdné hodnoty; princip paralelizace je stejný. | + | |
| - | + | ||
| - | - **Ukázkový kód:** paralelizace přes `omp parallel for`; žádná redukce není nutná, protože každé vlákno píše do unikátního prvku `y[i]`. | + | |
| - | </ | + | |
| - | < | + | |
| void matvec_dense(const std:: | void matvec_dense(const std:: | ||
| const std:: | const std:: | ||
| Line 466: | Line 594: | ||
| === Paralelní násobení dvou matic === | === Paralelní násobení dvou matic === | ||
| - | < | + | * **Naivní |
| - | - **Naivní prvek-po-prvku ($c_{ij}$)** škáluje, ale má špatnou | + | |
| - | - **Blokové (tiling) | + | * **Blokové (tiling) |
| - | | + | |
| - | | + | |
| - | ```c | + | |
| - | # | + | |
| - | for (int bi = 0; bi < N; bi += BS) | + | |
| - | for (int bj = 0; bj < N; bj += BS) | + | |
| - | for (int bk = 0; bk < N; bk += BS) | + | |
| - | | + | |
| - | ``` | + | |
| - | 3. *Combine* není potřeba – bloky zapisují do oddělených částí $C$. | + | |
| - | - **Work-stealing runtime** OpenMP při dynamickém rozvrhu zajistí, že vlákna s prázdnou frontou převezmou volné bloky → lepší vyvážení. | + | <code cpp> |
| - | - **Prakticky: | + | #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); | ||
| + | </ | ||
| + | |||
| + | | ||
| === Paralelní řešení systému lineárních rovnic (Gaussova eliminace) === | === Paralelní řešení systému lineárních rovnic (Gaussova eliminace) === | ||
| - | < | + | * **Gaussova eliminace (LU)**: v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$. |
| - | - **Gauss / LU**: pro každý krok $k$ lze *paralelně* provést eliminaci | + | |
| - | - Závisí na pivotu $A_{kk}$, takže v kroku $k$ musí být ukončené všechny změny z kroku $k-1$. | + | * Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti. |
| - | - `#pragma omp parallel for` na vnější smyčce řádků, `nowait` nelze kvůli závislostem. | + | |
| - | - **Ukázkový kód (bez otočných pivotů): | + | < |
| - | </ | + | |
| - | < | + | |
| void gauss_elim(std:: | void gauss_elim(std:: | ||
| for (int k = 0; k < ROWS - 1; ++k) { | for (int k = 0; k < ROWS - 1; ++k) { | ||
| Line 504: | Line 628: | ||
| } | } | ||
| </ | </ | ||
| - | < | ||
| - | - **Iterativní metody (CG, GMRES, Jacobi)** se paralelizují ještě lépe: operují hlavně s mat-vec a vektorovými redukcemi, kde OpenMP poskytuje hotové `reduction(+: | ||
| - | - **GPU / accelerator off-load:** v OpenMP | + | * **Iterativní metody (Jacobi, CG, GMRES)**: |
| - | jádro se provede na GPU, host kontroluje | + | |
| - | </ | + | |
| - | ===== Úvod do distribuovaných systémů | + | * **Off-load na GPU (OpenMP 5.x)**: |
| - | **charakteristiky DS, čas a typy selhání v DS** | + | * Pomocí `target teams distribute parallel for` lze výpočet přenést na GPU. |
| + | | ||
| - | DS je soubor nezávislých, | ||
| - | 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 | + | ===== Distribuované |
| - | Asynchronní x Synchronní | + | ===== 1. Úvod do distribuovaných systémů (DS) ===== |
| - | Asynchronní nemají žádné limity na rychlost vykonávání procesů | + | Distribuované systémy (DS) jsou o tom, jak spolupracují **nezávislé výpočetní jednotky**, které spolu **nesdílejí paměť |
| - | - Selhání procesu | + | *Distribuovaný systém je*: |
| - | * crash / fail-stop - proces | + | * soustava **autonomních |
| - | * libovolné | + | * komunikace probíhá **pouze zprávami** (message passing), |
| - | | + | * **žádná sdílená paměť**, **žádné globální hodiny**, |
| - | | + | |
| - | | + | * každý proces má **lokální hodiny**, které mohou běžet různou rychlostí. |
| - | | + | |
| - | Předpoklady | + | Kvůli těmto vlastnostem je velmi těžké se v systému spolehlivě orientovat v čase – nemůžeme dát pevný limit na doručení |
| - | Spolehlivé | + | |
| - | ===== Detekce selhání v DS ===== | + | ==== Asynchronní × Synchronní |
| - | **detektory selhání | + | Tyto modely popisují „jaký svět“ předpokládáme při návrhu distribuovaného algoritmu – tedy **jaké vlastnosti sítí, hodin a chování procesů** budeme brát jako dané. |
| - | **úplnost** - každé selhání je časem detekováno alespoň jedním bezvadným procesem | + | === Synchronní model === |
| + | | ||
| + | * zpoždění zpráv, | ||
| + | * rychlost výpočtu, | ||
| + | * odchylku mezi hodinami. | ||
| + | * Můžeme navrhovat algoritmy ve **fázích (kolech)** a spolehlivě používat timeouty. | ||
| + | * Takto předvídatelné sítě se v praxi téměř **nevyskytují** – je to spíš teoretický model. | ||
| - | **přesnost** - nedochází k mylné detekci | + | === Asynchronní model === |
| + | | ||
| + | * Timeouty **nejsou spolehlivé** – nelze říct, jestli se proces „jen zpozdil“ nebo opravdu „spadl“. | ||
| + | * Například slavný důkaz **FLP** ukazuje, že **v asynchronním modelu není možný deterministický konsensus**, pokud může padnout byť jen jeden proces. | ||
| - | nelze dosáhnout obou vlastností současně, je vyžadována | + | === Částečně synchronní model === |
| + | * Realistický kompromis: | ||
| + | * Systém se může nějakou dobu chovat asynchronně, **ale nakonec se „ustálí“** a začne dodržovat limity. | ||
| + | * Většina reálných protokolů (např. **Raft**, **PBFT**) počítá právě s tímto modelem. | ||
| + | * Výhoda: **odolnost vůči výpadkům i výkyvům**, | ||
| + | ==== Typy selhání v distribuovaných systémech ==== | ||
| + | V DS musíme počítat s tím, že **něco selže** – a často i nepozorovaně. Rozlišujeme: | ||
| + | * **Selhání procesu**: | ||
| + | * *crash / fail-stop* – proces přestane fungovat (nic už neposílá). | ||
| + | * *byzantské (libovolné) selhání* – proces dál funguje, ale **chybně** (např. posílá nesmysly, nebo se chová škodlivě). | ||
| + | * **Selhání kanálu**: | ||
| + | * *ztráta zprávy* – zpráva se ztratí v síti. | ||
| + | * *partitioning* – síť se rozdělí na **oddělené oblasti**, které spolu **nemohou komunikovat**. | ||
| + | * **Selhání časování**: | ||
| + | * odezva procesu nebo zprávy překročí **očekávané časové limity** – může jít o zpoždění i výpadek. | ||
| - | Frekvence selhání roste lineárně s počtem procesů ve skupině (selhání jsou běžná) | + | ==== Předpoklady na komunikační kanál ==== |
| + | Distribuované algoritmy často **předpokládají vlastnosti komunikační vrstvy** – obvykle se uvažuje tzv. „ideální, | ||
| - | Dva podprotokoly - detekce selhání a šíření informace o selhání | + | * **spolehlivé doručení** – žádné ztráty zpráv, |
| + | * **žádné duplikace** – zprávy se nedoručují víckrát, | ||
| + | * **žádné falešné zprávy** – proces nemůže dostat zprávu, kterou nikdo neposlal, | ||
| + | * **zachování pořadí** – zprávy mezi dvěma procesy dorazí ve stejném pořadí, v jakém byly odeslány. | ||
| - | Průběh detekce: | + | Tato vlastnosti se často **simulují vyšší vrstvou (např. TCP)**, ale ne vždy – a je třeba s tím počítat při návrhu protokolu. |
| - | - 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 | + | ===== 2. Detekce |
| + | V distribuovaných systémech je běžné, že některé procesy selžou – a aby systém mohl dál správně fungovat, ostatní uzly se to musí nějak **včas a spolehlivě dozvědět**. K tomu slouží tzv. **detektory selhání**, | ||
| - | === Centralizovaný heartbeat === | + | Jenže v distribuovaném prostředí nemáme jistotu, jestli uzel selhal, nebo je jen dočasně pomalý (např. síťová prodleva) – a proto je detekce selhání **zásadně nejistá**. Tato kapitola rozebírá vlastnosti detektorů selhání, různé typy heartbeat protokolů a praktický algoritmus SWIM. |
| - | Heartbeat jsou odesílány periodicky, každých $\mathcal{T}$ jednotek | + | |
| - | Heartbeat má pořadové | + | ==== Vlastnosti detektorů selhání ==== |
| + | * **Úplnost (completeness)** | ||
| + | * Každé skutečné selhání | ||
| + | * **Přesnost (accuracy)** | ||
| + | * Detektor **nemá falešné poplachy** – neoznačí proces | ||
| - | Pokud není heartbeat od $p_i$ přijat v $p_j$ v časovém limitu $\tau$, je $p_i$ označen jako havarovaný | + | Nelze zaručit obě vlastnosti zároveň (dle FLP výsledku) – proto většina systémů **upřednostňuje úplnost**, i když občas dojde k mylné detekci. |
| - | Je úplný pro všechny uzly kromě $p_j$, selhání $p_j$ není detekováno a při velkém počtu | + | Jinými slovy: **lepší je omylem někoho považovat za mrtvého, než si nevšimnout, |
| + | |||
| + | * Frekvence | ||
| + | |||
| + | ==== Průběh detekce ==== | ||
| + | - Proces | ||
| + | - Jiný proces $p_k$ jeho selhání **zjistí** (např. nepřišel heartbeat). | ||
| + | - Proces $p_k$ **šíří informaci** o selhání $p_j$ dalším | ||
| + | |||
| + | ==== Typy detekčních protokolů ==== | ||
| + | |||
| + | === Centralizovaný heartbeat === | ||
| + | * Každý uzel **periodicky posílá heartbeat** jednomu vybranému procesu | ||
| + | * $p_j$ si udržuje čítač a čas posledního | ||
| + | * Pokud nedorazí heartbeat během $\tau$ → $p_i$ je považován za selhaný. | ||
| + | **Vlastnosti: | ||
| + | * Jednoduchá implementace. | ||
| + | * **Nezjistí selhání $p_j$ samotného** – není nikdo, kdo by ho hlídal. | ||
| + | * $p_j$ může být **přetížen**, | ||
| === Kruhový heartbeat === | === Kruhový heartbeat === | ||
| - | Heartbeats jsou odesílány | + | * Každý proces |
| + | * Lze použít **jednosměrný** | ||
| - | | + | **Vlastnosti: |
| - | * není úplné při selhání více procesů (stačí jeden u jednosměrného, 2 u obousměrného) | + | * Není žádný centrální bod → lepší škálování. |
| - | * je třeba | + | * **Není úplný**, pokud selže |
| + | * Nutno **udržovat kruhovou | ||
| - | === All to all heartbeat === | + | === All-to-all heartbeat === |
| - | každý proces | + | Každý uzel **periodicky odesílá heartbeat všem ostatním**. |
| - | | + | |
| - | | + | |
| - | * 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 === | + | **Vlastnosti: |
| - | **Scalable weakly consistent infection-style proces group membership protocol** | + | * **Vysoká úplnost** – každý je hlídán všemi. |
| + | * Rovnoměrná zátěž mezi uzly. | ||
| + | * **Nízká přesnost** – síťové zpoždění může vést k falešnému označení za mrtvého. | ||
| + | * **Velké zatížení sítě** – škáluje špatně pro stovky uzlů. | ||
| - | * proces $p_i$ periodicky odesílá zprávu $\texttt{ping}$ náhodně vybranému uzlu $p_j$ a čeká na odpověď $\texttt{ack}$ | + | === SWIM protokol === |
| - | * pokud ji nedostance, odešle zprávu $\texttt{ping\_req}$ $\mathcal{K}$ náhodně vybraným uzlům | + | **Scalable Weakly-consistent Infection-style Membership** |
| - | * tyto uzly se zeptají $p_j$ pomocí zprávy $\texttt{ping}$ a pokud dostanou odpověď, odešlou ji $p_i$ jako $\texttt{ping\_ack}$ | + | |
| - | | + | |
| - | přesnost lze nastavit volbou $\mathcal{K}$, klesá exponenciálně s rostoucím $\mathcal{K}$ | + | Moderní |
| - | úplnost je zaručena, průměrný čas detekce je $\frac{e}{e - 1}\mathcal{T}$ | + | Každý proces $p_i$ periodicky: |
| + | - Posílá `ping` náhodnému uzlu $p_j$ a čeká na `ack`. | ||
| + | - Pokud žádná odpověď nepřijde, požádá | ||
| + | | ||
| + | - Pokud nikdo z $\mathcal{K}$ nedostane odpověď → $p_j$ je označen za mrtvého. | ||
| - | ===== Čas a kauzalita v DS ===== | + | **Vlastnosti: |
| - | **uspořádání událostí v DS, fyzické hodiny a jejich synchronizace, logické hodiny a jejich synchronizace** | + | * **Přesnost** lze nastavit volbou $\mathcal{K}$ – roste s $\mathcal{K}$, chybovost klesá exponenciálně. |
| + | | ||
| + | * **Průměrný čas detekce**: | ||
| + | * $\frac{e}{e - 1} \mathcal{T}$ | ||
| + | * průměrná délka detekčního cyklu v SWIM protokolu | ||
| + | * Dobře funguje i ve velkých systémech (1000+ uzlů). | ||
| - | clock slew - rozdíl v času hodin dvou procesů, mají li dvoje hodiny nenulovou mimoběžnost, | ||
| - | clock drift - rozdíl | + | ===== 3. Čas a kauzalita |
| + | V běžném programu máme přesné hodiny, které říkají, kdy se co stalo. V distribuovaném systému ale žádné „společné“ hodiny nemáme – každý uzel má své vlastní a běží jinak rychle. Proto je v DS mnohem důležitější **pořadí a závislosti událostí** než konkrétní čas. V této kapitole si vysvětlíme, | ||
| - | synchronizace | + | ==== Problémy s časem v DS ==== |
| - | * externí | + | * **Clock slew** – rozdíl ve skutečném čase mezi dvěma procesy. |
| - | | + | * **Clock drift** – rozdíl v rychlosti běhu hodin (jeden |
| - | * externí hodiny mohou být napojeny na UTC nebo atomové hodiny | + | * To znamená, že hodiny **nelze úplně sladit**, jen přiblížit. |
| - | | + | |
| - | | + | |
| - | | + | |
| - | * 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) | + | ==== Synchronizace |
| + | Synchronizace může být: | ||
| - | Cristianův algoritmus | + | === Externí synchronizace === |
| - | $$ \mathcal{C}_i \coloneq t + \frac{\mathcal{T}_\text{RT}-l_{\text{min}+l' | + | * Každý proces $p_i$ má své hodiny |
| - | chyba je omezena, tj maximálně | + | * Např. atomové hodiny, UTC, NTP servery. |
| + | * $|\mathcal{C}_i - \mathcal{S}| \leq \delta$ | ||
| + | * Každý uzel se snaží držet v intervalu $\delta$ od globálního času | ||
| + | * Typický příklad: **NTP (Network Time Protocol)**. | ||
| - | lokální | + | === Interní synchronizace === |
| + | * Zajišťuje, | ||
| + | * Formálně: $|\mathcal{C}_i - \mathcal{C}_j| \leq \delta$ | ||
| + | * Rozdíl mezi hodinami dvou uzlů je nejvýše $\delta$ | ||
| + | * Není vázaná na žádný „reálný | ||
| + | * Např. **Berkeley algorithm**. | ||
| - | NTP | + | ==== Praktické algoritmy |
| - | * 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 | + | |
| - | * $o = \frac{(t_1^{r} - t_2^{r}+t_2^{s} - t_1^{s})}{2}$ | + | |
| - | Logické hodiny | + | === Cristianův algoritmus === |
| + | * Klient se zeptá serveru: *„Kolik je hodin? | ||
| + | * Server odpoví, a klient si upraví svůj čas podle: | ||
| - | nepoužívají přímo aktuální čas ale časovou značku | + | $\mathcal{C}_i := t + \frac{\mathcal{T}_{RT} - l_{\text{min}} - l' |
| + | * RTT mínus odhadnutá minimální latence tam i zpět, děleno dvěma | ||
| - | kauzální vztah - první událost může ovlivnit druhou | + | Očekávaná **chyba synchronizace** je: $\leq \frac{\mathcal{T}_{RT} |
| - | 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}$, | ||
| - | - 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}$, | ||
| - | Kauzální nezávislost | + | Lokální |
| - | * relace stalo se před zavádí | + | |
| - | * $e_1$ -> $e_2$: potenciálně kauzálně závislé události ($e_2$ mohlo být ovlivněno $e_1$, ale nemuselo) | + | |
| - | | + | |
| - | Lamportovy logické hodiny - každý proces má své logické hodiny, které | + | === NTP === |
| + | * Servery tvoří **stromovou hierarchii** (stratum 0, 1, 2, …). | ||
| + | * Uzly synchronizují čas s rodiči i některými sousedy. | ||
| + | * Latence | ||
| - | Synchronizace logických hodin | + | $o = \frac{(t_1^{r} - t_2^{r} + t_2^{s} - t_1^{s})}{2}$ |
| - | - po každé události která se odehraje v $p_i$ se hodiny $\mathcal{C}_i$ inkrementují | + | * vypočtený odhad ofsetu mezi hodinami klienta |
| - | - každé zprávě $m$ odeslané procesem $p_i$ je přiřazená časová značka $ts(m) | + | |
| - | | + | |
| - | - 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 | + | ==== Logické |
| - | * Platí: jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$ | + | Logické hodiny nejsou o „skutečném čase“, ale o **pořadí událostí**. Nepotřebují |
| - | | + | |
| - | Vektorové hodiny - každý proces si udržuje vektor celočíselných hodin ostatních procesů | + | === Kauzální vztah – relace „stalo se před“ (→) === |
| + | Událost $\mathcal{A}$ **mohla ovlivnit** událost $\mathcal{B}$, | ||
| - | ===== Globální stav v DS a jeho výpočet ===== | + | * $\mathcal{A} \rightarrow \mathcal{B}$ – pokud obě nastaly ve stejném procesu |
| - | **řez distribuovaného výpočtu, algoritmus pro distribuovaný globální snapshot, stabilní vlastnosti DS** | + | * nebo $\mathcal{A}$ je odeslání zprávy a $\mathcal{B}$ je její přijetí, |
| + | | ||
| - | 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 | + | === Kauzální nezávislost === |
| + | * Události $e_1$, $e_2$ jsou **současné** (nezávislé), | ||
| + | * Jinými slovy: | ||
| - | globální snapshot je záznam globálního stavu | + | === Lamportovy logické hodiny === |
| + | Každý proces si udržuje **číselnou hodnotu svých hodin**: | ||
| + | * Při každé lokální události: $\mathcal{C}_i := \mathcal{C}_i + 1$ | ||
| + | * Při odeslání zprávy $m$: zpráva dostane časovou značku $ts(m) := \mathcal{C}_i$ | ||
| + | * Při přijetí zprávy $m$ procesem $p_j$: | ||
| - | například | + | Důležité: |
| - | * garbage collection | + | * Jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ |
| - | * deadlock detection | + | * Ale: $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ **neznamená**, že $e_1 \rightarrow e_2$ |
| - | * detekce ukončení výpočtu | + | |
| - | | + | |
| - | Řez - časová hranice v každém procesu a v každém komunikačním kanále | + | ⇒ Lamportovy hodiny |
| - | | + | |
| - | | + | |
| - | Konzistentní | + | === Vektorové hodiny === |
| - | $$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř}$$ | + | Abychom **přesně zachytili kauzalitu**, |
| - | tj. pokud řez obsahuje | + | |
| + | * Vektor $V_i$ proces $p_i$ má délku $n$ (počet procesů). | ||
| + | * Při každé lokální události: | ||
| + | * Při odeslání zprávy se posílá kopie $V_i$ | ||
| + | * Při přijetí zprávy $m$ se provede prvek po prvku: $$ V_i[j] := \max(V_i[j], V_m[j]) \quad \text{pro všechna | ||
| + | |||
| + | Událost $e_1$ předchází $e_2$ **ve vektorovém čase**, | ||
| + | |||
| + | To už umí odhalit **kauzální závislost i nezávislost**. | ||
| + | |||
| + | |||
| + | ===== 4. Globální stav v DS a jeho výpočet ===== | ||
| + | V distribuovaném systému neexistuje globální hodina ani centrální pohled na „okamžitý stav celého systému“. Přesto někdy potřebujeme **získat konzistentní snímek stavu** všech procesů a kanálů – třeba pro detekci uváznutí, garbage collection nebo checkpointing. Tato kapitola vysvětluje, | ||
| + | |||
| + | ==== Co je globální stav a snapshot ==== | ||
| + | |||
| + | **Globální stav** je: | ||
| + | * množina **lokálních stavů všech procesů** + | ||
| + | * stav **všech komunikačních kanálů** | ||
| + | * … ve stejném (logickém) okamžiku | ||
| + | |||
| + | **Globální snapshot** je **záznam** takového stavu, který může být analyzován mimo běžící systém (např. logicky, offline). | ||
| + | |||
| + | Použití: | ||
| + | * **garbage collection** – rozhodnutí, | ||
| + | * **detekce deadlocku** | ||
| + | * **ukončení výpočtu** | ||
| + | * **checkpointing** – ukládání stavu pro případ obnovení | ||
| + | |||
| + | ==== Řez distribuovaného výpočtu ==== | ||
| + | |||
| + | **Řez (cut)** definuje: | ||
| + | * **časový okamžik** v každém procesu a | ||
| + | * **hranicí** mezi tím, co se „už stalo“, a tím, co „teprve nastane“ | ||
| + | |||
| + | Události, které nastanou **před řezem**, do něj patří; zbytek je mimo. | ||
| + | |||
| + | === Konzistentní řez === | ||
| + | Řez $\mathcal{Ř}$ je **konzistentní**, | ||
| + | |||
| + | Jinými slovy: **jestliže | ||
| + | | ||
| + | |||
| + | Konzistentní řez je tedy **logický okamžik**, který by mohl být zpozorován „zvenčí“. | ||
| - | konzistentní řez = logický okamžik | ||
| {{statnice: | {{statnice: | ||
| Line 685: | Line 899: | ||
| {{statnice: | {{statnice: | ||
| - | Chamdy-Lamport algoritmus | + | ==== Algoritmus pro distribuovaný snapshot (Chandy-Lamport) ==== |
| - | | + | Chandy-Lamport algoritmus |
| - | | + | |
| - | - Jeden (libovolný) z procesů iniciuje | + | **Základní princip:** |
| - | - Procesy reagují | + | |
| - | - výsledkem | + | |
| + | * Algoritmus je **asynchronní** a **neblokující** – každý proces koná na základě přijatých značek. | ||
| + | |||
| + | **Průběh: | ||
| + | - Jeden proces iniciuje snapshot | ||
| + | - Když jiný proces obdrží `ZNAČKA ▪` poprvé: | ||
| + | * uloží svůj stav, | ||
| + | * pošle `ZNAČKA ▪` dál, | ||
| + | * vše, co do té doby přišlo | ||
| + | - Pokud přijde `ZNAČKA ▪` na kanál, u kterého už máme stav procesu, ale ne kanálu → zprávy mezi tím patří do snapshotu. | ||
| + | Výsledkem | ||
| {{statnice: | {{statnice: | ||
| - | stabilní vlastnost je taková vlastnost, že jakmile je ve výpočtu jednou splněna, zůtává splněna navždy | + | ==== Stabilní vlastnosti ==== |
| - | * například výpočet skončil, nastalo uváznutí, objekt je sirotek | + | |
| - | | + | **Stabilní |
| + | * Příklady: | ||
| + | * výpočet skončil | ||
| + | * došlo k uváznutí | ||
| + | * objekt je sirotek (už nikdy nebude dosažen) | ||
| - | Chandy-Lamport | + | **Nestabilní vlastnost**: |
| - | * Je daná stabilní vlastnost | + | * např. „žádný proces neselhal“ – může přestat platit. |
| - | - ANO - Vlastnost | + | |
| - | | + | === Kontrola stabilní vlastnosti pomocí snapshotu === |
| + | Chandy-Lamport algoritmus lze využít pro **detekci stabilních vlastností**: | ||
| + | |||
| + | Chceme vědět, jestli nějaká | ||
| + | * Pokud **platí v globálním snapshotu**, | ||
| + | * Platila už i ve skutečném systému v okamžiku | ||
| + | * Pokud **neplatí v snapshotu**, | ||
| + | | ||
| + | |||
| + | Snapshot tedy vytváří **spolehlivý časový úsek**, během kterého můžeme ověřit trvalost vybraných vlastností. | ||
| ===== Vzájemné vyloučení procesů v DS ===== | ===== Vzájemné vyloučení procesů v DS ===== | ||
| **algoritmy pro vyloučení procesů a jejich vlastnosti** | **algoritmy pro vyloučení procesů a jejich vlastnosti** | ||
| + | |||
| + | V distribuovaných systémech nemáme sdílenou paměť ani centrální plánovač. Pokud chceme zajistit, že do tzv. **kritické sekce** vstupuje vždy jen jeden proces, potřebujeme speciální algoritmy pro **vzájemné vyloučení**. Tato kapitola popisuje základní problém, požadavky na jeho řešení a několik klíčových algoritmů včetně jejich výhod a nevýhod. | ||
| ==== Problém vzájemného vyloučení ==== | ==== Problém vzájemného vyloučení ==== | ||
| - | < | + | |
| - | - *Kritická sekce* je část | + | * V distribuovaném prostředí je nutné |
| - | - Definujeme funkce | + | * Algoritmus poskytuje dvě základní operace: |
| - | - 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 | + | * `enter()` – požádá o vstup do kritické sekce |
| - | </ | + | * `exit()` – opustí kritickou sekci |
| ==== Požadavky na algoritmus pro vyloučení procesů ==== | ==== Požadavky na algoritmus pro vyloučení procesů ==== | ||
| - | < | + | * **Bezpečnost**: |
| + | * **Živost**: | ||
| + | * **Uspořádání (volitelné)**: | ||
| + | * Předpoklady: | ||
| + | * procesy neselhávají | ||
| + | * komunikace je spolehlivá (FIFO, bez ztrát, bez duplicit) | ||
| + | * systém je **asynchronní** s konečnou latencí | ||
| - | - *Bezpečnost* - Nejvýše jeden proces v kritické sekci | + | ==== Analýza výkonnosti algoritmů ==== |
| - | - *Živost* - Každý požadavek na vstup kritické sekce je časem uspokojen | + | * **Komunikační zátěž** – kolik zpráv |
| - | - *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 | + | * **Zpoždění klienta** – čas od požadavku po vstup, pokud nikdo jiný nečeká |
| - | - Uvažujeme navíc, že procesy neselhávají a komunikační kanály jsou perfektní (FIFO, zprávy se neduplikují, | + | * **Synchronizační zpoždění** – čas mezi výstupem |
| - | </ | + | |
| - | + | ||
| - | ==== Analýza výkonnosti algoritmů | + | |
| - | < | + | |
| - | + | ||
| - | - *Komunikační zátěž* | + | |
| - | - *Zpoždění klienta* | + | |
| - | - *Synchronizační zpoždění* | + | |
| - | </ | + | |
| ==== Centralizovaný algoritmus ==== | ==== Centralizovaný algoritmus ==== | ||
| - | < | + | * Jeden proces slouží jako **koordinátor** a spravuje **token**. |
| + | * Proces žádá koordinátora o token; po jeho získání vstoupí do kritické sekce. | ||
| + | * Po výstupu token vrací. | ||
| + | * Token je předáván podle fronty požadavků. | ||
| - | - Je zvolen jeden koordinátor | + | **Vlastnosti: |
| - | - 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 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ží | + | * Nevýhoda: **koordinátor je single point of failure**. |
| - | - Bezpečnost | + | |
| - | - Komunikační zátěž | + | |
| - | - Zpoždění klienta | + | |
| - | - Synchronizační zpoždění | + | |
| - | </ | + | |
| ==== Kruhový algoritmus ==== | ==== Kruhový algoritmus ==== | ||
| - | < | + | * Procesy jsou uspořádány v logickém kruhu. |
| + | * Jeden **token** obíhá dokola. | ||
| + | * Proces vstupuje do kritické sekce až po přijetí tokenu. | ||
| + | * Pokud token nepotřebuje, | ||
| - | - N procesů v kruhu | + | **Vlastnosti: |
| - | - 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 | + | * Výhoda: žádný centrální uzel. |
| - | - Pokud proces obdrží token a nečeká na vstup, tak jej hned předá dále | + | * Nevýhoda: token může „zabloudit“ nebo se ztratit. |
| - | - Komunikační zátěž | + | |
| - | - Zpoždění klienta | + | |
| - | - Synchronizační zpoždění | + | |
| - | </ | + | |
| ==== Ricart-Agrawalův algoritmus ==== | ==== Ricart-Agrawalův algoritmus ==== | ||
| - | < | + | * Nepoužívá token – pracuje pomocí **multicastu |
| - | - Nepoužívá token, ale kauzalitu | + | |
| - | - Nižší synchronizační zpoždění než kruhový algoritmus a nepoužívá centrální proces | + | * stav (*RELEASED*, *WANTED*, *HELD*) |
| - | - Každý proces si udržuje stav, který může nabývat 3 hodnot: | + | * frontu odložených žádostí |
| - | - Před vstupem | + | * Pro vstup do kritické sekce: |
| - | - Je nastaven stav na WANTED | + | * proces pošle `REQUEST` všem, zaznamená čas |
| - | - Poslán multicast | + | * čeká na odpovědi `OK` od všech |
| - | - Čeká na odpověď | + | * Ostatní procesy odpoví podle kauzálního (Lamportova) času |
| - | - Po přijetí | + | |
| - | - Po přijetí | + | <code cpp> |
| - | - Pokud je stav WANTED | + | // schéma odpovědi na REQUEST(K) |
| - | - Jinak je posláno | + | if (stav == HELD || (stav == WANTED |
| - | - Po výstupu z KS je stav nastaven na RELEASED a všem procesům ze seznamu je posláno OK | + | odlož požadavek; |
| - | - V nejhorším | + | } else { |
| - | - Je zachováno pořadí, | + | pošli |
| - | - Komunikační zátěž | + | } |
| - | - Zpoždění klienta | + | </ |
| - | - Synchronizační zpoždění | + | |
| - | </ | + | * Po ukončení práce |
| + | | ||
| + | * pošle OK na všechny odložené | ||
| + | |||
| + | **Vlastnosti: | ||
| + | * Komunikační zátěž: | ||
| + | * $2(N-1)$ | ||
| + | * až $(N-1)$ | ||
| + | | ||
| + | | ||
| + | * Výhoda: **zcela decentralizovaný**, | ||
| + | * Nevýhoda: **vysoký počet zpráv** | ||
| ===== Volba lídra v DS ===== | ===== Volba lídra v DS ===== | ||
| **algoritmy pro volbu lídra a jejich vlastnosti** | **algoritmy pro volbu lídra a jejich vlastnosti** | ||
| - | < | + | |
| - | - Cílem je, aby se všechny procesy shodly na jednom | + | V distribuovaném systému často potřebujeme zvolit jeden proces, který bude působit jako koordinátor – například pro synchronizaci, |
| - | - Předpokládáme možnost selhání (crash) | + | |
| - | - Výsledek nesmí záviset na tom, kdo volbu odstartoval, | + | Cílem |
| - | </ | + | * všechny |
| + | * nezáleželo na tom, kdo volbu zahájil, | ||
| + | * více paralelních voleb nakonec **konvergovalo k jedné**. | ||
| + | |||
| + | Předpokládáme: | ||
| + | * spolehlivé doručování zpráv (žádné ztráty ani duplicity), | ||
| + | * možnost selhání | ||
| + | * procesy mají unikátní ID (číselné) a dokážou je mezi sebou porovnat. | ||
| ==== Kruhový algoritmus (Ring) ==== | ==== Kruhový algoritmus (Ring) ==== | ||
| - | < | + | * Procesy |
| - | - Procesy | + | |
| - | - **Start**: | + | * pošle `ELECTION(i)` svému následníkovi. |
| - | - **Přijetí | + | * pokud příjemce dostane |
| - | - pokud $j > i$: předá | + | |
| - | | + | |
| - | | + | |
| - | - $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. | + | * Nový lídr pak vyšle `ELECTED(i)` kolem kruhu → všichni si uloží |
| - | - **Komplexita**: $\mathcal{O}(n)$ | + | |
| - | </ | + | **Vlastnosti:** |
| + | * Komunikační složitost: $\mathcal{O}(n)$ | ||
| + | * Funguje | ||
| + | * Zvítězí proces s nejvyšším ID | ||
| + | * Nevyžaduje globální znalost všech procesů | ||
| ==== Algoritmus Bully ==== | ==== Algoritmus Bully ==== | ||
| - | < | + | |
| - | - **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 | + | |
| - | | + | - Pošle `COORDINATOR(i)` všem **nižším ID** |
| - | | + | |
| - | | + | - Pokud neobdrží oznámení včas, znovu zahájí |
| - | | + | |
| + | **Zprávy: | ||
| + | * `ELECTION` – „ozvi se, pokud žiješ a jsi silnější“ | ||
| + | | ||
| + | * `COORDINATOR(k)` | ||
| - | - **Typy zpráv** | + | **Vlastnosti:** |
| - | | + | |
| - | | + | * Horší složitost: $\mathcal{O}(n^2)$ zpráv v nejhorším případě |
| - | | + | |
| + | | ||
| - | - **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ů. | ||
| - | </ | ||
