Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b36pdv [2025/06/04 22:52] – [Logické hodiny a kauzalita] zapleka3statnice:bakalar:b4b36pdv [2026/05/25 13:03] (current) – jpelc
Line 5: Line 5:
     - **Hardwarová podpora pro paralelní výpočty** – (super)skalární architektury, pipelining, spekulativní vyhodnocování, vektorové instrukce, vlákna, procesy, GPGPU. Hierarchie cache pamětí.     - **Hardwarová podpora pro paralelní výpočty** – (super)skalární architektury, pipelining, spekulativní vyhodnocování, vektorové instrukce, vlákna, procesy, GPGPU. Hierarchie cache pamětí.
     - **Komplikace v paralelním programování** – souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing).     - **Komplikace v paralelním programování** – souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing).
-    - **Podpora paralelního programování v C a C++** – pthreads, thread, jthread, atomic, mutex, lock_guard.+    - **Podpora paralelního programování v C a CPP** – pthreads, thread, jthread, atomic, mutex, lock_guard.
     - **Podpora paralelního programování v OpenMP** – sériově-paralelní model uspořádání vláken (fork-join), paralelizovatelná úloha (task region), různé implementace specifikace. Direktivy: parallel, for, section, task, barrier, critical, atomic.     - **Podpora paralelního programování v OpenMP** – sériově-paralelní model uspořádání vláken (fork-join), paralelizovatelná úloha (task region), různé implementace specifikace. Direktivy: parallel, for, section, task, barrier, critical, atomic.
     - **Techniky dekompozice programu** – statické a paralelní rozdělení práce. Threadpool a fronta úkolů. Balancování a závislosti (dependencies).     - **Techniky dekompozice programu** – statické a paralelní rozdělení práce. Threadpool a fronta úkolů. Balancování a závislosti (dependencies).
Line 103: Line 103:
  
 === Programovací modely === === Programovací modely ===
-  * **CUDA C/C++** – pro NVIDIA+  * **CUDA C/CPP** – pro NVIDIA
   * **OpenCL** – otevřený standard   * **OpenCL** – otevřený standard
-  * **SYCL** – moderní C++ model+  * **SYCL** – moderní CPP model
   * **OpenMP target** – direktivy pro GPU   * **OpenMP target** – direktivy pro GPU
  
Line 197: Line 197:
   * Pokud se to děje často, dochází k **velkému zpomalení**, protože cache se neustále synchronizuje mezi jádry.   * Pokud se to děje často, dochází k **velkému zpomalení**, protože cache se neustále synchronizuje mezi jádry.
   * Řešení:   * Řešení:
-    * **Zarovnat proměnné** tak, aby každá byla na vlastní cache line (např. pomocí `alignas(64)`).+    * **Zarovnat proměnné** tak, aby každá byla na vlastní cache line (např. pomocí ''alignas(64)'').
     * Přidat „padding“ mezi proměnné, které používají různá vlákna.     * Přidat „padding“ mezi proměnné, které používají různá vlákna.
  
Line 206: Line 206:
  
    
-===== 3. Podpora paralelního programování v C a C++ ===== +===== 3. Podpora paralelního programování v C a CPP ===== 
-Existuje více úrovní podpory – od nízkoúrovňových knihoven jako `pthreads` v C, až po elegantní moderní rozhraní ve stylu `std::thread`, `std::jthread`, `std::mutex` nebo `std::atomic` v C++. Pokud chceme psát vícevláknové programy efektivně a bezpečně, je důležité pochopit, kdy a jak jednotlivé nástroje použít – a čím se liší.+Existuje více úrovní podpory – od nízkoúrovňových knihoven jako ''pthreads'' v C, až po elegantní moderní rozhraní ve stylu ''std::thread'', ''std::jthread'', ''std::mutex'' nebo ''std::atomic'' v CPP. Pokud chceme psát vícevláknové programy efektivně a bezpečně, je důležité pochopit, kdy a jak jednotlivé nástroje použít – a čím se liší.
  
 ==== POSIX vlákna (pthreads) ==== ==== POSIX vlákna (pthreads) ====
-  * `pthreads` (POSIX Threads) je **standardní rozhraní v jazyku C** pro práci s vlákny.+  * ''pthreads'' (POSIX Threads) je **standardní rozhraní v jazyku C** pro práci s vlákny.
   * Poskytuje funkce pro:   * Poskytuje funkce pro:
-    * **vytváření vláken**: `pthread_create()`+    * **vytváření vláken**: ''pthread_create()''
     * **synchronizaci vláken**:     * **synchronizaci vláken**:
-      * **mutexy**: `pthread_mutex_lock()`, `pthread_mutex_unlock()` +      * **mutexy**: ''pthread_mutex_lock()'', ''pthread_mutex_unlock()'' 
-      * **podmínkové proměnné**: `pthread_cond_wait()`, `pthread_cond_signal()` +      * **podmínkové proměnné**: ''pthread_cond_wait()'', ''pthread_cond_signal()'' 
-      * **semafory**: `sem_init()`, `sem_wait()`, `sem_post()`+      * **semafory**: ''sem_init()'', ''sem_wait()'', ''sem_post()''
  
 Je to výkonný, ale nízkoúrovňový nástroj – programátor musí vše spravovat ručně. Hodí se pro systémy, kde je důležitá kontrola nad výkonem a kompatibilita se standardem POSIX. 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) ==== +==== std::thread (CPP11) ==== 
-  * Od C++11 je k dispozici standardní knihovna pro vlákna – `std::thread`.+  * Od CPP11 je k dispozici standardní knihovna pro vlákna – ''std::thread''.
   * Umožňuje jednoduché vytvoření a správu vláken pomocí objektově orientovaného rozhraní.   * Umožňuje jednoduché vytvoření a správu vláken pomocí objektově orientovaného rozhraní.
     * Vlákno spustíme předáním funkce (nebo lambdy) do konstruktoru.     * Vlákno spustíme předáním funkce (nebo lambdy) do konstruktoru.
-    * Synchronizace se řeší pomocí `std::mutex`, `std::condition_variable` a dalších primitiv.+    * Synchronizace se řeší pomocí ''std::mutex'', ''std::condition_variable'' a dalších primitiv.
  
-Výhodou oproti `pthreads` je **vyšší přehlednost, typová bezpečnost a integrace s C++ idiomy** (např. RAII, STL, lambdy).+Výhodou oproti ''pthreads'' je **vyšší přehlednost, typová bezpečnost a integrace s CPP idiomy** (např. RAII, STL, lambdy).
  
-==== std::jthread (C++20) ==== +==== std::jthread (CPP20) ==== 
-  * Od C++20 přibyla nová třída `std::jthread`, která automaticky spravuje vlákno. +  * Od CPP20 přibyla nová třída ''std::jthread'', která automaticky spravuje vlákno. 
-    * Při zničení objektu se vlákno **automaticky ukončí** (`join()` nebo `detach()`). +    * Při zničení objektu se vlákno **automaticky ukončí** (''join()'' nebo ''detach()''). 
-    * Má vestavěnou podporu pro **zrušení vlákna** pomocí `stop_token`.+    * Má vestavěnou podporu pro **zrušení vlákna** pomocí ''stop_token''.
     * Výborně se hodí pro práci s **RAII přístupem** a bezpečnější práci s vláknem.     * Výborně se hodí pro práci s **RAII přístupem** a bezpečnější práci s vláknem.
  
-To znamená, že se snižuje riziko zapomenutého `join()` a tím i potencionálních chyb.+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í nástroj, který **zajišťuje, že jen jedno vlákno přistupuje k určité části kódu najednou** – typicky tzv. *kritické sekci*. **Mutex** (*mutual exclusion*) je synchronizační nástroj, který **zajišťuje, že jen jedno vlákno přistupuje k určité části kódu najednou** – typicky tzv. *kritické sekci*.
-  * V C++ se používá `std::mutex` a jeho varianty: +  * V CPP se používá ''std::mutex'' a jeho varianty: 
-    * `std::recursive_mutex`, `std::timed_mutex`, …+    * ''std::recursive_mutex'', ''std::timed_mutex'', …
  
 Ukázka (ruční zamykání/odemykání): Ukázka (ruční zamykání/odemykání):
Line 267: Line 267:
 </code> </code>
  
-*Moderní C++* doporučuje použít `std::lock_guard`, který mutex **automaticky zamkne a odemkne** – tím se předejde chybám (např. zapomenutí `unlock()` při výjimce):+*Moderní CPP* doporučuje použít ''std::lock_guard'', který mutex **automaticky zamkne a odemkne** – tím se předejde chybám (např. zapomenutí ''unlock()'' při výjimce):
  
 <code cpp> <code cpp>
