Table of Contents

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

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

Vektorové instrukce

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

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:

Instruction-Level Parallelism (ILP)

Pipelining

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

Skalární vs. superskalární procesory

Skalární procesor

Superskalární procesor

Podtypy superskalární architektury

Shrnutí rozdílu

GPGPU

Architektura a omezení

Výpočetní výkon v praxi

* Threadripper 3990X + RTX 4090:

Programovací modely

Typické úlohy

Výhody

Nevýhody

Shrnutí

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.

Vlákna a procesy

Hierarchie cache pamětí

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

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.

2. Komplikace v paralelním programování

Když programujeme paralelně – tedy více věcí běží najednou – můžeme narazit na různé složitosti, které se u sekvenčních (jednovláknových) programů vůbec neřeší. Typickými komplikacemi jsou souběh (když dvě vlákna zasahují do stejných dat zároveň), uváznutí (když se navzájem blokují), nebo falešné sdílení (když si vlákna “lezou do cache”, i když pracují na různých datech). V téhle kapitole se na tyhle problémy podíváme a vysvětlíme si, jak a proč k nim dochází.

Race Condition (souběh)

Například: 

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

Deadlock (uváznutí)

Například: 

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

False Sharing

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

True Sharing (není komplikace)

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

3. Podpora paralelního programování v C a C++

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

POSIX vlákna (pthreads)

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)

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

std::jthread (C++20)

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

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

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

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

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.

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

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

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

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.

Příklad: 

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

Různé implementace OpenMP specifikace

OpenMP je pouze specifikace – jednotlivé kompilátory ji implementují v různé míře.

Přehled nejznámějších implementací (stav 2025):*

Přehled hlavních direktiv OpenMP

`#pragma omp parallel`

`for` / `do`

`sections` / `section`

`task`

`barrier`

`critical [(name)]`

`atomic`

Příklad zapojení všeho dohromady

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

5. Techniky dekompozice programu

Paralelní programy často potřebují být rozděleny na menší části – a to nejen podle funkcí, ale hlavně podle práce, kterou je třeba vykonat. Tato kapitola se věnuje technikám, jak takovou práci rozdělit mezi vlákna nebo úlohy (tasky), a jak přitom řešit problémy jako nevyvážená zátěž nebo závislosti mezi úlohami. Pochopení těchto principů ti pomůže psát efektivnější a škálovatelnější paralelní kód.

Statické × dynamické rozdělení práce

Thread-pool a fronta úkolů (work-stealing)

Balancování zátěže

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

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

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

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

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.

Řazení

quick sort a merge sort

Quick sort

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

Merge sort

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

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)

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

Paralelní násobení dvou matic

#pragma omp parallel for collapse(2) schedule(dynamic)
for (int bi = 0; bi < N; bi += BS)
  for (int bj = 0; bj < N; bj += BS)
    for (int bk = 0; bk < N; bk += BS)
      multiply_block(A, B, C, bi, bj, bk, BS);

Paralelní řešení systému lineárních rovnic (Gaussova eliminace)

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

Distribuované výpočty/systémy

1. Úvod do distribuovaných systémů (DS)

Distribuované systémy (DS) jsou o tom, jak spolupracují nezávislé výpočetní jednotky, které spolu nesdílejí paměť ani hodiny, ale komunikují pomocí zpráv. Jsou všude kolem nás – od cloudových služeb po blockchain nebo velké paralelní výpočty. Tato kapitola představuje základní charakteristiky DS, problematiku času a přehled typických typů selhání, se kterými musí každý návrh systému počítat.

*Distribuovaný systém je*:

Kvůli těmto vlastnostem je velmi těžké se v systému spolehlivě orientovat v čase – nemůžeme dát pevný limit na doručení zprávy nebo délku výpočtu.

Asynchronní × Synchronní DS

Tyto modely popisují „jaký svět“ předpokládáme při návrhu distribuovaného algoritmu – tedy jaké vlastnosti sítí, hodin a chování procesů budeme brát jako dané.

Synchronní model

Asynchronní model

Částečně synchronní model

Typy selhání v distribuovaných systémech

V DS musíme počítat s tím, že něco selže – a často i nepozorovaně. Rozlišujeme:

Předpoklady na komunikační kanál

Distribuované algoritmy často předpokládají vlastnosti komunikační vrstvy – obvykle se uvažuje tzv. „ideální, ale pomalá“ síť:

Tato vlastnosti se často simulují vyšší vrstvou (např. TCP), ale ne vždy – a je třeba s tím počítat při návrhu protokolu.

