Modely a architektury paralelních a distribuovaných systémů; prostředky pro jejich implementaci a základní algoritmy.

B4B36PDV Webové stránky předmětu Nové webové stránky předmětu

• Paralelní systémy/výpočty:
  1. 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í.
  2. Komplikace v paralelním programování – souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing).
  3. Podpora paralelního programování v C a C++ – pthreads, thread, jthread, atomic, mutex, lock_guard.
  4. 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.
  5. Techniky dekompozice programu – statické a paralelní rozdělení práce. Threadpool a fronta úkolů. Balancování a závislosti (dependencies).
  6. Techniky dekompozice programu na příkladech:
     1. Řazení – quick sort, merge sort.
     2. 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:
  1. Úvod do distribuovaných systémů (DS) – charakteristiky DS, čas a typy selhání v DS.
  2. Detekce selhání v DS – detektory selhání a jejich vlastnosti.
  3. Čas a kauzalita v DS – uspořádání událostí v DS, fyzické hodiny a jejich synchronizace, logické hodiny a jejich synchronizace.
  4. 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.
  5. Vzájemné vyloučení procesů v DS – algoritmy pro vyloučení procesů a jejich vlastnosti.
  6. Volba lídra v DS – algoritmy pro volbu lídra a jejich vlastnosti.

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í (pipelining), přes využití více výpočetních jader (vlákna, procesy), až po extrémní paralelismus na GPU. Pochopení těchto principů je zásadní pro efektivní vývoj výkonných softwarových systémů.

Často nazývané SIMD instrukce – *single instruction, multiple data*.

Vektorové instrukce vykonávají jednu danou operaci na velkém množství dat najednou. Pracují nad speciálními vektorovými registry – až 512bit.

• To znamená, že například můžete násobit dvě celé pole čísel “najednou”, místo po jednotlivých prvcích.
• 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 často nutná manuální implementace.

Na rozdíl od paralelizace mezi jádry se nemusí řešit problémy synchronizace a 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 registry
• AVX2 – novější, přidává nové operace a 256bit registry
• AVX512 – mnoho dalších operací a 512bit registry, méně rozšířený, většinou jen u high-end CPU

• Definice: ILP udává, kolik *nezávislých* instrukcí může procesor potenciálně spustit paralelně v rámci *jednoho* programu/vlákna.
• Zdroj ILP: nezávislé aritmetické operace, nezávislé paměťové přístupy, nezávislé větvení.
• Využití ILP: pipelining, superskalární/VLIW architektury, out-of-order execution.

• Princip: Instrukční cesta se dělí na fáze IF → ID → EX → MEM → WB.

To umožňuje, aby různé instrukce byly zpracovávány současně v různých fázích – zvyšuje se propustnost, i když latence jednotlivé instrukce zůstává stejná.

• Teoretický zisk: až 1 instrukce / takt (IPC = 1); limitují ho hazardy a větvení.
• Superpipelining: více než 10 stupňů; vyšší frekvence, ale větší penalizace při chybách predikce.
• Hazardy:
  • datové – řeší se forwardingem, stally, přejmenováním registrů
  • řídicí – predikce skoků + branch target buffer (BTB)
  • strukturální – řeší se duplikací jednotek

• 1 instrukce za takt (IPC ≤ 1)
• jednodušší architektura
• využívá pipelining

• více instrukcí za takt (IPC > 1)
• N-wide architektura (např. 4-wide = až 4 instrukce/takt)
• využívá ILP pomocí paralelního vykonávání více instrukcí

• Statická: paralelně jen instrukce jdoucí v kódu za sebou; při závislostech nastává stall.
• Dynamická: out-of-order execution a přejmenování registrů → lepší využití hardwaru.

• Skalární CPU ⇒ 1 instrukce/takt, jednoduché, predikovatelné chování.
• Superskalární CPU ⇒ více instrukcí/takt, složitější řízení, vyšší výkon.

* General-Purpose computing on Graphics Processing Units (GPGPU) využívá původně grafické karty pro obecné výpočty.

* GPU obsahují tisíce jednoduchých jader sdružených do streaming multiprocessorů (SM).

Ty spouštějí stovky až tisíce vláken najednou ve skupinách (warp – 32 vláken běžících lock-step).

• Výpočetní hierarchie: GPC → SM → block → warp → thread
• 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ů

* Threadripper 3990X + RTX 4090:

• single-thread: 49 GFLOPS
• multi-thread CPU: 3.7 TFLOPS
• CPU + GPGPU: 100 TFLOPS

• CUDA C/C++ – pro NVIDIA
• OpenCL – otevřený standard
• SYCL – moderní C++ model
• OpenMP target – direktivy pro GPU

• lineární algebra, strojové učení, ray-tracing, simulace, video encoding…

