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.

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

Č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

• 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í. Množství ILP se výrazně liší dle typu úlohy – numerické simulace mají ILP bohaté, kryptografie spíše skromné.
• Využití ILP: pipelining (překrytí fází), superskalární/vliw architektury (více jednotek), out-of-order execution (dynamické přeuspořádání).

• Princip: Instrukční cesta se dělí na fáze IF → ID → EX → MEM → WB; během jednoho taktu jsou různé instrukce v různých fázích, takže propustnost roste, ač latence jednotné instrukce zůstává.
• Teoretický zisk: při ideálních podmínkách 1 instrukce / takt (IPC = 1) i na skalárním jádře; skutečný zisk limitují hazardy a branch-stall cykly.
• Superpipelining: > 10 stupňů; kratší fáze dovolují vyšší frekvenci, ale zvyšují penalizaci při flushi (chybná predikce, datové konflikty).
• Hazardy:
  • datové (RAW, WAR, WAW) – řešení *forwarding*, *stall*y, *register renaming*,
  • řídicí (branch) – predikce skoků + BTB,
  • strukturální – duplikace funkčních jednotek.

• Jednoproudová (1-wide) architektura: front-end vydá a back-end vykoná jednu instrukci za takt (IPC ≤ 1). :contentReference[oaicite:13]{index=13}
• Pipelining zde paralelizuje různé fáze různých instrukcí, nikoli jejich současné vykonání.

• N-wide architektura: fetch/decode i back-end mohou spustit až N nezávislých instrukcí v jednom taktu → IPC > 1 (např. 4-wide jádro → max 4 instr/takt). :contentReference[oaicite:14]{index=14}
• Paralelizuje stejné fáze různých instrukcí a kombinuje se s pipeliningem; tím se ILP využívá naplno.

• Statická superskalární
  • Vydává paralelně jen instrukce jdoucí v kódu za sebou; při závislosti nastává stall. Menší řídicí logika, úspornější.
• Dynamická superskalární
  • Out-of-order execution a přejmenování registrů (ROB + Reservation Stations) spouští libovolné připravené instrukce, skryje latenci cache a zvedá IPC.
  • Vyžaduje přesnou predikci skoků a složitější hardwarové řízení; spotřeba i plocha čipu rostou.

• Skalární CPU ⇒ 1 instrukce/takt, architektonicky jednodušší.
• Superskalární CPU ⇒ N instrukcí/takt; statická verze je jednodušší, dynamická (OOO) dosahuje vyššího využití ILP za cenu složitosti.

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

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

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

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

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

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

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

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

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.

souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing)

• souběh (race condition), uváznutí (deadlock): (statnice:bakalar:b4b35osy)

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.

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.

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

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

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.

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

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

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.

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.

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

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

Běžně používané kompilátory a knihovny OpenMP (stav jaro 2025):

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

Ukázka kombinuje `parallel`, `for`, tasky a závislosti:

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

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

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.

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

quick sort a merge sort

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

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

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

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

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

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

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

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)
• 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 od všech ostatních procesů 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ů, pokud je vyšší tak to zahodím
  • 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

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