IB109 Návrh a implementace paralelních systémů

písemný test (> 60 %)

"Běda vám, jestli přijdete příště!"

"Tam se prostě svlíknete a všichni ostatní na vás vidí. Což ještě není tak hrozný, když na vás vidí, ale oni na vás můžou šahat."

"Podle make potom v Brně začali říkat 'maké'."

"Děti na vás!"

Důvody vývoje paralelních systémů

výkon -- procesory mají fyzické hranice (nemohou se zrychlovat donekonečna), při zvýšení počtu paměťových modulů roste propustnost
provedlitelnost -- potřebujeme to včas a máme toho hodně, tak to musíme udělat paralelně
bezpečnost -- duplikujeme části systému pro případ napadení, havárie nebo ztráty
cena -- levnější údržba při oddělení jednotlivých procesů

Paralelní výpočty

multitasking -- plánovací jednotka je proces

na jednom jádru -- aplikace se střídají
na více jádrech -- každá aplikace má své jádro

multithreading -- plánovací jednotka je vlákno, vlákna jedné aplikace mohou běžet na více jádrech

Flynnova klasifikace

Single Instruction Single Data -- sekvenční přístup
Single Instruction Multiple Data
Multiple Instruction Multiple Data -- vícejádrové procesory
Multiple Instruction Single Data -- nevyskytuje se

Distribuovaný systém

systém, který je specifikován po částech
jednotlivé procesy či vlákna jsou autonomní
emergentní jev -- chování systému jako celku (mravenci s cukrem)
systém se synchronizuje a komunikuje
problémy distribuovaného systému: nedeterministické chování, deadlock, livelock, stárnutí, přetečení bufferů (hromadění dat), ztráta výkonu (aktivní čekání)

Náročnost vývoje paralelních systémů

specifikace souběžných úkolů
paralelní algoritmy
nedostačující vývojová prostředí
nedeterminismus při simulaci
rychlý vývoj, zastarání použitých technologií

HPC (High Performance Computing) -- výpočty na vysoce paralelních platformách

Programování v prostředí se sdílenou pamětí

více procesorů, více jádrové procesory nebo procesory, které umí SMT, přistupují k jedné paměti více procesy/vlákny
hrozí přeuspořádání instrukcí nebo odložení zápsů do paměti

SMT (Simultální MultiThreading)

procesor pracuje na dvou věcech naráz (když je v první prodleva kvůli paměti, počítá druhou)
vyžaduje duplikaci registrů (nebo jiných částí procesoru)
vlákna sdílí cache
př. Inter Pentium 4 (Hyper-Threading Technology)

Proces vs. vlákno

Proces

= jednotka výpočtu, ideálně je izolovaný
vytvoření procesu je dražší
ID procesu a vlastníka, proměnné prostředí, pracovní adresář, kód, registry, zásobník, halda, orevřené soubory a sdílené knihovny, reakce na signály, kanály IPC

Vlákno

= potomek procesu, není izolováno (v rámci procesu)
vytvoření vlákna je levnější
v rámci procesu nemá soukromí, sdílejí globální proměnné
má vlastní zásobník, registry a frontu signálů

Efektivní využití cache

menší a rychlejší paměť
koherence -- existuje právě jedna platná hodnota asociovaná s daným paměťovým místem

cache line -- blok paměti natažený z operační paměti do cache

(cache) hit ratio -- úspěšnost obsloužení požadavků daty z cache

vylití cache -- zahození části obsahu kvůli uvolnění místa

výprask -- mám virtuální stránky na disku a pak dlouho trvá, když se stránky přesouvají

memalign -- zarovnaná alokace paměti

false sharing -- problém snižující výkonnost, když data sdílí cache paměť a procesoru, který s daty pracuje, je cache s daty vylita

nestálé proměnné -- každý mezivýpočet nemusí být uložen do paměti, ale může zůstat v registru, kde na něj ostatní vlákna nevidí; použujeme-li klíčové slovo volatile, uložení do paměti se vynutí

nemůžeme se na to spoléhat, může dojít k proložení vláken, zápisy do cache paměti jsou shlukovány a odkládány

paměťová bariéra -- slouží k synchronizaci na úrovni HW, instrukce procesoru mfence, způsobí serializace instrukcí load a store, které se vyskytují před bariérou