• vysoký výkon (tisíce FP jednotek)
• efektivita (TFLOPS/W)
• specializované instrukce (Tensor Cores…)

• paměťová latence
• omezené registry/shared memory
• přenosy mezi host ↔ device
• warp divergence (větvení)
• vendor lock-in (CUDA)

GPGPU nabízí řádově vyšší výkon než běžné CPU, ale vývoj je složitější. Správné řízení paměti a vláken, spolu s vhodným programovacím modelem, je klíčem k úspěchu.

* 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, více programů najednou).

* 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.

Moderní CPU mají vícestupňovou hierarchii cache, která zajišťuje rychlý přístup k často používaným datům:

• L1 cache – nejmenší (např. 32 KB), ale nejrychlejší (~4 cykly), zvlášť pro instrukce a data.
• L2 cache – větší (např. 256 KB), pomalejší (~12 cyklů), většinou sdílena mezi jádry.
• L3 cache – největší (např. 16 MB), ještě pomalejší (~30–40 cyklů), sdílená mezi všemi jádry.
• RAM – mnohem větší, ale o řád(y) pomalejší než cache (~100 ns).
• Zásada locality: data, která byla použita nedávno nebo jsou blízko sobě, mají vyšší šanci být v cache – tím se výrazně snižuje průměrná latence paměťových přístupů.

Efektivní využití cache (např. přístup po řádcích, nikoliv po sloupcích v 2D poli) může mít zásadní vliv na výkon.

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í.

* Souběh (race condition) nastává, když dvě nebo více vláken přistupuje ke stejným datům a alespoň jedno z nich je mění, přičemž jejich pořadí není řízené (např. zámky, mutexy).

* To znamená, že výsledek programu závisí na načasování – někdy to „vyjde dobře“, jindy ne. * Typickým příkladem je inkrementace sdílené proměnné – pokud není chráněná zámkem, může být výsledek menší, než kolik se očekává.

Například:

// špatně – race condition
for (int i = 0; i < 1000; i++) {
 counter++;
}

* Řešení:

• Použít synchronizační primitiva – mutexy, atomické operace, semafory apod.
• Nebo použít thread-local kopie a sloučit je až nakonec.

* Uváznutí (deadlock) nastává, když dvě nebo více vláken čeká na zdroj, který drží to druhé – a žádné se nepohne dál.

* Jednoduše řečeno: vlákno A čeká na zámek, který drží vlákno B, a vlákno B čeká na zámek, který drží vlákno A.

Například:

// pseudokód s potenciálním deadlockem
thread1:
lock(A)
lock(B)
 
thread2:
lock(B)
lock(A)

* Aby deadlock mohl nastat, musí být splněny tyto 4 podmínky (tzv. Coffmanovy podmínky):

• Vzájemné vyloučení – zdroje nejsou sdílené (jen jedno vlákno je může mít).
• Zadržení a čekání – vlákno drží jeden zámek a čeká na další.
• Neodnímatelnost – zdroj (zámek) nemůže být násilně odebrán.
• Cyklické čekání – existuje cyklus závislostí mezi vlákny.

* Prevence:

• Dodržovat pevné pořadí zamykání zdrojů.
• Používat timeouty u zámků.
• Využít algoritmy pro deadlock detection a recovery.

Nastává, když dvě vlákna přistupují k různým proměnným, které se ale nachází ve stejné cache line.

* Když jedno vlákno zapíše do své proměnné, CPU invaliduje celou cache line – i když druhé vlákno pracuje na jiné proměnné ve stejné linii. * Pokud se to děje často, dochází k velkému zpomalení, protože cache se neustále synchronizuje mezi jádry.

* Řešení:

• 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.

Nastává, když dvě vlákna přistupují ke stejné proměnné.

* Narozdíl od false sharing je to žádoucí chování, pokud víme, co děláme – ale musí být správně synchronizované. * Typicky jde o sdílené čítače, fronty, stavové proměnné atd.

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ší.

* `pthreads` (POSIX Threads) je standardní rozhraní v jazyku C pro práci s vlákny. * Poskytuje funkce pro:

• vytváření vláken: `pthread_create()`
• synchronizaci vláken:
  • mutexy: `pthread_mutex_lock()`, `pthread_mutex_unlock()`
  • podmínkové proměnné: `pthread_cond_wait()`, `pthread_cond_signal()`
  • 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.

* Od C++11 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í.

• 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.

Výhodou oproti `pthreads` je vyšší přehlednost, typová bezpečnost a integrace s C++ idiomy (např. RAII, STL, lambdy).

