statnice:bakalar:b4b36pdv

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

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

/*
###################################################################################################################################################################################
###################################################################################################################################################################################
###################################################################################################################################################################################
*/
===== 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í**
  * (super)skalární architektury, pipelining, spekulativní vyhodnocování, Hierarchie cache paměti: (statnice:bakalar:b0b35apo)
  * vlákna, procesy: (statnice:bakalar:b4b35osy)

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

ektorové instrukce vykonávají jednu danou operaci na velkém množství dat najednou.
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, jako např. násobení matic.
Moderní kompilátory jsou schopné automaticky vektorizovat části kódu.
Pro znatelné zrychlení je ale nutná manuální implementace.

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

Existuje mnoho standardů, nejznámější jsou x86 standardy:
  * AVX    - starší, velmi rozšířený, až 128bit registery
  * AVX2   - novější, velmi rozšířený, oproti AVX2 přidává nové operace a 256bit registery
  * AVX512 - oproti AVX2 přidává mnoho dalších operací a 512bit registery, není moc rozšířený, u nových procesorů pouze u AMD

==== Superskalární vs. skalární procesory ====
* **Skalární CPU** (klasické RISC): každém cyklu vydá a vykoná **jednu** instrukci.  
* **Superskalární CPU**: obsahuje více paralelních výkonných jednotek a dokáže **v jednom cyklu vydat/vykonat více nezávislých instrukcí** (typicky 2-8 wide). To zvyšuje paralelismus na úrovni instrukcí (ILP) bez zásahu programátora. :contentReference[oaicite:4]{index=4}

=== Jak to funguje ===
  * Front-end dekóduje několik instrukcí najednou, analyzuje závislosti a předává je do **více pipeline** (ALU, FPU, load/store unit).  
  * **Out-of-order** a **spekulativní vykonávání** plní pipeline, i když nejsou známé všechny výsledky větvení.  
  * Dynamické přejmenování registrů minimalizuje falešné závislosti (WAR/WAW). :contentReference[oaicite:5]{index=5}

=== Pipelining a jeho vztah k superskaláru ===
* **Pipeline** rozděluje vykonání instrukce do fází (IF, ID, EX, MEM, WB). Při dostatečné délce pipeline může CPU dosáhnout **1 instrukce / cyklus** i na skalárním jádře. :contentReference[oaicite:6]{index=6}  
* Superskalární jádro má **více* takových pipeline paralelně** – např. dvě ALU, jednu FPU, jednu vektorovou. Při ideálním ILP zvládne několik instrukcí za cyklus (CPI < 1).  
* Pipeline i superskalár vyžadují:  
  * přesné predikce větvení; chybné odhady = flush pipeline → ztráta cyklů,  
  * dostatek nezávislých instrukcí (kompilátor + out-of-order scheduler),  
  * rychlé cache, aby latence paměti nevyhladověla pipeline. 

=== Proč na tom záleží ===
S rostoucí hloubkou pipeline a šířkou superskaláru se zvyšuje maximální IPC, ale i složitost řídicí logiky a spotřeba. Moderní jádra (Intel Alder Lake, AMD Zen 4) kombinují 5-6 GHz frekvence, ~14–19 stupňové pipeline a 4-6-wide superskalární dekodéry, aby udržela výkon na jádro bez dramatického růstu spotřeby.

==== GPGPU ====

* **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické akcelerátory jako masivně paralelní výpočetní jednotky.
* Typický desktopový GPU (např. NVIDIA Ampere) má tisíce jednoduchých jader sdružených do **streaming multiprocessorů (SM)**, které spouštějí stovky až tisíce vláken v konceptu **warpů** (32 vláken běžících lock-step).&#x20;

=== Architektura a omezení ===

* **Hierarchie výpočetních bloků:** GPC $\rightarrow$ SM $\rightarrow$ processing block $\rightarrow$ warp $\rightarrow$ thread.
* **Sdílené prostředky SM:**

  * 128 KB *shared memory* + L1 cache
  * 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)&#x20;
* **Paměťová hierarchie GPU:**

  * L1/shared: ~33 cyklů
  * L2: až 2 TB/s (~200 cyklů)
  * 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.&#x20;

=== Výpočetní výkon v praxi ===

| Konfigurace                   | Single-thread | Multi-thread CPU | CPU + GPGPU    |
| Threadripper 3990X + RTX 4090 | 49 GFLOPS     | 3 .7 TFLOPS      | **100 TFLOPS** |