Line 295: Line 295:
 ==== 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. **Atomic** proměnné umožňují provádět operace, které jsou **nedělitelné (atomické)** – tím pádem **bezpečné vůči souběhu**, aniž by bylo potřeba používat mutex.
-  * V C++ se používá `std::atomic<T>` – kde `T` může být např. `int`, `bool`, pointer apod.+  * V CPP se používá ''std::atomic<T>'' – kde ''T'' může být např. ''int'', ''bool'', pointer apod.
     * V pozadí to využívá **atomické instrukce CPU** (pokud jsou dostupné), takže jsou **rychlejší než mutexy**.     * V pozadí to využívá **atomické instrukce CPU** (pokud jsou dostupné), takže jsou **rychlejší než mutexy**.
     * Pokud HW atomické instrukce neumí, fallback je přes mutex.     * Pokud HW atomické instrukce neumí, fallback je přes mutex.
  
-V praxi jsou tedy `std::atomic` velmi efektivní pro jednoduché sdílené proměnné – například čítače:+V praxi jsou tedy ''std::atomic'' velmi efektivní pro jednoduché sdílené proměnné – například čítače:
  
 <code cpp> <code cpp>
Line 327: Line 327:
 </code> </code>
  
-  * Jinými slovy – `std::atomic` je ideální, pokud chceš **rychlou synchronizaci bez složitých zámků**, ale nepotřebuješ složitou logiku jako čekání, notifikace, podmínky apod.+  * Jinými slovy – ''std::atomic'' je ideální, pokud chceš **rychlou synchronizaci bez složitých zámků**, ale nepotřebuješ složitou logiku jako čekání, notifikace, podmínky apod.
  
 ===== 4. Podpora paralelního programování v OpenMP ===== ===== 4. Podpora paralelního programování v OpenMP =====
-OpenMP je velmi populární knihovna pro paralelizaci v jazycích C, C++ a Fortran. Umožňuje snadno spouštět více vláken pomocí direktiv vkládaných přímo do zdrojového kódu. V této kapitole se podíváme na to, jak funguje základní model *fork-join*, jak se v OpenMP definují úlohy (tasky), a jaké máme k dispozici prostředky pro synchronizaci. Ukážeme si i různé varianty implementací OpenMP a přehled direktiv, které programátorům umožňují jemné řízení paralelismu.+OpenMP je velmi populární knihovna pro paralelizaci v jazycích C, CPP a Fortran. Umožňuje snadno spouštět více vláken pomocí direktiv vkládaných přímo do zdrojového kódu. V této kapitole se podíváme na to, jak funguje základní model *fork-join*, jak se v OpenMP definují úlohy (tasky), a jaké máme k dispozici prostředky pro synchronizaci. Ukážeme si i různé varianty implementací OpenMP a přehled direktiv, které programátorům umožňují jemné řízení paralelismu.
  
 ==== Sériově-paralelní model uspořádání vláken (fork-join) ==== ==== Sériově-paralelní model uspořádání vláken (fork-join) ====
-Fork-join model je základní exekuční schéma OpenMP. Program začíná jedním *master* vláknem, které po vstupu do direktivy **`parallel`** vytvoří tým dalších vláken (*fork*). Všechna vlákna spolupracují v daném paralelním regionu a na jeho konci se implicitní bariérou zase spojí do jediného vlákna (*join*).+Fork-join model je základní exekuční schéma OpenMP. Program začíná jedním *master* vláknem, které po vstupu do direktivy **''parallel''** vytvoří tým dalších vláken (*fork*). Všechna vlákna spolupracují v daném paralelním regionu a na jeho konci se implicitní bariérou zase spojí do jediného vlákna (*join*).
   * Výhody:   * Výhody:
     * jednoduchá správa vláken     * jednoduchá správa vláken
Line 358: Line 358:
  
 Další možnosti a doplňky modelu: Další možnosti a doplňky modelu:
-  * `#pragma omp barrier` – ruční synchronizační bod. +  * ''#pragma omp barrier'' – ruční synchronizační bod. 
-  * `single`, `master` – sekci vykoná pouze jedno vlákno. +  * ''single'', ''master'' – sekci vykoná pouze jedno vlákno. 
-  * `ordered` – zachování pořadí iterací ve smyčce. +  * ''ordered'' – zachování pořadí iterací ve smyčce. 
-  * `critical`, `atomic` – zajištění sériového přístupu ke sdíleným proměnným. +  * ''critical'', ''atomic'' – zajištění sériového přístupu ke sdíleným proměnným. 
-  * `nowait` – zabrání implicitní bariéře na konci paralelního bloku. +  * ''nowait'' – zabrání implicitní bariéře na konci paralelního bloku. 
-  * `OMP_NESTED=TRUE` nebo `omp_set_max_active_levels()` – aktivuje vnořenou paralelizaci. +  * ''OMP_NESTED=TRUE'' nebo ''omp_set_max_active_levels()'' – aktivuje vnořenou paralelizaci. 
-  * `task`, `taskgroup`, `depend(...)` – jemné řízení závislostí mezi úlohami (viz níže).+  * ''task'', ''taskgroup'', ''depend(...)'' – jemné řízení závislostí mezi úlohami (viz níže).
  
 ==== Paralelizovatelná úloha (task region) ==== ==== 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. +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`. +  * Tasky lze organizovat do ''taskgroup''. 
-  * Pomocí `depend(in|out|inout: var)` lze řídit pořadí a závislosti. +  * Pomocí ''depend(in|out|inout: var)'' lze řídit pořadí a závislosti. 
-  * `detach`, `priority` – umožňují pokročilou kontrolu provádění.+  * ''detach'', ''priority'' – umožňují pokročilou kontrolu provádění.
  
 Příklad: Příklad:
Line 387: Line 387:
  
 Přehled nejznámějších implementací (stav 2025):* Přehled nejznámějších implementací (stav 2025):*
-  * **GCC 14+ (libgomp)** – `-fopenmp`, verze 5.2 (téměř úplná), open-source klasika. +  * **GCC 14+ (libgomp)** – ''-fopenmp'', verze 5.2 (téměř úplná), open-source klasika. 
-  * **Clang 18+ (libomp)** – `-fopenmp`, verze 5.2 (většina), funguje i na Windows. +  * **Clang 18+ (libomp)** – ''-fopenmp'', verze 5.2 (většina), funguje i na Windows. 
-  * **Intel oneAPI (icx/icpx + iomp5)** – `-qopenmp`, verze 5.2, velmi výkonný runtime, podpora GPU. +  * **Intel oneAPI (icx/icpx + iomp5)** – ''-qopenmp'', verze 5.2, velmi výkonný runtime, podpora GPU. 
-  * **IBM XL (LLVM-based)** – `-qsmp=omp`, verze 5.1, optimalizace pro POWER.+  * **IBM XL (LLVM-based)** – ''-qsmp=omp'', verze 5.1, optimalizace pro POWER.
   * **AMD AOCC 4.x** – laděno pro AMD Zen, Clang + libomp.   * **AMD AOCC 4.x** – laděno pro AMD Zen, Clang + libomp.
   * **Cray/ROCm** – zaměřeno na GPU/offload (OpenMP target).   * **Cray/ROCm** – zaměřeno na GPU/offload (OpenMP target).
  
 ==== Přehled hlavních direktiv OpenMP ==== ==== Přehled hlavních direktiv OpenMP ====
-**`#pragma omp parallel`**  +**''#pragma omp parallel''**  
   * Vytvoří tým vláken.   * Vytvoří tým vláken.
-  * Podporuje: `num_threads`, `if`, `default`, `shared`, `private`, … +  * Podporuje: ''num_threads'', ''if'', ''default'', ''shared'', ''private'', … 
-**`for` / `do`**  +**''for'' / ''do''**  
   * Paralelizace smyčky.   * Paralelizace smyčky.
-  * Možnosti: `schedule(static|dynamic|guided)`, `collapse(n)`, `reduction`, `nowait`. +  * Možnosti: ''schedule(static|dynamic|guided)'', ''collapse(n)'', ''reduction'', ''nowait''. 
-**`sections` / `section`**  +**''sections'' / ''section''**  
   * Spustí nezávislé bloky kódu paralelně (např. různé funkce najednou).   * Spustí nezávislé bloky kódu paralelně (např. různé funkce najednou).
-**`task`**   +**''task''**   
-  * Vytvoří úlohu; možnost specifikace závislostí přes `depend(...)`. +  * Vytvoří úlohu; možnost specifikace závislostí přes ''depend(...)''. 
-  * Další klauzule: `priority`, `detach`. +  * Další klauzule: ''priority'', ''detach''. 
-**`barrier`**  +**''barrier''**  
   * Explicitní synchronizační bod – všechna vlákna musí dojít na toto místo.   * Explicitní synchronizační bod – všechna vlákna musí dojít na toto místo.