Rizika

race condition -- výsledek programu záleží na proložení instrukcí jednotlivých vláken, projevuje se nedeterministickým výstupem, problematické hlavně u neatomických operací

relativní rychlost výpočtu -- rychlost výpočtu jednotlivých vláken je relativní

deadlock -- inkremetální požadavky, zámky jsou unikátní a sdílené, zámky jsou alokovány v daném pořadí

livelock -- vlákno není schopno pokročit dál, protože mu v tom brání ostatní vlákna (není naplněna podmínka apod.)

thread-safe -- bezpečný kód, který lze provést pomocí více vláken bez dodatečné komunikace/synchronizace

re-entrantní procedura -- procedura, která je schopna běžet naráz ve více kopiích (např. když dojde k přerušení)

serializace globálních proměnných -- seřazení do řady požadavků na změny

kritická sekce -- část kódu, kde typicky přistupujeme ke sdíleným zdrojům (např. globálním proměnným), nesmí být proložena instrukcemi jiného vlákna

není-li zdroj aktuálně dostupný, mohou nastat tyto varianty:
- spinlock -- (aktivní čekání) "Už tam budem?"
- uspání -- zkusí to za nějakou dobu nebo je probudí jiné vlákno
pokud je zdroj odemčen, přístup získá náhodné čekající vlákno
rizika zamykání: uváznutí, stárnutí, snížení výkonnosti
Petersonův algoritmus -- spravedlivý algoritmus, který nezpůsobuje strárnutí ani uváznutí

Nebezpečné postupy

nekontrolovaný přístup ke globálním proměnným na haldě
alokace a dealokace např. souborů
přístup skrz ukazatele

POSIX Threads

standardní rozhraní pro vlákna
#include <pthread.h>
proces má 1 hlavní vlákno, které rekurzivně vytváří další vlákna

Posix Thread API - funkcionalita

správa vláken
- vytvoření nového vlákna - funkce pthread_create, při úspěchu vrací 0

int pthread_create(*vytvorene_vlakno,
               *atributy,
               *fuknce_vlakna,
               *parametry_funkce_vlakna)

ukončení vlákna
- void pthread_exit(*navratova_hodnota) -- vlákno se samo ukončí, před ukončením musíme uvolnit prostředky
- int pthread_cancel(*vlakno) --vlákno je zrušeno jiným vláknem, vrací 0, když vlákno stále existuje, uvolní všechny prostředky
spojování vláken
- int pthread_join(vlakno, *navratova_hodnota) -- bude se čekat na dokončení vlákna v parmetru
- vlákna dělíme na spojitelná a nespojitelná (je dobré to nastavit)
nastavení, zjištění stavu
vzájemné vyloučení (mutex)
podmínkové proměnné -- komunikace a synchronizace vláken

Vzájemné vyloučení (Mutual Exlusion, Mutex)

zámek
typy -- nastavujeme funkcí pthread mutexattr_settype_np
- normální mutex
- rekurzivní mutex -- může být zamknutý opakovaně, následně musí být stejněkrát odemknut
- normální mutex s kontrolou chyby -- ohlásí chybu při pokusu o druhé zamčení

int pthread_mutex_init(*mutex, *atributy)

int pthread_mutex_lock(*mutex)

int pthread_mutex_unlock(*mutex)

int pthread mutex trylock (*mutex) - zkusí zamčít, pokud se to nepovede, nezařazuje proces do fronty čekajících, pouze vrátí EBUSY, využítí při aktiviním čekání

Podmínkové proměnné v POSIX Threads

aktivní čekání nebo uspání, k následnému probuzení při určité události se využívají podmínkové proměnné
vyžaduje použití mutexu
svážeme mutex s podmínkovou proměnnou, která po uvolnění mutexu vzudí buď jedno vlákno, nebo všechna čekající
uspané vlákno se probudí buď signálem od podmínkové proměnné nebo po vypršení časového limitu

int pthread_cond_init (*podm_promenna, *atributy) -- inicializace podmínkové proměnné

int pthread_cond_destroy(*podm_promenna) -- zničení podmínkové proměnné

int pthread cond wait (*podm_promenna, *mutex) -- mutex je zamčený volajícím vláknem, funkce uvolní mutex a zablokuje vlákno pomocí podmínkové proměnné podm_promenna