2. Detekce selhání v DS

V distribuovaných systémech je běžné, že některé procesy selžou – a aby systém mohl dál správně fungovat, ostatní uzly se to musí nějak včas a spolehlivě dozvědět. K tomu slouží tzv. detektory selhání, které monitorují ostatní uzly (např. pomocí heartbeat zpráv) a označují ty, které nereagují, jako havarované.

Jenže v distribuovaném prostředí nemáme jistotu, jestli uzel selhal, nebo je jen dočasně pomalý (např. síťová prodleva) – a proto je detekce selhání zásadně nejistá. Tato kapitola rozebírá vlastnosti detektorů selhání, různé typy heartbeat protokolů a praktický algoritmus SWIM.

Vlastnosti detektorů selhání

Nelze zaručit obě vlastnosti zároveň (dle FLP výsledku) – proto většina systémů upřednostňuje úplnost, i když občas dojde k mylné detekci.

Jinými slovy: lepší je omylem někoho považovat za mrtvého, než si nevšimnout, že skutečně spadl.

Průběh detekce

  1. Proces $p_j$ selže.
  2. Jiný proces $p_k$ jeho selhání zjistí (např. nepřišel heartbeat).
  3. Proces $p_k$ šíří informaci o selhání $p_j$ dalším uzlům – podle typu protokolu.

Typy detekčních protokolů

Centralizovaný heartbeat

Vlastnosti:

Kruhový heartbeat

Vlastnosti:

All-to-all heartbeat

Každý uzel periodicky odesílá heartbeat všem ostatním.

Vlastnosti:

SWIM protokol

Scalable Weakly-consistent Infection-style Membership

Moderní přístup k detekci, který škáluje a je adaptivní.

