KIV/PPR Flashcards
Program, programový kód - definice
◦ statický popis výpočetního postupu, tj. co bude počítač provádět
◦ nemá stav
Assembler - definice
◦ 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
Vlákno (fiber, thread, task) - definice
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
Proces - definice
◦ 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
Distribuovaná aplikace - definice
◦ 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
Paralelní výpočet - definice
◦ Buď vícevláknový program,
◦ Nebo distribuovaná aplikace
◦ Nebo kombinace obou
◦ Výpočet je dynamicky strukturován na procesy a vlákna
Paralelní program - definice
◦ Kód je staticky strukturován na podprogramy vláken
◦ Má deklarovaná sdílená data
Interakce + Synchronizace - definice
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í
Symetrický multiprocesor (SMP)
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
NUMA
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
Asymetrický multiprocesor (ASMP)
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
Multiprocesor s distribuovanou pamětí
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
Distribuovaný systém
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í
Vektorový paralelní počítač
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
Flynnova taxonomie
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)
SISD
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
SIMD
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
MISD
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
MIMD
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
SPMD
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
MPMD
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
Složitost sekvenčních vs paralelních algoritmů
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
Cena paralelního algoritmu
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ů
Urychlení - definice
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 :-)
Anomální urychlení
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
Superlineární urychlení
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
Amdahlův zákon
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á
Gustafsonův zákon
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ě
Vliv cache na urychlení
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
Účinnost
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
Karp-Flattova metrika
Metrika určená z naměřených časů
- Vzorečky v přednášce
Škálovatelnost
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
Flow & Logically Correct
(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
Nedeterminismus logicky správného výsledku
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í
Zásady psaní paralelního programu (5x)
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
Debugging paralelních programů
Č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í
Formy interakce
Primitivní
◦ Synchronizace
◦ Sdílení dat
◦ Zasílání zpráv
Strukturované
◦ Monitor
◦ Rendez-vous
Granularita
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
Precedenční graf
◦ 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í
Petriho sítě
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íť
Temporální logika
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}
Paralelizace cyklů - dělení proměných
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é
Redukční proměnná
◦ Nejprve je čtena, pak zapsána
◦ Uvedené se odehraje v jedné iteraci
Uzamykaná proměnná
min:=Items[0];
for i:=1 to High(Items) do
if min
Uspořádaná proměnná
◦ 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.
Out-of-Order Execution
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ě
Registry Renaming
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
Pipeline
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
Speculative Execution
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é
Predikce skoků
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