int pthread cond signal (*podm_promenna) -- signalizuje probuzení uspaného vlákna nad podmínkou podm_promenna

int pthread cond broadcast (*podm_promenna) -- signalizuje probuzení všem čekajícím vláknům

int pthread cond timedwait (*podm_promenna, *mutex, *cas) -- probuzení po uplynutí času cas, vrací chybu

TSD (Thread Specific Data)

globální proměnné s různými hodnotami pro různá vlákna
implementace pomocí pole nebo jako slovník klíč:hodnota (POSIX - vlákno má klíč pthread_key_create)

WRRM (Write-Rarely-Read-Many)

chceme, aby čtení mohlo probíhat souběžně
zapisovatel má přednost, i když čeká
zapisuje se sériově, čte se paralelně
zjištění kurzu v bance

Nástroje sloužící k synchronizaci

bariéra -- synchronizační primitivum, podmíněné čekání, než doběhnou ostatní vlákna, implementace pomocí mutexů nebo podmínkové proměnné a počítadla

semafor -- lze použít pro synchronizaci procesů (nebo vláken), může být zapnut a vypnut různými vlákny v rámci jednoho procesu (u mutexů to nejde)

monitor -- označuje kritickou sekci, součást programovacího jazyka vyšší úrovně, sdružuje data a procesy, ostantí procesy mají přístup k monitoru, nikoli přímo k jeho datům

Vlákna v MS Windows

synchronizační prostředky fungují i mezi procesy
jeden typ pro všechny entity HANDLE
CreateThread, ThreadExit

Lock-Free programování

implementace paralelních aplikací bez použití mutexů nebo jiných makro-synchronizačních mechanizmů
výhody: nemůže nastat uváznutí či stárnutí, rychlejší
nevýhody: náročnější na implementaci
většinou jedna velký atomická instrukce

waitfree procedura -- nedochází k čekání

lockfree procedura -- alespoň 1 vlákno dokončí činnost, nenastane deadlock

CAS (Compare and Swap/Set)

atomická instrukce procesoru
pokud je na adrese očekávaná hodnota, nahradí se za ni nová, vrací True nebo False podle úspěchu

ABA problém

mezi kontrolou a CAS může ještě někdo změnit očekávanou hodnotu tam a zpět
řešení: přidáme časový údaj

WRRM Mapa

příklad s kurzem měny
implementujeme s použitím CAS
při čtení se nic nezamyká
při zápisu se vytvoří kopie, v té se změní potřebná data a následně se atomicky zamění (CAS) za data původní (pomocí ukazatele)
lockfree, ale ne waitfree (když upravují dva naráz, musí čekat)
dealokace mapy: držíme si počet vláken, které pracují s daným ukazatelem

Modifikace WRRM mapy

Procedura Update -- provádí změny, pokud žádné jiné vlákno ukazatel nepoužívá
Procedura Lookup -- zvýší čítač, přistoupí ke struktuře, ukončí práci, sníží čítač, podmíněně dealokuje

CAS2