*Na stejném stroji GPU dodá ~×25 výkon oproti plně vytíženému CPU;

=== Programovací modely ===

* **CUDA C/C++** – proprietární, de-facto standard pro NVIDIA.
* **OpenCL 3.0** – otevřený standard podporovaný NVIDIA, AMD, Intel, ARM Mali.
* **SYCL 2020** – moderní C++20 nad OpenCL/CUDA/Level Zero; přenositelné šablony a paralelní STL.
* **OpenMP 5.x target/teams** – off-load direktivy do GPU, relativně snadná migrace existujícího kódu.
* Další možnosti: Vulkan Compute, DirectX 12 Compute, Thrust (C++ algoritmy nad CUDA).

=== Typické úlohy ===

* lineární algebra (matmul, BLAS), strojové učení, ray-tracing, simulace částic/CFD, kryptografie, video-encoding.

=== Výhody ===

* **Obrovský teoretický throughput** (tisíce FP jednotek).
* **Energetická efektivita**: TFLOPS/W často výrazně lepší než CPU.
* **Specializované instrukce** (Tensor Cores, BF16/FP16).

=== Nevýhody ===

* **Paměťová latence** mimo L1/shared, nutnost koalesovaného přístupu.
* **Omezená velikost registrů a shared memory** $\rightarrow$ ladění obsazenosti.
* **Drahé přenosy host ↔ device** (PCIe).
* **Divergence warpů** (větvení) snižuje výkon – kód musí být datově paralelní.
* **Vendor lock-in** (CUDA) či různé úrovně podpory standardů na HW.

=== Shrnutí ===
GPGPU nabízí **řádově vyšší paralelní výkon** než mainstreamové CPU, ale vyžaduje uvědomělou práci s pamětí a thread-level paralelismem. Správná volba programovacího modelu (CUDA ↔ OpenCL/SYCL ↔ OpenMP target) umožní radikální zrychlení numericky-intenzivních úloh při zachování udržitelnosti kódu.
/*
###################################################################################################################################################################################
###################################################################################################################################################################################
###################################################################################################################################################################################
*/
===== Komplikace v paralelním programování =====
**souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing)**
  * souběh (race condition), uváznutí (deadlock): (statnice:bakalar:b4b35osy)

==== False Sharing ====
Nastává když dvě vlákna přistupují k **různým** promněným na stejné cache line.
Když jedno vlákno zapíše do cache svojí variable, tak se automaticky invalidují všechna data na stejné cache line.
Pokud tedy tyto dvě vlákna konstantně tyto dvě promněné mění, dochází ke značnému poklesu výkonu.

==== True Sharing (není komplikace) ====
Nastává když dvě vlákna přistupují k **stejné** promněné. 

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++ =====
**pthreads, thread, jthread, atomic, mutex, lock_guard**

  * pthreads: POSIX vlákna (pthreads) jsou standardní rozhraní pro práci s vlákny v jazyku C. Umožňují vytvářet, spravovat a synchronizovat vlákna v aplikacích. Příklady použití zahrnují vytváření vláken pomocí pthread_create(), synchronizaci pomocí mutexů (pthread_mutex_lock(), pthread_mutex_unlock()), podmínkových proměnných (pthread_cond_wait(), pthread_cond_signal()) a semaforů (sem_init(), sem_wait(), sem_post()).
  * thread: C++11 přidává standardní knihovnu pro práci s vlákny, která zahrnuje třídu std::thread pro vytváření a správu vláken. Synchronizace se provádí pomocí mutexů (std::mutex), podmínkových proměnných (std::condition_variable) a dalších synchronizačních primitiv.
  * jthread: C++20 přidává třídu std::jthread, která automaticky spravuje životní cyklus vlákna a umožňuje snadnější použití s lambda výrazy. Na rozdíl od std::thread se jthread automaticky uvolní při skončení funkce.

==== Mutex a Lock Guard ====
Mutex (mutual exclusion) je synchronizační primitivum, které zajišťuje vzájemné vyloučení přístupu k sdíleným prostředkům mezi vlákny. Používá se k ochraně kritických sekcí kódu, aby se zabránilo souběžnému přístupu více vláken k těmto prostředkům. V C++ se mutexy implementují pomocí třídy std::mutex a jejích variant (např. std::recursive_mutex, std::timed_mutex).

Ukázkový kód:
<code cpp>
#include <iostream>
#include <thread>
#include <mutex>

int main() {
    std::mutex mtx;

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

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

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

    return 0;
}
</code>

