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 15:00] – 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ěť | + | * Výhody: |
| - | + | * jednoduchá správa vláken | |
| - | < | + | * sdílená paměť |
| - | - **Explicitní synchronizace uvnitř regionu** | + | * předvídatelné chování a synchronizace |
| - | - `#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ý | + | |
| - | + | ||
| - | - **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** | + | Ukázkový kód: |
| - | `task`, `taskgroup`, | + | <code cpp> |
| - | + | ||
| - | + | ||
| - | 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 | + | ===== 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 726: | 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ů. | ||
| - | </ | ||
