---
tags: Společný základ
---
# SZ 3. Výkonné počítače a intenzivní výpočty
*Výkonné počítače a intenzivní výpočty: Superskalární, multijádrové a mnohojádrové (GPU, MIC) procesory, MIMD a SIMD paralelismus. Organizace paměti, sdílená a distribuovaná, cache koherence. Optimalizace kódu, optimalizující překladače. Distribuované systémy, topologie síťového propojení. Programování paralelních a distribuovaných systémů.*

Zdroje:
- https://www.fi.muni.cz/~xslanin/szz/PA039-pa039.pdf - nie moje, mala som uložené v PC keď som sa učila na skúšku a už neviem dohľadať autora ¯\\_(ツ)_/¯.
- internety na GPU/MIC
- https://www.fi.muni.cz/~xbarnat/IB109/ - programovanie paralelných. systémov
---
:::danger
**TODO**
- Formátovanie, príp. zamyslenie sa, či ešte dačo nepridať do progr. distribuovaných systémov.
:::

## Intro

Historicky boli superpočítače špeciálne počítače vyrábané na zakázku, dnes sa s klesajúcou cenou HW a zvyšujúcim výkonom PC vo všeobecnosti podobajú na klasické PC, akurát s veľkým množstvom procesorov / RAMky / GPUs. Dnes sa superPC používajú na rozsiahle simulácie a modelovanie (napr. predpoveď počasia). Zároveň majú veľké nároky na kvalitu SW, ktoré musia byť schopné efektívne využiť tisícky procesorov na počítanie 1 úlohy.

## Superskalárne procesory
Vznikli pridaním nových vlastností do RISC procesorov na ich zrýchlenie. V dnešnej dobe sa všetky procesory dajú považovať za superskalárne.
- mali **2 aritmeticko logické (ALU) a 2 floating point (FPU)** jednotky
- podporovali **paralelizmus na instrukční úrovni** vo vnútri procesora (t.j. programátor programuje sekvenčne a inštrukcie, ak sa to dá, sa vykonajú paralelne bez jeho vedomia)
- obsahovali **inštrukciu MADD (multiply-add)**, zvládnu vykonať $x*y+z$ v jednom kroku
- obe FPU jednotky **nemuseli byť ekvivalentné** - často napríklad len jedna zvládala deliť, lebo je to drahá (z pohľadu počtu potrebných tranzistorov) a nie veľmi častá operácia

## multijádrové a mnohojádrové (GPU, MIC) procesory
Multijádrovými procesory se typicky rozumí 2-8 jádrový procesory (CPUs), zatímco monohojádrové (manycore) mají typicky stovky (MIC) nebo tisíce (GPU) procesorů. Multijádrový se zaměřují na rychlé sekvenční výpočty (min latence). Mnohojádrové na rychlé paralelní výpočty (max propustnost).

### GPUs vs. multijádrové procesory
Hlavný rozdiel spočíva v tom, či prioritizujú **latency** (časovú prodlevu) alebo **throughput** (priepustnosť).
- **Latencia** - čas, ktorý treba na dokončenie jednej úlohy
- **Priepustnosť** - počet úloh dokončených za jednotku času

GPUs majú výbornú priepustnosť za cenu horšej latencie. Preto vynikajú pri maticových operáciach (jednoduché operácie na veľkej škále), ale zaostávali by pri komplexných problémoch, ako bežanie operačného systému. Taktiež horšie spracuvávajú kód, ktorý sa veľmi vetví. GPUs = pole SIMD procesorov pracujúce nad spoločnou pamäťou. GPUs sa teda viac hodia na výpočty, ktoré sú obmedzené priepustnosťou, CPUs na výpočty, ktoré sú obmedzené latenciou.

GPUs boli donedávna používané len na grafické úlohy, v poslednom desaťročí sa začínali sústrediť na vedecké výpočty - *High Performance Computation (HPC)*. Tiež priamo súvisia s "Deep learning revolution" v skorých 2010s. Jednak začal vychádzať lepší HW, druhak prišly softwareové zmeny - nVIDIA vydala CUDA framework (2007), ktorý v Cčku dovolil programovať GPUs nielen pre hry, ale pre akékoľvek paralelné výpočty - prvý jasný kandidát boli maticové výpočty.


Pre úplnosť - nVIDIA prišla v 2017 s architektúrou založenou na tzv. Tensor cores (TPU - Tensor processing unit), s ktorou dosahuje až 12x throughput čo s obyčajou CUDA na GPU.

**MIC = Many Integrated Cores** - odpoveď Intelu na GPUs od nVIDIe
MIC je typ architektúry, s ktorým Intel zvyšuje throughput a zlepšuje výkon štandardných multijadrových chipov.
- obsahuje veľa fyzických jadier (ale rádovo menej než GPUs) na jednom čipe
- vytvorené pre účely HPC
- pôvodne mali mať výhodu oproti GPUs tým, že sú generickejšie - hodia sa na akékoľvek výpočty, GPUs sa ale stávajú generickejšie a MIC postupne pridávajú viac jadier, takže rozdiel sa zmazáva