Moderní c++ umožnuje použít **std::lock_guard** pro automatické zamykání a odemykání mutexu. To zjednodušuje správu mutexů a zabraňuje zapomenutí odemknout mutex v případě výjimky nebo předčasného ukončení funkce.
<code cpp>

#include <iostream>
#include <thread>
#include <mutex>

int main() {
    std::mutex mtx;

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

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

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

    return 0;
}

</code>

==== Atomic ====
Atomic je typ datového typu, který zajišťuje atomické operace na sdílených proměnných mezi vlákny. V C++ se atomické operace implementují pomocí třídy std::atomic. Atomic proměnné zajišťují, že operace na nich jsou prováděny jako nedělitelný celek, což zabraňuje problémům se souběhem.
V podstatě je to jako mutex, ale bez zamykání a odemykání. Atomic proměnné jsou rychlejší než mutexy (Pokud to hw podporuje), protože nevolají do jádra pro mutex, pokud hw nepodporuje atomické operace, tak se použije mutex. Atomic proměnné jsou v podstatě implementovány jako atomické instrukce na procesoru, které zajišťují, že operace na těchto proměnných jsou prováděny jako nedělitelný celek. VV praxi jsou na hardweru většinou (jsem si téměř jistý že vždy) implementovány jako instrukce nad normálními proměnnými, nic jako datový typ není na hw.

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

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

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

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

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

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

    return 0;
}
</code>



/*
###################################################################################################################################################################################
###################################################################################################################################################################################
###################################################################################################################################################################################
*/
===== 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, sections, task, barrier, critical, atomic.**

==== 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áka (*join*).  
Výhody: jednoduchá správa vláken, sdílená paměť a do jisté míry předvídatelná synchronizace.

<markdown>
- **Explicitní synchronizace uvnitř regionu**
  - `#pragma omp barrier` – ruční bariéra.
  - `single` / `master` – sekci vykoná pouze jedno vlákno.
  - `ordered` – zachování pořadí iterací ve smyčce.
  - `critical(name)` nebo `atomic` – sériový přístup k proměnné či úseku.

- **Omezení serializace**  
  Přidej klauzuli `nowait`, pokud bariéru na konci *work-sharing* konstrukce nepotřebuješ.

- **Vnořená paralelizace**  
  Výchozí stav je vypnutý (`OMP_NESTED=TRUE` nebo `omp_set_max_active_levels()` ji zapne).

- **Tasky a datové závislosti**  
  `task`, `taskgroup`, `depend(in|out|inout: A)` umožní jemnější DAG nad stávajícím fork-join skeletonem.


Ukázkový kód (C):

```c
#include <omp.h>
#include <stdio.h>

int main(void) {
    #pragma omp parallel
    {
        int id  = omp_get_thread_num();
        int n   = omp_get_num_threads();
        printf("Hello from thread %d of %d\n", id, n);
    }   /* <-- implicit join & barrier */
    return 0;
}
````
</markdown>
Poznámka: **Fork-join v OpenMP vytváří vlákna, nikoli samostatné procesy**. Implementace obvykle stojí na POSIX/pthreads; celý tým sdílí stejnou adresní prostor a paměť. (Procesy se používají jen ve speciálních hybridních modelech např. MPI+OpenMP.)

===== Různé implementace OpenMP specifikace =====
Běžně používané kompilátory a knihovny OpenMP (stav jaro 2025):

<markdown>
| Implementace | Kompilátor / knihovna | Úroveň podpory | Poznámky |
|--------------|----------------------|----------------|----------|
| **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, funguje i na Windows. |
| **Intel oneAPI (icx/icpx + iomp5)** | `-qopenmp` | 5.2 | Vysoce optimalizovaný runtime, podporuje offload na GPU. |
| **IBM XL / LLVM-based** | `-qsmp=omp` | 5.1 | Optimalizace pro POWER. |
| **AMD AOCC 4.x** | Clang + libomp | 5.1 | Laděno pro Zen architekturu. |
| **Cray/AMD ROCm (OpenMP Offload)** | Clang | 5.2 | Zaměřeno na akcelerátory a HPC. |
</markdown>

==== Přehled hlavních direktiv OpenMP ==== 
<markdown>

* **`parallel`** – vytvoří tým vláken; podporuje klauzule `if`, `num_threads`, `default`, `shared`, `private`, …
* **`for` / `do`** – paralelizuje smyčku; plánování (`schedule(static|dynamic|guided)`), `collapse(n)`, `reduction`, `nowait`.
* **`sections` / `section`** – spustí nezávislé bloky kódu souběžně.
* **`task`** – vytvoří paralelizovatelnou úlohu, volitelně s `depend`, `priority`, `detach`.
* **`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>

==== Příklad zapojení všeho dohromady ====
Ukázka kombinuje `parallel`, `for`, tasky a závislosti:

<code c>
#include <omp.h>
#include <stdio.h>

int main(void) {
    #pragma omp parallel
    #pragma omp single          // jeden thread spouští tasky
    {
        #pragma omp task depend(out: sum)
        {
            int sum = 0;
            
            #pragma omp parallel for reduction(+\:sum) nowait
            for (int i = 0; i < 1e6; ++i)
                sum += i;
            
            printf("Sum done: %d\n", sum);
        }

        #pragma omp task depend(in: sum)
        {
            printf("Post-processing...\n");
        }
    }   // implicit taskgroup -> čekáme na všechny tasky
    return 0;

} </code>


/*
###################################################################################################################################################################################
###################################################################################################################################################################################
###################################################################################################################################################################################
*/

===== Techniky dekompozice programu =====
**statické a dynamické rozdělení práce. Thread-pool a fronta úkolů. Balancování a závislosti (dependencies).**

<markdown>
### Statické × dynamické rozdělení práce
- **Statické rozdělení** (`schedule(static[,chunk])`) přiřadí iterace/vlákna předem, minimální overhead, ale hrozí nevyváženost u nepravidelné práce.  
- **Dynamické rozdělení** (`schedule(dynamic[,chunk])`) přiděluje iterace za běhu podle aktuálního vytížení; víc synchronizace, ale lepší vyrovnání.  
- **Guided** (`schedule(guided[,chunk])`) začíná velkými bloky a postupně zmenšuje, kompromis mezi overheadem a vyvážením.  
- Další volby: `runtime` (čte z `OMP_SCHEDULE`), `auto` (nechá výběr na runtime).

### Thread-pool a fronta úkolů (work-stealing)
- První paralelní region vytvoří **persistentní tým** vláken – thread-pool – který se recykluje pro všechny další regiony.  
- Každé vlákno udržuje **lokální deque** s tasky; když jeho fronta zeje prázdnotou, **ukradne** (steals) úkol z cizí → vyrovnání zátěže bez centrální zámky.  
- Fronty se většinou zamykají jen při krádeži, takže běžné push/pop jsou lock-free a škálují.

### Balancování zátěže
- **Smyčky**: volba plánu (`static`, `dynamic`, `guided`), velikost chunku, případně `collapse(n)` pro součtové smyčky.  
- **Tasky**: work-stealing, `priority(expr)`, hromadné throttling limity a heuristiky kompilátoru (např. inline-ing malých tasků přes `if(too_small)`).

