Zkouška PPR, 8.1.2002:

1.Vysvětlete stručně:

[2b]Komunikátor v MPI (co to je, k čemu je dobrý, jakou má základní hodnotu)
[3b]Co to je "složitost" algoritmu, jakou složitost má sekvenční součet vektoru čísel (rozmer K)
a jakou složitost paralelního součtu vektoru lze dosáhnout v topologii n-rozměrné krychle.
[3b]Pokuste se předchozí bod demonstrovat číselně: sčítáme vektor čísel s rozměrem K = 2 na n,
kde n = 12. kolikrát rychlejší bude součet na stroji s distribuovanou pamětí s komunikační 
topologií n-rozměrné krychle proti sekvenčnímu součtu (procesory jsou stejné, doba potřebná 
pro komunikaci v paralelním případě se zanedbá).
[2b]Amdahlův zákon (napsat vzoreček, stručně vysvětlit).
[2b]Jaké urychlení lze na sym. multiprocesoru dosáhnout v ideálním případě při paralelizaci 
cyklu (pro vysvětlení použijte předchozí vztah - Amdahlův zákon).
[2b]Bariéra (co to je, k čemu slouží, jaká je základní operace nad bariérou).
[3b]Rendez-vous v Adě (k čemu je, jak se používá (třeba příklad), proč asymetrické).
[2b]Jaké skryté atributy objektu v Javě byste zavedli pro implementaci monitoru (tj. pro
implementaci synchronized, wait() a notify())?
[2b]Redukční proměnná v paralelizovaném cyklu, čím se liší od uzamykané a jak se s ní zachází
(obecně plus příklad).
[2b]Jaká je elementární (tj. na úrovni strojového kódu) atomická synchronizační operace
(tj. instrukce) pro architekturu se sdílenou pamětí a jak se používá.
[2b]Jakého typu jsou komunikační operace v Occamu (synch/asynch, s přímou/nepřímou adresací),
uvést příklad.
----------------------------------------------------------------------------------------------
2. Vlákna probíhající podle stejného programu (nekonečný cykl) se v každé obrátce synchronizují
(tj. čekají na sebe) na bariéře pomocí operace sync(BAR *). Bariéra je implementována s využitím
standardního binárního semaforu (typ SEM). Vláken je pevný počet N (zavedeno jako konstanta
#DEFINE N ...).
a)[3b]Zavedte v jazyce C typ BAR (s využitím SEM a primitivních typů). Dále napište inicializační
funkci bariéry ini_bar(BAR *). Máte k dispozici inicializační funkci binárního semaforu 
initsem(SEM *, int ini_count).
b)[7b]Napište v C (nebo v nějakém pseudokódu) synchronizační operaci sync(BAR *). Máte k dispozici
standardní (atomické) operace nad binárním semaforem - V(SEM *), P(SEM *), tj. uvolnění a čekání.

3. [4b]Vysvětlete stručně slovně následující funkce m MPI. Též uveďte, jaké má parametry (aspoň
zhruba).

int MPI_Comm_size(...)
int MPI_Finalize(...)
int MPI_Comm_rank(...)

4. [10b]Napiště v Javě vhodnou formou typový monitor, který realizuje celočíselný semafor se 
standardními operacemi (P, V a inicializace(konstruktor)). Přidejte jěště neblokující test stavu
semaforu (vrátí hodnotu čítače).

5. a)[7b]Napište v PVM (formou vývojového diagramu, resp. pseudokódu, popřípadě slovně) programy
procesů Farmer a Worker, které ve výpočetním modelu farmer-workers realizující hledání všech
výskytů daného slova (řetězce) v knize (sdílený textový soubor členěný na stránky a dále na řádky,
slova nejsou rozdělená mezi stránky a řádky). Pozn: Výskyt = {stránka, řádka, pozice}, typy
funkcí pro čtení ze souboru si zavedte - předpokládejmte sdílený read-only soubor.
b)[4b]Popište a stručně vysvětlete všechny funkce PVM, které jste použili v předchozím textu. Též
popište vlastní funkce, pokud jste nějaké zavedli.