* Od C++20 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()`).
• 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.

To znamená, že se snižuje riziko zapomenutého `join()` a tím i potencionálních chyb.

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:

• `std::recursive_mutex`, `std::timed_mutex`, …

Ukázka (ruční zamykání/odemykání):

#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." << std::endl;
        mtx.unlock();
    };
 
    std::thread t1(threadFunc);
    std::thread t2(threadFunc);
 
    t1.join();
    t2.join();
 
    return 0;
}

*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):

#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;
}

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 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.

V praxi jsou tedy `std::atomic` velmi efektivní pro jednoduché sdílené proměnné – například čítače:

#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;
}

* 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.

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.

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:

• jednoduchá správa vláken
• sdílená paměť
• předvídatelné chování a synchronizace

Ukázkový kód:

#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;
}

* Poznámka: OpenMP vytváří vlákna, nikoliv procesy – všechna sdílí paměť. Vlákna jsou obvykle implementována pomocí POSIX/pthreads.

Další možnosti a doplňky modelu:

• `#pragma omp barrier` – ruční synchronizační bod.
• `single`, `master` – sekci vykoná pouze jedno vlákno.
• `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.
• `nowait` – zabrání implicitní bariéře na konci paralelního bloku.
• `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).

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: var)` lze řídit pořadí a závislosti. * `detach`, `priority` – umožňují pokročilou kontrolu provádění.

Příklad:

#pragma omp task depend(out: A) {
  // vypočítáme A
}
 
#pragma omp task depend(in: A) {
  // použijeme A
}

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), funguje i na Windows.
• 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.
• AMD AOCC 4.x – laděno pro AMD Zen, Clang + libomp.
• Cray/ROCm – zaměřeno na GPU/offload (OpenMP target).

* `#pragma omp parallel`

• Vytvoří tým vláken.
• Podporuje: `num_threads`, `if`, `default`, `shared`, `private`, …

* `for` / `do`

• Paralelizace smyčky.
• Možnosti: `schedule(static|dynamic|guided)`, `collapse(n)`, `reduction`, `nowait`.

* `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, zápis, čtení…).

#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á se na všechny tasky
    return 0;
}

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)`).

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é 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.
• 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í.

* 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])`.
• 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[, 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á.

* 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.

* 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 a zůstávají aktivní i pro další úseky programu.

* Každé vlákno má vlastní lokální deque (obousměrnou frontu), do které si vkládá nové úkoly.

* Work-stealing: pokud vlákno nemá co dělat, zkusí si „ukrást“ úkol z cizí fronty.

• Tento přístup pomáhá automaticky vyvažovat zátěž.
• Push/pop na vlastní frontě jsou většinou lock-free; zámky se používají jen při krádeži.

Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu.

* U smyček:

• Volba správného `schedule(…)` plánu.
• 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.

* U tasků:

• Work-stealing pomáhá s dynamickým plánováním.
• 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í.

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í:

• `depend(in: X)` – task potřebuje data `X`.
• `depend(out: X)` – task produkuje data `X`.
• `depend(inout: X)` – task `X` čte i zapisuje.
• Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře.

Ukázkový kód:

#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();

* OpenMP runtime si z těchto závislostí sestaví DAG (acyklický graf). * 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, plánovače, grafy).

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.

quick sort a merge sort

* Proč „rozděl a panuj“?

• *Divide*: vybereme pivot a jedním průchodem rozdělíme pole na část < pivot a část ≥ pivot.
• *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í.

* Paralelizace: po operaci `partition` spustíme levé větvení jako `omp task`, pravé běží ve vlákně dál.

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);
    }
}

* 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: obě rekurze běží jako tasky, po jejich dokončení proběhne `inplace_merge`.

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);
}

násobení matice × vektor, násobení dvou matic, řešení systému lineárních rovnic

* Princip: každý prvek $y_i$ je skalární součin řádku $A_i$ a vektoru $x$.

• *Divide*: rozdělíme po řádcích.
• *Conquer*: každý řádek počítá vlákno nezávisle.
• *Combine*: nepotřebujeme – každý výstupní `y[i]` je unikátní.

* U husté matice: nejlepší přístup po řádcích (row-major). * U řídké: paralelizace přes nenulové řádky (např. CSR formát).

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;
    }
}

* Naivní přístup: každý prvek $c_{ij}$ samostatně – špatná cache-lokalita.

* Blokové (tiling) násobení:

• *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)`.
• *Combine*: není třeba – bloky jsou oddělené.

#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);

* Pro vysoký výkon: používat BLAS knihovny (OpenBLAS, MKL…) se SIMD a tilingem.

* Gaussova eliminace (LU): v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$.

• Paralelizujeme řádky $i = k+1..n-1$.
• Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti.

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];
        }
    }
}

* Iterativní metody (Jacobi, CG, GMRES):

• Lépe paralelizovatelné než Gauss – hlavně `matvec`, vektorové operace, redukce.
• OpenMP poskytuje `reduction(+:)` a `atomic` pro synchronizaci.

