Úvod do paralelních systémů 1. část
FIT VUT v Brně
Obsah • •
Paralelní přístup z pohledu praxe Technologické důvody pro zavedení paralelismu – Proč nestačí jedno jádro?
•
Moderní procesory – přehled vývoje architektur – – – – –
•
Skalární Superskalární Koncept SIMD – vektorové instrukce, MMX, SSE,… Architektura VLIW Vícevláknové zpracování
Paralelní a distribuované systémy – Základní koncepty architektury – Propojovací sítě a topologie – Vliv architektury paralelního systému na výkonnost
•
Masivně paralelní architektury - GPU – Využití grafických čipů pro obecné výpočty (GPGPU)
Podrobně je problematika paralelních systémů probírána v magisterských kurzech: Architektura procesorů Architektura a programování paralelních systémů Paralelní a distribuované algoritmy 2
Proč paralelní přístup? • Paralelní přístup je nutný pro řešení složitých úloh, které vyžadují vysoký výpočetní výkon. – paralelní počítání (na vhodně propojených počítačích běží paralelní algoritmus)
• Stávající technologická omezení nutí pro zajištění co nejvyšší výkonnosti používat paralelní přístup na všech úrovních (dat, instrukcí, vláken atd.) – Jednoprocesorové systémy potřebují k navýšení výkonnosti neúměrně vysoký příkon. – Vícejádrové procesory poskytují pro daný povolený příkon vyšší výkonnost.
3
Moorův zákon a výkonnost procesorů •
Dříve (~ do 2005): výkonnost procesorů rostla zejména díky možnosti zvyšování pracovní frekvence a miniaturizaci tranzistorů – –
•
Možnost implementovat složitější, sofistikovanější HW Rostoucí složitost a frekvence však vyžaduje vyšší příkon
Současnost: roste složitost, ale příkon (frekvenci) už příliš zvyšovat nelze (CMOS) –
Vyšší výkonnost lze dosáhnout zvýšením stupně paralelismu
Zdroj: International Solid-State Circuits Conference, 2013 4
Technologické limity • • • •
Frekvenci f nelze zvyšovat nad jistou mez => problém s odvedením tepla Jaká je rozumná mez pro příkon? Dnešní procesory mají cca 100 W·cm-2 Při snížení Vdd je nutné snížit frekvenci (CMOS) – min. Vdd je cca 0,5V Dynamická kapacita C – přibližně odpovídá počtu tranzistorů a jejich aktivitě
1000
P C Vdd f 2
Atomový reaktor
W/cm2
100 Pentium III
Horká plotna
P Vdd
Pentium II
10
Pentium Pro i386
1 1,5µ
Pentium
3
Na příkon má největší vliv Vdd.
i486 0,07µ
[Pollack, F. J. : “New microarchitecture challenges in the coming generations of CMOS process technologies“, http://research.ac.upc.edu/HPCseminar/SEM9900/Pollack1.pdf]
5
Příkon vs. výkonnost • Příkon roste úměrně složitosti • Pollackovo pravidlo (empirické) – Efektivní (užitečná) výkonnost procesorů je přibližně úměrná druhé odmocnině jejich složitosti – 2x více tranzistorů => jen 1,4x vyšší výkonnost
výkonnost
1000 příkon CPU (W)
1.4x
Neudržitelné!
100
10
příkon
1990 1995 2000 2005 2010 2015 6
Trendy v oblasti vývoje výpočetních systémů Zdroj: International Solid-State Circuits Conference, 2013
• Redukce příkonu (snižování Vdd a frekvence) => snížení výkonosti • Kompenzace v podobě zvýšení stupně paralelismu • CLOCK: IBM System Z: 5,7 GHz, 2,75 mld. tranzistorů • CORE: 24-jádrový procesor, Fudan University, Shanghai 7
Trendy v oblasti vývoje výpočetních systémů International Technology Roadmap for Semiconductors, www.itrs.net
• Předpovědi vývoje různých parametrů v oblasti polovodičů a jejich aplikací
Předpověď 2008 Předpověď 2011
Předpověď 2008 Předpověď 2011 Zdroj: ITRS 2011 Executive Summary, www.itrs.net
8
Měření výkonnosti • Skalární procesory Výkonnost = f / (CPI x 106) [MIPS] CPI – Clocks Per Instruction - Př. CPI = 2 znamená, že v každém druhém taktu je dokončena instrukce (obvykle se CPI uvádí jako průměrná hodnota)
• Superskalární, vícejádrové procesory Výkonnost = f x IPC IPC – Instructions Per Clock - Př. IPC = 4 znamená, že je možné dokončit 4 instrukce v každém taktu (obvykle se IPC uvádí jako průměrná hodnota)
• Požadujeme – Co nejvyšší výkonnost za rozumnou cenu (počet tranzistorů a příkon).
9
10
11
Power ~ (1+0,2)3
12
Power ~ (1+0,2)3
Power ~ (1-0,2)3
13
14
Příklad z praxe: Nižší příkon při zvýšení výkonnosti • Systém: řízení a zpracování dat v FPGA pro inteligentní kameru • Stávající řešení – FPGA, napájecí napětí 1,8 V, pracovní frekvence 100MHz, 150nm CMOS technologie
• Technické řešení – Pracovní frekvence je snížena úměrně napájecímu napětí na 1,2V/1,8 V × 100MHz = 66 MHz – Příkon nové jednotky
Pnew 90 / 150 (1,2 / 1,8) 2 66 / 100 0,176 P – Výpočetní jednotka je 3× replikována
• Nové řešení – FPGA, napájecí napětí 1,2 V, 90nm technologie (menší parazitní kapacity), větší čip (díky novější technologii výroby) – Cena nového FPGA je prakticky stejná
• Výsledný obvod - odhad – Dvojnásobná výkonnost 3 × 66 MHz = 198 MHz oproti původním 100 MHz – Poloviční příkon
Popt 3 Pnew 3 0,176 P 0,528 P 15
Paralelní zpracování v procesorech • Funkční paralelismus – paralelismus na úrovni instrukcí (ILP – Instruction level Parallelism) • řetězení ~ překrývající se zpracování instrukcí • vícecestné zpracování
– paralelismus na úrovni vláken (TLP – Thread Level Parallelism)
• Datový paralelismus – provádění stejných operací nad různými daty (MMX, SSE) – vektorový procesor - opakované využití funkčních jednotek a překrytí operací v čase
16
Klasifikace procesorů • Architekturu procesoru charakterizují parametry: – m - počet instrukcí, které se v jednom okamžiku vydávají ke zpracování – r - počet současně prováděných (rozpracovaných) instrukcí
• Subskalární procesory (von neumannovské) r = 1, m = 1 – doba provádění programu je součtem dob trvání jednotlivých instrukcí. – nová instrukce může být vydána až po té, co je zpracována předchozí.
• Skalární procesory r>1, m=1 – využívají řetězené zpracování instrukcí, kdy je v každém taktu vydávána maximálně jedna instrukce, ale současně jich může být rozpracováno několik.
• Superskalární procesory r>1, m>1 – vydávají k zpracování více než jednu instrukci v jednom taktu – současně je rozpracováno několik instrukcí
• Další charakteristika – Vícevláknové procesory - několik vláken je prováděno na 1 CPU – Vícejádrové procesory – více vláken na několika CPU – Vektorové procesory, VLIW atd. 17
Klasifikace vybraných procesorů • Subskalární – 4004, 8008
• Skalární – 8086, 80286, 80386, 80486
• Superskalární – Intel Pentium 1-4, AMD Opteron,…
• VLIW – Itanium, Itanium 2
• Vícejádrové (superskalární) – – – – –
Core Duo, Core 2 Duo, Core 2 Quad core i3, Core i5, Core i7 and Core i9 Pentium D, 2 single-core dies packaged in a multi-chip module. Pentium Dual-Core, a dual-core processor. Xeon dual-, quad- and hexa-core processors
18
Superskalární procesory • m-cestný (řetězený) procesor – Dovoluje vydávat v jednom taktu až m instrukcí. – Podporuje řetězené zpracování instrukcí, kdy se využívá několik paralelně pracujících linek (paralelní načítání, paralelní dekódování instrukcí atd.) – Mezi stupni řetězené linky jsou vícemístné buffery namísto registrů. – Data-flow zpracování - rozpracované instrukce, které čekají na operandy, je možné odložit do bufferu a probudit je, až budou operandy připraveny.
• Procesor má tři části – Načtení/dekódování/rozesílání (pořadí instrukcí dodrženo) – Provedení instrukcí v paralelně pracujících linkách (instrukce mohou být provedeny mimo pořadí) – Dokončení (podle pořadí)
• Charakteristika – – – –
Dynamické plánování instrukcí Provádění instrukcí mimo pořadí Spekulativní provádění skoků Pokročilé řešení konfliktů ILP – přejmenování registrů (HW podpora), přeskládání instrukcí, pokročilý přístup do cache atd. 19
Př. Intel Pentium (1993)
Advanced Programmable Interrupt Controller
http://en.wikipedia.org/wiki/Pentium
Bus width 64 bits System bus clock rate 60 or 66 MHz Address bus 32 bits Addressable Memory 4 GB Virtual Memory 64 TB Superscalar architecture Runs on 5 volts 16 KB of L1 cache U and V pipeline (m=2)
20
Intel Pentium 4 - mikroarch. NetBurst BTB (4k entries)
I-TLB/Prefetcher
Trace Cache BTB (512 entries)
64 bits
IA32 Decoder
Code ROM
Execution Trace Cache
op Queue
Allocator / Register Renamer Memory op Queue Memory scheduler
INT / FP op Queue
64-bit System Bus Quad Pumped 400M/533MHz 3.2/4.3 GB/sec BIU
Fast Slow/General FP scheduler Simple FP
INT Register File / Bypass Network
FP RF / Bypass Ntwk
U-L2 Cache FP FP AGU AGU 2x ALU 2x ALU Slow ALU 256KB 8-way Move Simple Simple Complex MMX Ld addr St addr 128B line, WB Inst. Inst. Inst. SSE/2 48 GB/s 256 bits L1 Data Cache (8KB 4-way, 64-byte line, WT, 1 rd + 1 wr port) @1.5Gz 21
Superskalární procesory • Superskalární přístup dosáhl svých mezí – Výkonnost = IPC x f – IPC a f [MHz] jdou proti sobě! • Vysoký IPC (až 6) => složitý HW => nízká f • Vysoká f => jednodušší HW => nízké IPC
– Pro m > 4-8 již většinou nemá smysl (zrychlení je <3x) – Zvyšování f je nevýhodné z hlediska příkonu - plánované projekty superskalárních procesorů s vysokými kmitočty (9,2 GHz a10,2 GHz firmy Intel) byly opuštěny pro vysoký příkon
• Další vývoj: VLIW, vícevláknové procesory, vícejádrové procesory
22
Př. Pentium 4 (2000), mikroarchitektura NetBurst • • • • • • • • •
stupňů linky: 20 (až 31) rozpracováno až 126 instrukcí Branche Target Buffer (BTB) 4096 pol. Trace cache 12K (místo I-cache) L1 D-cache: 8 kB, Load: 2 takty L2 cache: 256 kB, 256 bitů SSE2 – viz dále hyperthreading – viz dále externí přenosy QDR (Quad Data Rate): s 200 MHz dosáhne 6,4 GB/s.
• Pozn.: Nástupcem NetBurst je od r. 2006 Core 2 (dvoujádrový procesor s nižším příkonem) 23
Intel Core 2
Sdíleno!
http://en.wikipedia.org/wiki/Intel_Core_(microarchitecture)
24
VLIW = Very Long Instruction Word • • •
•
•
•
Používá několik nezávislých funkčních jednotek (např. 2 x FX, 2 x FP, 2 x L/S) pracujících synchronně Existuje mnoho bran čtení a zápisu u souboru registrů FX a FP i paměti. Kompilátor sbalí pevný počet instrukcí do jedné VLIW instrukce o délce 64 -128 bitů a víc; sbalené instrukce nemusí být v původním pořadí. Kompilátor plánuje instrukce staticky (oproti superskalárním procesorům) v době kompilace a určuje, které instrukce mohou běžet paralelně, a zahrne tuto informaci do strojové instrukce VLIW. Operace specifikované ve VLIW musí být nezávislé na sobě navzájem i na předchozích VLIW. Když nelze naplánovat plný počet instrukcí, doplní se instrukce NOP. Dílčí instrukce z nezávislých skupin jsou vydávány a prováděny paralelně, v každém taktu jedno VLIW.
25
Př. VLIW: Intel Itanium 2 (IA-64) • • • • • • • • •
1,5 (1,7) GHz, 130 W, 1,3 V, proces 130 nm Jednotky: 2 x store, 2 x Load, 4 x MMX, 4 x FP, 6 x FX L1 I-cache, D-cache: 4-cestná, 16 kB, write-through L2 cache 256 kB, 8-cestná, write-back, sjednocená L3 cache: 6 MB, 24-cestná, write-back, také na čipu ! 128 registrů FX (65 bit), 128 registrů FP + MMX (82 bit) 8 registrů cílových adres nepřímých skoků (branch register) Sběrnice 128 datových bitů @ 400 MHz = 6,4 GB/s (oproti 2,1 GB/s u Itania).
26
Vývoj moderních mikroarchitektur AMD 2011
2012
2013
2014
www.anandtech.com 27
Př.: mikroarchitektura AMD Piledriver (2012)
http://www.xbitlabs.com/hot-topics/amd-piledriver 28
Vektorové procesory • •
• •
Procesor obsahuje vektorovou jednotku, která pracuje souběžně se skalární; Každý takt končí operace s jedním prvkem vektoru, operace na prvcích vektoru jsou datově nezávislé. Je nutný vektorizující kompilátor schopný účinně konvertovat skalární kód na vektorový. Použití: vědecké výpočty
Procesor VDLX (modifikace DLX) Na obrázku má pole VRF (vector register file) 8 vektorových registrů, 16 bran čtení a 8 bran zápisu; každý registr obsahuje 64 prvků, 64 bitů / prvek. 29
Vektorové procesory • Dosažitelné zrychlení za použití vektorové jednotky je závislé na části kódu, který je převoditelný na vektorové instrukce. • Příklady vektorových instrukcí: – – – –
addv v3, v1, v2 lv v1, r1 ; načti vektor z paměti do registru v1; adresa 1. prvku je v r1 lvi v1,(r1+v2) ; načti vektor podle indexů ve vektoru v2, adresa prvku je r1 + v2(i): s**v v1,v2 ; nastav 64-bitový registr masky VM (Vector Mask) podle relace ** (eq, ne, gt,...) mezi prvky v1 a v2 – Další: Vektorová redukce (např. součet/max/min/průměr položek ve vektoru), skalární součin atd.
Paralelně pracující sčítačky nebo zřetězená sčítačka
30
Instrukce MMX • •
Podpora multimediálních instrukcí v procesorech Intel (od Pentia II) Zavedeny nové sbalené (packed) datové typy – malé datové prvky (8-bitové pixely, 16- bitové vzorky zvuku,...) jsou sbaleny dohromady do jednoho 64-bitového slova
•
Zavedeny nové instrukce (57), které pracují se všemi datovými prvky paralelně (styl SIMD) – výkonnost zlepšena 3-5krát pro vnitřní smyčky, 1,5 – 2 krát pro celé programy – plná kompatibilita s existujícími mikroprocesory Intel (OS a SW)
•
Registry MMX – 64-bitové registry MMX (MM0 - MM7) jsou mapovány na registry FP - jsou identické s dolní částí 80-bitových registrů FP – při zápisu do registrů MMX je bit 64 až 79 nastaven na 1 (NaN, Not a Number) – do souboru registrů MMX je možný náhodný přístup!
•
Aplikace nemohou používat registry FP současně pro FP a MMX data a kód musí být rozdělen na části FP a MMX.
31
MMX
32
SIMD: Instrukce SSE • Další rozšíření intelovské architektury IA (od Pentia III) je SSI (SIMD Streaming Instructions, proudové instrukce SIMD). – Přidány nové 128b registry (XMM) a instrukce
• V tomto rozšíření mohou registry o velikosti 128 bitů uchovávat několik čísel FP, na kterých se provádějí paralelní operace FP ve stylu SIMD. • Cenou za toto další rozšíření je navýšení plochy proti Pentiu II o 10%, zvýšení výkonnosti však činí až 62% (3D grafika) nebo 29% (MM). • SSE2, SSE3, SSSE3, SSE4 – další vylepšení • AVX – 256-bitové registry, v budoucnu až 1024 bitů
33
Instruction Level: Intel® SSE SSE Operation
In Each Core
(SSE/SSE2/SSE3) SOURCE
Single Cycle SSE
DECODE
127
0
X4
X3
X2
X1
Y4
Y3
Y2
Y1
X4opY4
X3opY3
X2opY2
X1opY1
X2opY2
X1opY1
SSE/2/3 OP
DECODE
DEST
Core™ arch CLOCK CYCLE 1
EXECUTE
EXECUTE
Previous CLOCK CYCLE 2
Perf Energy
CLOCK CYCLE 1
X4opY4
X3opY3
SIMD instructions compute multiple operations per instruction *Graphics not representative of actual die photo or relative size
34
Multivláknové procesory • Vlákno (thread) je posloupnost instrukcí vyžadující určitý adresový prostor a čas CPU. Vlákna jsou (oproti procesům) lehká, přepnutí kontextu je rychlejší, kopíruje se méně dat. • Vlákna tvořená v rámci procesu sdílí jeho adresový prostor a další prostředky – kód, hromadu aj. K vláknu patří jen ukazatele IP a SP (instruction pointer, stack pointer), PSW (program status word) včetně myid a priority, sada registrů a zásobník. • Nejčastěji je to programátor, kdo explicitně vlákna vytvoří při paralelizaci programu. • Multivláknový provoz (MT - MultiThreading) – Časový – vlákna se střídají na jednom CPU (TMT) – Prostorový – vlákna běží paralelně v multiprocesorovém systému se sdílenou pamětí (P procesorů / P vláken) – Časoprostorový (na P procesorech běží R vláken a R>P)
35
Multivláknové procesory • Podpora více vláken v HW je asi nejzajímavější technika pro překlenutí vysoké latence přístupu do paměti. – Musí však existovat dostatek vláken. – Doba přepnutí vlákna (přepnutí kontextu) musí být krátká. – Na obrázku je porovnání typického výpočtu pro různé architektury:
36
Př. Počet vláken pro TMT • Jestliže chceme tolerovat latenci přístupů do paměti (např. L = 70 taktů) multivláknovými CPU, kolik vláken (N) bude třeba pro získání maximální účinnosti, když jedno vlákno běží průměrně R=10 taktů a přepnutí kontextu trvá S = 3 takty?
(N – 1)R + NS ≥ L (N – 1)10 + 3N ≥ 70 13N ≥ 80 N ≥ 6,15 N≥7 37
Multivláknový procesor •
Z pohledu HW – Prostředky sdílené vlákny: • Procesor, cache, prediktory skoků
– Prostředky replikované pro každé vlákno • Sada registrů, PC, SP, PSW, řadič přerušení
– Je třeba dodat nový HW – např. pro výběr vlákna
•
Techniky TMT – Hrubý MT • Jedno vlákno běží řadu taktů, k přepnutí kontextu dochází pouze při výskytu události s dlouhou latencí, která by vedla k zastavení linky.
– Jemný MT • každém taktu se přepíná na jiné vlákno (prokládání vláken).
– SMT, souběžný (současný) MT (Simultaneous Multithreading). • V každém taktu přepíná kontext několika vláken současně, protože v jednom taktu se zpracovávají instrukce z několika vláken. • Hyperthreading (firemní název, Pentium 4) – 2 vlákna – kombinuje jemný MT (pokud vlákna nejsou pozastavena) a hrubý MT (pokud je jedno vlákno pozastaveno). – Nárůst ploch cca 5%, nárůst výkonnosti cca 25%. (4-cestný superskalární CPU, TNT)
38
Multithread, multicore - shrnutí • Podpora vícevláknového zpracování (multitasking, multithreading) může mít různou podobu – Přepínání úloh pouze z úrovně OS – dnes se již samostatně téměř nepoužívá – Přepínání s podporou HW CPU – nejedná se o paralelní zpracování, úlohy běží v časovém multiplexu (hrubý/jemný MT) – Vícecestné procesory – souběžný MT, výhradně s HW podporou CPU, paralelní vykonávání instrukcí různých úloh (pokud je to možné – sdílení určitých komponent CPU) – Vícejádrové procesory (multiprocesory) – každé jádro může autonomně spouštět různé úlohy (vlákna nebo i procesy). Běžně se používá v kombinaci s dříve uvedenými přístupy.
• Komunikace mezi vlákny se provádí přes sdílenou paměť. • Programování nejčastěji pomocí OpenMP (C/C++)
39
Ukázka kódu s více vlákny (OpenMP) • OpenMP – MultiProcessing – rozšíření C/C++ o direktivy #pragma omp … a další knihovní funkce, umožňující specifikovat, jakým způsobem má být kód paralelizován.
40
Pokračování příště
41
Úvod do paralelních systémů 2. část
FIT VUT v Brně
Obsah • •
Paralelní přístup z pohledu praxe Technologické důvody pro zavedení paralelismu – Proč nestačí jedno jádro?
•
Moderní procesory – přehled vývoje architektur – – – – –
•
Skalární Superskalární Koncept SIMD – vektorové instrukce, MMX, SSE,… Architektura VLIW Vícevláknové zpracování
Paralelní a distribuované systémy – Základní koncepty architektury – Propojovací sítě a topologie – Vliv architektury paralelního systému na výkonnost
•
Masivně paralelní architektury - GPU – Využití grafických čipů pro obecné výpočty (GPGPU)
Podrobně je problematika paralelních systémů probírána v magisterských kurzech: Architektura procesorů Architektura a programování paralelních systémů Paralelní a distribuované algoritmy 43
Jak využít n procesorů? • Procesory nekomunikují (n krát rychlejší než sekvenční počítač) – Mohu spustit současně více různých úloh, každou na jednom procesoru – Mohu spustit stejnou úlohu na n procesorech, ale s jinými parametry (např. program pro předpověď počasí s různým nastavením počátečních podmínek – zrychlení n-krát oproti sekvenčnímu počítači)
• procesory komunikují (spolupracují) za účelem vyřešení složité úlohy v rozumném čase, jedná se o paralelní systém – Návrh řešení určité úlohy na paralelním systému se nazývá paralelní programování – Procesory společně řeší jednu úlohu, musí být vhodně propojeny – Někdy je možné dosáhnout větší zrychlení než v předchozím případě! – Příklad: paralelní řazení Enumeration sort (pro k prvků) • Pokud je k dispozici k2 procesorů, je časová složitost O(log k)
– Příklad: paralelní řazení Bucket sort (pro k prvků) • Pokud je k dispozici log (k) procesorů, je časová složitost O(k)
44
Paralelní systém – základní vrianty •
Se sdílenou pamětí (shared memory, SM) – Obvykle řešeno jako tzv. UMA – uniform memory access, kdy latence přístupu do sdílené paměti je stejná u všech procesorů (SMP – symetrický multiprocesor). – Programování pomocí OpenMP – Výhoda: efektivní komunikace – Nevýhoda: max. pouze ~ 32 procesorů (v závislosti na použité propojovací síti)
•
S distribuovanou pamětí (distributed memory, DM) – Každý procesor má svoji (privátní) paměť – Programování (komunikace) pomocí knihovny zasílání zpráv (MPI – Message Passing Imterface), případně přes síťové sokety – Výhoda: škálovtelnost – Nevýhoda: vyšší komunikační režie
•
Se distribuovanou sdílenou pamětí (distributed shared memory, DSM) – Obvykle řešeno jako tzv. CC-NUMA (cache coherent non-uniform memory access) 45
Propojení víceprocesorových systémů • Komunikace mezi procesory a přístup ke sdíleným prostředkům jsou realizovány přes propojovací sítě např. sběrnice,
úplné propojení,
Xbar apod. (viz dále)
http://www.fujitsu.com/global/services/computing/server/sparcenterprise/technology/performance/crossbar.html
46
Křížový přepínač (X-bar) • Propojení 1:1 mezi vstupy a výstupy. • Je možné propojit 1 vstup k několika výstupům. • Více vstupů k jednomu výstupu se připojit nesmí. • Je nutné použít arbitr. • Cena: p2 přepínačů (řešení založeno na multiplexorech) – drahé řešení • Použití: propojení procesorů s procesory nebo paměťovými moduly
Způsob propojení procesorů a typ linek má zásadní vliv na výkonnost! 47
Zahltit sběrnici není obtížné •
Uvažme procesory (každý s I-cache a D-cache) propojené navzájem sběrnicí a připojené k paměti – – – –
• • • • •
Hit rate hi = 98% v I-cache Hit rate hd = 95% v D-cache Procesor má výkonnost 250 MIPS Přístup do D- cache potřebuje 1/3 instrukcí (~ 75 MIPS)
• •
Počet výpadků v I-cache 2% x 250 MIPS = 5 M výpadků /s Počet výpadků v D-cache 5% x 75 MIPS = 3,75 M výpadků /s Celkem 8,75 M výpadků/s Při každém výpadku se po sběrnici přenáší blok o velikosti 16B. Potřebná šířka pásma je pro každý procesor 8,75 M výpadků/s x 16B = 140 MB/s Kolik procesorů zahltí sběrnici, která má propustnost 1GB/s? N = 1000 / 140 => 7 procesorů
•
Závěr: Větší počet procesorů nemá smysl propojovat sběrnicí!
48
Přímé propojovací sítě – příklady topologií
49
Př. Sečtení k čísel na n procesorech • Sekvenční řešení: ts= k - 1 kroků • Paralelní řešení (každý procesor má k/n čísel): – Hyperkostka: tp = k/n + 2 log2 n kroků – Kruh: tp = k/n + 2n/2 = k/n + n kroků práce jednoho procesoru
komunikační režie Kruh n = 8 krok 1
Hyperkostka n = 8
krok 1
krok 2
krok 3
výsledek
1
2
2
3 3
4 výsledek
Pozn.: Operace “pošli mezivýsledek a sečti” je počítána jako 2 kroky. 50
Př. Sečtení k čísel na n procesorech •
zrychlení = ts / tp 8 procesorů 9 zrychleni_krychle 8
zrychleni_kruh
7
6
5
4
3
2
1
0 0
500
1000
1500
2000
k
Je patrný velký vliv komunikační režie na zrychlení pro nízké hodnoty k. 51
Př. Sečtení k čísel na n procesorech k = 2048 100 90 80 70
zrychleni_hyperkostka zrychleni_kruh
60 50
k
40 30 20 10 0 0
200
400
600
800
1000
n
U kruhu je patrný velký vliv komunikační režie na zrychlení pro větší počet procesorů. 52
Nejvýkonnější superpočítače (2013)
http://www.top500.org/
53
Vybrané paralelní výpočetní systémy v ČR • Výpočetní cluster na FIT VUT v Brně (řízeno systémem SGE) – Až 2400 procesů (dle stavu jednotlivých serverů/modulů) – V současnosti 102 uzlů, každý vybaven 2x CPU 4-16 jader, 4-256 GB RAM
• „Malý cluster“ Anselm, VŠB-TU Ostrava (spuštěn 2013), součást projektu IT4Innovations (VUT je účastníkem projektu) – Přes 200 uzlů, každý vybaven 2x CPU Intel Sandy Bridge 8-core, 96 GB RAM, některé navíc disponují GPU akcelerátorem Nvidia Tesla Kepler K20
• Ve výstavbě je „velký cluster“ – dokončení ~ 2015, současný odhad kolem 15. místa v top500 (IT4Innovations, VŠB-TU Ostrava) 54
Graphics Processing Elements (GPU) • GPU – programovatelná grafická karta (od r. 2001, Nvidia GeForce 3) • Tradiční použití GPU – grafická pipeline
GPU
• Propustnost
55
General-Purpose Computation on Graphics Hardware (GPGPU) • •
GPGPU – provádění obecných výpočtů na GPU (v současnosti velmi populární, vysoký výkon za nízkou cenu) Má smysl pro určité úlohy typu SIMD (statisíce datových položek) rychlé a velké cache, predikce skoků, vysoká výkonnost pro jedno vlákno, podpora přerušení, virtualizace paměti.
velké množství ALU – zejména operace MAD vynásob a sečti, FMA (MAD pro FP, jedno zaokrouhlení), mnoho HW vláken, rychlé lokální paměti, špatná podpora větvení, nízký výkon na jedno vlákno.
přibližně stejná plocha ve srovnání s CPU
http://www.pgroup.com/lit/articles/insider/v2n4a1.htm
56
Vhodné problémy pro GPU
57
Výkonnost GPU ve srovnání s procesory
http://michaelgalloy.com/2013/06/11/cpu-vs-gpu-performance.html
58
Př. GeForce GTX 280
SM – streaming multiprocessor SFU - Special Function Units TPC -Texture/Proces-sor Cluster 59
Příklad současné GPU
60
Prostředky pro tvorbu aplikací na GPU •
CUDA (Compute Unied Device Architecture) je knihovna firmy Nvidia určená pro obecné výpočty optimalizované na GPU. – Příklad: násobení matic konvenčně a pomocí CUDA C
•
OpenCL – platforma pro tvorbu aplikací přenositelných mezi různými architekturami (např. GPU, ARM a další) – Méně efektivní, překlad prováděn za běhu automaticky pro danou architekturu 61
Literatura • • • • • •
Dvořák, V., Drábek, V.: Architektura procesorů. Studijní opora. FIT VUT v Brně 2006 Dvořák, V.: Architektura a programování paralelních systémů. Skriptum VUT v Brně 2004 Hanáček, P.: Paralelní a distribuované algoritmy. Přednášky FIT VUT v Brně, 2008 Fučík O.: Hardware/Software codesign. Habilitační přednáška, FIT VUT v Brně 2009 Bhandarkar D.: The Dawn of a New Era: Multi-Core Computing. Intel 2006 Pospíchal P.: Akcelerace genetického algoritmu s využitím GPU. Diplomová práce FIT VUT v Brně, 2009
•
Pozn. Většina obrázků převzata z internetu a uvedených publikací
• Podrobně je problematika paralelních výpočtů probírána v magisterských kurzech: – Architektura procesorů – Architektura a programování paralelních systémů – Paralelní a distribuované algoritmy
62