## MIMD a SIMD paralelismus
- **SIMD = Single instruction multiple data** - Odpovedá predstave o vektorovom počítaní - všetky procesory sú synchronizované, vykonávajú rovnaké inštrukcie - nie je vhodné na skalárne operácie. Procesory sú jednoduché, jednoduchší programovací model. Použité v GPUs.
- **MIMD = Multiple instruction multiple data** - Niečo ako cluster so servrami. Jedná sa o plne asynchrónny model so samostatnými procesormi. Viac flexibilné, lebo netreba všetko vyjadrovať ako vektor, ale vyžaduje si zložitejšie programovacie modely (napr. explicitná synchronizácia v kóde). Použité v multijadrových CPUs.
- **SISD** - Single instruction single data - v jeden okamih sa spracováva jedna inštrukcia, ktorá pracuje nad jedným dátovým prúdom - klasický sekv. výpočet
- MISD - nevyskytuje sa

## Organizácia pamäte
Pamät je usporiadaná do riadkov a stĺpcov (= matice), jej adresa má 2 časti (číslo segmentu a offset). Naraz obvykle čítame skupinu súvisiacich bytov.
V súvislosti s pamäťou nás zaujíma: **prístupová doba** (memory access time) a **cyklus pamäte** (určuje ako často sa dajú dáta čítať) - závisia na type (dynamická vs. statická).

- **vyrovnávacia pamäť** (4KB-16MB), organizovaná v riadkoch pevnej dĺžky, typy:
- priamo adresovateľná - rýchla, potenciálne neefektívna
- čiastočne alebo plne asociatívna - zložité obvody, ale veľmi efektívna
- **prekladaná (interleaved) pamäť** - kompenzuje nízku rýchlosť dynamickej RAM rovnomernejším rozložením pamäte do rôznych blokov, umožňuje okamžitý prístup
- logická pamäť sa prekladá na fyzickú pomocou Translation look-aside buffer (TLB), riešime TLB misses

## Sdílená a distribuovaná (pamäť)
- **Zdieľaná pamäť** sa vyskytuje v malých systémoch, je oddelená od procesorov, pripojená zbernicou a so zvyšujúcim počtom procesorov klesá výkon (pamäť je pomalá, kapacita zbernice je pomalá). Predkladanie výpočtu a komunikácia sú zložité (aktívne čakanie).
- **Distribuovaná pamäť** sa vyskytuje v distr. systémoch, kde každý procesor má vlastnú pamäť a iné do nej nevidia. Ak chcú procesory medzi sebou komunikovať, musia dáta zabaliť a odoslať, čo má za následok vysokú cenu komunikácie (žiadosť, zabalenie dát, vytvorenie, odoslanie, prevzatie, rozbalenie). Výhodou je jednoduchšie predkladanie výpočtov - 1 vlákno čaká, iné môžu počítať niečo iné.

## Koherencia cache
### Príčiny výpadkov cache:
1. Compulsory miss - procesor chce dáta, ktoré nie sú v cache
2. Capacity miss - nízka kapacita cache
3. Coherence - v cache je stará kópia dát
4. Conflict - rôzne adresy sú mapované do rovnakého miesta

### Riešenia:
Pomocou tzv. **snoopy cache** (broadcastová vyrovnávacia pamäť) - sleduje komunikáciu po zbernici:
1. Zneplatnenie - dáta vo vyrovnávacej pamäti sú zneplatnené a v prípade opakovaného prístupu sú načítané z hlavnej pamäte
2. aktualizácia (update) - dáta sa hneď aktualizujú (čítajú sa zo zbernice)

Snoopy cache je nepoužiteľná pri veľkých systémoch - všetky CPUs by museli byť pripojené na 1 zbernicu.
Možné riešenia tam:
1. adresárový prístup - pamätá sa, ktoré riadky hl. pamäte majú kópiu vo vyr. pamäti
2. vektor príznakov - drží sa príznak (značiaci či má procesor vlastnú kópi dát) pre každý procesor a každý riadok v pamäti
- problém: takmer všetky hodnoty sú nulové, treba veľa pamäte na réžiu
- riešenia:
- plne mapované adresáre - proc. žiadajú exkluzívny prístup k riadku v pamäti
- obmedzené adresáre - obmedzený počet procesorov, kt. môžu paralelne pristupovať k 1 riadku
- previazané adresáre - info o žiadosti o riadok sa uloží do hl. pamäte
## Optimalizace kódu, optimalizující překladače
- **Optimalizácie kódu**
- odstránenie závislosti na poradí vyhodnotenia inštrukcií, možnosť pridania paralelizmu
- odstránenie mŕtveho kódu - šetrenie cache
- niektoré inštrukcie sú pomalšie ako iné - napr. 2\*k sa prevedie na k+k
- odstraňovanie smetia - zrušenie nadbytočných testov (tautológie), inline funkcie namiesto klasických, reorganizácia podmienených výrazov
- optimalizácia cyklov:
- loop unrolling - zníženie počtu iterácií tak, že v jednej sa toho spočíta toľko, čo predtým vo viacerých
- opt. prístupu k pamäti - prístup k prvkom dvojrozmerného poľa, obrátenie indexov
- **optimalizujúci prekladač** - Prekladač do medzijazyka
- Fáze optimalizácie:
- source to source (napr. z javy do "lepšej" javy)
- preklad do strojového kódu
- optimalizácia behu

