KIV/PPR Flashcards

Question

Anomální urychlení

Answer 1

 Distribuce rozsáhlých dat u distribuované aplikace může omezit nutnost stránkovat RAM  S dostatečně rychlými komunikačními kanály pak dojde k rychlejšímu vykonávání programového kódu, protože odpadá čekání na zpomalující I/O operace provázející stránkování, včetně obsluhy příslušných přerušení (KIV/OS)  Např. paralelizované vyhledávací algoritmy mohou mít větší než lineární urychlení ◦ Lze rychleji upřesnit výběrová kritéria

Answer 2

 V některých případech je skutečně možné, aby S vyšlo lépe než je perfektní urychlení ◦ V těchto případech se nejedná o chybu ve výpočtu ◦ Zejména, porovnáváme-li oproti nejlepšímu sekvenčnímu algoritmu  Cache procesoru ◦ Mnohem častější cache-hit než je tomu u referenčního programu ◦ Výpočet je pak prováděn mnohem rychleji, než když se programový kód a data dostávají k procesoru z pomalejší paměti ◦ Záleží na konkrétním programovém kódu, zda se ho bude dostatečné množství nalézat právě v lokálních cache jednotlivých procesorů  Analogicky datová cache

Answer 3

 Tvrdí, že nelze dosáhnout perfektního urychlení, protože vždy bude nějaká část výpočtu provedena sekvenčně  G + H – čas strávený sekvenčně provedeným výpočtem  G - čas strávený vykonáváním neparalelizovatelného kódu, tj. sekvenčně - Unavoidably Serial  H - čas strávený vykonáváním paralelizovaného kódu, ale sekvenčně - Serialized-Parallel  E(p) = G + H/p  S(p) = (G+H)/(G+H/p)  Pro velké p platí S(p) = 1+H/G ◦ To by znamenalo, že dosažení perfektního urychlení je možné, pokud se můžeme vyhnout kódu, který nelze paralelizovat ◦ Má vliv na H ◦ Ale – čím větší počet procesorů, tím např. větší režie jejich komunikace => takže přece jenom nepůjde…  Režie OS (plánování, I/O, atd.) se o to také postará

Answer 4

 S(P) = P - α×(P-1) ◦ S – urychlení ◦ P – počet procesorů ◦ α - část procesu, kterou nelze paralelizovat  Amdahl uvažuje konstantní velikost problému, takže se sériový čas nemění, jen paralelizovaný se zmenšuje  Gustafson uvažuje konstantní paralelizovaný čas za předpokladu, že více procesorů zvládne větší velikost problému  Nerozdělíme výpočet podle paralelizovatelnosti kódu, ale podle podílů času – sériově vs. paralelně

Answer 5

 Ani Amdahlův ani Gustafonův zákon nepočítá s různými rychlostmi mezipamětí  Pokud se data a instrukce vejdou do L1-L3 mezipaměti použitých procesorových jader, přístup k nim bude rychlejší než k hlavní paměti (dále viz přednáška BigData) ◦ =>lze dosáhnout superlinárního urychlení, které si Amdahlův ani Gustafsonův zákon neumí vysvětlit  Klíčem k superlineárnímu urychlení je používat menší datové bloky, které se vejdou do některé z pamětí (nejlépe do L1, nebo aspoň do L2 nebo L3) ◦ To samé platí i pro instrukce

Answer 6

 Urychlení dělené počtem procesorů ◦ Uvažujeme urychlení proti sekvenčnímu algoritmu  Sekvenční výpočet trvá 10s, paralelní algoritmus na 4 procesorech trvá 5s ◦ Urychlení: 2 ◦ Účinnost: 0,5

Answer 7

Metrika určená z naměřených časů | - Vzorečky v přednášce

Answer 8

 Nezávislost na počtu dostupných procesorů |  S rostoucím počtem procesů narůstá i komunikační režie a dochází ke zpomalování výpočtu

Answer 9

 (control) Flow Correct ◦ Chová se deterministicky ◦ Nevykazuje chyby v důsledku nedeterminismu plánování vláken - Nepředbíhám ve frontě, nedeterminismus plánování vláken  Logically Correct ◦ Dá správný výsledek  Musí být splněno Flow Correct ◦ Pozor – řeklo se „správný výsledek“, ne že správný výsledek bude pořád stejný - Mám pole, kde hledám minimální číslo - Rozdělím pole na n částí, každé vlákno prohledá jeden kus - Můžu mít více minimálních čísel v různých částech paměti - Které vlákno vrátí minimální číslo jako první, tak tu pozici vyberu

Answer 10

 Mějme model nějakého efektu, a hledejme paralelně parametry tohoto modelu tak, abychom dosáhli co nejmenší průměrné odchylky vypočítaných hodnot od naměřených hodnot ◦ Tj. jde o redukční operaci  Může se nám tedy stát, že dvě různá vlákna nám mohou vygenerovat dvě různé množiny parametrů, pro které vypočítají dvě různé množiny odchylek ◦ {1; 2; 1; 2; 1} a {1; 0; 3; 2; 1} ◦ Pokud bychom počítali průměrnou odchylku, tak nám v obou případech vyjde stejné číslo ◦ Ale které z nich z použijeme a které je správně?  To záleží na tom, které vlákno odevzdá své výsledky ke globálnímu porovnání jako první  Zvolená metrika vhodnosti výsledku nám to neumožňuje lépe rozhodnout  Kdybychom vyhodnocovali sériový program, pak se nám bez této znalosti může mylně zdát, že na rozdíl od paralelního programu pracuje správně, protože dá vždy stejný výsledek ◦ Přičemž výsledek sériového programu nemusí být lepší než některý z jiných výsledků paralelního výpočtu  Některé knihovny, např. Intel Threading Building Blocks, nabízejí deterministickou verzi redukční operace ◦ Není tak rychlá jako nedeterministická verze, ale měla by vždy dát stejný výsledek, protože se snaží práci pokaždé rozdělit stejně ◦ Tj. neřeší za nás metriku vhodnosti řešení!  Další komplikací je fakt, že na FPU sčítání ani násobení nejsou nezbytně asociativní, ačkoliv jsou komutativní ◦ Tj. (a +b) + c nemusí dát ten samý výsledek jako a + (b + c)  Důvodem je konečný počet číslic reprezentujících daná čísla --> Jedná se o sčítání doublů, tam to samozřejmě nevychází

Answer 11

1) Minimalizovat počet interakcí vláken 2) Minimalizovat dobu trvání interakcí  Obě uvedené zásady mohou někdy vést ke kompromisu 3) Násilné nezasahování do stavu jiných vláken ◦ Proměnné ◦ Stav, kontext  Programátor OS/mezivrstvy bude mít v tomto případě jiný názor (OS kill) 4) Rychlostní nezávislost vláken – tj. neuvažovat v návrhu, že dané vlákno poběží nějakou rychlostí ◦ V případě hard-real time systémů by se mohla najít vyjímka ◦ Nespoléhat se na předpokládaný postup plánovače vláken  S další verzí se může změnit  Může nastat podmínka, která změní plánování, ale vy o ní nevíte  Nezneužívat priority 5) Interakce musí být atomické ◦ Navrhnout a dodržet společnou politiku přístupu ke kritickým sekcím, např. dvoufázové zamykání ◦ Uvědomit si, že přístup k HW (a jiným prostředkům OS/mezivrstvy) je vstup do kritické sekce na úrovni OS/mezivrstvy

Answer 12

 Čistě sériový kód se dá odladit snadno, protože posloupnost vykonávání instrukcí je pokaždé stejná  U paralelních výpočtů to neplatí  Odladit netriviální, navíc je-li optimalizovaný, paralelní výpočet je jedna z nejtěžších věcí ad Testování ◦ I když vypadá kód bez chyby, stejně ho nechte testovat víc než dostatečně dlouho za různých podmínek ad Sériový kód ◦ Stále je třeba odladit sériový kód, resp. kód vlákna, zda např. provádí správně např. I/O operace ◦ Jde o kontrolu té části výpočtu, kdy nedochází k interakci s ostatními vlákny, ani se nepřistupuje ke sdíleným proměnným ◦ Lze s ním odladit pouze omezenou množinu všech možných chyb paralelního programu ◦ Většinou jde o chyby, které je vidět přímo ze zdrojového kódu ad Kontrolní výpisy ◦ Výsledek paralelního programu s chybnou synchronizací závisí i na tom, jak rychle poběží jeho vlákna ◦ Krokování v debuggeru IDE způsobuje velké prodlevy --> Může tak docházet k dodatečné synchronizaci, jejímž následkem se chyba neprojeví ◦ Kontrolní výpis sice neposkytne tolik informací jako použití debuggeru, ale zase je rychlost vykonávání vláken bližší jejich běžné rychlosti --> Kontrolní výpis také způsobuje dodatečnou synchronizaci, která může zabránit chybě, aby se projevila ◦ Fce volající jádro způsobují dodatečnou synchronizaci --> Např. v kontrolním výpisu GetThreadID ad Randseed ◦ Rychlost programu, tj. i možné potlačení chyby, ovlivní ◦ Debug verze vs. release verze  Release verze by minimálně díky optimalizaci měla běžet rychleji  V debug verzi může být něco od překladače, co způsobí dodatečnou synchronizaci ad Zátěž systému ◦ V systému může běžet několik aplikací, uzamykatelné zdroje nemusí být vždy stejně dostupné, využití systémových zdrojů se mění - viz zátěžové testy simulující nedostatek systémových zdrojů ad Náhodné spoždění ◦ Je možné do debug verze programu přidat náhodné zpoždění – sleep(rand) ◦ A na začátku inicializovat proměnnou randseed, tak aby se případná chyba dala zopakovat --> Pokud ji ovšem způsobují náhodné prodlevy, opakované ve stejném pořadí

Answer 13

 Primitivní ◦ Synchronizace ◦ Sdílení dat ◦ Zasílání zpráv  Strukturované ◦ Monitor ◦ Rendez-vous

Answer 14

 Poměr objemu výpočtu k objemu komunikace ◦ Čím jemnější (Fine-Grained), tím menší objem dat je vypočítán mezi komunikací dvou vláken => častá komunikace o malých objemech  Hrubší (Coarse-Grained) – opak jemnější  Jemnější umožňuje vyšší paralelizaci, ale je třeba „zjemňování zastavit včas“, jinak se výpočet začne zpomalovat díky komunikační režii a režii synchronizace

Answer 15

◦ Vyjadřuje návaznost činností ◦ Acyklický graf  Smyčka znamená uvíznutí  Uzel je ohodnocen náklady na výpočet – např. doba výpočtu  Hrana je ohodnocena náklady na komunikaci  Má smysl u distribuovaných výpočtů  U sdílené paměti je můžeme zanedbat  Umožňuje analyzovat urychlení výpočtu ◦ Doba výpočtu na jednoprocesorovém systému je dána součtem dob všech výpočtů ◦ Doba výpočtu na víceprocesorovém systému je nejdelší cesta grafem, který reprezentuje alokaci výpočtů na jednotlivé procesory ◦ V uvedeném obrázku je  Výpočet na 3 procesorech: 16  Výpočet na 1 procesoru: 35  Urychlení: 35/16 = 2,1875  Nelze tedy automaticky tvrdit, že s n procesory něco poběží n-krát rychleji  Synchronizace znamená, že se čeká na dokončení všech činností, z jejichž uzlů vedou hrany do daného uzlu  Alternativě můžeme uvažovat grafy, kdy ◦ Uzel představuje synchronizační bod ◦ Hrana jsou náklady na výpočet ◦ Hodí se do prostředí se sdílenou pamětí

Answer 16

```  Dva typy uzlů ◦ Místo – kruh, modeluje činnost ◦ Přechod – úsečka, modeluje událost  Hrana udává přechod  Stav systému vyjadřuje značení  Plné kruhy  Celočíselná hodnota = Počet plných kruhů v uzlu ```  K přechodu dojde tehdy, jestliže má každá vstupní hrana značení  Počet značek může reprezentovat počet zdrojů ◦ Např. producent-konzument  p2 a p4 na obrázku jsou kritické sekce dvou procesů/vláken, které přistupují ke sdíleným datům  existuje-li takový stav, kdy není možný žádný přechod, pak v systém může nastat uvíznutí  přechod je okamžitý, s časem počítá stochastická Petriho síť

Answer 17

 Důkaz správnosti programu  Proměnné popisují stavy a vlastnosti programu ◦ Každá proměnná x prvkem V ◦ V(ocabulary) je množina všech proměnných  Aplikací logických operátorů na proměnné a konstanty se zkonstruují výrazy, které popisují nějakou vlastnost programu ◦ =, >, &, not, pro vsechny, existuje, …  Jazyk k popisu programu lze rozšířit o vlastní operátory – např. časové ◦ p W q => p čeká (pokud není) q  Jde o automat s množinou proměnných V, počátečním stavem q a konečnou množinou přechodů T  Co hledáme je tzv. invariant ◦ Výraz, který říká, že např. v kritické sekci vzájemného vyloučení bude vždy maximálně jenom jeden proces  Ověřující podmínka efektu přechodu mezi dvěma stavy říká, že každý následník t stavu j je stav y ◦ {j} t {y}

Answer 18

1) Lokální proměnné - jsou inicializována uvnitř smyčky 2) Sdílené proměnné - hodnoty se přenáší mezi jednotlivými iteracemi - dělí se na nezávislé a závislé 2a) Nezávislé - jsou využívána pouze pro čtení - v případě pole jde pouze o jeden prvek, se kterým se pracuje pouze v jedné iteraci 2b) Závislé - redukční - uzamykané - uspořádané

Answer 19

◦ Nejprve je čtena, pak zapsána | ◦ Uvedené se odehraje v jedné iteraci

Answer 20

min:=Items[0]; for i:=1 to High(Items) do if min

Answer 21

◦ Správného výsledku je dosaženo pouze tehdy, jsou-li iterace vykonávány pouze ve stanoveném pořadí for i:=1 to High(Items) do Items[i]:=Items[i] + Items[i-1];  Na rozdíl od předchozích cyklů, tento nelze urychlit tak, že vlákna současně vykonají operace nad svou částí pole (a pak jedno z nich zpracuje mezivýsledky). Je třeba to zařídit jinak.

Answer 22

 Procesor načítá instrukce dopředu a hledá mezi nimi závislosti  Po nalezení závislostí zpřehází instrukce tak, aby instrukce, které na sobě nezávisí, mohl vykonat paralelně

Answer 23

 Ve specifikaci architektury procesoru je konečný počet pojmenovaných registrů, viditelných programátorovi  Ale ve skutečnosti jich má procesor víc, takže když překladači dojdou volné registry, procesor je stále schopný paralelně vykonávat instrukce, které zdánlivě pracují se stejným registrem  Nicméně, i programátorovi-nepojmenovaných registrů je konečné množství ◦ Málo registrů, to je bída – aneb znáte alespoň jeden procesor s Java ByteCode jako nativní instrukční sadou?  Když dojdou registry, přistupuje se do pomalejší paměti a tím se zpomaluje běh programu  Proto se vyplatí omezit počet proměnných v bloku/funkci ◦ Např. „roztrhat“ náročnější tělo cyklu na několik cyklů ◦ Ne tedy napsat „kilometr dlouhý “ kód, ve kterém bude málo proměnných, zato s obskurními názvy a používané pro cokoliv

Answer 24

 Architektura procesoru mj. říká, jaké má procesor instrukce ◦ Tj. to, s čím pracuje programátor  Zpracování jedné instrukce lze rozdělit do několika fází jako je načtení, dekódování, vykonání, přístup do paměti ◦ Počet fází závisí na konkrétním procesoru ◦ Instrukce se skládá z několika mikroinstrukcí  => mikroarchitektura, kterou programátor nevidí  procesor bez pipeline vykonává jednu instrukci několik cyklů ◦ např. 386 (byť ne že by neměla nic jako pipeline)  pipeline procesoru (486) má sama o sobě možnost vykonávat instrukce paralelně – tj. nezávisle na sobě se snaží vykonávat různé mikroinstrukce ◦ => paralelismus na úrovni instrukcí  ve špičkovém výkonu lze každý cyklus dokončit jednu instrukci

Answer 25

Aby procesor neztrácel čas načítáním instrukcí, snaží se začít vykonávat instrukce už v době, kdy se předchozí instrukce teprve zpracovávají ◦ Dokud procesor nenarazí na podmínku, běží na plný výkon ◦ Jakmile narazí na podmínku, podmíněný skok nebo podmíněný přesun dat, tak si tipne, jak podmínku vyhodnotí  Pokud se nesplete, pokračuje dál jakoby se nic nestalo  Pokud se ale splete, musí vyprázdnit celou pipeline, zahodit výsledky vypočítané po podmínce, vrátit se zpět za podmínku a začít s prázdnou pipeline  => zdržení, a pokud se děje často, pak i významné

Answer 26

Aby se minimalizoval počet podmínek, které procesor špatně odhadne, má Branch Target Buffer, kde si udržuje statistiku o několika posledních podmínkách, se kterými se potkal ◦ Každá taková podmínka má 2-bitové číslo.  Zvyšuje se o 1, pokud byla splněna  Pokud nebyla splněna, sníží se o 1  Počítadlo nepodteče, ani nepřeteče ◦ Pokud se procesor s podmínkou ještě nesetkal, předpokládá, že bude splněna – Static Branch Prediction Algorithm