Paralelní programování

Úvod

Paralelismus

• Základní úrovně:• hardwarová (procesory, jádra)• programová (procesy, vlákna)• algoritmická (uf... )

• Motivace:• zvýšení výkonu• redundance

• jiné cíle, ale podobné nástroje a problémy

Proč zvyšovat výkon?

• Moorův zákon:• „... Počet tranzistorů/komponent, které lze levně

integrovat se zdvojnásobí každý rok...“ • 12 měsíců (1965)• 18 měsíců (≈ 1985)• 24 měsíců (≈2005)• ?

• Jedná se spíš o strategii Intelu než o zákon• Dodržuje se zvyšováním počtu jader

• nejsou integrované na jednom polovodiči

Skutečný průběh Zdvojnásobení každých:12 měsíců24 měsíců

Počet tranzistorů vs. výkon

Počet tranzistorů vs. výkon

Frekvence

• Posledních 10 let se drží okolo 3Ghz

• Růst se neočekává

• Rychlost elektronů je konečná

• Tranzistory mají konečnou velikost

Výkon pořád roste

Kapacita × zpoždění

• průměr 1m• délka 1200km• kapacita

• 160 000 000 litrů/den

• zpoždění (latency)• 12 dní

• propustnost?• odezva?

Terminologie

• Paralelní systém – systém, ve kterém může probíhat několik procesů/činností současně

• Rozlišovací úroveň• instrukce, iterace, procedura, vlákno, proces,

úloha• Proces × Vlákno

• vlákno – instance kódu + dat a stav zásobníku + registrů

• proces – kolekce vláken, společný kód + data

Terminologie

• Procesor × Jádro• jádro (core) – čip + paměť + řadič vykonávající

jedno vlákno• procesor – kolekce jader• multithreaded-core• multiprocesor = multicore

• Abstrakce• MProcesory se sdílenou pamětí

• symetrické × nesymetrické• MProcesory s distribuovanou pamětí

Paralelizace – HW

• Flynnova klasifikace systému• staré (1966), hrubé, ale používané• Single Instruction, Single Data stream (SISD)• Single Instruction, Multiple Data streams (SIMD)• Multiple Instruction, Single Data stream (MISD)

• Multiple Single Instruction stream, Multiple Data stream (MSIMD) – několik propojených SIMD

• Same Program, Multiple Data stream (SPMD) – každý procesor provádí stejný program, využívají se běžné CPU

• Multiple Instruction, Multiple Data streams (MIMD)

Single Instruction, Single Data

• data jsou zpracovávána výhradně sériově• instrukce jsou prováděny sériově• stačí jeden CPU• řídicí jednotky• klasický von

Neumannův počítač

Multiple Instruction, Single Data

• jedna data jsou předávána více instrukcím• více CPU, každý zpracovává data v jiné fázi• „výrobní linka“• umělá kategorie• není to pipelining

Single Instruction, Multiple Data

• Jedná instrukce se provádí na více datech• Více CPU provádí stejnou instrukci s jinými daty• Typické GPU

• maticové procesory• array/matrix procesor

for (int i = 0; i <= n; i++) { X[i] = Y[i] + Z[i];}

Multiple Instruction, Multiple Data

• Různá CPU mohou provádět různé operace• Různá CPU pracují s jinými daty• Moderní počítače• Distribuované systémy

• HW virtualizace• Grid

CPU vs. GPU

• multi-core mikroprocesory• zrychlování sekvenčních programů• rozsáhlé univerzální instrukční soubory• více jader:

• hypertherading s dvěma a více vlákny• pipeline

• many-core mikroprocesory• zvyšování propustnosti (throughput)• stovky jader, stovky vláken• zaměřeno na floating-point operace

Exotický HW

• Asociativní procesory• maticový procesor s HW propojovací sítí• adresace dat podle obsahu (ekvivalence, klíč,

interval)• Počítače řízené daty

• instrukce nemají vedlejší efekty• výstupem je vždy hodnota• průmyslový HW

• ...

Koncepty

• Komunikace – výměna dat mezi paralelně probíhajícími procesy

• Synchronizace – zaručení definované posloupnosti operací, logika procesů

• Režie (overhead) paralelismu • čas spotřebovaný na komunikaci• čas spotřebovaný na synchronizaci a výměnu dat• ostatní režie (knihovny, spuštění, zastavení)

• Škálovatelnost (scalability)• míra růstu výkonosti s růstem paralelismu

Amdahlův zákon

• – podíl programu, který nelze paralelizovat• – podíl programu, který lze paralelizovat• t – celková doba výpočtu• p – počet procesorů

• Dva pohledy

Amdahlův zákon

Zrychlení

𝑓 𝑝

Amdahlův zákon

Gustafsonův zákon

Možnosti paralelizace

• Nízko úrovňové (fine grained)• pipelining, multithreading, a podobné vychytávky• pomáhá při běžných operacích• neřešíme

• Vyšší úroveň• použití více jader / procesorů

• pod 60% nezajímavé• paralelizace algoritmu

• zvyšujeme • využití speciálního HW (GPU)

Co musíme vyřešit

• synchronizace• přístup ke sdílené paměti

• různé modely• distribuce dat• distribuce instrukcí (práce)• komunikace• minimalizovat režii• použít vhodný HW• měření

Předmět PP

• Zápočet nebo zkouška?• Projekt

• dvojice• paralelizace nějaké úlohy

• téma je volné• vyhodnocení

• tzn. zpracování stejné úlohy paralelně a sériově• distribuovaný výpočet nebo GPU

• jednoduchý test