### Závislosti (dependencies)
- Tasks mohou deklarovat závislosti pomocí `depend` – `in`, `out`, `inout`, `mutexinoutset`, `depobj`.  
  ```c
  #pragma omp task depend(out:A)
  build_A();
  #pragma omp task depend(in:A) depend(out:B)
  build_B();
  #pragma omp task depend(in:B)
  use_B();
````

* Runtime tvoří orientovaný acyklický graf; když jsou všechny závislosti splněné, task se stane „ready“ a fronty si ho mohou volně rozebrat.

  </markdown>

===== Techniky dekompozice programu na příkladech =====
==== Řazení ====
**quick sort a merge sort**

=== Quick sort ===
<markdown>
- **Proč „rozděl a panuj“?**  
  - *Divide*: vyber pivot a pole jedním průchodem **rozděl** na část ↙︎ < pivot a část ↗︎ ≥ pivot.  
  - *Conquer*: obě části se **řadí rekurzivně** – ideální příležitost spustit dva *tasky* souběžně.  
  - *Combine*: žádné explicitní slévání není potřeba – rozdělení zaručilo správné pořadí.
- Paralelizace: po operaci `partition` spustíme řazení levé části v `omp task`, zatímco aktuální vlákno pokračuje pravou částí (viz kód).
- Zdrojový kód:
```cpp
void qs(std::vector<int>& vec, int from, int to) {
    if (to - from <= base_size) {
        std::sort(vec.begin() + from, vec.begin() + to);
        return;
    }

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

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

</markdown>

=== Merge sort === 
<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ě**, často opět ve dvou paralelních *tascích*.
  * *Combine*: dvě seřazené půlky se **slijí** lineárním `merge`, čímž vznikne seřazené pole větší velikosti.
* Paralelizace: dvě rekurzivní výzvy běží souběžně; po `taskwait` proběhne lineární slévání.
* Zdrojový kód:

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

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

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

</markdown>

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

=== Paralelní násobení matice × vektor (SpMV/Dense MV) ===
<markdown>
- **Princip:** každý výstupní prvek $y_i$ je skalární součin $i$-tého řádku matice $A$ a vektoru $x$.  
  - *Divide*: rozdělíme práci po řádcích (každý řádek je nezávislý).  
  - *Conquer*: vlákna počítají dot-product paralelně.  
  - *Combine*: žádná synchronizace není potřeba, každý řádek zapisuje vlastní $y_i$.

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

=== Paralelní násobení dvou matic ===
<markdown>
- **Naivní prvek-po-prvku ($c_{ij}$)** škáluje, ale má špatnou cache-lokalitu (každé vlákno prochází celou druhou matici).
- **Blokové (tiling) rozdělení:**  
  1. *Divide* výslednou matici $C$ na bloky $B_{pq}$ o velikosti např. 64 × 64.  
  2. *Conquer* — každý blok počítá jedno vlákno nebo task (`collapse(2)` či ruční tasking).  
     ```c
     #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);
     ```
  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í.
- **Prakticky:** pro výkon se používají knihovny pro matematické výpočty BLAS (OpenBLAS, MKL, libflame) s vysoce optimalizovaným blokováním a SIMD.
</markdown>

=== Paralelní řešení systému lineárních rovnic (Gaussova eliminace) ===
<markdown>
- **Gauss / LU**: pro každý krok $k$ lze *paralelně* provést eliminaci řádků $k+1..n-1$.  
  - Závisí na pivotu $A_{kk}$, takže v kroku $k$ musí být ukončené všechny změny z kroku $k-1$.  
  - `#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ů):**
</markdown>
<code c>
void gauss_elim(std::vector<double>& A) {         // ROWS × COLS, row-major
    for (int k = 0; k < ROWS - 1; ++k) {
        #pragma omp parallel for
        for (int i = k + 1; i < ROWS; ++i) {
            double c = -A[i * COLS + k] / A[k * COLS + k];
            for (int j = k; j < COLS; ++j)
                A[i * COLS + j] += c * A[k * COLS + j];
        }
    }
}
</code>
<markdown>
- **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(+:)` a `atomic`.

- **GPU / accelerator off-load:** v OpenMP 5.x pomocí `target teams distribute parallel for` →
  jádro se provede na GPU, host kontroluje synchronizaci.
</markdown>

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

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

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

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

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

Asynchronní x Synchronní DS
Asynchronní nemají žádné limity na rychlost vykonávání procesů ani trvání přenosů zpráv a časovému driftu lokálních hodin. (sychronní opak)

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

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

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

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

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

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



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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Logické hodiny

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

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

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

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

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

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

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

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

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

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

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

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

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

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

konzistentní řez = logický okamžik

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

==== Ricart-Agrawalův algoritmus ====
<markdown>
- Nepoužívá token, ale kauzalitu a multicast
- Nižší synchronizační zpoždění než kruhový algoritmus a nepoužívá centrální proces
- Každý proces si udržuje stav, který může nabývat 3 hodnot: WANTED, HELD, RELEASED (u všech procesů je inicializován na RELEASED)
- Před vstupem do KS:
	- Je nastaven stav na WANTED
	- Poslán multicast REQUEST všem ostatním procesům
	- Čeká na odpověď
	- Po přijetí OK je stav změněn na HELD a proces vstupuje do KS
- Po přijetí REQUEST
	- Pokud je stav WANTED a je časová značka přijaté zprávy nižší než čas ve kterém začal stav WANTED, je příslušný proces uložený do seznamu čekajících požadavků
	- Jinak je posláno OK
- Po výstupu z KS je stav nastaven na RELEASED a všem procesům ze seznamu je posláno OK
- V nejhorším případě je nutno čekat než všech $(N-1)$ pošle OK
- Je zachováno pořadí, požadavky s nižší lamportovou značkou mají přednost
- Komunikační zátěž – $2(N-1)$ při vstupu, až $(N-1)$ při výstupu
- Zpoždění klienta – **2** latence
- Synchronizační zpoždění – 1 latence
</markdown>

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

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

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

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

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

Navigation

Print/export

Tools

QR Code