prevede CAS na 2 slova paměti (musí být vedle sebe)
-> WRRMBNTM (Write Rarely Read Many, But Not To Many

Lock-Free Garbage Collector

hazardní ukazatel -- nelze dealokovat, někdo jiný k němu přistupuje

udžuji si seznam hazardních ukazatelů a dealokuji jen ty ukazatele, které v něm nejsou
občas seznam projdu a dealokuji ty, které již nejsou hazardní
seznam je globální, tedy musím ošetřit paralelní přístupy
metoda Acquire() -- přidání ukazatele do seznamu
metoda Release() -- zneplatnění objektu
metoda Retire() -- odloží ukazatel do seznamu
metoda Scan() -- hledá v setříděné kopii seznamu ukazatelů, jestli se daný ukazatel ještě někde používá, nepoužíváné dealokuje

Další možnosti lockfree programování

MCAS (Multiple CASS) -- libovolná velikost struktury
Transakční paměť
Load-Link/Store-Conditional -- jak CAS na jiných procesorech, instrukce LL a SC

OpenMP, TBB, C++11

POSIX Threads a Lock free přístup jsou na příliž nízké úrovni, chceme něco na úrovni programovacího jazyka

OpenMP

co má být provedeno paralelně nikoli jak
značky pro překlad se píšou do kódu ("tuto funkci teď proveď paralelně) (!)
překladač si určuje vhodný počet vláken a celý zbytek implementace
zbytek kódu běží sekvenčně
paralelní bloky lze i zanořovat
direktivy:

`#pragma omp parallel`

následujcí blok {} se provede paralelně
podporuje i podmíněné spuštění

Datová lokalita

private -- z originálu se vytvoří lokální proměnné
firstprivate -- private + inicializace na hodnotu originálu
shared -- proměnná se sdílí a přístup k ní je serializován
default shared/none -- vše sdíleno / uvedeno jako shared nebo private
reduction -- kombinace uvedených proměnných s pomocí daného operátoru

`#pragma omp for`

iterace cyklu budou provedeny paralelně
private, firstprivate, reduction
lastprivate -- výsledek se uloží do proměnné, která bude dostupná i po skončení cyklu
ordered -- kód proběhne ve stejné pořadí, jako by běžel sekvenčně
nowait -- nemusí čekat, až doběhnou ostatní vlákna, nemusí se synchronizovat
schedule
- static -- rovnoměrné rozdělení
- dynamic -- když množství práce jednotlivých instancí není konstantní a některé z vláken by mohlo skončit dřív
- guided -- blok iterací = (nezpracovaných iterací / počet vláken)
- runtime -- určení plánování až za běhu

`#pragma omp sections`

v bloku sections vyznačíme jednotlivé bloky section, ty pak mohou být provedeny paralelně

`#pragma omp barrier`

místo, kam musí dojít všechna vlákna
musí být v části kódu, která se vždy provede, aby nebyla náhodou při překladu odstraněna

`#pragma omp single`

následujcí sekce je prováděna právě jedním vláknem (je jedno kterým)

`#pragma omp master`

stejné jako single, ale sekci provádí hlavní vlákno)

`#pragma omp critical`

označení kritické sekce

`#pragma omp atomic`

`#pragma omp flush`

zkopírování registr -> paměť -> registr

`#pragma omp threadprivate`

přetrvávající globální proměnné
přežijí i zánik vlákna

`#pragma omp copyin`

stejné jako treadprivate, pouze s inicializací na původní hodnotu
void omp set num threads (int num threads) -- nastavení počtu vláken
int omp get num threads () -- zjištění počtu vláken
další funkce pro: maximální počet vláken, identifikační kód vlákna, počet procesů, identifikace paralelního bloku, kontrolu vytváření vláken, mutexy
proměnné prostředí: počet vláken, povoleno dynamické měnění počtu vláken, povolen vnořený paralelismus, nastavení mapování iterací cyklu

Intel's Thread Building Blocks (TBB)

C++ knihovna, která poskytuje šablony (např. paralelní for)
založeno na principu generic programming (specializujeme připravené konstrukce, objekty a algoritmy)
nabízí např. šablony pro: definice vlastních paralelních datových struktur, zamykání přístupů do kritické sekce, paralelizaci iterací cyklu,...

Paralelní for

datová paralelizace
blok kódu k provedení
rozsah indexů -- tato část se (rekurzivně) rozdělí mezi jednotlivá vlákna

Paralelní reduce, vector, queue, hash_map

C++11

revoluce
paralelní programování součástí jazyka
problém s výjimkami: jestliže nastane výjimka a vynořím se aniž bych odemčela mutex, který je až někde dál v kódu
řešení: mutex se zamče vytvořením instance mutex třídy, odemče se destruktorem mutexu, ten se spustí při vynoření z výjimky (princip RAII)

Principy návrhu paralelních algoritmů

dekompozice -> mapování -> implementace

Co jde paralelizovat?
Namapování do vláken.
Zajištění vstupů a výstupů.
Ošetření souběžného přístupu.
Zajištění synchronizace.

graf závislostí -- acyklický orientovaný graf

granularita -- počet úloh, na který lze úkol dekomponovat

fine-grained
coarse-grained

stupeň souběžnosti -- maximální počet podúloh, které lze spustit souběžně (limitováno granularitou)

Dekompozice

Obecná dekompozice

rekurzivní dekompozice -- úkon dělíme rekurzivně stále stejným způsobem (např. hledání minima v O(log(n)))
datová dekompozice -- rozdělíme data a ty přiřadíme jednotlivým vláknům (např. násobení matic)
- embarrassingly parallel -- triviální, jednotlivé bloky dat spolu neinteragují

Specializované dekompozice

průzkumová dekompozice -- využívá se při prohledávání, končí, jakmile je dosaženo cíle (nalezení prvku)
spekulativní dekompozice -- sekvence závislých úloh, čekající úloha odhaduje, jak její prerekvizita dopadne a počítá si to dopředu
hybridní dekompozice -- kombinace různých přístupů, map-reduce (např. hledání minima v poli)

Techniky mapování a vyrovnávání zátěže

přiřazení jednotlivých úloh vláknům
zohlednění grafu závislostí
maximalizace paralelismu a využití zdrojů
minimalizace času a zatížení datových cest

Ovlivňující faktory

statické vs. dynamické úlohy -- úlohy (ne)přibývají
velikost úlohy
velikost dat potřebných k provedení úlohy

Rozdělení dat

bloková distribuce -- AAABBBCCC
cyklická distribuce
- blokově-cyklická distribuce -- ABCABCABC
náhodná distribuce
grafové dělění -- data organizována jako graf, chceme dosáhnout stejného počtu vrcholů ve všech částech a mezi čásmi co nejmenší počat hran (NP-úplné)

Rozdělení při statických úlohách

podle grafu závislostí
hierarchické dělení -- na jednotlivých vrstvách hierarchie jsou použity jiné způsoby dekompozice

Rozdělení při dynamických úlohách

centralizované schéma dynamického mapování -- jedna úloha je vyhrazena na přiřazování nových úloh procesům
distribuované schéma dynamického mapování -- úlohy se mohou za běhu prohazovat mezi procesy

Afinitní plánování

při dělení se snažíme, aby jeden proces/vlákno pracovalo na jednom fyzickém procesoru
lepší využítí cache, vyšší výkon

Metody pro redukci režie interakce

u embarrassingly parallel k režii nedochází
chceme:
- snížit objem dat -- lokální kopie dat, lokální ukládání mezivýsledků, minimalizace objemu sdílených dat
- snížit frekvenci interakce -- bufferování, cache, prosotrová lokalizace přenášených dat
- redukovat cenu komunikace -- synchronizace a předávání dat
Data potřebuje víc úloh naráz. -> Rozdělíme je na části a každá úloha bude postupně získávat jinou část dat.
Prodlevy při manupulaci s daty. -> Během prodlevy děláme něco jiného.
Drahý přístup ke sdíleným datům. -> Vytvoříme lokální kopii a pracujeme s ní.
Komunikace mezi procesy je drahá. -> MPI
Malý propustnost komuniakční sítě. -> Místo (A->B), (B->C), (C->D) zvolíme (A->B), (A->D, B->C)

latence -- doba potřebná pro doručení prvního bitu

přenosová rychlost -- objem dat přenesený za jednotku času

cena komunikace -- cena_zahajeni_komunikace + pocet_linek * (cena_hopu + delka_zpravy * cena_prenosu_jednoho_slova)

Programování aplikací pro prostředí s distribuovanou pamětí

Principy programování s předáváním zpráv

asynchronní paradigma -- úlohy začnou se stejný čas, ale neprobíhají stejně rychle, můžeme je v určitých bodech synchronizovat

Send a Recieve -- Základní stavební kameny

send(void *sendbuf, int nelems, int dest)

receive(void *recvbuf, int nelemns, int src)

Komunikační módy

bufferované & blokující -- send skončí po nakopírování dat do bufferu
bufferované & neblokující -- send skončí při zahájení DMA přenosu
nebufferované & blokující -- send skončí po skončení operace recieve
nebufferované & neblokující -- send skončí ihned

MPI (Message Passing Interface)

standardizace syntaxe a sémantiky komunikačních primitiv
MPI_Init, MPI_Finalize, MPI_Comm_size (počet procesů), MPI_Comm_rank (identifikátor volajícího procesu), MPI_Send, MPI_Recv
MPI_Sendrecv -- přijímá a posílá zároveň

Neblokující komunikace

dotazujeme se na dokončení operace

Kolektivní komunikace

všechny procesy v doméne (množina zapojených procesů) musí volat odpovídající MPI funkci
bariéra -- synchronizační primitivum
int MPI_Bcast() -- vysílá zprávu všem (OTA One To All)
int MPI_Reduce() -- spojí jednotlivé výsledky do jednoho
int MPI_Scan() -- prefixová redukce, prefixový součet
int MPI_Gather(), int MPI_Allgather(), int MPI_Scatter(), int MPI_Alltoall()
k funkcím existují jejich vektorové varianty, které typicky umožňují posílat/příjímat různě velké objemy dat od/do jednotlivých procesů

Skupiny, komunikátory a topologie

int MPI_Comm_split(MPI) -- rozdělí komunikační doménu
mapování přes MPI je výhodné, minimalizuje cenu komunikace
kartézské topologie -- wft?

Kolektivní komunikační primitiva

Kvantitativní parametry komunikace

cena interakce by neměla negativně ovlivňovat výhodnost paralelní řešení

latence -- zpoždění kvůli zahájení komunikace

šířka pásma -- maximální počet dat přenesených za jednotku času

objem -- množství dat

cena komunikace -- latence + (šířka_pásma × objem)

Topologie

sběrnice
kliky (úplné sítě)
kruh
hvězdice
hyperkostka
strom s aktivními vnitřními uzly

Způsoby vysílání (komunikační primitiva)

OTA (One To All)

topologie prstenu či řetězu -- rekurzivní zdvojení
topologie 2D mřížky -- střídáme rozeslání vždy v jednom měru ob jeden uzel a sousednímu uzlu
topologie hyperkostky -- cena je rovna dimenzi, v každém kroku se počet informovaných uzlů zdvojí

ATO Redukce (All To One)

ATA (All To All)

při každé itaraci se informovanost uzlu zdvojnásobí

ATA Redukce (All To All)

po každé itaraci je objem zpráv zredukován na polovinu

ATA (All To All) - individuální komunikace

každá úloha posílá různá data ostatním úlohám
topologie prsten -- vše pošlu jedním směrem, nechám si to, co je pro mě
topologie mřížky -- zprávy se pošlou v rámci řádku, každý si nechá to, co náleží do jeho sloupce, následně se pošlou v rámci sloupce
topologie hyperkostky -- algoritmus pro topologii mřížky není optimální
- e-cube routing -- cesta mezi dvěmi body je určena odlišnými bity, posílá se vždy do méně významného bitu

Analytický model paralelních programů

Režie (overhead) paralelních programů

činnosti, které přímo nevykonávají zadaný úkol, ale slouží k manipulaci (prostoje při čekání na data), komunikaci apod.

Metriky výkonnosti

čas výpočtu -- T_s

celková režie (Overhead) -- T_o, rozdíl časů výpočtu paralelního programu a optimálního sekvenčního programu

zrychlení (Speed up) -- S poměr času optimálního sekvenčního výpočtu a času paralelního výpočtu, maximální zrychlení při použití p jednotek je p

super-lineární zrychlení -- zrychlení je větší než počet jednotek

falešné super-lineární zrychlení -- např. neuvažujeme optimální sekvenční algoritmus
skutečné super-lineární zrychlení -- může nastat při správném využítí cache paměti

Amdahlův zákon

paralelizujeme pouze část programu
jaké bude největší možné zrychlení

Smax = 1 / ((1-P) + (P/Sp))
P .... podíl systému, který paralelizujeme
Sp ... zrychlení, které dosáheme paralelizací

cena -- počet procesních jednotek * doba paralelního výpočtu, optimální cena roste asymptoticky stejně rychle jako cena optimální sekvenčního výpočtu

Vliv granularity na cenovou optimalitu

granularita ovlivňuje cenu
v praxi se volí položka vsutpu = jednotka
deškálování -- umělé snižování granularity

Škálovatelnost paralelních programů

zachování výkonu a efektivity při zvyšování počtu procesních jednotek

Efektivita**

podíl zrychlení a počtu procesních jednotek
1 / (1 + (To/Ts))
zachování efektivity -- zvyšujeme počet procesních jednotek i množství dat současně

izoefektivita -- konstantní efektivita, vztah, jak se má zvýšit Ts při zvýšení počtu procesních jednotek

Files

IB109.md

Latest commit

History