-**`critical [(name)]`**  +**''critical [(name)]''**  
   * Zamezí více vláknům vstup do stejné sekce kódu najednou.   * Zamezí více vláknům vstup do stejné sekce kódu najednou.
   * Jméno odděluje různé nezávislé sekce.   * Jméno odděluje různé nezávislé sekce.
-**`atomic`**  +**''atomic''**  
   * Odlehčená synchronizace pro jednoduché operace s proměnnou (inkrementace, zápis, čtení…).   * Odlehčená synchronizace pro jednoduché operace s proměnnou (inkrementace, zápis, čtení…).
  
Line 443: Line 443:
 </code> </code>
    
-Tento příklad ukazuje vytvoření tasku se závislostí `depend(out: sum)`, paralelní redukci vnitřní smyčky, a následný task, který čeká na výsledek (`depend(in: sum)`).+Tento příklad ukazuje vytvoření tasku se závislostí ''depend(out: sum)'', paralelní redukci vnitřní smyčky, a následný task, který čeká na výsledek (''depend(in: sum)'').
  
  
Line 451: Line 451:
 ==== Statické × dynamické rozdělení práce ==== ==== Statické × dynamické rozdělení práce ====
   * **Statické rozdělení** – práce (např. iterace smyčky) se rozdělí předem mezi všechna vlákna.   * **Statické rozdělení** – práce (např. iterace smyčky) se rozdělí předem mezi všechna vlákna.
-    * Např. pomocí `schedule(static[, chunk])` v OpenMP.+    * Např. pomocí ''schedule(static[, chunk])'' v OpenMP.
     * Výhodou je **nízký overhead** (prakticky žádná synchronizace).     * Výhodou je **nízký overhead** (prakticky žádná synchronizace).
     * Nevýhodou je, že **u nepravidelných úloh může být některé vlákno přetížené**, zatímco jiné skončí dříve a zahálí.     * Nevýhodou je, že **u nepravidelných úloh může být některé vlákno přetížené**, zatímco jiné skončí dříve a zahálí.
   * **Dynamické rozdělení** – práce se přiděluje **za běhu** podle toho, které vlákno je volné.   * **Dynamické rozdělení** – práce se přiděluje **za běhu** podle toho, které vlákno je volné.
-    * Používá se `schedule(dynamic[, chunk])`.+    * Používá se ''schedule(dynamic[, chunk])''.
     * Výhodou je lepší **vyvážení zátěže**.     * Výhodou je lepší **vyvážení zátěže**.
     * Nevýhodou je **vyšší režie kvůli synchronizaci**.     * Nevýhodou je **vyšší režie kvůli synchronizaci**.
   * **Guided plánování** – kompromis mezi statickým a dynamickým:   * **Guided plánování** – kompromis mezi statickým a dynamickým:
-    * `schedule(guided[, chunk])` začíná velkými bloky a postupně zmenšuje chunk velikost.+    * ''schedule(guided[, chunk])'' začíná velkými bloky a postupně zmenšuje chunk velikost.
     * Vhodné pro případy, kdy práce trvá různě dlouho a časem ubývá.     * Vhodné pro případy, kdy práce trvá různě dlouho a časem ubývá.
   * Další možnosti:   * Další možnosti:
-    * `schedule(runtime)` – výběr plánování je ponechán na hodnotě proměnné `OMP_SCHEDULE`. +    * ''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.+    * ''schedule(auto)'' – nechá výběr plánu na implementaci OpenMP.
  
 ==== Thread-pool a fronta úkolů (work-stealing) ==== ==== Thread-pool a fronta úkolů (work-stealing) ====
Line 476: Line 476:
 Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu. Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu.
   * U **smyček**:   * U **smyček**:
-    * Volba správného `schedule(...)` plánu. +    * Volba správného ''schedule(...)'' plánu. 
-    * Velikost `chunku` ovlivňuje granularitu přidělené práce. +    * Velikost ''chunku'' ovlivňuje granularitu přidělené práce. 
-    * `collapse(n)` – slučuje více vnořených smyček do jedné, čímž zvyšuje počet iterací pro paralelizaci.+    * ''collapse(n)'' – slučuje více vnořených smyček do jedné, čímž zvyšuje počet iterací pro paralelizaci.
   * U **tasků**:   * U **tasků**:
     * Work-stealing pomáhá s dynamickým plánováním.     * Work-stealing pomáhá s dynamickým plánováním.