Každý proces $p_i$ periodicky:

  1. Posílá `ping` náhodnému uzlu $p_j$ a čeká na `ack`.
  2. Pokud žádná odpověď nepřijde, požádá $\mathcal{K}$ jiných uzlů, aby se zeptaly místo něj (`ping_req`).
  3. Tyto uzly pingnou $p_j$, a pokud odpověď dostanou, pošlou ji zpět $p_i` jako `ping_ack`.
  4. Pokud nikdo z $\mathcal{K}$ nedostane odpověď → $p_j$ je označen za mrtvého.

Vlastnosti:

3. Čas a kauzalita v DS

V běžném programu máme přesné hodiny, které říkají, kdy se co stalo. V distribuovaném systému ale žádné „společné“ hodiny nemáme – každý uzel má své vlastní a běží jinak rychle. Proto je v DS mnohem důležitější pořadí a závislosti událostí než konkrétní čas. V této kapitole si vysvětlíme, jak fungují fyzické a logické hodiny, co znamená synchronizace a jak se sleduje kauzalita mezi událostmi.

Problémy s časem v DS

Synchronizace hodin

Synchronizace může být:

Externí synchronizace

Interní synchronizace

Praktické algoritmy pro synchronizaci

Cristianův algoritmus

$\mathcal{C}_i := t + \frac{\mathcal{T}_{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$

Očekávaná chyba synchronizace je: $\leq \frac{\mathcal{T}_{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$

Lokální čas lze zvyšovat okamžitě, ale nelze ho vracet zpět – místo toho se mění rychlost přibývání.

NTP

$o = \frac{(t_1^{r} - t_2^{r} + t_2^{s} - t_1^{s})}{2}$

Logické hodiny a kauzalita

Logické hodiny nejsou o „skutečném čase“, ale o pořadí událostí. Nepotřebují žádnou synchronizaci – pouze konzistentní značkování událostí podle „co mohlo ovlivnit co“.

Kauzální vztah – relace „stalo se před“ (→)

Událost $\mathcal{A}$ mohla ovlivnit událost $\mathcal{B}$, pokud:

Kauzální nezávislost

Lamportovy logické hodiny

Každý proces si udržuje číselnou hodnotu svých hodin:

Důležité:

⇒ Lamportovy hodiny respektují kauzalitu, ale neumí ji zpětně ověřit.

Vektorové hodiny

Abychom přesně zachytili kauzalitu, každý proces si udržuje vektor hodin, kde každý prvek reprezentuje „jaký čas vím o ostatních“:

Událost $e_1$ předchází $e_2$ ve vektorovém čase, pokud: $$ V(e_1)[k] \leq V(e_2)[k] \ \forall k \text{ a alespoň jedna nerovnost je ostrá} $$

To už umí odhalit kauzální závislost i nezávislost.

4. Globální stav v DS a jeho výpočet

V distribuovaném systému neexistuje globální hodina ani centrální pohled na „okamžitý stav celého systému“. Přesto někdy potřebujeme získat konzistentní snímek stavu všech procesů a kanálů – třeba pro detekci uváznutí, garbage collection nebo checkpointing. Tato kapitola vysvětluje, co znamená řez distribuovaného výpočtu, jak funguje Chandy-Lamportův algoritmus pro získání globálního snapshotu a co jsou stabilní vlastnosti systému.

Co je globální stav a snapshot

Globální stav je:

Globální snapshot je záznam takového stavu, který může být analyzován mimo běžící systém (např. logicky, offline).

Použití:

Řez distribuovaného výpočtu

Řez (cut) definuje:

Události, které nastanou před řezem, do něj patří; zbytek je mimo.

Konzistentní řez

Řez $\mathcal{Ř}$ je konzistentní, pokud: $$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř} $$

Jinými slovy: jestliže obsahuje důsledek, musí obsahovat i příčinu.

Konzistentní řez je tedy logický okamžik, který by mohl být zpozorován „zvenčí“.

Konzistentní globální snapshot odpovídá konzistentnímu řezu.

Algoritmus pro distribuovaný snapshot (Chandy-Lamport)

Chandy-Lamport algoritmus umožňuje distribuovaným procesům získat konzistentní snapshot, aniž by existovalo globální hodiny.

Základní princip:

Průběh:

  1. Jeden proces iniciuje snapshot – uloží si stav a pošle `ZNAČKA ▪` všem sousedům.
  2. Když jiný proces obdrží `ZNAČKA ▪` poprvé:
    • uloží svůj stav,
    • pošle `ZNAČKA ▪` dál,
    • vše, co do té doby přišlo na kanálu, patří do snapshotu.
  3. 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.

ilustrace algoritmu slide 15-21

Stabilní vlastnosti

Stabilní vlastnost je taková, že když začne platit, zůstává platná navždy.

Nestabilní vlastnost:

Kontrola stabilní vlastnosti pomocí snapshotu

Chandy-Lamport algoritmus lze využít pro detekci stabilních vlastností:

Chceme vědět, jestli nějaká stabilní vlastnost $\mathcal{V}$ v systému nastala.

Snapshot tedy vytváří spolehlivý časový úsek, během kterého můžeme ověřit trvalost vybraných vlastností.

Vzájemné vyloučení procesů v DS

algoritmy pro vyloučení procesů a jejich vlastnosti

V distribuovaných systémech nemáme sdílenou paměť ani centrální plánovač. Pokud chceme zajistit, že do tzv. kritické sekce vstupuje vždy jen jeden proces, potřebujeme speciální algoritmy pro vzájemné vyloučení. Tato kapitola popisuje základní problém, požadavky na jeho řešení a několik klíčových algoritmů včetně jejich výhod a nevýhod.

Problém vzájemného vyloučení

Požadavky na algoritmus pro vyloučení procesů

Analýza výkonnosti algoritmů

Centralizovaný algoritmus

Vlastnosti:

Kruhový algoritmus

Vlastnosti:

Ricart-Agrawalův algoritmus

// schéma odpovědi na REQUEST(K)
if (stav == HELD || (stav == WANTED && (můj_čas < jejich_čas || (můj_čas == jejich_čas && můj_id < jejich_id)))) {
    odlož požadavek;
} else {
    pošli OK;
}

Vlastnosti:

Volba lídra v DS

algoritmy pro volbu lídra a jejich vlastnosti

V distribuovaném systému často potřebujeme zvolit jeden proces, který bude působit jako koordinátor – například pro synchronizaci, správu zámků nebo organizaci úkolů. Jelikož uzly mohou selhávat, musí volba probíhat robustně a bez centrální autority.

Cílem algoritmu pro volbu lídra je zajistit, aby:

Předpokládáme:

Kruhový algoritmus (Ring)

Vlastnosti:

Algoritmus Bully

  1. Pošle `ELECTION` všem procesům s vyšším ID
  2. Pokud žádný neodpoví → $P_i$ se prohlásí lídrem
  3. Pošle `COORDINATOR(i)` všem nižším ID
  4. Pokud někdo odpoví `OK` → $P_i$ čeká na `COORDINATOR(k)` od silnějšího
  5. Pokud neobdrží oznámení včas, znovu zahájí volby

Zprávy:

Vlastnosti: