PPR

Zkouška 22.1.2004, zk.: Racek, s sebou povolena vlastní semestrálka (doporučuji z části koncipovat jako tahák; přineste si ji s sebou [marné hledání ve zmateném paklu žádná slast]):

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 (rozměr 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ⁿ, 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] K čemu je dobrý objekt typu podmínková proměnná v interface vláken POSIX a jaké operace nad ní jdou provést (vše slovně, popřípadě typy operací v C).
   • Porovnejte mezi sebou fyzické komunikační topologie dvourozměrná mřížka a n-rozměrná krychle (platí počet uzlů N = 1024 = m² = 2ⁿ) v hodnotách ukazatelů počet sousedů a maximální komunikační vzdálenost.
   • [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č je 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.
   (celý bod 1 musí být splněn na minimálně 15 bodů)
2. [4b] Vysvětlete stručně slovně co dělají následující funkce m MPI. Též uveďte, jaké mají parametry (alespoň zhruba).
   • int MPI_Comm_size (...)
   • int MPI_Finalize (...)
   • int MPI_recv (...)
   • int MPI_Comm_rank (...)
3. [10b] Napiště v Javě vhodnou formou monitor, který realizuje celočíselný semafor se standardními operacemi (P, V a inicializace (konstruktor)). Přidejte ještě neblokující test stavu semaforu (vrátí hodnotu čítače).
4. Paralelizaci v modelu MPMD (tj. tzv. funkční paralelismus) lze popsat tzv. precedenčním grafem (hrany = dílčí činnosti, uzly = synchronizace činností). Paralelní výpočet popsaný precedenčním grafem realizujeme v distribuovaném prostředí s využitím PVM.
   1. [5b] Popište slovně jak byste výpočet realizovali, konkrétně:
      • čemu by odpovídali procesy PVM
      • jak by si procesy předávaly data
      • jak by se procesy synchronizovaly
      • jak by se celý výpočet inicioval a ukončil
   2. [5b] Na obrázku je nějaký fragment precedenčního grafu. Napište (formou vývojového diagramu, resp. pseudokódu, popřípadně slovně) program procesu odpovídajícího činnosti c. Výsledkem činností a a b je reálné číslo, v rámci c jsou tato čísla sečtena a předána navazujícím činnostem d a e.

                        a                                 d    
                       ----->+---+      c       +-----+----->
                             | i |------------->| i+1 |      
                       ----->+---+              +-----+----->
                        b                                 e    
                    

   3. [3b] Popište slovně funkce PVM (co dělají, parametry, které jste potřebovali v bodě b).
5. Realizujeme model SPMD s využitím vláken POSIX a potřebujeme vlákna synchronizovat na bariéře. Vláken je pevný počet N (zavedeno jako konstanta #DEFINE N ...).
   1. [2b] Jaké objekty podporované v interface POSIX potřebujete pro realizaci bariéry (slovně popsat, zavést nějaké pojmenování objektů).
   2. [3b] Napište kousek C-kódu (nebo pseudokód) společného programu vláken využitý pro synchronizaci na bariéře.
   3. [3b] Jak byste v C (plus interface POSIX) realizovali objektový typ bariéra, přestože C není objektový jazyk (slovní vysvětlení, popřípadě kousky C-kódu).

Zkouška 5.2.2004 (zmateně, nepřesně, po paměti):

1. Vysvětlete stručně:
   • Jaký je maximální počet procesorů v symetrickém multiprocesoru a čím je shora omezen?
   • Rozdíl mezi procesem a vláknem; napište stavy vlákna.
   • Co se stane, když v Javě ve vícevláknovém programu zavolám v metodě run() vlákna A "B.join()"?
   • Jaké je maximální urychlení redukční operace (např. součtu) (n = rozměr dat, N = počet procesorů) paralelismu na
     • symetrickém multiprocesoru
       s =
       - co v tomto případě znamená ideální případ?
     • v topologii hyperkrychle v multiprocesoru s distribuovanou pamětí
       s =
       - co v tomto případě znamená ideální případ?
   • Maximální vzdálenost, počet sousedních prvků a ??? v topologii 3D (a 2D?) mřížky se stranou m = 4.
   • Jak dlouho potrvá broadcasting v "3D krychli" se stranou m = 4, když mezi sousedy to trvá 10µs?
   • Jaký je rozdíl v komunikaci v MPI a PVM?
   • Jak se v MPI udělá ???nějaké rozdělení či co???, kterou funkcí, zapište její syntax a vysvětlete.
   • Nakreslete precedenční graf pro: a=..., b=..., c=..., d=...c..., e=...c..., f=...d+e...
2. 1. v Javě libovolný netriviální typ RECORD, udělejte konstruktor a getry a setry
   2. udělejte RECORD_PAR jako monitor nad RECORD pro vícevláknový program. Jen jeden zdroj; je-li plný nelze psát; je-li prázdný nelze číst; udělejte konstruktor a getry a setry
   3. udělejte třídu procesu, co bude pomocí read_in() odněkud číst vstup, pomocí write_out() psát výstup v cyklu; něco tlačit do RECORD_PAR (v konstruktoru musí být ten monitor jako parametr)
3. 1. V PMV situace: procesy MASTER, WORKER1 a WORKER2; MASTER dá vstupy WORKERovi1, ten zpracuje a předá WORKERovi2, ten opět MASTERovi. Napište v PVM MASTERa a komentujte:

                          program:           |           komentář:
                                             |
                                             |
                                             |
                                             |
                                             :
                                             . 
                  

   2. Jakého lze docílit maximálního urychlení a čím je toto urychlení dle vás omezeno?
4. MPMD - střídají se vlákna a(), b(), c(), d(), e(), f(); procesy P1(), P2(), P3() dělají různě ac, bd, etc.; použijte semafory k napsání procesu co bude dělat pořadí abcdef a napište na jaké hodnoty musí semafory inicializovány.