-    * Pomocí `priority(expr)` lze zvýhodnit důležité úkoly.+    * Pomocí ''priority(expr)'' lze zvýhodnit důležité úkoly.
     * Heuristiky runtime mohou **omezit vznik malých tasků** (např. jejich inline-ing) → lepší škálování.     * Heuristiky runtime mohou **omezit vznik malých tasků** (např. jejich inline-ing) → lepší škálování.
  
 ==== Závislosti (dependencies) ==== ==== Závislosti (dependencies) ====
-Tasky mohou mít mezi sebou **závislosti**, které určují pořadí provádění. V OpenMP se deklarují pomocí `depend(...)`.+Tasky mohou mít mezi sebou **závislosti**, které určují pořadí provádění. V OpenMP se deklarují pomocí ''depend(...)''.
   * Typy závislostí:   * Typy závislostí:
-    * `depend(in: X)` – task **potřebuje** data `X`. +    * ''depend(in: X)'' – task **potřebuje** data ''X''. 
-    * `depend(out: X)` – task **produkuje** data `X`. +    * ''depend(out: X)'' – task **produkuje** data ''X''. 
-    * `depend(inout: X)` – task `X` čte i zapisuje. +    * ''depend(inout: X)'' – task ''X'' čte i zapisuje. 
-    * Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře.+    * Další pokročilé typy: ''mutexinoutset'', ''depobj'' – pro specializované scénáře.
  
 Ukázkový kód: Ukázkový kód:
Line 510: Line 510:
  
 ===== 6. Techniky dekompozice programu na příkladech ===== ===== 6. Techniky dekompozice programu na příkladech =====
-Abychom lépe pochopili různé způsoby paralelizace, ukážeme si je na konkrétních příkladech z oblasti řazení, lineární algebry a strojového učení. Uvidíme, jak lze algoritmy jako quick sort nebo násobení matic přirozeně rozdělit do paralelních částí a jaké techniky přitom použít – např. tasky, `collapse`, blokové zpracování či závislosti.+Abychom lépe pochopili různé způsoby paralelizace, ukážeme si je na konkrétních příkladech z oblasti řazení, lineární algebry a strojového učení. Uvidíme, jak lze algoritmy jako quick sort nebo násobení matic přirozeně rozdělit do paralelních částí a jaké techniky přitom použít – např. tasky, ''collapse'', blokové zpracování či závislosti.
  
 ==== Řazení ==== ==== Řazení ====
Line 520: Line 520:
     * *Conquer*: obě části rekurzivně řadíme – ideální místo pro vytvoření dvou paralelních úloh (*tasků*).       * *Conquer*: obě části rekurzivně řadíme – ideální místo pro vytvoření dvou paralelních úloh (*tasků*).  
     * *Combine*: není třeba – dělení samo zajistí správné pořadí.     * *Combine*: není třeba – dělení samo zajistí správné pořadí.
-  * Paralelizace: po operaci `partition` spustíme levé větvení jako `omp task`, pravé běží ve vlákně dál.+  * Paralelizace: po operaci ''partition'' spustíme levé větvení jako ''omp task'', pravé běží ve vlákně dál.
  
 <code cpp> <code cpp>
Line 546: Line 546:
     * *Divide*: rekurzivní dělení pole na půlky.       * *Divide*: rekurzivní dělení pole na půlky.  
     * *Conquer*: každou půlku řadíme paralelně.       * *Conquer*: každou půlku řadíme paralelně.  
-    * *Combine*: dvě seřazené části spojíme lineárním `merge`. +    * *Combine*: dvě seřazené části spojíme lineárním ''merge''. 
-  * Paralelizace: obě rekurze běží jako tasky, po jejich dokončení proběhne `inplace_merge`.+  * Paralelizace: obě rekurze běží jako tasky, po jejich dokončení proběhne ''inplace_merge''.
  
 <code cpp> <code cpp>
Line 575: Line 575:
     * *Divide*: rozdělíme po řádcích.       * *Divide*: rozdělíme po řádcích.  
     * *Conquer*: každý řádek počítá vlákno nezávisle.       * *Conquer*: každý řádek počítá vlákno nezávisle.  
-    * *Combine*: nepotřebujeme – každý výstupní `y[i]` je unikátní.+    * *Combine*: nepotřebujeme – každý výstupní ''y[i]'' je unikátní.
   * U husté matice: nejlepší přístup po řádcích (row-major).     * U husté matice: nejlepší přístup po řádcích (row-major).  
   * U řídké: paralelizace přes nenulové řádky (např. CSR formát).   * U řídké: paralelizace přes nenulové řádky (např. CSR formát).
