Skuska 2017/18 Flashcards Preview

PARALELPR > Skuska 2017/18 > Flashcards

Flashcards in Skuska 2017/18 Deck (15):
1

Slovne popis co su kolektivne komunikacne operacie.

kolektívna komunikácia - komunikácia medzi skupinou procesov

každá kolektívna operácia je definovaná na skupine, ktorá je určená komunikátorom

všetky procesy musia zavolať operáciu

niektoré významné operácie: bariéra, broadcast, redukcia, scatter, gather

efektívna implementácia:
-lepšia výkonnosť, jednoduchší vývoj, cena, kvalita SW
-nutnosť využiť architektúru komunikačných operácií

MPI - message passing interface - obsahuje množinu funkcií pre kolektívne operácie

vzorové architektúry komunikačných operácií
kruhová mriežka
2D mriežka
hyperkocka

2

all to all broadcast a reduction slovne popisat

zovšeobecnenie operácie broadcast, v ktorej je každý proces zdrojom aj cieľom

proces posiela tú istú správu dĺžky m všetkým ostatným procesom, avšak rôzne procesy môžu posielať rôzne správy

Reduction
Podobná komunikačná štruktúra ako má „All-to-All
Broadcast“, akurát operácie sú v opačnom poradí

Po prijatí správy musí uzol kombinovať tuto spravu s lokalnou kopiou spravy, ktora ma rovnakeho adresata ako prijata sprava, a to este pred odoslanim kombinovanej spravy nasledujucemu susedovy

3

zakreslit a popisat all to all reduction na kruhovej topologii

jednoduchý prístup: vykonanie p broadcastov jeden viacerým je neefektívne

každý uzol najskôr zašle údaje jednému zo svojich susedných uzlov
v nasledujúcich krokoch odosiela už prijaté údaje od jedného zo susedných uzlov druhému

algoritmus končí za p-1 krokov

Reduction:
podobná komunikačná štruktúra ako má “all-to-all broadcast”, akurát operácie sú v opačnom poradí

po prijatí správy musí uzol kombinovať lokálnu správu s rovnakým adresátom ako má prijatá správa ešte pred jej preposlaním nasledujúcemu susednému uzlu

4

Graf zavislosti a interakcie. Slovne opisat a nakreslit.

Graf zavislosti medzi ulohami

prvý krok - dekomponovať problém na úlohy vykonateľné súbežne
viaceré možnosti dekompozície
úlohy rovnakej, rôznej a tiež nekončiacej veľkosti
Dekompozicia moze byt zobrazena formou orientovaneho grafu s uzlami reprezentujucimi ulohy a hranamy reprezentujucimi zavislosti jednej ulohy od inej

Dlzka kriticke cesty - najdlhsia cesta v grafe zavislosti

najdlhsia cesta urcuje najkratsi mozny cas vykonania paralelneho programu
cesta po orientovanych hranach v grafe zavisloti reprezentuje postup uloh, ktore musia byt vykonane jedna po druhej v danom poradi

Graf interakcie

dekomponované úlohy si zvyčajne potrebuju vymieňať údaje

graf úloh (uzly) a ich interakcie-výmeny údajov (hrany) sa nazýva graf interakcie medzi úlohami (task interaction graph)

Graf interakcie – dátová závislosť
Graf závislosti – riadiaca závislosť

napriklad:
Triviálne násobenie matice s vektorom – ak vektor b nie
je replikovaný, je potrebné komunikovať prvky vektora

5

Vymenovat techniky dekompozicie

rekurzivna, datova, spekulativna, exploracna, hybridna dekompozicia

6

Rekurzívna dekompozícia

vo všeobecnosti vhodné pre problémy riešené stratégiou “rozdeľuj a panuj”
problém je najskôr dekomponovaný na množinu podproblémov
podproblémy sú potom rekurzívne dekomponované až kým nie je dosiahnutá požadovaná zrnitosť


quiksort, hľadanie minima v zozname prvkov

7

Dátová dekompozícia

identifikácia údajov, nad ktorými sa výpočet realizuje
rozdelenie údajov medzi rôzne úlohy
rozdelenie zahŕňa aj dekompozíciu problému
možnosť rozdeliť údaje rôznymi spôsobmi - kritické vzhľadom na výkonnosť paralelného algoritmu