Preklad do medzijazyka môže zahŕňať:
- medziprocedurálnu analýzu
- optimalizáciu cyklov
- globálnu optimalizáciu

## Distribuované systémy, topologie síťového propojení. Programování paralelních a distribuovaných systémů.
(tu som úplne nenašla v študíjnych materiáloch pa039 konkrétnu rozpravu ani o jednej veci z týchto, preto to tak nejak pozliepavam z inej literatúry, hlavne: https://cs.qwe.wiki/wiki/Distributed_computing, tak berte s rezervou.)

**Distribuovaný systém (DS):** je systém viacerých komponent nachádzajúcich sa na rôznych strojoch (fyzické servre, kontainery, virt. stroje), ktoré komunikujú a koordinujú operácie tak, aby sa javili ako jednoliaty koherentný systém.
### Výhody DS:
- horizontálna škálovateľnosť (ľahko sa pridajú ďalšie uzly)
- spoľahlivosť (veľa uzlov pracuje spolu - nevadí ak u jedného nastane chyba)
- výkon - DS sú efektívne, pretože sú schopné úlohy deliť na posielať ich podčasti na jednotlivé uzly

### Výzvy DS:
- plánovanie - DS musí určiť ktoré joby kedy a kde pobežia
- odozva (latency) - čím širší systém je, tým je náchylnejší na pomalú odozvu pri komunikácií
- zbieranie metrík / debuggovanie

### Typy DS (architektúra):
- klient-server
- trojvrstvé
- n-tier
- peer-to-peer

### Rozdiel medzi paralelným a distribuovaným systémom:
- v paralelnom systéme majú všetky procesory prístup k zdieľanej pamäti pre výmenu informácií
- v distr. má každý procesor vlastnú pamäť, informácie sa vymieňajú posielaním správ medzi procesormi

### Topologie síťového propojení
TOP:
https://www.cs.iusb.edu/~danav/teach/b424/b424_24_networks.html

Zapájanie procesorov do sietí: Zameriavame sa na 2 vlastnosti:
- **Rozšíriteľnosť** (ideálne chceme aby s počtom procesorov klesala doba spracovania úlohy)
- **zrýchlenie** (zmena rýchlosti výpočtu úlohy na 1 procesore oproti výpočtu na n procesoroch - ideálne chceme, aby sa výpočet n-krát skrátil, ale prakticky to tak nie je, treba doplniť nejakú logiku).
- Amdalov zákon - riešenie sériového problému sa nezrýchli pridaním procesorov

#### Parametre siete:
- počet uzlov
- stupeň uzlu
- počet liniek v sieti
- redundancia siete - koľko hrán treba odstrániť aby sa sieť rozdelila na 2

##### Topológie sietí:
- jednorozmerné prepojovacie siete - pocesory sú jeden za druhým = tzv. korálky, nízka cena, najhoršie vlastnosti
- dvojrozmerné prepojovacie siete - kruh (do max. 8 uzlov), hviezda (dobrý polomer, vysoká záťaž pre uzol v strede), stromy (dobrý polomer, záťaž pre root)
- hyperkocka - viacrozmerná sieť, dobré parametre, vyššia cena
- plné prepojenie siete - každý stroj napojený na každý ďalší, vysoká cena

## Programování paralelních a distribuovaných systémů

Spoločným rysom oboch je, že k výpočtu jednej úlohy sa nepristupuje klasicky sekvenčne, ale snažíme sa ho paralelizovať. Pri paralelných systémoch zvyčajne pracujeme s jedným strojom, ktorého procesorový čas sa snažíme čo najefektívnejšie rozdeliť. Problematickou komponentou je hlavne zdieľaná pamäť, kde sme v situácií, že viaceré vlákna/procesy sa k nej snažia pristupovať/zapisovať. Distribuované systémy naopak pozostávajú z viacerých autonómnych počítačov, ktoré sa použivateľovi majú javiť ako jeden systém - nemajú teda zdieľanú pamäť - počítače spolu komunikujú cez posielanie správ.

### Paralelné programovanie

#### Výzvy paralelných aplikácií (čo treba riešiť):
- identifikovať činnosti, ktoré môžu bežať paralelne a ich závislosti
- mapovať ich do procesov
- zaistiť distribúciu vstupných, výstupných a vnútorných dát
- spravovať súbežný prístup k dátam a zdieľaným prostriedkom
- synchronizovať jednotlivé procesy

#### Návrh paralelných algoritmov
- dekompozícia problému na podproblémy
- typy: rekurzívna (rozdeľuj a panuj), dátová, **prieskumová (napr. prehľadávanie stavového priestoru)**
- definícia grafu závislosti podúloh - určuje poradie vykonania (napr. `v AND x AND (y OR z)`)
- stupeň súbežnosti: maximálny počet úloh, ktoré môžu byť vykonávané súbežne
- kritická cesta: súčet prác je maximálny - čím menej práce, tým väčší potenciál pre paralelizáciu
- definícia grafu komunikácie úloh
- napr. jednosmerná: násobenie matice vektorom
- mapovanie úloh na vlákna/procesy - cieľ: minimalizovať čas bežania úlohy, maximalizovať súbežnosť
- statické, dynamické, naivné: úloha = proces/vlákno
- redukcia réžie interakcie
- zvýšenie dátovej lokality (chceme znížiť objem prenášaných dát)
- redukcia ceny komunikácie v adresovom priestore

#### Problémy paralelných aplikácií:
- prístup do pamäte cez zbernicu je pomalý
- problém koherencie cache
- race condition - nedeterministické správanie paralelných programov
- výsledok závisí na absolútnom poradí vykonaných inštrukcií zúčastnených procesov/vlákien
- uviaznutie (deadlock) - môže nastať pokiaľ majú vlákna inkrementálne požiadavky na unikátne zdieľané zdroje = znamená nemožnosť pokračovania vo výpočte
- hladovanie (= starnutie) (livelock) - aspoň jedno vlákno nie je schopné vzhľadom k paralelnému súbehu s iným vláknom pokročiť vo výpočte

#### Prostriedky:
- pre paralelnú úlohu je potrebná **medzi-procesová komunikácia (IPC)** - riadia sa zdieľané pamäťové segmenty, sockety, pipes
- **vlákna** - existujú v rámci 1 procesu, zdieľajú výpočetné prostriedky, komunikácia cez zdieľané dátové štruktúry
- každé vlákno ma privátne: registre, zásobník, frontu signálov
- rodičovské vlákno môže vytvárať child vlákna
- cache - menšia, ale rýchlejšia pamäť na pomalej dátovej ceste
- pre efektívne použitie treba voliť:
- prístup v malom časovom intervale
- prístup k dátam uloženým vedľa seba
- zarovnaná alokácia pamäte
- javy:
- [false sharing](https://en.wikipedia.org/wiki/False_sharing)
- nestále premenné - prekladače nevynucujú ukladanie každej vypočítanej hodnoty do pamäte - modifikácia zdieľanej premennej v jednom vlákne sa môže v druhem prejaviť až neskôr (predchádza sa v C kľúčovým slovom **volatile**)
- HW primitíva pre synchronizáciu
- atomické inštrukcie: test-and-set, compare-and-swap, XCHG

#### Prístup k zdieľaným premenným
- musí sa robiť kontrolovane: zamykanie kritickej sekcie
- zdieľaná **bitová premenná**, ktorej hodnota indikuje prítomnosť procesu/vlákna v krit. sekcií
- algoritmy/techniky zamykania kritickej sekcie:
- Petersonov - pre vzájomné vylúčenie, nespôsobuje hladovanie ani uviaznutie
- uspávanie - procesy/vlákna sa po neúspechu vstúpenia do krit. sekcie uspia, zobudia sa po náhodnom timeoute
- spinlock - vlákna opätovane skúšajú vstúpiť do krit. sekcie
- synchronizačné primitíva:
- semafóry, mutexy, monitory
- lock-free programovanie = programovanie viacvláknových aplikácií bez použitia zamykania, či iných synchronizačných mechanizmov
- API: CAS, WRRM Map, MCAS

### Distribuované programovanie
= large-scale multiprocessing, stovky a viac procesorov, distribuovaná pamäť
- predávanie správ: vlastná pamäť u každého procesu, vysoká cena komunikácie, môžme prekladať výpočty a komunikáciu

#### Prístup k pamäti:
- Non-uniform memory access (NUMA)
- každej logickej adrese odpovedá jedna fyzická
- Cache-only memory access COMA
- Distributed shared-memory (DSM)
- lokálna pamäť každého uzlu, "fikcia" jednej rozsiahlej pamäte
- využíva princíp virtuálnej pamäte