Line 598: Line 598:
   * **Blokové (tiling) násobení**:   * **Blokové (tiling) násobení**:
     * *Divide*: rozdělíme výstupní matici $C$ na bloky $B_{pq}$.     * *Divide*: rozdělíme výstupní matici $C$ na bloky $B_{pq}$.
-    * *Conquer*: každý blok počítá vlákno/task – např. pomocí `collapse(2)`.+    * *Conquer*: každý blok počítá vlákno/task – např. pomocí ''collapse(2)''.
     * *Combine*: není třeba – bloky jsou oddělené.     * *Combine*: není třeba – bloky jsou oddělené.
  
Line 614: Line 614:
   * **Gaussova eliminace (LU)**: v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$.   * **Gaussova eliminace (LU)**: v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$.
     * Paralelizujeme řádky $i = k+1..n-1$.     * Paralelizujeme řádky $i = k+1..n-1$.
-    * Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti.+    * Nutná synchronizace mezi kroky – ''taskwait'' nebo sekvenční závislosti.
  
 <code cpp> <code cpp>
Line 630: Line 630:
  
   * **Iterativní metody (Jacobi, CG, GMRES)**:   * **Iterativní metody (Jacobi, CG, GMRES)**:
-    * Lépe paralelizovatelné než Gauss – hlavně `matvec`, vektorové operace, redukce. +    * Lépe paralelizovatelné než Gauss – hlavně ''matvec'', vektorové operace, redukce. 
-    * OpenMP poskytuje `reduction(+:)` a `atomic` pro synchronizaci.+    * OpenMP poskytuje ''reduction(+:)'' a ''atomic'' pro synchronizaci.
  
   * **Off-load na GPU (OpenMP 5.x)**:   * **Off-load na GPU (OpenMP 5.x)**:
-    * Pomocí `target teams distribute parallel for` lze výpočet přenést na GPU.+    * Pomocí ''target teams distribute parallel for'' lze výpočet přenést na GPU.
     * Host kontroluje synchronizaci, ale výpočet běží plně na zařízení.     * Host kontroluje synchronizaci, ale výpočet běží plně na zařízení.
  
Line 756: Line 756:
  
 Každý proces $p_i$ periodicky: Každý proces $p_i$ periodicky:
-  - Posílá `ping` náhodnému uzlu $p_j$ a čeká na `ack`. +  - 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`). +  - 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`.+  - 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.   - Pokud nikdo z $\mathcal{K}$ nedostane odpověď → $p_j$ je označen za mrtvého.
  
Line 904: Line 904:
 **Základní princip:** **Základní princip:**
   * Procesy si **lokálně zaznamenají** svůj stav.   * Procesy si **lokálně zaznamenají** svůj stav.
-  * Stav kanálů mezi nimi se zjistí pomocí **speciální zprávy**: `ZNAČKA ▪`.+  * Stav kanálů mezi nimi se zjistí pomocí **speciální zprávy**: ''ZNAČKA ▪''.
   * Algoritmus je **asynchronní** a **neblokující** – každý proces koná na základě přijatých značek.   * Algoritmus je **asynchronní** a **neblokující** – každý proces koná na základě přijatých značek.
  
 **Průběh:** **Průběh:**
-  - Jeden proces iniciuje snapshot – uloží si stav a pošle `ZNAČKA ▪` všem sousedům. +  - Jeden proces iniciuje snapshot – uloží si stav a pošle ''ZNAČKA ▪'' všem sousedům. 
-  - Když jiný proces obdrží `ZNAČKA ▪` poprvé:+  - Když jiný proces obdrží ''ZNAČKA ▪'' poprvé:
       * uloží svůj stav,       * uloží svůj stav,
-      * pošle `ZNAČKA ▪` dál,+      * pošle ''ZNAČKA ▪'' dál,
       * vše, co do té doby přišlo na kanálu, **patří do snapshotu**.       * vše, co do té doby přišlo na kanálu, **patří do snapshotu**.
-  - 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.+  - 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 je **konzistentní globální snapshot**. Výsledkem je **konzistentní globální snapshot**.
  
Line 949: Line 949:
   * V distribuovaném prostředí je nutné **synchronizovat přístup přes zprávy**.   * V distribuovaném prostředí je nutné **synchronizovat přístup přes zprávy**.
   * Algoritmus poskytuje dvě základní operace:   * Algoritmus poskytuje dvě základní operace:
-    * `enter()` – požádá o vstup do kritické sekce +    * ''enter()'' – požádá o vstup do kritické sekce 
-    * `exit()` – opustí kritickou sekci+    * ''exit()'' – opustí kritickou sekci
  
 ==== Požadavky na algoritmus pro vyloučení procesů ==== ==== Požadavky na algoritmus pro vyloučení procesů ====
Line 998: Line 998:
     * frontu odložených žádostí     * frontu odložených žádostí
   * Pro vstup do kritické sekce:   * Pro vstup do kritické sekce:
-    * proces pošle `REQUEST` všem, zaznamená čas +    * proces pošle ''REQUEST'' všem, zaznamená čas 
-    * čeká na odpovědi `OK` od všech+    * čeká na odpovědi ''OK'' od všech
   * Ostatní procesy odpoví podle kauzálního (Lamportova) času   * Ostatní procesy odpoví podle kauzálního (Lamportova) času
  
Line 1042: Line 1042:
   * Procesy jsou logicky uspořádány do kruhu (např. podle ID). Každý zná svého následníka a umí ho kontaktovat.   * Procesy jsou logicky uspořádány do kruhu (např. podle ID). Každý zná svého následníka a umí ho kontaktovat.
   * Při podezření na pád lídra (např. po timeoutu) proces $P_i$ zahájí volby:   * Při podezření na pád lídra (např. po timeoutu) proces $P_i$ zahájí volby:
-    * pošle `ELECTION(i)` svému následníkovi. +    * pošle ''ELECTION(i)'' svému následníkovi. 
-    * pokud příjemce dostane `ELECTION(j)`:+    * pokud příjemce dostane ''ELECTION(j)'':
       * pokud $j > i$, předá dál beze změny,       * pokud $j > i$, předá dál beze změny,
       * pokud $j < i$, nahradí vlastním ID a pošle dál,       * pokud $j < i$, nahradí vlastním ID a pošle dál,
       * pokud $j = i$, zpráva oběhla kruh ⇒ $P_i$ má nejvyšší ID ⇒ vítězí.       * pokud $j = i$, zpráva oběhla kruh ⇒ $P_i$ má nejvyšší ID ⇒ vítězí.
-  * Nový lídr pak vyšle `ELECTED(i)` kolem kruhu → všichni si uloží nového lídra.+  * Nový lídr pak vyšle ''ELECTED(i)'' kolem kruhu → všichni si uloží nového lídra.
  
 **Vlastnosti:** **Vlastnosti:**
Line 1058: Line 1058:
   * Procesy jsou propojeny do **úplné sítě** – každý zná každého.   * Procesy jsou propojeny do **úplné sítě** – každý zná každého.
   * Pokud $P_i$ zjistí, že koordinátor mlčí (timeout), zahájí volby:   * Pokud $P_i$ zjistí, že koordinátor mlčí (timeout), zahájí volby:
-  - Pošle `ELECTION` všem **procesům s vyšším ID**+  - Pošle ''ELECTION'' všem **procesům s vyšším ID**
   - Pokud žádný neodpoví → $P_i$ se **prohlásí lídrem**   - Pokud žádný neodpoví → $P_i$ se **prohlásí lídrem**
-  - Pošle `COORDINATOR(i)` všem **nižším ID** +  - Pošle ''COORDINATOR(i)'' všem **nižším ID** 
-  - Pokud někdo odpoví `OK` → $P_i$ čeká na `COORDINATOR(k)` od silnějšího+  - Pokud někdo odpoví ''OK'' → $P_i$ čeká na ''COORDINATOR(k)'' od silnějšího
   - Pokud neobdrží oznámení včas, znovu zahájí volby   - Pokud neobdrží oznámení včas, znovu zahájí volby
  
 **Zprávy:** **Zprávy:**
-  * `ELECTION` – „ozvi se, pokud žiješ a jsi silnější“ +  * ''ELECTION'' – „ozvi se, pokud žiješ a jsi silnější“ 
-  * `OK` – potvrzení, že někdo silnější žije +  * ''OK'' – potvrzení, že někdo silnější žije 
-  * `COORDINATOR(k)` – oznámení o novém lídrovi+  * ''COORDINATOR(k)'' – oznámení o novém lídrovi
  
 **Vlastnosti:** **Vlastnosti:**

Trace: • b4b38nvs

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b36pdv (generated for current page)