podľa výstupných údajov
často každý prvok výstupných údajov môže byť vypočítaný nezávisle na ostatných (jednoducho ako funkcia vstupov)
rozdelenie výstupu medzi úlohy prirodzene dekomponuje problém


násobenie nxn matíc
nemusí byť jednoznačná


ak je databáza replikovaná medzi procesmi, každá úloha môže byť vykonávaná bez komunikácie
ak je databáza rozdelená medzi procesy, každá úloha vykoná výpočet čiastočných početností a tieto početnosti sa nakoniec agregujú do výsledných početností


podľa vstupných údajov
vo všeobecnosti použiteľné, ak každý výstup môže byť prirodzene vypočítaný ako funkcia vstupov
v mnohých prípadoch jediný prirodzený spôsob dekompozície, keďže výstup nie je dopredu známy (napr. problém hľadania minimálneho prvku poľa)
úloha je asociovaná s každou časťou vstupných dát, väčšinu výpočtu úloha realizuje nad svojou časťou dát
nasledujúce spracovanie skombinuje čiastkové výsledky


podľa medzivýsledkov
výpočet môže byť často považovaný za transformáciu vstupov na výstupy
v takomto prípade je často užitočné využiť medzivýsledky ako základ pre dekompozíciu


násobenie matíc


Pravidlo “vlastník počíta”
pravidlo vlastník počíta - proces priradený k nejakému údaju je zodpovedný za všetky výpočty spojené s údajom

8

Exploračná dekompozícia

v mnohých prípadoch dekompozícia problému je spojená s vykonávaním programu
takéto problémy zvyčajne vyžadujú prehľadávanie stavového priestoru riešení
problémy z tejto oblasti spadajú pod optimalizačné problémy, dokazovanie tvrdení, hranie hier,...

anomálne výpočty
v mnohých prípadoch použitia exploračnej dekompozície - spôsob dekomponovania určuje množštvo práce v paralelnom riešení
výsledok môže byť super-lineárny alebo sub-lineárny

9

Špekulatívna dekompozícia

v niektorých aplikáciách závislosti medzi úlohami nie sú dopredu známe
v takýchto prípadoch nie je možné dopredu identifikovať úlohy
v takýchto prípadoch sú možné dva prístupy:
konzervatívny, ktorý identifikuje nezávislé úlohy iba ak je zaručené, že medzi nimi nie sú závislosti
slabá súbežnosť
optimistický, ktorý naplánuje úlohy aj keď môžu byť chybné
krok späť (roll-back) v prípade chyby


simulácia pomocou diskrétnych udalosté (discrete event simulation)
hlavná údajová štruktúra - zoznam udalostí usporiadaných v čase
udalosti sú spracovávané v poradí danom časom, výsledné udalosti sú umiestňované do zoznamu


simulácia jedného pracovného dňa


simulácia siete uzlov (pásová výroba)

10

Hybridná dekompozícia

často je potrebné vykonať dekompozíciu použitím viacerých spomenutých spôsobob
quicksort - iba rekurzívna dekompozícia obmedzuje súbežnosť, kombinácia rekurzívnej a dátovej dekompozície je vhodnejšia
v simulácii pomocou diskrétnych udalostí môže byť spracovanie udalosti vykonané súbežne - kombinácia špekulatívnej a dátovej dekompozície môže byť vhodná
hľadanie minimálneho prvku v poli - kombinácia dátovej a rekurzívnej dekompozície

11

Vlastnosti uloh a interakcii

Po dekomponovaní problému na nezávislé úlohy,
vlastnosti úloh významne ovplyvňujú výber a výkonnosť
paralelného algoritmu

Vlasnosti úloh

a) sposob generovania uloh
b) velkost uloh
c) velkost udajov asociovanych s ulohou

spôsob generovania úloh
statické generovanie úloh
súbežné úlohy je možné dopredu identifikovať
problémy s pravidelnou štruktúrou: násobenie matíc, grafové algoritmy, spracovanie obrazu
dynamické generovanie úloh
úlohy sú generované v priebehu vykonávania výpočtu
hranie hier
exploratívna a špekulatívna dekompozícia

