KIV/PPR

Question 1

Program, programový kód - definice

Answer 1

◦ statický popis výpočetního postupu, tj. co bude počítač provádět
◦ nemá stav

Question 2

Assembler - definice

Answer 2

◦ Překladač do strojového kódu cílového procesoru
◦ I když formálně nesprávně, používá se i k označení jazyka symbolických adres, ve kterém budou některé ilustrativní příklady
 x86/x86-64
◦ dokud neuvidíte, do čeho vlastně procesor nutíte, neznáte skutečné náklady kódu ve vyšším jazyku

Question 3

Vlákno (fiber, thread, task) - definice

Answer 3

Thread - v kernel space, nejmenší jednotka plánovatelná schedulerem - preempitvní

Fiber - v user space, jejich vykonání není řízeno kernelem, naopak je samořízeno, fiber je přeplánován jen po zavolání yield - kooperativní

Task - Linux nedělá rozdíly mezi vláknem a procesem, vše je pro něj runnable task

◦ vykonávaný programový kód
◦ tj. aktivita v čase, která má svůj stav, který je určen
 aktuálním místem v programu (CS:RIP),
 obsahem registrů procesoru
 a obsahem zpracovávaných dat
◦ vlákno v jednom časovém okamžiku běží pouze na jednom procesoru

Question 4

Proces - definice

Answer 4

◦ Dynamická kolekce vláken => má stav daný vlákny
◦ Vždy obsahuje alespoň jedno vlákno, které vytvořil operační systém/interpret (např. JVM)
◦ Vlastní prostředky, které operační systém/interpret přidělil důsledkem činnosti některého vlákna
◦ Vlákna jednoho procesu mohou běžet současně, je-li k dispozici více než jeden procesor

Question 5

Distribuovaná aplikace - definice

Answer 5

◦ Několik spolupracujících procesů
◦ Obvykle jsou distribuovány na uzly počítačové sítě
 Jeden uzel má n procesorů
◦ V extrémním případě mohou být na jednom uzlu
 Dříve, kdy ještě platilo 1 proces = 1 vlákno, se
spouštělo několik instancí jednoho programu

Question 6

Paralelní výpočet - definice

Answer 6

◦ Buď vícevláknový program,
◦ Nebo distribuovaná aplikace
◦ Nebo kombinace obou
◦ Výpočet je dynamicky strukturován na procesy a vlákna

Question 7

Paralelní program - definice

Answer 7

◦ Kód je staticky strukturován na podprogramy vláken

◦ Má deklarovaná sdílená data

Question 8

Interakce + Synchronizace - definice

Answer 8

 Interakce
◦ Spolupráce na úrovni vláken uvnitř procesů
◦ Spolupráce na úrovni procesů distribuované aplikace
◦ Výměna informací

 Synchronizace
◦ Forma interakce
◦ Zajištění správné návaznosti operací

Question 9

Symetrický multiprocesor (SMP)

Answer 9

 Všechny procesory jsou identické
 Vlákno může být alokováno na libovolný procesor
 Pro plánovač OS je to jednodušší, než kdyby se procesory významně lišily
 Front-Side Bus
◦ procesory sdílejí jednu sběrnici pro IO a paměť – uzké hrdlo
 Point-To-Point
◦ Jednotlivé procesory jsou spojené přímo - odstraněné problému Front
Side Bus
◦ Hyper Transport Consortium (AMD)
◦ Intel QuickPath

Question 10

NUMA

Answer 10

 Non-Uniform Memory Access
 DSM – Distributed Shared Memory
 Další pokus o vylepšení škálovatelnosti, kde jedna sběrnice SMP systémů představuje limit
◦ Existuje několik sběrnic, které jsou vzájemně propojené
 Zavádí pojem lokální a vzdálené paměti
 Každý procesor má svůj „kus“ paměti
 Doba přístupu do paměti procesorem se může lišit, podle toho, kde paměť fyzicky je => non-uniform
 Problém, když proces odmigruje příliš daleko na jiný procesor

Question 11

Asymetrický multiprocesor (ASMP)

Answer 11

 Kromě sdílené paměti, každý procesor má vlastní lokální paměť a vlastní připojení I/O
◦ Každý procesor může mít jinou instrukční sadu
 V extrémním případě na každém z nich běží jiný OS
 OS nemůže alokovat libovolný proces na libovolný
procesor
 Jednotlivé procesory mohou vykonávat specifické úkoly
 Sdílená paměť může obsahovat pouze minimum dat
◦ Minimalizace úzkého hrdla sběrnice

• Buď integrovaná v procesoru -> část paměti vyhrazenu GPU část CPU
• Nebo dedikovaná -> má svojí paměť, výměna přes DMA

Question 12

Multiprocesor s distribuovanou pamětí

Answer 12

 Každý procesor má svou lokální paměť, sdílná paměť není
 Každý uzel je v podstatě počítač s omezeným I/O
 Komunikuje se zasíláním zpráv
 Typické topologie jsou 2D cyklicky uzavřené mřížky, nebo n-rozměrná krychle
 Výhodou je odstranění jedné sběrnice jako úzkého hrdla
 Nevýhodou je však malá univerzálnost – výkonnost záleží na způsobu alokace procesů na uzly a použitém komunikačním schématu
 Vhodné např. pro tzv. pipe-lines
 Transputery - Occam

• Není stejné jako dedikovaná karta
• Více počítačů, komunikace po síti

Question 13

Distribuovaný systém

Answer 13

 De facto počítačová síť, která se může tvářit jako jeden stroj
 Dědí problémy multiprocesoru s distribuovanou pamětí
 Každý uzel je plnohodnotný počítač, na kterém může běžet několik procesů zároveň
 Např. cluster
◦ Počítače propojené velmi rychlou lokální sítí

Question 14

Vektorový paralelní počítač

Answer 14

 Provádějí operace s vektory čísel na úrovni instrukcí
strojového kódu
 Dříve doména superpočítačů jako Cray-1, dnes např.:
◦ MMX (Intel) – Matrix Math eXtension?
◦ SSE1-5 (Intel, AMD) – Streaming SIMD Extensions
◦ 3DNow! (AMD)
◦ AVX, AVX2, AVX-512 (Intel) – Advanced Vector Extensions
◦ AltiVec (IBM, Apple, Motorola)

• Vektorová instrukce = operace nad několika vektory místo čísly

Question 15

Flynnova taxonomie

Answer 15

Single Data + Single Instruction = SISD
Single Data + Multiple Instruction = MISD
Multiple Data + Single Instruction = SIMD
Multiple Data + Multiple Instruction = MIMD

 Uvedené jsou čtyři základní klasifikace podle Flynna
◦ Počet konkurenčně prováděných instrukcí
 A někdy nesprávně používanému „programů“, např. SPMD, což ale není formálně správně právě podle Flynna
◦ Počet existujících dat (Data Streams)

Question 16

SISD

Answer 16

Základní sériový přístup
Jeden princ, jedna princezna atp.

Urychlení:
◦ Turbo Boost – jestliže má procesor sníženou spotřebu energie a teplotu pod limity dané výrobcem, procesor dokáže dočasně zvýšit pracovní frekvenci a tím i výkon
◦ Využití jenom jednoho jádra to umožňuje

Question 17

SIMD

Answer 17

Viz vektorový paralelní počítač

 SIMT – Single Instruction, Multiple Threads
◦ Ta samá instrukce je zároveň provedena na několika procesorových jádrech
 Thread of SIMD Instructions
◦ Např. GPGPU, když se vlákna povede správně naplánovat
 Cílem je redukovat režii načítání identického kódu pro několik jader
(NVIDIA marketing)

Urychlení:
urychlení odpovídá velikosti vektoru, tj. počtu jeho prvků
◦ Analogicky SPMD a SIMT

Question 18

MISD

Answer 18

 Multiple Instruction (Program), Single Data Stream, linerání urychlení
 Instruction: Používá se v tzv. Pipeline architektuře
◦ několik procesů zpracovává data v jednom datovém proudu
◦ Např. instrukční pipeline procesoru nebo analogicky montážní linka v továrně
 Program: Používáno pro výpočty odolné proti poruchám (Fault Tolerant)
◦ Několik různých systémů zpracovává ty samá data a musejí se shodnout na výsledku – např. řízení letu raketoplánu, letadla, atd. – jedno o urychlení, ale o odolnost proti chybám

• Každá činnost dedikovaná jednotka, můžou jet paralelně
• Instrukce rozdělena na mikroinstrukce
• Analogie na výrobním pásu
• Urychlení x Redundance

Urychlení:
◦ Pipeline urychlení se může blížit počtu serverů v pipeline
◦ V případě fault-tolerant se výpočet neurychluje, ale duplikuje

Question 19

MIMD

Answer 19

 Procesory pracují asynchronně a nezávisle na sobě
 Procesory buď mají sdílenou paměť,
◦ Programátorovi snáze srozumitelný přístup
◦ O zajištění integrity dat se stará OS
 nebo distribuovanou
◦ má lepší škálovatelnost
 Distribuovaný systém – viz výše i dále
 MIMD programy lze odladit i na jednom počítači
◦ Virtualizace jednoho procesoru pro sdílenou paměť
◦ localhost a pro distribuovanou paměť
◦ Samozřejmě, některé chyby takto mohou uniknout, protože se neprojeví díky jinému komunikačnímu zpoždění, nebo díky virtualizaci jednoho procesoru, kdy žádná dvě vlákna neběží současně

 MIMD – dále se dělí na
◦ SPMD – Single Program, Multiple Data Streams
◦ MPMD – Multiple Program, Multiple Data Streams
 Používají se termíny funkční a datový paralelismus

Urychlení:
◦ Záleží na datech, programu i hw
◦ Je třeba odměřit a spočítat

Question 20

SPMD

Answer 20

 Single Program, Multiple Data Streams
 Několik procesorů autonomně vykonává jeden program nad různými daty
 Bod vykonávání programu nemusí být na všech procesorech stejný
 Označuje se též jako dekompozice dat
 Používá se ke zpracovávání velkých objemů dat
◦ k procesů běžících podle stejného programu zpracovává strukturně stejná, ale hodnotově různé části dat
◦ např. násobení matic – každý prvek, řádek, či sloupec matice lze spočítat jedním procesem/vláknem
 Sleduje se čistě výkonnostní hledisko
 Předpokládá se, že každý z procesorů je schopen vykonávat ten samý program

Question 21

MPMD

Answer 21

 Multiple Program, Multiple Data Streams
 Několik procesorů autonomně vykonává více než jeden program nad různými daty
 Např. farmer-worker, kdy jeden proces úkoluje ostatní
 Nemusí jít nutně pouze o urychlení výpočtu
◦ Může jít o aplikaci, kdy se každý proces stará „o to svoje“ a zároveň spolupracuje s ostatními
◦ Např. Cisco IOS – síť A s OSPF, síť B s EIGRP, border router vyplní směrovací tabulku podle obou
 Dist. Simulace – systém spolupracujících komponent

Question 22

Složitost sekvenčních vs paralelních algoritmů

Answer 22

 Maximální doba výpočtu algoritmu pro všechny možné kombinace vstupních dat

 O(n) = n
◦ složitost sekvenčního algoritmu, která je lineárně závislá na n počtu prvků
◦ např. součet čísel

 Paralelní součet na p = n/2 procesorech má složitost O(log n)
◦ Logaritmus s libovolným základem

Question 23

Cena paralelního algoritmu

Answer 23

 Složitost vzhledem k počtu použitých procesorů
◦ Kolik celkového strojového času, tj. všech použitých procesorů, výpočet spotřebuje
◦ Např. (log n)*n/2

 Je úměrná celkovému strojovému času všech použitých procesorů

Question 24

Urychlení - definice

Answer 24

Poměr doby výpočtu referenčního algoritmu a
porovnávaného algoritmu
◦ Např. nejlepšího známého sekvenčního algoritmu a paralelního algoritmu na témže (paralelním) počítači
 Lze ovšem porovnat i urychlení referenčního sekvenčního algoritmu oproti provedené optimalizaci
 Anebo porovnat dva různé paralelní algoritmy
 S(p) = E(1) / E(p)
◦ >1 znamená urychlení
 Perfektní urychlení
 Poměr je přesně roven počtu procesorů
◦ Asi těžko ho dosáhnete :-)

Question 25

Anomální urychlení

Answer 25

 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

Question 26

Superlineární urychlení

Answer 26

 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

Question 27

Amdahlův zákon

Answer 27

 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á

Question 28

Gustafsonův zákon

Answer 28

 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ě

Question 29

Vliv cache na urychlení

Answer 29

 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

Question 30

Účinnost

Answer 30

 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

Question 31

Karp-Flattova metrika

Answer 31

Metrika určená z naměřených časů

- Vzorečky v přednášce

Question 32

Škálovatelnost

Answer 32

 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

Question 33

Flow & Logically Correct

Answer 33

 (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

Question 34

Nedeterminismus logicky správného výsledku

Answer 34

 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í

Question 35

Zásady psaní paralelního programu (5x)

Answer 35

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

Question 36

Debugging paralelních programů

Answer 36

 Č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í

Question 37

Formy interakce

Answer 37

 Primitivní
◦ Synchronizace
◦ Sdílení dat
◦ Zasílání zpráv

 Strukturované
◦ Monitor
◦ Rendez-vous

Question 38

Granularita

Answer 38

 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

Question 39

Precedenční graf

Answer 39

◦ 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í

Question 40

Petriho sítě

Answer 40

 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íť

Question 41

Temporální logika

Answer 41

 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}

Question 42

Paralelizace cyklů - dělení proměných

Answer 42

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é

Question 43

Redukční proměnná

Answer 43

◦ Nejprve je čtena, pak zapsána

◦ Uvedené se odehraje v jedné iteraci

Question 44

Uzamykaná proměnná

Answer 44

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

Question 45

Uspořádaná proměnná

Answer 45

◦ 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.

Question 46

Out-of-Order Execution

Answer 46

 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ě

Question 47

Registry Renaming

Answer 47

 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

Question 48

Pipeline

Answer 48

 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

Question 49

Speculative Execution

Answer 49

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é

Question 50

Predikce skoků

Answer 50

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