Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b36pdv [2025/06/01 10:24] – [Ricart-Agrawalův algoritmus] 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 |
| - | + | ||
| - | + | ||
| ==== Instruction-Level Parallelism (ILP) ==== | ==== Instruction-Level Parallelism (ILP) ==== | ||
| - | * **Definice: | + | * **Definice: |
| - | * **Zdroj ILP:** nezávislé aritmetické operace, nezávislé paměťové přístupy, nezávislé větvení. Množství ILP se výrazně liší dle typu úlohy – numerické simulace mají ILP bohaté, kryptografie spíše skromné. | + | * **Zdroj ILP:** nezávislé aritmetické operace, nezávislé paměťové přístupy, nezávislé větvení. |
| - | * **Využití ILP:** pipelining | + | * **Využití ILP:** pipelining, superskalární/ |
| - | + | ||
| - | ---- | + | |
| ==== Pipelining ==== | ==== Pipelining ==== | ||
| - | * **Princip: | + | * **Princip: |
| - | * **Teoretický zisk: | + | To umožňuje, aby různé instrukce |
| - | * **Superpipelining: | + | * **Teoretický zisk: |
| - | * **Hazardy: | + | * **Superpipelining: |
| - | * datové | + | * **Hazardy: |
| - | * řídicí | + | * datové – řeší se forwardingem, stally, přejmenováním registrů |
| - | * strukturální – duplikace funkčních | + | * řídicí – predikce skoků + branch target buffer (BTB) |
| - | + | * strukturální – řeší se duplikací | |
| - | ---- | + | |
| ==== Skalární vs. superskalární procesory ==== | ==== Skalární vs. superskalární procesory ==== | ||
| + | |||
| === Skalární procesor === | === Skalární procesor === | ||
| - | * **Jednoproudová (1-wide) architektura: | + | * 1 instrukce |
| - | * Pipelining zde paralelizuje **různé fáze** různých instrukcí, nikoli jejich současné vykonání. | + | * jednodušší architektura |
| + | * využívá pipelining | ||
| === Superskalární procesor === | === Superskalární procesor === | ||
| - | * **N-wide architektura:** fetch/ | + | * více instrukcí za takt (IPC > 1) |
| - | * Paralelizuje **stejné fáze** různých instrukcí a kombinuje se s pipeliningem; | + | |
| + | * využívá | ||
| ==== Podtypy superskalární architektury ==== | ==== Podtypy superskalární architektury ==== | ||
| - | * **Statická | + | * **Statická:** paralelně jen instrukce jdoucí v kódu za sebou; při závislostech |
| - | * Vydává | + | * **Dynamická:** out-of-order execution a přejmenování registrů |
| - | * **Dynamická | + | |
| - | * **Out-of-order execution** a **přejmenování registrů** (ROB + Reservation Stations) spouští libovolné připravené instrukce, skryje latenci cache a zvedá IPC. | + | |
| - | * Vyžaduje přesnou predikci skoků a složitější hardwarové řízení; spotřeba i plocha čipu rostou. | + | |
| - | === Shrnutí rozdílu === | + | ==== Shrnutí rozdílu |
| - | * **Skalární CPU** ⇒ 1 instrukce/ | + | * **Skalární CPU** ⇒ 1 instrukce/ |
| - | * **Superskalární CPU** ⇒ N instrukcí/ | + | * **Superskalární CPU** ⇒ více instrukcí/ |
| - | ==== GPGPU ==== | + | |
| - | * **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické | + | ==== GPGPU ==== |
| - | * Typický desktopový | + | |
| + | * GPU obsahují | ||
| + | * Ty spouštějí stovky až tisíce vláken | ||
| === Architektura a omezení === | === 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ů | ||
| - | * **Hierarchie výpočetních bloků:** GPC $\rightarrow$ SM $\rightarrow$ processing block $\rightarrow$ warp $\rightarrow$ | + | === Výpočetní výkon v praxi === |
| - | * **Sdílené prostředky SM:** | + | * Threadripper 3990X + RTX 4090: |
| + | | ||
| + | | ||
| + | * CPU + GPGPU: | ||
| - | | + | === Programovací modely === |
| - | * max 64 warpů ≈ 2048 vláken na SM | + | |
| - | * 64 k 32-bit registrů; limit ≈ 255 registrů na vlákno (nižší počet registrů = vyšší obsazenost)&# | + | * **OpenCL** – otevřený standard |
| - | * **Paměťová hierarchie GPU:** | + | * **SYCL** – moderní C++ model |
| + | * **OpenMP target** – direktivy pro GPU | ||
| - | * L1/shared: ~33 cyklů | + | === Typické úlohy === |
| - | * L2: až 2 TB/s (~200 cyklů) | + | * lineární algebra, strojové učení, ray-tracing, |
| - | * HBM2: 1.5 TB/s (~290 cyklů) | + | |
| - | * Host ↔ GPU: PCIe Gen4 ~32 GB/s, NVLink ~50 Gb/s pár signálů | + | |
| - | * ⇒ 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 === | + | === Výhody |
| + | * vysoký výkon (tisíce FP jednotek) | ||
| + | * efektivita (TFLOPS/ | ||
| + | * specializované instrukce (Tensor Cores…) | ||
| - | | Konfigurace | + | === Nevýhody === |
| - | | Threadripper 3990X + RTX 4090 | 49 GFLOPS | + | * paměťová latence |
| + | | ||
| + | | ||
| + | | ||
| + | * vendor lock-in (CUDA) | ||
| - | *Na stejném stroji GPU dodá ~×25 výkon | + | === Shrnutí === |
| + | GPGPU nabízí | ||
| - | === Programovací modely | + | ==== 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, | ||
| + | * **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. | ||
| - | * **CUDA C/C++** – proprietární, de-facto standard pro NVIDIA. | + | ==== Hierarchie cache pamětí ==== |
| - | * **OpenCL 3.0** – otevřený standard podporovaný NVIDIA, AMD, Intel, ARM Mali. | + | Moderní CPU mají vícestupňovou |
| - | * **SYCL 2020** – moderní C++20 nad OpenCL/ | + | * **L1 cache** – nejmenší (např. 32 KB), ale nejrychlejší (~4 cykly), zvlášť pro instrukce a data. |
| - | * **OpenMP 5.x target/ | + | * **L2 cache** – větší (např. 256 KB), pomalejší (~12 cyklů), většinou sdílena mezi jádry. |
| - | * Další možnosti: Vulkan Compute, DirectX 12 Compute, Thrust (C++ algoritmy nad CUDA). | + | * **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ů. | ||
| - | === Typické úlohy === | + | 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. |
| - | * lineární algebra (matmul, BLAS), strojové | + | ===== 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í. | ||
| - | === Výhody | + | ==== 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á. | ||
| - | * **Obrovský teoretický throughput** (tisíce FP jednotek). | + | Například: |
| - | * **Energetická efektivita**: TFLOPS/W často výrazně lepší než CPU. | + | <code cpp> |
| - | * **Specializované instrukce** | + | // špatně – race condition |
| + | for (int i = 0; i < 1000; i++) { | ||
| + | | ||
| + | } | ||
| + | </ | ||
| - | === Nevýhody === | + | * Řešení: |
| + | * Použít **synchronizační primitiva** – mutexy, atomické operace, semafory apod. | ||
| + | * Nebo použít **thread-local** kopie a sloučit je až nakonec. | ||
| - | * **Paměťová latence** mimo L1/shared, nutnost koalesovaného přístupu. | + | ==== Deadlock (uváznutí) ==== |
| - | * **Omezená velikost registrů a shared memory** $\rightarrow$ ladění obsazenosti. | + | * **Uváznutí |
| - | * **Drahé přenosy host ↔ device** | + | * Jednoduše řečeno: vlákno A čeká |
| - | * **Divergence warpů** (větvení) snižuje výkon | + | |
| - | * **Vendor lock-in** (CUDA) | + | |
| - | === Shrnutí === | + | Například: |
| - | GPGPU nabízí **řádově vyšší paralelní výkon** než mainstreamové CPU, ale vyžaduje uvědomělou práci | + | <code cpp> |
| - | /* | + | // pseudokód |
| - | ################################################################################################################################################################################### | + | thread1: |
| - | ################################################################################################################################################################################### | + | lock(A) |
| - | ################################################################################################################################################################################### | + | lock(B) |
| - | */ | + | |
| - | ===== Komplikace v paralelním programování ===== | + | thread2: |
| - | **souběh (race condition), uváznutí | + | lock(B) |
| - | * souběh (race condition), uváznutí (deadlock): (statnice: | + | lock(A) |
| + | </code> | ||
| + | |||
| + | * Aby deadlock mohl nastat, musí být splněny tyto 4 podmínky | ||
| + | * **Vzájemné vyloučení** – zdroje nejsou sdílené | ||
| + | * **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. | ||
| + | | ||
| + | * 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 je to **žádoucí chování**, | ||
| + | * Typicky jde o sdílené čítače, fronty, stavové proměnné atd. | ||
| - | Narozdíl od false sharing chtěná (pokud umíte programovat) vlastnost, je nutná korektní synchronizace. | ||
| - | |||
| - | /* | ||
| - | ################################################################################################################################################################################### | ||
| - | ################################################################################################################################################################################### | ||
| - | ################################################################################################################################################################################### | ||
| - | */ | ||
| - | ===== 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 190: | Line 253: | ||
| mtx.lock(); | mtx.lock(); | ||
| // Kritická sekce | // Kritická sekce | ||
| - | std::cout << " | + | std::cout << " |
| mtx.unlock(); | mtx.unlock(); | ||
| }; | }; | ||
| Line 204: | Line 267: | ||
| </ | </ | ||
| - | Moderní | + | *Moderní |
| - | <code cpp> | + | |
| + | <code cpp> | ||
| #include < | #include < | ||
| #include < | #include < | ||
| Line 228: | 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 261: | 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 307: | 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 352: | 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 364: | 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 440: | 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 472: | Line 566: | ||
| | | ||
| } | } | ||
| - | ``` | + | </code> |
| - | + | ||
| - | </markdown> | + | |
| ==== Numerická lineární algebra a strojové učení ==== | ==== Numerická lineární algebra a strojové učení ==== | ||
| Line 480: | 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 507: | 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 545: | 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 výpočtu. | + | ===== Distribuované výpočty/ |
| + | |||
| + | ===== 1. Úvod do distribuovaných systémů (DS) ===== | ||
| + | Distribuované systémy (DS) jsou o tom, jak spolupracují **nezávislé výpočetní jednotky**, které spolu **nesdílejí paměť ani hodiny**, ale komunikují pomocí zpráv. Jsou všude kolem nás – od cloudových služeb po blockchain nebo velké paralelní výpočty. Tato kapitola představuje základní charakteristiky DS, problematiku času a přehled typických typů selhání, se kterými musí každý návrh systému počítat. | ||
| + | |||
| + | *Distribuovaný systém je*: | ||
| + | * soustava **autonomních procesů** spojených sítí, | ||
| + | * komunikace probíhá **pouze zprávami** (message passing), | ||
| + | * **žádná sdílená paměť**, **žádné globální hodiny**, | ||
| + | * procesy mohou **selhávat nezávisle**, | ||
| + | * každý proces má **lokální hodiny**, které mohou běžet různou rychlostí. | ||
| + | |||
| + | Kvůli těmto vlastnostem je velmi těžké se v systému spolehlivě orientovat v čase – nemůžeme | ||
| + | |||
| + | ==== Asynchronní × Synchronní DS ==== | ||
| + | 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é. | ||
| - | ==== Asynchronní x Synchronní DS ==== | ||
| - | Popisují model světa ve kterém DS existuje. rozdělení synchroní a asynchroní popisuje množinu předpokladů, | ||
| === Synchronní model === | === Synchronní model === | ||
| - | * **Známe | + | * Známe |
| - | * maximální | + | * zpoždění |
| - | * maximální | + | * rychlost výpočtu, |
| - | * maximální drift lokálních hodin | + | * odchylku mezi hodinami. |
| - | * Algoritmy můžeme | + | * Můžeme |
| - | * V praxi čistě synchroní sétě skoro neexistují | + | * Takto předvídatelné sítě se v praxi téměř **nevyskytují** – je to spíš teoretický model. |
| === Asynchronní model === | === Asynchronní model === | ||
| - | * **Žádné | + | * **Žádné |
| - | běžet | + | * Timeouty |
| - | * Timeout tedy **nemůže spolehlivě rozlišit** „zpomalení“ od „pádu“. | + | * Například slavný důkaz **FLP** ukazuje, že **v asynchronním modelu není možný deterministický konsensus**, pokud může |
| - | * V tomto modelu je např. prokázáno (FLP), že deterministický konsensus | + | |
| - | s možností jediného pádu procesu | + | |
| - | === Částečně synchronní model (real-world kompromis) === | + | |
| - | * Systém se může | + | |
| - | * 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í“. | + | |
| - | | + | |
| + | === Částečně synchronní model === | ||
| + | * Realistický kompromis: | ||
| + | * Systém se může nějakou dobu chovat asynchronně, | ||
| + | * 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**, | ||
| - | - Selhání procesu | + | ==== Typy selhání v distribuovaných systémech ==== |
| - | * crash / fail-stop - proces přestane vykonávatz algoritmus | + | V DS musíme počítat s tím, že **něco selže** – a často i nepozorovaně. Rozlišujeme: |
| - | | + | |
| - | - Selhání kanálu | + | |
| - | | + | |
| - | * 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: | + | * **Selhání procesu**: |
| - | Spolehlivé doručování, | + | * *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. | ||
| - | ===== Detekce selhání v DS ===== | + | ==== Předpoklady na komunikační kanál |
| - | **detektory selhání a jejich | + | Distribuované algoritmy často |
| - | **úplnost** - každé selhání je časem detekováno alespoň jedním bezvadným procesem | + | |
| + | * **žá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. | ||
| - | **přesnost** - nedochází k mylné detekci | + | Tato vlastnosti se často |
| - | nelze dosáhnout obou vlastností současně, je vyžadována | + | ===== 2. Detekce selhání v DS ===== |
| + | 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í**, | ||
| + | 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. | ||
| + | ==== Vlastnosti detektorů selhání ==== | ||
| + | * **Úplnost (completeness)** | ||
| + | * Každé skutečné selhání je **časem detekováno** alespoň jedním bezchybným uzlem. | ||
| + | * **Přesnost (accuracy)** | ||
| + | * Detektor **nemá falešné poplachy** – neoznačí proces za havarovaný, | ||
| - | Frekvence selhání roste lineárně s počtem procesů ve skupině (selhání jsou běžná) | + | Nelze zaručit obě vlastnosti zároveň |
| - | Dva podprotokoly - detekce selhání a šíření informace o selhání | + | Jinými slovy: **lepší je omylem někoho považovat za mrtvého, než si nevšimnout, |
| - | Průběh detekce: | + | * Frekvence selhání v praxi roste **lineárně s počtem uzlů** – tj. v systému se stovkami uzlů je běžné, že některé z nich selžou v každém okamžiku. |
| - | - 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 | + | ==== Průběh detekce ==== |
| + | - Proces $p_j$ selže. | ||
| + | - Jiný proces $p_k$ jeho selhání | ||
| + | - Proces $p_k$ **šíří informaci** o selhání $p_j$ dalším uzlům – podle typu protokolu. | ||
| + | |||
| + | ==== Typy detekčních protokolů ==== | ||
| === Centralizovaný heartbeat === | === Centralizovaný heartbeat === | ||
| - | Heartbeat jsou odesílány | + | * Každý uzel **periodicky |
| + | * $p_j$ si udržuje čítač a čas posledního přijetí od každého uzlu. | ||
| + | * Pokud nedorazí heartbeat během $\tau$ → $p_i$ je považován za selhaný. | ||
| - | Heartbeat má pořadové číslo, to odeslání heartbeatu je inkrementován lokální čítač pro každý proces | + | **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**, | ||
| - | Pokud není heartbeat | + | === Kruhový |
| + | * Každý proces periodicky posílá heartbeat **sousedovi** | ||
| + | * Lze použít **jednosměrný** nebo **obousměrný** kruh. | ||
| - | 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. | + | **Vlastnosti: |
| + | * Není žádný centrální bod → lepší škálování. | ||
| + | * **Není úplný**, pokud selže jeden (v jednosměrném) nebo dva (v obousměrném) uzly. | ||
| + | * Nutno **udržovat kruhovou topologii** – složitější údržba. | ||
| + | === All-to-all heartbeat === | ||
| + | Každý uzel **periodicky odesílá heartbeat všem ostatním**. | ||
| - | === Kruhový heartbeat === | + | **Vlastnosti: |
| - | Heartbeats jsou odesílány periodicky sousedům | + | * **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ů. | ||
| - | * není centrální uzel | + | === SWIM protokol === |
| - | * není úplné při selhání více procesů (stačí jeden u jednosměrného, | + | **Scalable Weakly-consistent Infection-style Membership** |
| - | | + | |
| - | === All to all heartbeat === | + | Moderní přístup k detekci, který |
| - | každý proces periodicky odesílá heartbeat všem ostatním procesům | + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | | + | |
| - | === SWIM === | + | Každý proces $p_i$ periodicky: |
| - | **Scalable weakly consistent infection-style proces group membership protocol** | + | - Posílá `ping` náhodnému uzlu $p_j$ a čeká na `ack`. |
| + | - Pokud žádná odpověď nepřijde, požádá $\mathcal{K}$ jiných uzlů, aby se zeptaly místo něj (`ping_req`). | ||
| + | - Tyto uzly pingnou $p_j$, a pokud odpověď dostanou, pošlou ji zpět $p_i` jako `ping_ack`. | ||
| + | - Pokud nikdo z $\mathcal{K}$ nedostane odpověď → $p_j$ je označen za mrtvého. | ||
| - | | + | **Vlastnosti: |
| - | * pokud ji nedostance, odešle zprávu | + | * **Přesnost** lze nastavit volbou |
| - | * tyto uzly se zeptají $p_j$ pomocí zprávy | + | * **Úplnost** je zaručena. |
| - | * pokud ani jeden z $\mathcal{K}$ uzlů nedostane odpověď, označí $p_i$ $p_j$ jako havarovaný | + | * **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ů). | ||
| - | přesnost lze nastavit volbou $\mathcal{K}$, | ||
| - | úplnost je zaručena, průměrný čas detekce je $\frac{e}{e - 1}\mathcal{T}$ | + | ===== 3. Čas a kauzalita v DS ===== |
| + | 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 a kauzalita | + | ==== Problémy s časem |
| - | **uspořádání událostí | + | * **Clock slew** – rozdíl ve skutečném čase mezi dvěma procesy. |
| + | * **Clock drift** – rozdíl | ||
| + | * To znamená, že hodiny **nelze úplně sladit**, jen přiblížit. | ||
| - | clock slew - rozdíl v času hodin dvou procesů, mají li dvoje hodiny nenulovou mimoběžnost, jsou nesynchronizované | + | ==== Synchronizace |
| + | Synchronizace může být: | ||
| - | clock drift - rozdíl | + | === Externí synchronizace === |
| + | * Každý proces $p_i$ má své hodiny $\mathcal{C}_i$ udržované v rozmezí $\delta$ od nějakého **externího referenčního času** $\mathcal{S}$. | ||
| + | * Např. atomové hodiny, UTC, NTP servery. | ||
| + | * $|\mathcal{C}_i | ||
| + | * Každý uzel se snaží držet | ||
| + | * Typický příklad: **NTP (Network Time Protocol)**. | ||
| - | synchronizace | + | === Interní |
| - | * externí | + | * Zajišťuje, |
| - | | + | * Formálně: |
| - | * externí hodiny mohou být napojeny na UTC nebo atomové hodiny | + | * Rozdíl mezi hodinami dvou uzlů je nejvýše $\delta$ |
| - | * například NTP | + | * Není vázaná na žádný „reálný |
| - | * interní | + | * Např. **Berkeley |
| - | * každý pár procesů $(p_i, p_j)$ má hodnoty | + | |
| - | * například | + | |
| - | Externí synchronizace typu Kolik je hodin? -> odešle odpověď -> nastaví čas, má chybu nastavení špatného času kvůli komunikační prodlevě (latenci) | + | ==== Praktické algoritmy pro synchronizaci ==== |
| - | Cristianův algoritmus | + | === Cristianův algoritmus |
| - | $$ \mathcal{C}_i \coloneq t + \frac{\mathcal{T}_\text{RT}-l_{\text{min}+l' | + | * Klient se zeptá serveru: *„Kolik |
| - | chyba je omezena, tj maximálně $\frac{\mathcal{T}_\text{RT} - l_{\text{min}} - l' | + | * Server odpoví, a klient si upraví svůj čas podle: |
| - | lokální čas lze posunou libovolně dopředu, ale ne dozadu, je možné zvýšit nebo snížit rychlost hodin | + | $\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 | ||
| - | NTP | + | Očekávaná |
| - | * 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 | + | |
| - | | + | |
| - | | + | |
| - | Logické hodiny | ||
| - | nepoužívají | + | Lokální čas lze zvyšovat okamžitě, ale **nelze ho vracet zpět** – místo toho se mění rychlost |
| - | kauzální vztah - první událost může ovlivnit druhou | + | === NTP === |
| + | * Servery tvoří **stromovou hierarchii** (stratum 0, 1, 2, …). | ||
| + | * Uzly synchronizují čas s rodiči i některými sousedy. | ||
| + | * Latence se odhaduje pomocí offsetu: | ||
| - | Relace stalo se před | + | $o = \frac{(t_1^{r} - t_2^{r} + t_2^{s} - t_1^{s})}{2}$ |
| - | - Jsou-li | + | |
| - | | + | |
| - | | + | |
| - | Kauzální nezávislost | + | ==== Logické hodiny a kauzalita ==== |
| - | * relace stalo se před zavádí | + | Logické hodiny nejsou o „skutečném čase“, ale o **pořadí událostí**. Nepotřebují žádnou synchronizaci – pouze konzistentní značkování událostí podle „co mohlo ovlivnit co“. |
| - | | + | |
| - | | + | |
| - | Lamportovy logické hodiny - každý proces má své logické hodiny, které | + | === Kauzální vztah – relace „stalo |
| + | Událost $\mathcal{A}$ **mohla ovlivnit** událost $\mathcal{B}$, | ||
| - | Synchronizace logických hodin | + | * $\mathcal{A} \rightarrow \mathcal{B}$ – pokud obě nastaly ve stejném procesu a $\mathcal{A}$ byla dřív, |
| - | - po každé události která se odehraje v $p_i$ se hodiny | + | |
| - | | + | * nebo (tranzitivně): |
| - | - kdykoliv proces $p_j$ přijme zprávu $m$, tak: | + | |
| - | - upraví své lokální hodiny | + | |
| - | - provede krok 1 předtím než předá $m$ aplikaci (<= přijetí zprávy je událost) | + | |
| - | Lamportovy hodiny neimplikují kauzalitu! | + | === Kauzální nezávislost === |
| - | * Platí: jestliže | + | * Události |
| - | * Neplatí: jestliže $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$, | + | * Jinými slovy: žádná z nich nemohla ovlivnit druhou. |
| - | Vektorové | + | === Lamportovy logické |
| + | Každý proces si udržuje | ||
| + | * 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$: | ||
| - | ===== Globální stav v DS a jeho výpočet ===== | + | Důležité: |
| - | **řez distribuovaného výpočtu, algoritmus pro distribuovaný globální snapshot, stabilní vlastnosti DS** | + | * Jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ |
| + | | ||
| - | 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 | + | ⇒ Lamportovy hodiny **respektují kauzalitu**, |
| - | globální snapshot je záznam globálního stavu | + | === Vektorové hodiny === |
| + | Abychom **přesně zachytili kauzalitu**, | ||
| - | například | + | |
| - | | + | * Při každé lokální události: $V_i[i] += 1$ |
| - | * deadlock detection | + | * Při odeslání zprávy se posílá kopie $V_i$ |
| - | * detekce ukončení výpočtu | + | * Při přijetí zprávy $m$ se provede prvek po prvku: $$ V_i[j] := \max(V_i[j], |
| - | * checkpointing | + | |
| - | Řez - časová hranice v každém procesu a v každém komunikačním kanále | + | Událost $e_1$ předchází $e_2$ **ve vektorovém čase**, pokud: $$ V(e_1)[k] \leq V(e_2)[k] \ \forall k \text{ a alespoň jedna nerovnost je ostrá} $$ |
| - | * události které nastanou | + | |
| - | | + | |
| - | Konzistentní | + | To už umí odhalit **kauzální závislost i nezávislost**. |
| - | $$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř}$$ | + | |
| - | tj. pokud řez obsahuje | + | |
| + | ===== 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í**, pokud: $$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř} $$ | ||
| + | |||
| + | 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 744: | 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 OK; |
| - | - 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ů. | ||
| - | </ | ||