veľkosť úloh
rovnomerná veľkosť úloh alebo nerovnomerná veľkosť úloh
úlohy nerovnomernej veľkosti - možnosť odhadnúť dopredu veľkosť alebo nie
diskrétna optimalizácia - ťažké určiť efektívnu veľkosť stavového priestoru

veľkosť údajov asociovaných s úlohou
veľkosť asociovaných dát môže byť veľká alebo malá v kontexte veľkosti úlohy
malý kontext úlohy znamená, že algoritmus môže ľahko komunikovať úlohu inému procesu dynamicky
rozsiahly kontext pripútava úlohu k procesu


Vlastnosti interakcií
úlohy môžu medzi sebou komunikovať rôznymi spôsobmi
statické interakcie:
úlohy a ich interakcie sú dopredu známe
zvyčajne jednoduchšie na implementáciu
dynamické interakcie:
časovanie a interakcie úloh nie je možné dopredu definovať
zložitejšia implementácia, obzvlášť pri modeloch zasielania správ
pravidelné regulárne interakcie:
definovaný vzor v grafe interakcií
možnosť využiť vzor pre efektívnu implementáciu
nepravidelné iregulárne interakcie
interakcie nevykazujú dobre definované typológie v grafe
interakcie iba čítanie alebo zápis a čítanie
interakcie typu “iba čítanie” - úlohy iba čítajú údaje prislúchajúce iným úlohám
interakcie typu “čítanie a zápis” - úlohy čítajú, ale aj modifikujú údaje prislúchajúce iným úlohám
vo všeobecnosti sa ťažšie implementujú, vyžadujú použitie dodatočných synchronizačných primitív
jednostranné alebo obojstranné interakcie
jednostranné interakcie
iniciované a vykonané iba jednou z dvoch interagujúcich úloh
ťažšie sa implementujú v modeloch zasielania správ
obojstranné interakcie
vyžadujú participáciu oboch úloh

12

Co znamena klauzula schedule pri direktive for. Popis vsetky moznosti pre tuto klauzulu a vysvetli co ovplyvnuje parameter chunk.

OpenMP
klauzula SCHEDULE
ako sú iterácie rozdelené medzi vlákna
STATIC - určené rozsahy podľa parametra chunk a tie staticky priradené vláknam
DYNAMIC - iterácie rozdelené do rozsahov veľkosti chunk a tie dynamicky priraďované vláknam
GUIDED - veľkosť rozsahu daná počtom nepriradených iterácií vydelených počtom vlákien až po veľkosť chunk
RUNTIME - podľa premennej prostredia OMP_SCHEDULE
AUTO - ponechané na kompilátor
//tieto dalsie uz nepatria do schedule podla mna
NO WAIT - nie je synchronizácia na konci oblasti
ORDERED - iterácie vykonávané ako v sériovom programe
COLLAPSE - počet vnorených cyklov použitých na vytvorenie jedného “priestoru” iterácií


chunk - veľkosť bloku

13

Aku klauzulu schedule by si pouzil a preco? Predpoklada sa ze vypocet moze trvat pre kazdu iteraciu rozne dlhy cas. (to bolo dolezite) Dopln do kodu direktivu:
For (i = 0; i<1000; i++){
Time = rand(10000);
compute(time);
}

Pouzit calause dynamic, pretoze tato klauzula sa pouziva ked neviem dopredu kolko prace a kolko casu bude trvat uloha.

doplnit:
#pragma omp parallel for schedule(dynamic, chunk_size)

14

Co je to klauzula reduction, uved aj priklad pouzitia.

Purpose:
The REDUCTION clause performs a reduction operation on the variables that appear in its list.
A private copy for each list variable is created and initialized for each thread. At the end of the reduction, the reduction variable is applied to all private copies of the shared variable, and the final result is written to the global shared variable.

priklad
double ave=0.0, a[MAX];
int i;

#pragma omp parallel for reduction(+:ave)
for(i=0; i < MAX; i++){
ave += A[i];
}
ave = ave/MAX;

15

MPI - bol tu ukazany algoritmus na vypocitanie klzaveho priemeru a tvojou ulohou bolo doplnit do kodu zabezpecenie rozdelenia tejto ulohy pre N procesov.

???