* Off-load na GPU (OpenMP 5.x):

• 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í.

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.

Popisují model světa ve kterém DS existuje. rozdělení synchroní a asynchroní popisuje množinu předpokladů, které budeme používat při psaní distribuovaného algoritmu.

• Známe horní hranice
  • maximální zpoždění zprávy
  • maximální čas mezi dvěma kroky procesu
  • maximální drift lokálních hodin
• Algoritmy můžeme psách v fázích/kolech a spolehlivě používat timeouty
• V praxi čistě synchroní sétě skoro neexistují

• Žádné limity – zpráva může bloudit libovolně dlouho, proces může

běžet tak pomalu, jak chce, hodiny se mohou rozejít.

• Timeout tedy nemůže spolehlivě rozlišit „zpomalení“ od „pádu“.
• V tomto modelu je např. prokázáno (FLP), že deterministický konsensus

s možností jediného pádu procesu nelze vyřešit.

• Systém se může chovat asynchronně, ale po nejpozději neznámém čase stabilně do režimu, kdy už limity platí.
• Většina produkčních protokolů (Raft, PBFT …) předpokládá právě tenhle model – jsou robustní vůči výkyvům, ale nakonec se „chytí“.

1. 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
2. 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
3. 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í

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:

1. havárie procesu $p_j$
2. detekce selhání procesu $p_j$ nějakým procesem $p_k$
3. proces $p_k$ rozšiřuje informaci o selhání procesu $p_j$ do ostatních procesů

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

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.

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

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)

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}$

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

1. 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}$
2. Je-li $\mathcal{A}$ odeslání zprávy a $\mathcal{B}$ je přijetí této zprávy, pak $\mathcal{A} \rightarrow \mathcal{B}$
3. 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

1. po každé události která se odehraje v $p_i$ se hodiny $\mathcal{C}_i$ inkrementují o 1
2. každé zprávě $m$ odeslané procesem $p_i$ je přiřazená časová značka $ts(m) = \mathcal{C}_i$
3. kdykoliv proces $p_j$ přijme zprávu $m$, tak:
   1. upraví své lokální hodiny $\mathcal{C}_j$ na $max\{\mathcal{C}_j, ts(m)\}$ a poté
   2. 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ů

ř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

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.

Chamdy-Lamport algoritmus pro distribuovaný globální snapshot

1. (Vytváření snapshotu je distribuované.)
2. Speciální zpráva: ZNAČKA ▪
3. Jeden (libovolný) z procesů iniciuje vytvoření snapshotů.
4. Procesy reagují na příjem zprávy ZNAČKA ▪
5. výsledkem je konzistentní řez

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?
  1. ANO - Vlastnost $\mathcal{V}$ bude ve výpočtu splněna i ve fyzickém okamžiku doběhnutí snapshot algoritmu.
  2. NE - Vlastnost $\mathcal{V}$ nemohla být ve výpočtu splněna ani ve fyzickém okamžiku zahájení snapshot algoritmu.

algoritmy pro vyloučení procesů a jejich vlastnosti

• 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

• 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í

• 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

• 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

• 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í

• 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)

  1. identifikátor kritické sekce, kterou zamyká,
  2. stav: RELEASED, HELD nebo WANTED, a
  3. frontu odložených požadavků.

Na začátku je stav každého zámku každého procesu nastaven na RELEASED. V systému kolují pro každou kritickou sekci dva typy zpráv: REQUEST a OK

1. Pokud chce proces P[i] požádat o vstup do kritické sekce K, zaznamená čas T[i] kdy o zdroj žádá a pošle zprávu REQUEST(K) s tímto časem všem procesům, které do K přistupují. Nastaví stav svého zámku K na WANTED.
2. Zámek K procesu je ve stavu WANTED dokud neobdrží zprávu OK(K) od každého dalšího přistupujícího procesu. Poté se nastaví na HELD.
3. Pokud procesu P[j] přijde zpráva REQUEST(K) od procesu P[i] s časem T[i], tak

   • pokud je zámek K ve stavu HELD, pak zprávu REQUEST(K) zařadí mezi odložené požadavky a neodpoví
   • pokud je ve stavu WANTED a o vstup do kritické sekce žádal v čase T[j] < T[i], případně T[j] = T[i] a j < i, pak zprávu REQUEST(K) zařadí mezi odložené požadavky a neodpoví,
   • jinak pošle zprávu OK(K) procesu P[i].
4. Pokud proces P[i] dokončí práci v kritické sekci K, nastaví stav zámku K na RELEASED, odpoví na všechny zprávy ve frontě zámku a frontu vyprázdní.

• 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

algoritmy pro volbu lídra a jejich vlastnosti

• 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).

• 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í.

• 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ů.