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

Modely a architektury paralelních a distribuovaných systémů

Paralelní programování

1 program, vícero úloh pro vyřešení úlohy, sdílení paměti a synchronizace
Chceme zrychlit řešení problému.

Distribuované systémy

Vícero programů, výpočetní procesy, každý svou paměť.
Chceme mít robustnější systém.

Prostředky pro implementaci paralelních a distribuovaných systémů

Paralelizace na úrovni instrukci (Instruction Level Paralelization - ILP)

SIMD - single instruction multiple data
  • jedna řídící jednotka vícero ALU (arithmetic logical unit) jednotek
  • datový paralelismus
  • vektorové procesory, GPU
MISD - multiple instruction single data
MIMD - multiple instruction multiple data
  • více jádrové procesory
  • různé jádra různé instrukce

Vlákna

  • create
  • join

Synchronizace

Mutexy

  • Mutex (lock, unlock)
  • Semafor (post, wait)
  • Monitor (účastníci mohou mezi sebou komunikovat)
  • Podmínková proměnná (notify, notify all, wait)

OpenMP

  • omp parallel for
  • pragma task - await all and stuff
  • reduction (+:a) převede normální sčítání na vektorové

Compare and swap

Využití u atomických proměnných. Atomické proměnné zajišťují, že operaci nad nimi provedené jsou atomické (princip makové buchty). Při použití compare_strong_Exchange - kromě hodnoty, kterou chceme vložit, ji posíláme i s hodnotou o které se myslíme že v proměnné je. Pokud máme pravdu tak se to normálně vloží. Pokud se nám to ale pod rukama změní, tak operace skončí s návratovou hodnotou false, a do proměnné s expected hodnotou se přiřadí aktuální hodnota, která nám tam proklouzla z jiného vlákna.

Rozdělené práce

Fixní a statické: ne nutně při kompilaci ale jakmile jednou vlákno dostane přiřazenou úlohu už mu zůstane
Dynamické: program rozděluje úlohy dynamicky podle vytíženosti jednotlivých vláken
  • jedna fronta úkolů z které vlákna berou → dobré pro velké úlohy, při vícero malých úkolech to bude bottleneck
  • každé vlákno se svou frontou, jakmile nemá tasky tak bere od dalších vláken, tím se balancuje
Jednotlivé úlohy na sobě mohou záviset, v openMP to pak lze řešit pomocí
#pragmaomptasksdepend([in/out/inout]:variables)

Základní paralelní a distribuované algoritmy