42 - Klasifikace a vlastnosti paralelních a distribuovaných architektur Flashcards
Přehled Paralelních architektur, Flynnova klasifikace
• vonNeumann
○ SISD (single instruction, single data) - Konvenční, VLIW (podle slides)
○ SIMD (single instruction, multiple data) § Vektorové procesory § Asociativní procesory § Zřetězené SIMD § Multiple SIMD § Same Program Multiple Data
○ MISD - Zřetezené procesory - Rozdělení úlohy
○ MIMD § VLIW (podle wikipedie) § Zřetězené MIMD § Se společnou sběrnicí § S propojovací sítí § S pevnou sítí
* Data Flow - není von Neumannovská architektura (nemá program a PC), provádí interpretaci grafu toku dat * Redukční
Flynnova klasifikace popisuje pouze Von-Neumannovské architektury (model architektury počítače využívající společnou paměť pro data i instrukce).
Single Instruction Multiple Instruction
Single Data SISD MISD
Multiple Data SIMD MIMD
SISD - konvenční procesory
SIMD - vektorové procesory
MISD - řetězové procesory
MIMD - více procesorů, který každý pracuje na vlastních datech
SISD (Single Instruction Single Data) - Konvenční
VLIW (Very Long Instruction Word)
○ Je procesorová architektura, která umožňuje instrukční paralelismus (vykonávání několik nezávislých instrukcí souběžně)
- Paralelismu je dosaženo sloučením vzájemně nezávislých operací v jeden celek (instrukční paket).
- (CPU tedy nemusí vyhodnocovat časovou návaznost jednotlivých operací a možné kolize. O to (seskupování operací) se už postará kompilátor.)
○ Typické rysy VLIW architektury § Jednotlivé operace (instrukce) jsou seskupeny do instrukčního paketu o stejné délce (až stovky bitů). § Jednotlivé operace v paketu se vykonávají souběžně a jsou vzájemně nezávislé. □ Nicméně pakety (velké instrukce) se vykonávají sekvenčně a CPU má jediný tok řízení. § Větší množství registrů. ○ Jediný tok řízení, který řídí všechny procesory § Instrukce jsou vykonávány sekvenčně ○ Každá instrukce - samostatné pole s operačním kódem pro všechny procesory ○ Instrukce také určují, jak probíhá komunikace mezi procesory. Jsou v nich uloženy informace o odesílateli, příjemci a velikosti dat - Tyto informace s ohledem na časování generuje kompilátor § Kompilace spočívá v skládání VLIW instrukcí z několika jednoduchých instrukcí - v nejlepším případě budou pracovat všechny procesory, v nejhorším jen jeden (kolize, čekání na mezivýsledek,..) ○ Výhody: § Jednoduchý hardware (CPU neprovádí žádné triky jako out-of -order execution v Core i7, heavylifting tady udělá již samotný kompilátor) § Dobře škálovatelný ○ Nevýhody: § Podmíněné skoky (když jedna instrukce skočí, ostatní mají problém) § Instrukce v jednom kroku nemohou navzájem používat své výsledky § Odhad závislostí v době překladu (např. kompilátor nemůže vědět jak dlouho bude trvat přístup do paměti - jestli nebude zrovna HIT nebo MISS v cache, atd.) □ Toto může snížit efektivitu, jelikož kompilátor nemůže dělat moc optimistické odhady (NOP instrukce (no operation)). § VLIW nejsou často zpětně kompatibilní. § Neustálý vývoj výrobních technologií a vnitřních struktur procesorů způsobuje změny v časování některých instrukcí, změny ve výpočetních jednotkách i v počtu univerzálních registrů.
VLIW a superskalární procesory
- VLIW se nachází někde mezi statickými a dynamickými superskaláry
Superskalarita umožňuje v jednom taktu zpracovat více strojových instrukcí zároveň, protože některé části procesoru jsou duplikovány
- například matematický koprocesor (FPU) nebo aritmeticko-logická jednotka (ALU)
Statické superskalární procesory
- zpracovávají sekvenční program na více procesorech in-order, takže paralelnost je jen za souběhu správných instrukcí.
- (Zpracovávají více instrukcí paralelně ale v programovém pořadí)
Dynamické superskalární procesory
- zpracovávají sekvenční program na více procesorech out-of-order, např. spekulativní výpočty za skokem.
- (Zpracovává více instrukcí paralelně i mimo programové pořadí)
SIMD (Single Instruction Multiple Data) - Vektorové (Např. použité v moderních grafických kartách)
• Výhody:
○ Jednodušší než MIMD (jednoduchá implementace)
○ Menší nároky na paměť
○ Odpadá režie se složitou synchronizací mezi procesy, která je u MIMD
○ Rychlejší komunikace mezi procesory než u MIMD
• Nevýhody:
○ Ne všechny problémy jsou datově paralelizovatelné
○ Propad výkonu u programu s mnoha podmíněnými skoky
○ Nevhodné pokud máme malý počet procesorů
○ Vyžadují ne úplně běžné procesory
§ Vektorové procesory - paralelně se provádí stejná instrukce na n procesorech a n částech vstupních dat (MMX, SSE)
• Další varianty
○ Multiple SIMD (MSIMD) - více kontrolních jendotek procesory se dynamicky přidělují
○ Same Program, Multiple Data (SPMD) - procesory provádí stejný program, ale zcela nezávisle (žádná synchronizace)
- Se společnou pamětí (přístup ke všem modulům (pamětím) je stejně rychlý, problém je současná práce více procesorů s jedním modulem)
- S oddělenou pamětí (každý procesor pracuje se svým pam. modulem (práce s lokálními daty je rychlejší než s globálními))
MISD (Multiple Instruction Single Data) - Řetězové/zřetězené
• Lineárně propojené procesory -> pipeline
• Řešení úloh s proudovým charakterem
○ Data procházejí postupně jednotlivými procesory
○ Rozdělení úlohy -> data se předají několika procesorům, každý procesor provede nějakou část výpočtu
§ Např.: Ověření prvočísla se provede tak, že se číslo předá x procesorům a každý z nich vyzkouší dělení určitou skupinou dělitelů.
MIMD (Multiple Instruction Multiple Data)
• Multiprocesory (sdílená pamět)
- všechny procesy mají přístup do společného paměťového prostoru
- řešení současného přístupu k jedné buňce paměti:
» Exclusive-read, Exclusive-Write (EREW)
» Concurrent-Read, Exclusive-Write (CREW)
» Exclusive-Read, Concurrent-Write (ERCW) - nedava smysl :)
» Concurrent-Read, Concurrent-Write (CRCW)
- > multitasking - 1 cpu, přepínání kontextu, virtuální procesory
- > sdílená paměť - CPU mají svou cache, zbytek na sběrnici (boj), předávání zpráv může být v HW nebo simulace SW, těsně vázané
• Multicomputery (předávání zpráv) - Distribuované systémy
○ každý procesor má svou vlastní paměť
○ každý procesor má svůj adresový prostor
- > virtuální sdílená paměť - all chache, spojení caches komunikačními kanály, navenek se tváří jako jediný adresový prostor (CPU má svou paměť, ale je virtuálně spojena v simulovanou sdílenou, opět HW/SW simulované zasílání zpráv )
- > předávání zpráv - volně vázaná architektura, pořítačové sítě, propojeny pouze procesory, sdílená paměť simulovaná SW
Data Flow architektura
INTERPRETACI GRAFU TOKU DAT
• Řízena tokem dat (program převeden na graf toku dat, který je následně interpretován)
• Není von Neumannovská architektura - nemá program ani PC (Program counter)
• Provádí INTERPRETACI GRAFU TOKU DAT
• Jde o orientovaný graf
○ Uzly představují instrukce
○ Hrany představují datové závislosti mezi instrukcemi
- Operace se provede (firing) když má na vstupu všechny operandy
- Paralelismus spočívá v několika operačních jednotkách, které vybírají události a pouští je grafem.
- Potenciální problém: pokud se na jedné hraně objeví dvě události, mohlo by dojít k přehození pořadí
Dataflow procesor
- Graf toku dat je uložen v paměti aktivit
Redukční architektura
Stromová architektura
* Redukce - náhrada části výrazu jeho významem (2 * 3 -> 6) - možnost provádět paralelně * Používá se stromová architektura (Program se převede na strom a po zadání hodnot se strom redukuje až na jeden uzel výsledek)
= Redukce - náhrada části výrazu jeho významem (2 * 3 -> 6)
Používá se stromová architektura
Příklad: Výraz: (x*y)+(x-y) Zapíšeme: +)(-)> - sekvence Redukce pro x=3 y=2: \+)(-<3 2>)> \+< 6 1 > 7
Additional - Kvantové počítače a granularita paralelismu
Kvantové počítače
• Může dosáhnout exponenciálního zrychlení.
• Pro řešení problému s N možnostmi potřebujeme pouze 〖log〗_2N Q-bitů.
○ Můžeme použít kvantový jev, který může zkolabovat do dvou stavů - např. spin, nebo polarizaci fotonů.
• Kvantový počítač nelze jen tak debugovat, došlo by totiž ke kolapsu kvantového stavu.
• Pracuje se s pravděpodobností.
• Je tedy vhodné výsledek ověřit.
Granularita paralelismu
1. Uvnitř instrukcí (nejjemnější) 2. Mezi instrukcemi (některé instrukce se provádějí paralelně) 3. Mezi příkazy (vektorové počítače, koprocesory (FPU)) 4. Mezi vlákny (mezi bloky procesu) 5. Mezi procesy (zpravidla nemají sdílenou paměť, mohou být odděleně kompilovány)
