I IB109 Návrh a implementace paralelních systémů Organizace kurzu a úvod Jiří Barnat Organizace kurzu IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 2/31 Organizace kurzu Místo a čas • Pátek 10:00-11:40, D3 Ukončení předmětu • Závěrečný písemný test na odpřednášený obsah • Možno získat několik bodů za nepovinné domácí úlohy o Požadavky na úspěšné ukončení předmětu Z: bodové hodnocení testu nad 50% ZK: bodové hodnocení testu nad 50%(E), 60%(D), 70%(C), 80%(B), 90%(A) IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 3/31 Cílem předmětu je seznámit studenty s • Problematikou programování paralelních aplikací. 9 Programátorskými prostředky pro vývoj paralelních aplikací, o Možnostmi studia tématu na Fl. Úspěšný absolvent kurzu • Umí identifikovat paralelně proveditelné úlohy. o Má základní přehled o problémech souvisejících s paralelizací. • Nebojí se implementovat vlastní vícevláknové nebo jinak paralelní aplikace či systémy. 9 Má představu o tom, co se děje v zákulisí použitých knihoven pro podporu programování paralelních aplikací. o Umí tyto knihovny správně použít. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 4/31 Osnova: o Práce s daty ve sdílené paměti • POSIX Threads o Lock-Free programování • OpenMP 9 Generické programovania paralelismus (TBB) • Předávání zpráv (v distribuované paměti) o Kolektivní komunikace Složitostní analýza paralleních programů • Algoritmizace paralelních aplikací IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod Předpoklady a kontext na Fl IB109 9 Úvodní kurz určený pro bakalářské studium. • Povinný v rámci oboru Paralelní a distribuované systémy Předpoklady 9 Základní znalosti o fungování výpočetních prostředků a operačních systémů. • Základní zkušenost s imperativním programováním sekvenčních algoritmů. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 6/31 Kontext v rámci Fl PV192 - Paralelní algoritmy • Paralelní zpracování, Klasifikace paralelních systémů, Úrovně paralelismu, Paralelní počítače, Systémy s distribuovanou pamětí, MPI PV197 - GPU Programming • Paralelní výpočty na grafických kartách s technologií CUDA. PA150 - Principy operačních systémů 9 Vlákna, procesy, monitory, semafory, synchronizace. 9 Hierarchie pamětí. IA039 - Architektura superpočítačů a intenzivní výpočty o Procesory. Paralelní počítače. Překladače. MPI. PVM a koordinační jazyky. Profilovania měření výkonu. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 7/31 Kontext v rámci Fl - pokr IV100 - Paralelní a distribuované výpočty 9 Distribuované systémy a algoritmy. Komunikační protokoly. Směrovací algoritmy a tabulky. Distribuované algoritmy pro detekci ukončení, volbu vůdce, vzájemné vyloučení, hledání nej kratší cesty. Byzantská shoda. IV010 - Komunikace a paralelismus • Teoretický model paralelních procesů a komunikace. CCS. Synchronizace, vnitřní akce. Ekvivalence systémů pomocí slabé/silné bisimulace a relace kongruence. IV113 - Úvod do validace a verifikace • Model checking, verifikace paralelních systémů. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 8/31 Kontext v rámci Fl Laboratoře 9 PV177 Laboratoř pokročilých síťových technologií (vývojová) • IV074 Laboratoř paralelních a distribuovaných systémů (výzkumná) • ????? Laboratoř architektury a konstrukce číslicových počítačů Projekty 9 IV112 - Projekt z programování paralelních aplikací • PV197 - GPU Programming IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 9/31 Studijní materiály Knihy • Maurice Herlihy, Nir Shavit: The Art of Multiprocessor Programming • A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to Parallel Computing <* I. Foster: Designing and Building Parallel Programs • W. Group, E. Lusk, A. Skjellum: Using MPI • ... IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 10/31 Studijní materiály E-zdroje: • http://www.wikipedia.org • Kurzy a jejich studijní materiály na různých univerzitách • http://www.cs.arizona.edu/people/greg/mpdbook (Foundations of M u I tit h reded, Parallel, and Distributed Programming) • http://renoir.csc.ncsu.edu/CSC495A 9 http://www.hlrs.de/organization/par/par_prog_ws Parallel Programing Workshop (MPI, OpenMP) • Domovské stránky projektů MPI, TBB, OpenMP, ... 9 Online tutoriály • ... IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 11/31 Motivace IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 12/31 Souběžnost a Výpočetní paralelismus Souběžnost • Existence dvou a více procesů (v obecném smyslu slova) v jeden časový okamžik. Výpočetní paralelismus NV XV V ■ / V ■ I ■ I . v apric všemi úrovněmi, od implementace registru az po koexistenci rozsáhlých výpočetně distribuovaných aplikací. • Chtěný pro zvýšení výkonu. o Vykoupený složitostí návrhu a pořizovací cenou. Souběžnost v Computer Science o Specifikace, implementace a analýza paralelních a distribuovaných systémů. • Inherentně sekvenční algoritmy, složitostní třída A/C. 7 • Historicky možný kandidát na problém P = NP. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 13/31 Důvody vývoje paralelních aplikací Výkonnost • Umožní efektivně využít aggregované výpočetní prostředky k zrychlení výpočtu. Proveditelnost • Agregace výpočetní síly není volba, ale nutnost pro dokončení výpočtu. Bezpečnost 9 Duplikace klíčových částí systému pro případ havárie, či ohrožení důvěry jedné části. Cena • Oddělení nesouvisejících částí aplikace, levnější údržba. • Agregovaná výpočetní síla je levnější. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 14/31 Výpočetních platformy - abstraktně Abstraktní model výpočetního systému • Všechny části systému mohou být úzkým místem vůči výkonnosti aplikace jako celku. 9 Paralelismus je přirozený způsob překonání úzkých míst. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 15/31 Procesory Procesory 9 Neustálá potřeba zvyšovat výkon. • Výkon procesoru spojován s Moorovým zákonem. Moorův zákon • Gordon Moore, spoluzakladatel Intelu • Počet tranzistorů v procesoru se zdvojnásobí přibližně každých 18 měsíců. Metody zvyšování výkonu procesorů • Zvyšování frekvence vnitřních hodin. • Multiplicita, Paralelismus IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 16/31 Microprocessor Transistor Counts 1971-2011 & Moore's Law Date of introduction IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod Trend ve vývoji procesorů Pozorování • Výrobcům procesorů se nedaří zvyšovat výkon jednoho jádra. 9 Fyzikální zákony brání neustálé miniaturizaci - okolo 5nm již nelze udržet elektrony v atomu. • Současná technologie 14-16nm (dříve 22nm, 28nm, 32nm, 45nm, 65nm, 90nm). Řešení • Multi-core a many-core procesory. • Pravděpodobný způsob zvyšování výkonu i v budoucnosti. o Částečný odklon od jednotek monolityckých jader k desítkám menších specializovaných, či k hybridním řešením. Důsledek o Sekvenční algoritmy nemohou nadále těžit z rostoucího výkonu procesorů. • Paralelizace výpočtů je nevyhnutelný směr vývoje. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 18/31 Datové cesty Role paralelismu v komunikaci 9 Větší propustnost komunikačních linek s následným efektem snižování latence. • Robustnost a spolehlivost komunikačních linek. Příklady paralelismu na datové cestě • Sirka sběrnice 32/64/128 bitů. • Domácí dual-band WIFI router. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 19/31 Fakta 9 Výkon procesorů převyšuje výkon ostatních komponent. • Cesta procesor - paměť - disk je zdlouhavá. • Doba nutná pro získání jednotky informace z paměti roste se vzdáleností místa uložení od místa zpracování. Víceúrovňové uložení informací • Registry procesoru • L1/L2/L3 cache • Operační paměť o Cache 1/0 zařízení • Magnetické/optické mechaniky IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod Cache Cache paměť obecně: • Kopie části dat v rychleji dostupném místě. 9 Může a nemusí být kontrolovatelná uživatelem nebo OS. Příklady Cache s různou možností kontroly • L1/L2 cache v rámci CPU nekontrolovatelná programátorem o l/O efficient algoritmy • Obcházejí virtualizaci paměti kontrolovanou OS, a místo toho realizují vlastní způsob použití operační paměti jako cache pro data na disku. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 21/31 Použití mnoha paměťových modulů Multiplicita paměťových modulů • Větší množství uložitelných/zapamatovatelných informací. • Větší množství linek do paměti (větší propustnost), o Větší režie na udržení konzistence. Příklady • Disková pole. 9 Peer-to-Peer sítě. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 22/31 Flynnova klasifikace Single Instruction Single Data • V daný okamžik je zpracovávána jedna instrukce, která pracuje nad jedním datovým proudem. • Klasický sekvenční výpočet. Single Instruction Multiple Data • Jedna tatáž instrukce je vykonávána nad více datovými proudy. • Vektorové instrukce CPU, architektura GPU. Multiple Instruction Multiple Data o Nezávislý souběh dvou a více SISD, SIMD přístupů. o Více jádrové procesory. Multiple Instruction Single Data • Prakticky se nevyskytuje. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 23/31 Úskalí paralelních výpočtu IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 24/31 Distribuovaný systém Distribuovaný/paralelní systém • Specifikován po částech (procesy). 9 Chování systému vzniká interakcí souběžných procesů. • Emergentní jevy. Synchronizace • Omezení na prokládání a souběh akcí jednotlivých procesů distribuovaného systému. Komunikace Přenos informace z jednoho procesu na druhý. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 25/31 Příklad distribuovaného systému IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 26/31 Vybrané problémy distribuovaných systémů Jevy Nekonzistentní vize konzistentního světa Vzájemná interference Rizika • Race-condition, nedeterministické chování, o Uváznutí (Deadlock, Livelock) • Stárnutí (Starwing) • Přetečení buferů, problém producent-konzument. 9 Zbytečná ztráta výkonu (aktivní čekání). IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 27/31 Vývoj paralelních systémů je náročnější Důvody: • Nutnost specifikace souběžných úkolů a jejich koordinace. Paralelní algoritmy. • Nedostačující vývojová prostředí. 9 Nedeterminismus při simulaci paralelních aplikací. • Absence reálného modelu paralelního počítače. • Rychlý vývoj a zastarávání použitých technologií. 9 Výkon aplikace náchylný na změny v konfiguraci systémů. • ... Příklad • V minulých letech byl doporučován pro hry 2-jádrový procesor, proč ne 4-jádrový, když byl zcela určitě výkonnější? IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 28/31 Vývoj paralelních systémů je náročnější Důvody: • Nutnost specifikace souběžných úkolů a jejich koordinace. Paralelní algoritmy. • Nedostačující vývojová prostředí. 9 Nedeterminismus při simulaci paralelních aplikací. • Absence reálného modelu paralelního počítače. • Rychlý vývoj a zastarávání použitých technologií. 9 Výkon aplikace náchylný na změny v konfiguraci systémů. • ... Příklad • V minulých letech byl doporučován pro hry 2-jádrový procesor, proč ne 4-jádrový, když byl zcela určitě výkonnější? • Je obtížné napsat herní engine, který by fungoval dobře na 2-jádrovém stroji a na 4-jádrovém stroji běžel 2x rychleji, je preferována vyšší frekvence 2-jádrového procesoru. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 28/31 HPC IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 29/31 c H PC (High Performance Computing) • Oblast Computer Science • Výpočty na vysoce paralelních platformách Nejvýkonejší počítač světa [Jaro 2010] • Roadrunner 9 Procesory: PowerXCell 8i 3.2 Ghz / Opteron DC 1.8 GHz o Počet jader: 129 600 • Rok výroby: 2008 • Výrobce: IBM 9 GFLOPS: 1 105 000 (ve špičce 1 456 704) • Více viz www.top500.org. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 30/31 Nejrychlejší počítač světa dle (www.top500.org IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 31/31 I IB109 Návrh a implementace paralelních systémů Programování v prostredí se sdílenou pamětí Jiří Barnat HW model prostředí se sdílenou pamětí IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 2/32 HW platformy Paralelní systémy se sdílenou pamětí • Systémy s více procesory • Systémy s více-jadernými procesory • Systémy s procesory se zabudovaným SMT o Kombinace Rizika paralelních výpočtů na soudobých procesorech o Mnohé optimalizace na úrovni procesoru byly navrženy tak, aby zachovávaly sémantiku sekvenčních programů. Pozor zejména na • Přeuspořádání instrukcí • Odložené zápisy do paměti IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 3/32 Simultání multithreading (SMT) Princip • Procesor využívá prázdné cykly způsobené latencí paměti k vykonávání instrukcí jiného vlákna. 9 Vyžaduje duplikaci jistých částí procesoru (např. registry). • Vlákna sdílí cache. Příklad: Intel Pentium 4 • Hyper-Threading Technology (HTT) • OS s podporou SMP vidí systém se SMT/HTT jako více procesorový systém. • Až 30% nárůst výkonu, ale vzhledem ke sdílené cache může být rychlost výpočtu jednoho vlákna nižší. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 4/32 Více-jaderné procesory (multicores] Více plnohodnotných procesorů v jednom chipu. Výhody • Efektivnější cache koherence na nejnižší úrovni. • Nižší náklady pro koncového uživatele. Nevýhody o Víc jader emituje větší zbytkové teplo. • Takt jednoho jádra bývá nižší. 9 Automatické dočasné podtaktování/přetaktování. • Jádra sdílí datovou cestu do paměti. Realita • Více-jádrové procesory se SMT. • Intel Core-i7 (hexa-core se SMT = 12 paralelních jednotek) IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 5/32 Paralelismus v prostředí se sdílenou pamětí Idealizovaný model • Na této úrovni se řeší návrh paralelního algoritmu. • Jednotlivá výpočetní jádra paralelního systému pracují zcela nezávisle. • Přístupy k datům v paměti jsou bezčasové a vzájemně výlučné. • Komunikace úloh probíhá atomicky přes sdílené datové struktury. Realita • Na této úrovni musí programátor řešit technickou realizaci paralelního algoritmu. 9 Přístup do paměti přes sběrnici je pro CPU příliš pomalý. • Registry procesoru a cache paměti - rychlé kopie malého množství dat na různých místech datové cesty. • Problém koherence dat. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 6/32 Paralelní úlohy v kontextu OS - Procesy a vlákna Procesy • Skrývají před ostatními procesy své výpočetní prostředky. • Pro řešení paralelní úlohy je potřeba mezi-procesová komunikace (IPC). • Sdílené paměťové segmenty, sokety, pojmenované a nepojmenované roury. Vlákna o Existují v kontextu jednoho procesu. • V rámci rodičovského procesu sdílí výpočetní prostředky. 9 Komunikace probíhá přes sdílené datové struktury. • Účelem interakce je spise synchronizace než transport dat. • Subjekty procedury plánování. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 7/32 Příklad použití vláken v rámci procesu Vlákno • Realizuje výpočet, tj sekvenci instrukcí. • Každý proces je tvořen alespoň jedním vláknem. • Hlavní vlákno procesu vytváří další vlákna. Příklad 1 for (i=0; i 4.1) • type __sync_val_compare_and_swap (...) • type __sync_fetch_and_add (...) Možnost 3: Součást programovacího jazyka • C++ rev. 11, Java, ... IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 32/32 I IB109 Návrh a implementace paralelních systémů Programování v prostredí se sdílenou pamětí Jiří Barnat Rizika spojená se sdílenou pamětí IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 2/30 Race condition Pozorování • Paralelní programy mohou při opakovaném spouštění zdánlivě náhodně vykazovat různá chování. 9 Výsledek provedení programu může záviset na absolutním pořadí provedení instrukcí programu, tj. na proložení instrukcí zúčastněných procesů/vláken. Race condition • Nedokonalost paralelního programu, která se projevuje takovýmto nedeterministickým chováním se označuje jako race condition, (zkráceně race). IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 3/30 Race condition - příklad Příklad *myStructure p; PO { p = new myStructure; p -> data = 1; cout «(p->data)«endl; p = new myStructure; p -> data = 2; cout «(p->data)«endl; IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 4/30 Atomicita operací Pozorování • Jednoduchý příkaz ve vyšším programovacím jazyce neodpovídá nutně jedné instrukci procesoru. o V moderních operačních systémech je každé vlákno podrobeno plánovacímu procesu. • Vykonání posloupnosti instrukcí procesoru odpovídající jednomu příkazu vyššího programovacího jazyka může být přerušeno a proloženo vykonáním instrukcí jiného vlákna. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 5/30 Atomicita operací Příklad 9 Přičtení čísla do proměnné efektivně může znamenat načtení proměnné do registru, provedení aritmetické operace, a uložení výsledku do paměti. • Při vhodném souběhu následujících procesů, se může efekt jednoho přiřazení do sdílené globální proměnné zcela vytratit volatile int a=0; • Demonstrujte proložení instrukcí, které vyústí v jinou hodnotu, než 30. PO { Pl { a = a + 10; a = a + 20; } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 6/30 Relativní rychlost výpočtu Pozorování Nelze spoléhat na současný souběh vláken, potažmo relativní rychlost výpočtu jednotlivých vláken. Příklad volatile int a=0; PO { usleep 200; a = 0; } Pl { a = 1; usleep 200; } o Po skončení obou vláken (současně spuštěných) bude mít sdílená proměnná ve většině případů hodnotu 0. Není to však ničím garantováno, tj. může nastat situace, kdy bude mít hodnotu 1. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 7/30 Uváznutí (Deadlock) • Pokud mají vlákna inkrementální požadavky na unikátní sdílené zdroje, může dojít k tzv. uváznutí, tj. nemožnosti pokračování ve výpočtu. Příklad PO { Pl { zamkni A; zamkni B; zamkni B; zamkni A; • • • • • • } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 8/30 Hladovění Hladovění, Stárnutí, Neprogrese (Livelock) • Jev, kdy alespoň jedno vlákno není schopné vzhledem k paralelnímu souběhu s jiným vláknem pokročit ve výpočtu za danou hranici. Příklad volatile int a=0; po { while (true) {; a++; a—; }••• } pí { while (a == 0) { }; } • Vlákno Pl může na vyznačeném řádku strávit mnoho času IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 9/30 Thread-safe a re-entrantní procedury Thread-safe procedura 9 Označení procedury či programu, jejíž kód je bezpečné provádět (vzhledem k sémantice výstupu a stabilitě výpočtu) souběžné několika vlákny bez nutnosti vzájemné domluvy/synchronizace. • Knihovní funkce nemusí být thread-safe! • rand() -> rand_r() Re-entrantní procedura • Procedura, jejíž provádění může být v rámci jednoho vlákna přerušeno, kód kompletně vykonán od začátku do konce v rámci téže úlohy, a poté obnoveno/dokončeno přerušené vykonávání kódu. • Termím pochází z dob, kdy nebyly multitaskingové operační systémy. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 10/30 Vztah thread-safe a re-entrantnřch procedur Neporovnatelné • Re-entrantní procedura nemusí být thread-safe. viz http://en.wikipedia.org/wiki/Reentrancy_(computing) • Thread-safe procedura nemusí být re-entrantní. (Problémem je například používání globálních zámků.) Příklad 9 Thread-safe procedura, která není re-entrantní: WC { je-li odemčeno, vejdi a zamkni, jinak čekej • • • odemkni a opusť onu místnost } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 11/30 Thread-safe a re-entrantní procedury Nebezpečné akce zhledem k paralelnímu zpracování 9 Nekontrolovaný přístup ke globálním proměnným a haldě. o Uchovávání stavu procedury do globálních proměnných. o Alokace, dealokace zdrojů globálního rozsahu (soubory, ...). • Nepřímý přístup k datům skrze odkazy nebo ukazatele. 9 Viditelný vedlejší efekt (modifikace nestálých proměnných). Bezpečná strategie • Přístup pouze k lokálním proměnným (zásobník). • Kód je závislý pouze na argumentech dané funkce. • Veškeré volané podprocedury a funkce jsou re-entrantní. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 12/30 Procedura, která není thread-safe *myStructure p; *myStructure functionO { p=new myStructure; return p; } PO { Pl { ♦myStructure x; *myStructure x; x=functionO ; x=functionO ; } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 13/30 Přístup ke sdíleným proměnným Pozorování • Přístup ke sdíleným proměnným je „kořenem všeho zla". 9 Přístup a použití sdílených proměnných se musí provádět kontrolovane. Zamykání a kritické sekce • Část kódu, jehož provedení je neproložitelné instrukcemi jiného vlákna. • Problém realizace kritické sekce musí být řešen způsobem, který je odolný vůči plánování. Jednoduché řešení 9 Sdílená atomicky přistupovaná bitová proměnná, jejíž hodnota indikuje přítomnost procesu/vlákna v přidružené kritické sekci. 9 Manipulována při vstupu a výstupu do/z kritické sekce. • Vyžaduje podporu HW pro atomickou manipulaci. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 14/30 Zamykaní a související pojmy Petersonův algoritmus (spinlock, user-space) • Algoritmus pro vzájemné vyloučení. • Nezpůsobuje stárnutí ani uváznutí. • Pozor na implementaci a provádění instrukcí mimo pořadí. Uspávání • Procesy/vlákna se po neúspěchu vstoupit do kritické sekce sami vzdají procesorového kvanta (uspí se). • Jsou buzeny buď po vypršení časového limitu nebo explicitně jiným běžícím vláknem. Spinlock o Vlákna opakovaně zkouší vstoupit do kritické sekce. o Pro krátké čekací dobyje efektivnější, než přepínání kontextů vláken, natož pak procesů. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 15/30 Výkonostní rizika Přístup ke sdíleným globálním proměnným • Veškeré modifikace a neatomická čtení globálních proměnných musí být serializovány, tj. prováděny po získání odpovídajícího zámku na danou operaci. o Získání zámku vynucuje vylití cache pamětí. • Mnoho přístupů k zamykaným proměnným může být úzkým místem výkonu aplikace. Lokální data vláken (Thread-private data) 9 Vlákna mají své lokální proměnné. 9 Data mohou uloženy v globální sdílené struktuře, pokud odpovídající část datové struktury je přistupována pouze daným vláknem. • Typicky pole indexovaná unikátním identifikátorem vlákna. • Riziko falešného sdílení. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 16/30 POSIX Thread API IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 17/30 Historie a POSIX standard Historie • SMP systémy 9 Vlákna implementována jednotlivými výrobci HW 9 IEEE POSIX 1003.1c standard IEEE POSIX 1003.1c • Programátorský model semaforů a provádění operací v kritické sekci 9 Rozhraní pro C • POSIX threads, PThreads Jiné normy • Operační systémy: NT Threads (Win32), Solaris threads, . .. • Programovací jazyky: Java threads, C++11 threading, ... IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 18/30 Základní dělení funkcionality Správa vláken • Vytváření, oddělování a spojování vláken • Funkce na nastavenia zjištění stavu vlákna Vzájemná vyloučení (mutexes) • Vytváření, ničení, zamykania odemykání mutexů o Funkce na nastavenia zjištění atributů spojených s mutexy Podmínkové/podmíněné proměnné (conditional variable) • Slouží pro komunikaci/synchronizaci vláken o Funkce na vytváření, ničení, "čekání na" a "signalizování při" specifické hodnotě podmínkové proměnné o Funkce na nastavenia zjištění atributů proměnných IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 19/30 POSIX standard Přes 60 API funkcí 9 #include • Překlad s volbou -pthread Mnemotechnické předpony funkcí 9 pthread_, pthread_attr_ • pthread_mutex_, pthread_mutexattr_ o pthread_cond_, pthread_condattr_ • pthread_key_ Pracuje se skrytými objekty (Opaque objects) • Objekty v paměti, o jejichž podobě programátor nic neví o Přistupovány výhradně pomocí odkazu (handle) Nedostupné objekty a neplatné (dangling) reference IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 20/30 Idea o Vlastnosti všech vláken, mutexů i podmínkových proměnných nastavovány speciálními objekty • Některé vlastnosti entity musí být specifikovány již v době vzniku entity Typy atributových objektů • Vlákna: pthread_attr_t • Mutexy: pthread_mutexattr_t Podmínkové proměnné: pthread_condattr_t Vznik a destrukce • Funkce _init a _destroy s odpovídající předponou o Parametr odkaz na odpovídající atributový objekt IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí Vytváření vlákna • Každý program má jedno hlavní vlákno • Další vlákna musí být explicitně vytvořena programem 9 Každé vlákno (i vytvořené) může dále vytvářet další vlákna o Vlákno vytvářeno funkcí pthreacLcreate o Vytvářené vlákno je ihned připraveno k provádění • Může být plánovačem spuštěno dříve, než se dokončí volání vytvářecí funkce 9 Veškerá data potřebná při spuštění vlákna, musí být připravena před voláním vytvářecí funkce • Maximální počet vláken je závislý na implementaci IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 22/30 int pthreacLcreate ( pthreacLt *thread_handle, const pthread_attr_t *attribute, void * (*thread_function) (void *), void *arg); • thread-handle odkaz na vytvořené vlákno o attribute odkaz na atributy vytvořeného vlákna (NULL pro přednastavené nastavení atributů) • thread_function ukazatel na funkci nového vlákna o arg ukazatel na parametry funkce thread_function o Při úspěšném vytvoření vlákna vrací 0 IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 23/30 Ukončení vlákna nastává • Volaním funkce pthreacLexit • Pokud skončí hlavní funkce rodičovského vlákna jinak než voláním pthreacLexit 9 Je-li zrušeno jiným vláknem pomocí pthreacLcancel • Rodičovský proces je ukončen (násilně nebo voláním exit) void pthreacLexit (void *value) o Ukončuje běh vlákna 9 Odkazy na prostředky procesu (soubory, IPC, mutexy, ...) otevřené v rámci vlákna se nezavírají • Data patřící vláknu musí být uvolněna před ukončením vlákna (systém provede uvolnění prostředků až po skončení rodičovského procesu) • Ukazatel value předán při spojení vláken IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 24/30 Správa vláken - příklad 1 #include 2 #include 3 #define NUM.THREADS 5 4 5 void *PrintHello(void *threadid) 6 { printf C7.d: Hello World!\n", threadid) ; 7 pthread_exit (NULL) ; 8 } 9 10 int main (int argc, char *argv[]) 11 { pthread_t threads [NUM_THREADS] ; 12 for (int t=0; t 0 ) 434 pthread_cond_wait (&is_empty, femutex); • • • 456 pthread_mutex_unlock(&mutex); 715 [pthread_mutex_lock(&mutex);] • • • 721 size=0; 722 pthread_cond_signal(&is_empty); 723 [pthread_mutex_unlock(&mutex) ;] IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 12/46 Globální, přesto vláknu specifické proměnné Problém • Vzhledem k požadavkům vytváření reentrantních a thread-safe funkcí se programátorům zakazuje používat globální data. o Případné použití globálních proměnných musí být bezstavové a prováděno v kritické sekci. o Klade omezení na programátory. Řešení • Thread specific data (TSD) • Globální proměnné, které mohou mít pro každé vlákno jinou hodnotu. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 13/46 Implementace TSD Standardní řešení • Pole indexované jednoznačným identifikátorem vlákna. o Vlákna musí mít rozumně velké identifikátory. 9 Snadný přístup k datům patřící jiným vláknům - potenciální riziko nekorektního kódu. Řešení POSIX standardu • Identifikátor (klíč) a asociovaná hodnota. 9 Identifikátor je globální, asociovaná hodnota lokální proměnná. Klíč - pthread_key_t. • Asociovaná hodnota - univerzální ukazatel, tj. void *. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 14/46 POSIX Klíče int pthread_key_create ( ptrhead_key_t *key, void (*destructor)(void*)) • Vytvoří nový klíč (jedná se o globální proměnnou). • Hodnota asociovaného ukazatele je nastavena na NULL pro všechna vlákna. a Parametr destructor - funkce, která bude nad asociovanou hodnotou vlákna volána v okamžiku ukončení vlákna, pokud bude asociovaná hodnota nenulový ukazatel. • Parametr destructor je nepovinný, lze nahradit NULL. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 15/46 Zničení klíče a asociovaných ukazatelů • int pthread_key_delete (ptrhead_key_t key) • Nevolá žádné destructor funkce. 9 Programátor je zodpovědný za dealokaci objektů před zničením klíče. Funkce na získania nastavení hodnoty asociovaného ukazatele • void * pthread_getspecif ic (ptrhead_key_t key) • int pthread.set specif ic ( ptrhead_key_t key, const void *value) IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads ptrheacLt pthreacLself () • Vrací unikátní systémový identifikátor vlákna int pth.read_equ.al (pthreacLt threadl, pthread_t thread2) • Vrací nenula při identitě vláken threadl a thread2 pthread_once_t once.control = PTHREAD_ONCE_INIT; int pthread_once(pthread_once_t *once_control, void (*init_routine) (void)) ; 9 První volání této funkce z jakéhokoliv vlákna způsobí provedení kódu init_routine. Další volání nemají žádný efekt. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 17/46 Další funkce v POSIX Threads Plánování (scheduling) vláken • Není definováno, většinou je výchozí politika dostačující. o POSIX Threads poskytují funkce na definici vlastní politiky a priorit vláken. 9 Není požadována implementace této části API. Správa priorit mutexů Sdílení podmínkových proměnných mezi procesy Vlákna a obsluha POSIX signálů IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 18/46 Typické konstrukce IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 19/46 Čtenáři a písaři - WRRM Mapa Specifikace problému • Vlákna aplikace často čtou hodnotu, která je relativně méně často modifikována. (Write-Rarely-Read-Many) • Je žádoucí, aby čtení hodnoty mohlo probíhat souběžně. Možné problémy • Souběžný přístup dvou vláken-písařů, může vyústit v nekonzistentní data nebo mít nežádoucí vedlejší efekt, například memory leak. Souběžný přístup vlákna-písaře v okamžiku čtení hodnoty jiným vláknem-čtenářem může vyústit v čtení neplatných, nekonzistentních dat. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 20/46 Řešení s použitím POSIX Threads ■v 9 Ctení a modifikace dat bude probíhat v kritické sekci. • Přístup do kritické sekce bude řízen pomocí funkcí pthreacL*. Další požadavky • Vlákno-čtenář může vstoupit do kritické sekce, pokud v ní není nebo na ní nečeká žádné vlákno-písař. • Vlákno-čtenář může vstoupit do kritické sekce, pokud v ní jsou jiná vlákna-čtenáři. 9 Přístupy vláken-písařů jsou serializovány a mají přednost před přístupy vláken-čtenářů. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 21/46 Čtenáři a písaři - Implementace Jednoduché řešení • Použít jeden pthread_mutex_t pro kritickou sekci. 9 Vylučuje souběžný přístup vláken-čtenářů. Lepší řešení 9 Implementujeme nový typ zámku - rwlock_t o Funkce pracující s novým zámkem • rwlock_rlock(rwlock_t *1) - vstup vlákna-čtenáře • rwlock_wlock(rwlock_t *1) - vstup vlákna-písaře • rwlock_unlock(rwlock_t *1) - opuštění libovolným vláknem • Funkce rwlock implementovány s pomocí POSIX Thread API IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 22/46 Čtenáři a písaři - Implementace rlock unl rlock sleep rlock KS unlock rlock unlock wlock sleep wlock KS sleep wlock KS unlock IB109 Návrh a implementace paralelních systémů POSIX Threads - pokračování, Win32 Threads str. 23/46 Čtenáři a písaři - Implementace 1 typedef struct { 2 int readers; 3 int writer; 4 pthread_cond_t readers_proceed; 5 pthread_cond_t writer_proceed; 6 int pending.writers; 7 pthread_mutex_t lock; 8 } rwlock_t; 9 10 void rwlock_init (rwlock_t *1) { 11 l->readers = l->writer = l->pending_wr iters = 0; 12 pthread_mutex_init(&(l->lock) ,NULL) ; 13 pthread_cond_init (&(l->readers_proceed) ,NULL); 14 pthread_cond_init (&(l->writer_proceed) ,NULL) ; 15 } IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 24/46 Čtenáři a písaři - Implementace 16 17 void rwlock_rlock (rwlock_t *1) { 18 pthreadjnutex_lock (& (l->lock)); 19 while (l->pending_writers>0 || (l->writer>0)) { 20 pthread_cond_wait (&(l->readers_proceed), &(l->lock)); 21 } 22 l->readers++; 23 pthreadjnutex_unlock(&(l->lock)); 24 } 25 IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 25/46 Čtenáři a písaři - Implementace 26 27 void rwlock_wlock (rwlock_t *1) { 28 pthreadjnutex_lock (& (l->lock)); 29 while (l->writer>0 || (l->readers>0)) { 30 l->pending_writers++; 31 pthread_cond_wait (&(l->writer_proceed), &(l->lock)); 32 l->pending_writers —; 33 } 34 l->writer++; 35 pthreadjnutex_unlock(&(l->lock)); 36 } 37 IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 26/46 Čtenáři a písaři - Implementace 38 39 void rwlock_unlock (rwlock_t *1) { 40 pthreadJiiutex_lock (& (l->lock)); 41 if (l->writer>0) 42 l->writer=0; 43 else if (l->readers>0) 44 l->readers—; 45 pthreadjnutex_unlock(&(l->lock)); 46 if ( l->readers == 0 && l->pending_writers >0) 47 pthread_cond_signal( &(l->writer_proceed) ); 48 else if (l->readers>0) 49 pthread_cond_broadcast ( &(l->readers_proceed) ) 50 } 51 IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 27/46 Čtenáři a písaři - Příklady použití Počítání minima 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 rwlock_rlock(&rw_lock); if (myjmin < globaljnin) { rwlock_unlock(&rw_lock); rwlock_wlock(&rw_lock); if (my_min < global_min) global_min = my_min; } } rwlock_unlock(&rw_lock) ; { o Hašovací tabulky IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 28/46 Bariéry Specifikace problému « Synchronizační primitivům • Vláknu je dovoleno pokračovat po bariéře až když ostatní vlákna dosáhly bariéry. • Naivní implementace přes mutexy vyžaduje aktivní čekání (nemusí být vždy efektivní). Lepší řešení • Implementace bariéry s použitím podmínkové proměnné a počítadla. o Každé vlákno, které dosáhlo bariéry zvýší počítadlo. • Pokud není dosaženo počtu vláken, podmíněné čekání. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 29/46 Bariéry - Implementace 1 typedef struct { 2 pthread_mutex_t count_lock; 3 pthread_cond_t ok_to_proceed; 4 int count; 5 } barrier.t; 6 7 void barrier_init (barrier_t *b) { 8 b->count = 0; 9 pthread_mutex_init (&(b->count_lock), NULL); 10 pthread_cond_init (& (b->ok_to_proceed), NULL); 11 } IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 30/46 Bariéry - Implementace 12 void barrier (barrier_t *b, int nr.threads) { 13 pthreadJiiutex_lock(&(b->count_lock)); 14 b->count ++; 15 if (b->count == nr_threads) { 16 b->count = 0; 17 pthread_cond_broadcast (& (b->ok_to_proceed)); 18 } 19 else 20 while (pthread_cond_wait (&(b->ok_to_proceed), 21 &(b->count_lock)) !=0); 22 pthread_mutex_unlock(& (b->count_lock)) ; 23 } IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 31/46 Bariéry - Efektivita implementace Problém • Po dosažení bariéry všemi vlákny, je mutex count_lock postupně zamčen pro všechny vlákna o Dolní odhad na dobu běhu bariéry je tedy 0(r?), kde n je počet vláken participujících na bariéře Možné řešení o Implementace bariéry metodou binárního půlení • Teoretický dolní odhad na bariéru je 0(n/p + log p), kde p je počet procesorů C" v y viceni 9 Implementujte bariéru využívající binárního půlení • Měřte dopad počtu participujících vláken na dobu trvání lineární a logaritmické bariéry na vámi zvoleném paralelním systému IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 32/46 Chyby, krom nezamykaného prístupu ke globální proměnné Typické chyby - situace 1 • Vlákno VI vytváří vlákno V2 a V2 požaduje data od VI o VI plní data až po vytvoření V2 o V2 použije neinicializovaná data Typické chyby - situace 2 • Vlákno VI vytváří vlákno V2 • VI předá V2 pointer na lokální data VI • V2 přistupuje k datům asynchronně o V2 použije data, která už neexistují (VI skončilo) Typické chyby - situace 3 • VI má vyšší prioritu než V2, čtou stejná data o Není garantováno, že VI přistupuje k datům před V2 • Pokud V2 má destruktivní čtení, VI použije neplatné data IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 33/46 Ladění programů s POSIX vlákny Valgrind 9 Simulace běhu programu. • Analýza jednoho běhu programu. Nástroje valgrindu • Memcheck - detekce nekonzistentního použití paměti. • Callgrind - jednoduchý profiler. • kcachegrind - vizualizace. • Helgrind - detekce nezamykaných přístupů ke sdíleným proměnným v POSIX Thread programech. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 34/46 Rozšíření POSIX Threads - nepovinná dle standardu Barriéry o pthread_barrier_t • pthread_barrierattr_t • _init(...),-destroy(...), _wait(...) Read-Write zámky • pthread_rwlock_t o pthread_rwlockattr_t • _init(...), -destroy(...) • _rdlock(...), _wrlock(...),.unlock(...) • _tryrdlock(...) , _trywrlock(...) • _timedrdlock(...), _timedwrlock(...) IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 35/46 Další způsoby synchronizace IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 36/46 Synchronizace procesů Problém - jak synchronizovat procesy • Mutexy z POSIX Threads dle standardu slouží pouze pro synchronizaci vláken v rámci procesu. 9 Pro realizaci kritických sekcí v různých procesech je třeba jiných synchronizačních primitiv. • Podpora ze strany operačního systému. Semafory Čítače používané ke kontrole přístupů ke sdíleným zdrojům. 9 POSIX semafory (v rámci procesu) 9 System V semafory (mezi procesy) • Lze využít i pro synchronizaci vláken. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 37/46 Semafory Semafor • Celočíselný nezáporný čítač jehož hodnota indikuje "obsazenost" sdíleného zdroje. • Nula - zdroj je využíván a není k dispozici. Nenula - zdroj není využíván, je k dispozici. • sem_init() - inicializuje čítač zadanou výchozí hodnotou • sem_wait() - sníží čítač, pokud může, a skončí, jinak blokuje • sem_post() - zvýší čítač o 1, případně vzbudí čekající vlákno Semafory vs. mutexy 9 Mutex smí odemknout pouze to vlákno, kterého jej zamklo. • Semafor může být spravován / manipulován různými vlákny. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 38/46 y Monitor • Synchronizační primitivům vyššího programovacího jazyka. • Označení kódu, který může být souběžně prováděn nejvýše jedním vláknem. • JAVA - klíčové slovo synchronized Semafory, mutexy a monitory 9 Se semafory a mutexy je explicitně manipulováno programátorem. • Vzájemné vyloučení realizované monitorem je implicitní, tj. explicitní zamykání skrze explicitní primitiva doplní překladač. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 39/46 Vlákna ve Win32 IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 40/46 Vlákna ve Win32 Vyšší programovací jazyk • C++-11 • JAVA • ... POSIX Thread pro Windows • Knihovna mapující POSIX interface na nativní WIN32 rozhraní Nativní Win32 rozhraní • Přímá systémová volání (součást jádra OS) • Pouze rámcově podobná funkcionalita jako POSIX Threads • Na rozdíl od POSIX Threads nemá nepovinné části (tudíž neexistují různé implementace téhož). IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 41/46 Win32 vs. POSIX Threads - Funkce WIN 32 POSIX Threads Pouze jeden typ HANDLE Každý objekt má svůj vlastní typ (např. pthreacLt, pthread.jnutex_t, . . .) Jedna funkce pro jednu činnost, (např. WaitForSingleObject) Různé funkce pro manipulaci s různými objekty a jejich atributy. Typově jednodušší rozhraní (bez typové kontroly), čitelnost závislá na jménech proměnných. Typová kontrola parametrů funkcí, lepší čitelnost kódu. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 42/46 Win32 vs. POSIX Threads - Synchronizace WIN 32 POSIX Threads Události (Events) Semafory Mutexy Kritické sekce Mutexy Podmínkové proměnné Semafory Signalizace pomocí událostí. Signalizace v rámci podmínkových proměnných. Jakmile je událost signalizována, zůstává v tomto stavu tak dlouho, dokud ji někdo voláním odpovídající funkce nepřepne do nesignalizovaného stavu. Signál zachycen čekajícím vláknem, pokud takové není, je signál zahozen. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 43/46 Win32 vs. POSIX Threads - Základní mapování WIN 32 POSIX Threads CreateThread pthread_create pthread_attr_* ThreadExit pthread_exit WaitForSingleObj ect pthread_join pthread_attr_setdetachstate pthread_detach SetPriorityClass SetThreadClass Pouze nepřímo mapovatelné. setpriority sched_set scheduler sched_setparam pthread-setschedparam IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 44/46 Win32 vs. Linux/UNIX - Mapování synchronizace WIN32 Threads Linux threads Linux processes Mutex PThread Mutex System V semafor Kritická sekce PThread Mutex Semafor PThread podm. proměnné POSIX semafor System V semafor Událost PThread podm. proměnné POSIX semafor System V semafor IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 45/46 Win32 vs. UNIX - Pozorování Pozice vláken ve WIN32 9 Silnější postavení než vlákna v Linuxu. • Synchronizační prostředky fungují i mezi procesy. • Vlákna ve vlákně (Processes-Threads-Fibers) Výhody jednoho typu • Jednou funkcí lze čekat na nekonkrétní vlákno. 9 Jednou funkcí lze čekat na vlákno a na mutex. IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 46/46 IB109 Návrh a implementace paralelních systémů Implementace Lock-Free datových struktur Jiří Barnat Motivace Klasická škola vícevláknového programování • Přístup ke sdíleným datům musí být chráněný. • Přístupy k datům se musí serializovat s využitím různých synchronizačních primitiv (mutexy, semafory, monitory). • Vlákna operují s daty tak, aby se tyto operace jevily ostatním vláknům jako atomické operace. Problémy • Prodlevy při přístupu ke sdíleným datům. • Uváznutí, živost, férovost. • Korektnost implementace. 9 Atomicita operací. (Je ++i atomické?) IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 2/42 Lock-free programování • Programování paralelních (vícevláknových) aplikací bez použití zamykání nebo jiných makro-synchronizačních mechanismů. Vlastnosti lock-free programování • Používá se (typicky) jedna jediná atomická konstru kce / i nstru kce • Minimální prodlevy související s přístupem k datům • Neexistuje uváznutí, je garantována živost AI ■ . ■ I I . XV V ■ V X V XX • Algoritmicky obtížnější uvazovaní • Korektnost algoritmu náchylná na optimalizace překladače IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 3/42 •HTTP y Wait-free procedura • Procedura, která bez ohledu na souběh dvou a více vláken dokončí svou činnost v konečném čase, tj. neexistuje souběh, který by nutil proceduru nekonečně dlouho čekat, či provádět nekonečně mnoho operací. Lock-free procedura 9 Procedura, která garantuje, že při libovolném souběhu mnoha soupeřících vláken, vždy alespoň jedno vlákno úspěšně dokončí svou činnost. Některá soupeřící vlákna mohou být libovolně dlouho nucena odkládat dokončení své činnosti. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 4/42 Historie Maurice Herlihy 9 Článek: Wait-Free Synchronization (1991) o Ukázal, že konstrukce jako • test-and-set • swap 9 fetch-and-add 9 fronty s atomickými operacemi vložení a výběru nejsou vhodné pro budování lock-free datových struktur pro vícevláknové aplikace. • Ukázal, že existují konstrukce, které vhodnejšou (např. CAS). • Dijkstrova cena za distribuované počítání (2003) http://www.pode.org/dij kstra/2003.html Důsledek • Současné procesory mají odpovídající HW podporu pro CAS. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 5/42 Konstrukce compare-and-swap (CAS) Sémantika daná pseudo-kódem: • template bool CAS(T* addr, T exp, T val) { if (*addr == exp) { *addr = val; return true; } return falše; } Slovní popis • CAS porovná obsah specifikované paměťové adresy addr s očekávanou hodnotou exp a v případě rovnosti nahradí obsah paměťové adresy novou hodnotou val. 0 úspěchu či neúspěchu informuje uživatele návratovou hodnotou. Celá procedura proběhne atomicky. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 6/42 Princip použití instrukce CAS Postup při přístupu ke sdíleným datům • Přečtu stávající hodnotu sdíleného objektu 9 Připravím novou hodnotu sdíleného objektu • Aplikuji instrukci CAS Návratová hodnota • True - Objekt nebyl v mezičase modifikován, nově vypočítaná hodnota je platná a je uložena ve sdíleném objektu. • Falše - Objekt byl v mezičase modifikován (z jiného vlákna), instrukce CAS neměla žádný efekt a je nutné celý postup opakovat. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 7/42 Nebezpečí použití CAS - ABA problém Klíčová vlastnost 9 Modifikace objektu proběhnuvší mezi načtením hodnoty objektu a aplikací instrukce CAS nesmí vyprodukovat tutéž hodnotu sdíleného objektu. Možný chybový scénář • Hodnota objektu, načtená vláknem A za účelem použití v následné instrukci CAS, je x. • Před použitím instrukce CAS vláknem A, je objekt modifikována jinými vlákny, tj. nabývá hodnot různých od x. • V okamžiku aplikace instrukce CAS vláknem A, má objekt opět hodnotu x. o Vlákno A nepozná, že se hodnota objektu měnila. 9 Následná aplikace instrukce CAS uspěje. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 8/42 CAS - provádění instrukcí mimo pořadí a cena Provádění instrukcí mimo pořadí Pokud používáme CAS na zpřístupnění nějakých dat, je potřeba zajistit, aby předcházející inicializace proměnných byly již v okamžiku vykonání instrukce CAS vykonány. 9 Vyžaduje použití paměťové bariéry. • Dotčené proměnné musejí být označeny jako nestálé. Cena • Použití CAS odstranilo režii související se zamykáním. 9 Zůstává však režie související s koherencí cache pamětí. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 9/42 Programování s CAS Win32 • lnterlockedCompareExchange(...) Asembler i386, (pro x86_64 nutné přejmenovat edx na rdx) • inline int32_t compareAndSwap (volatile int32_t & v, int32_t exValue, int32_t cmpValue) { asm volatile ("lock; cmpxchg :°/07oecx, (°/07oedx)" : "=a" (cmpValue) : "d" (&v), "a" (cmpValue), "c" (exValue)); return cmpValue; } GCC - zabudované funkce 9 bool __sync_bool_compare_and_swap (T *ptr, T old, T new, ...) • T __sync_val_compare_and_swap (T *ptr, T old, T new, ...) IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 10/42 WRRM Mapa - Příklad IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 11/42 Write Rarely Read Many Mapa • Zprostředkovává překlad jedné entity na jinou. (Klíč—^Hodnota). 9 Příklad - kurz Koruny vzhledem k jiným měnám • Mění se jednou denně. • Používá se při každé transakci. Možné implementace s využitím STL • map, hash_map • assoc_vector (uspořádané dvojice) Použití o Map mojeMapa; IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 12/42 Implementace s použitím Mutexů template class WRRMMap { Mutex mtx_; Map map_; public: V Lookup(constK& k) { Lock lock(mtx_); return map_[k]; } void Update(const K& k, const V& v) { Lock lock(mtx_); map_.insert(make_pair(k,v)); } }; IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 13/42 Implementace s použitím instrukce CAS Operace čtení o Probíhá zcela bez zamykání. Operace zápisu 9 Vytvoření kopie stávající mapy. • Modifikace/přidání dvojice do vytvořené kopie. • Atomická záměna nové verze mapy za předcházející. Reálné omezení CAS o Obecné použití schématu CAS na WRRMMap by vyžadovalo atomickou změnu relativně rozsáhlé oblasti paměti. 9 HW podpora pro CAS je omezena na několik bytů (typicky jedno, nebo dvě slova procesoru). • Atomickou záměnu provedeme přes ukazatel. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 14/42 Implementace s použitím instrukce CAS template class WRRMMap { Map * pMap_; public: V Lookup(constK& k) { return (*pMap_) [k]; } void Update(const K& k, const V& v) { Map * pNew=0 do { Map * pOld = pMap_; delete pNew; //if (pNew==0) nothing happens pNew = new Map(*pOld); (*pNew)[k] = v; } while (!CAS(&pMap_, pOld, pNew)); // DON'T delete pOld; } IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 15/42 WRRM Map - vlastnosti a problém dealokace Proč je nutná instrukce CAS a nestačí jen pOld = pNew? • Vlákno A udělá kopii mapy. o Vlákno B udělá kopii mapy, vloží nový klíč a dokončí operaci, o Vlákno A vloží nový klíč. o Vlákno A nahradí ukazatel, vše, co vložilo B, je ztraceno. Update • Je lock-free, ale není wait-free. Správa paměti 9 Update nemůže uvolnit starou kopii datové struktury, jiné vlákno může nad datovou strukturou provádět operaci čtení. Možné řešení: Garbage collector (JAVA) IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 16/42 WRRM Map nefunkční řešení dealokace - odložený delete Odložená dealokace paměti • Místo delete, se spustí (asynchronně) nové vlákno. <* Nové vlákno počká 200ms a pak provede dealokaci. Myšlenka • Nové operace probíhají nad novou kopií, za 200ms se všechny započaté operace nad starou kopií dokončí a bude bezpečné strukturu dealokovat. Problémy • Krátkodobé intenzivní přepisování hodnot nebo vkládání nových hodnot může způsobit netriviální paměťové nároky. Není garantováno, že se veškeré operace čtení z jiných vláken za daný časový limit dokončí. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 17/42 WRRM Map a počítání odkazů Nápad • Napodobíme metodu používanou při automatickém uvolňování paměti k tomu, abychom mohli explicitně dealokovat strukturu. 9 Počítání odkazů - s každým ukazatelem je svázáno číslo, které udává počet vláken, jež tento ukazatel ještě používají. Modifikace WRRM mapy • Procedura Update provádí podmíněnou dealokaci, tj. dealokuje objekt odkazovaný ukazatelem, pouze pokud žádné jiné vlákno ukazatel nepoužívá. 9 Procedura Lookup postupuje tak, že zvýší čítač spojený s ukazatelem, přistoupí ke struktuře skrze tento ukazatel, sníží čítač po ukončení práce se strukturou a podmíněně dealokuje strukturu. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 18/42 WRRM Map a počítání odkazů - nefunkční řešení Čítač asociovaný s ukazatelem MAP* 9 template class WRRM Map { typedef std::pair*,unsigned> Data; Data* pData_; } 9 CAS instrukce nad ukazatelem pData_ • Podmíněná dealokace: if (pData_->second==0) delete (pData_->first); Problém v proceduře Lookup • Vlákno A načte strukturu Data (přes *pDate_) a je přerušeno. • Vlákno B vloží klíč, sníží čítač a dealokuje *pOid->f irst. • Vlákno A zvýší čítač, ale přistoupí k neplatnému ukazateli. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 19/42 WRRM Map a počítaní odkazů - CAS2 Problém předchozí verze • Akce uchopení ukazatele a zvýšení odpovídajícího čítače nebyly atomické. Řešení o Pomocí jedné instrukce CAS je třeba přepnout ukazatel a korektně manipulovat s čítačem. • Teoreticky je možné implementovat CAS pracující s více strukturami zároveň, ovšem ztrácí se efektivita, pokud neexistuje odpovídající HW podpora. • Moderní procesory mají podporu pro instrukci CAS pracující se dvěma po sobě uloženými slovy procesoru (CAS2). IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 20/42 WRRM Map s využitím CAS2 Myšlenka • template class WRRM Map { typedef std::pair*,unsigned> Data; Data data ; } • Struktura Data je tvořena dvěma slovy: ukazatel a čítač • Ukazatel a čítač jsou uloženy v paměti vedle sebe. • Strukturu je možné modifikovat pomocí instrukce CAS2. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 21/42 WRRM Map s využitím CAS2 - Lookup V Lookup (const K& k) { Data old; Data fresh; do { old = data_; fresh = old; ++fresh.second; } while (!CAS2(&data_, old, fresh)); V temp = ((*fresh.first)[k] do { old = data_; fresh = old; -fresh.second; } while (!CAS2(&data_, old, fresh)); if (fresh.second == 0) { delete fresh.first; } return temp; } IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 22/42 WRRM Map s využitím CAS2 - stále nefunkční Otázka 9 Umíme atomicky realizovat počítání odkazů, je tedy navrhované řešení korektní? Problém —] XV X XV X V X. V I II* I • Zvýšeni a sníženi citace procedurou Lookup je ve zcela nezávislých blocích. Pokud se mezi provedením těchto bloků realizuje nějaká procedura Update, tak přičtení a odečtení jedničky k čítači proběhne nad jinými ukazateli. • Riziko předčasné dealokace. • Ztráta ukazatelů na staré kopie - memory leak. Řešení • Čítač spojený s ukazatelem použijeme jako stráž. • Proceduře Update bude provádět změny struktury pouze pokud žádné jiné vlákno ke struktuře nepřistupuje. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 23/42 WRRM Map s využitím CAS2 - realizace Update Odkládání provedení modifikace v proceduře Update 9 Atomické nahrazení ukazatele se děje v okamžiku, kdy jsou všechna ostatní vlákna mimo proceduru Lookup. • Časové intervaly, po které se jednotlivá vlákna nacházejí v proceduře Lookup čtenářům se však mohou překrývat. • Čítač po celou dobu existence jiného vlákna v proceduře Lookup neklesá na minimální hodnotu a procedura Update tzv. hladoví (starve). Optimalizace procedury Update 9 Při opakovaných neúspěších instrukce CAS dochází k opakovanému kopírování původní struktury a následnému mazání vytvořené kopie. • Neefektivní opakované kopírování lze odstranit pomocí pomocného ukazatele last. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 24/42 WRRM Map s využitím CAS2 - Update void Update (const K& k, const V& v) { Data old; Data fresh; old.second = 1; fresh.first = 0; fresh.second = 1; Map* last = 0; do { old.first = data_.first; if (last != old.first) { delete fresh.first; fresh.first = new Map(old.first); fresh.first->insert(make_pair(k,v)); last = old.first; } } while (!CAS2(&data_, old, fresh)); delete old.first; IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 25/42 WRRM Map - pozorování ohledně realizace s CAS2 Lookup Není wait-free, inkrementace a dekrementace čítače interferuje s procedurou Update. 9 Volání procedur Update je málo - nevadí. Update 9 Není wait-free, interferuje s procedurou Lookup. • Volání procedur Lookup je mnoho - problém. Čeho jsme dosáhli 9 WRRM BNTM Mapa • Write Rarely Read Many, But Not Too Many IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 26/42 Hazardní ukazatele IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 27/42 Hazardní ukazatele Motivace 9 Dealokace datových struktur v kontextu lock-free XX- I . XV x programovaní je obtizna. 9 Ukazatel na datový objekt nerozliší, zda je možné, objekt uvolnit z paměti, či nikoliv. 9 Čítače použití ukazatelů nejsou dobré řešení. Princip řešení pomocí hazardních ukazatelů 9 Vlákna vystavují ostatním vláknům seznam ukazatelů, které momentálně používají - tzv. hazardní ukazatele. 9 Bezpečně lze dealokovat pouze objekty, které nejsou odkazovány hazardními ukazateli. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 28/42 WRRM Mapa a hazardní ukazatele Původní problém lock-free implementace WRRM Mapy 9 Procedura update vytvoří kopii mapy, modifikuje ji, nahradí touto kopií aktuální mapu a starou mapu dealokuje. 9 Dealokace staré mapy může interferovat s probíhající procedurou Lookup jiného vlákna. Řešení o WRRM Mapa udržuje seznam ukazatelů, které jsou momentálně používány nějakým vláknem v proceduře Lookup. 9 Lookup - vkládá a odebírá ukazatel do seznamu. 9 Update - uchovává (per-thread) již neplatné ukazatele a příležitostně je prochází a dealokuje ty, které nejsou hazardní. • Hazardní ukazatele jsou uchovávány ve sdílené datové struktuře, je třeba ošetřit paralelní přístupy. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 29/42 Schrána pro hazardní ukazatel - Třída HPRecType Spojový seznam • int active_ • void* pHazard • ... Metoda Acquire() • Vytvoří nebo znovu použije neplatný objekt seznamu a vrátí volajícímu ukazatel na tento objekt. 9 Použije se pro zveřejnění používaného ukazatele. Metoda Release() • Použije se pro zneplatnění objektu, tj. oznámení, že ukazatel uložený v tomto objektu již není dále používán. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 30/42 Schrána pro používané ukazatele - Třída HPRecType class HPRecType { HPRecType * pNext_; int active_; static HPRectType* pHead_; static int listl_en_; public: void * pHazard_; static HPRecType* Head() { return pHead_; } static HPRecType* Acquire() { } } static void Release(HPRecType* p) { p->pHazard_ = 0; // Order matters, pHazard_=0 first p->active_ = 0; } IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 31/42 Objekt pro používané ukazatele static HPRecType* Acquire() { HPRecType *p = pHead_; for(; p; p=p->pl\lext_) { // Try to reuse if (p->active_ or !CAS(&p->active_,0,l)) continue; return p; } int oldLen; // Increment the length do { oldLen = listl_en_; } while (!CAS(&listl_en_,oldLen, oldLen+1)); HPRecType *p = new HPRecType; // Allocate new slot p->active_ = 1; p->pHazard_ = 0; do { // Push it to the front old = pHead_; p->pNext_ = old; } while (!CAS(&pHead_, old , p)); return p; } IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 32/42 Seznam odložených ukazatelů určených k dealokaci Princip • Ukazatele na instance, určené k dealokaci jsou schromažďovány do seznamu odložených ukazatelů. • Každé vlákno má svůj vlastní seznam. Retire() Nahrazuje funkci delete, odkládá ukazatel do seznamu. • Je-li seznam příliš dlouhý, volá proceduru Scan, která ze seznamu odstraní nadále nepoužívané ukazatele. • Příliš dlouhý - dáno parametrem R. Scan() • Vytvoří kopii seznamu používaných ukazatelů a seznam setřídí. 9 Pro každý odložený ukazatel hledá binárním půlením v seznamu používaných ukazatelů, zda je ještě používán. • Nadále nepoužívané objekty dealokuje. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 33/42 Seznam odložených ukazatelů určených k dealokaci class HPRecType { }; ' _per_thread_vector*> rlist; template class WRRMMap { private: static void Retire(Map* pOld) { rlist. push_back(pOld); if (rlist.size() >= R) Scan(HPRecType::Head()); } void Sean(HPRecType* head) { } }; IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 34/42 Dealokace odložených ukazatelů void Scan(HPRecType* head) { vector hp; // collect non-null hazard pointers while (head) { void* p = head->pHazard_; if (p) hp.push_back(p); head = head->pNext_; } sort(hp.begin(),hp.end(), less()); vector*>::iterator i = rlist.begin(); while (i!=rlist.end()) { // for every retired pointer if (!binary_search(hp.begin(),hp.end(),*i) { // if not used anymore }; } delete *i; if (&*i != &rlist.back()) *i = rlist.back(); rlist.pop_back(); } else { ++i; } // delete it //and dequeue it // replace it with the last one // dequeue the last one IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 35/42 Modifikace základních procedur WRRM Mapy - Update void Update(const K& k, const V& v) { Map * pNew=0 do { Map * pOld = pMap_; delete pNew; //if (pNew==0) nothing happens pNew = new Map(*pOld); (*pNew)[k] = v; } while (!CAS(&pMap_, pOld, pNew)); Retire(pOld); IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 36/42 Modifikace základních procedur WRRM Mapy - Lookup V Lookup(constK& k) { HPRecType *pRec = HPRecType::Acquire(); Map *ptr; do { ptr = pMap_; pRec -> pHazard_ = ptr; } while (pMap_ != ptr); // is ptr still valid? if so, go on V result (*ptr) [k]; HPRecType::Release(pRec); return result; IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 37/42 WRRM Mapa - Máme hotovo WRRM Mapa a Hazardní ukazatele • Volání procedury Update interferuje s procedurou Lookup. • Procedura Lookup není wait-free. • Předpokládáme přístup v režimu Write Rarely, takže to nevadí. Hazardní ukazatele 9 Možné řešení problému deterministické dealokace v případě, že systém nepodporuje garbage collection. • Obecně je možné udržovat vícero hazardních ukazatelů na jedno vlákno. 9 Amortizovaná složitost je konstantní. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 38/42 Lock-Free programování Návrh Lock-Free datových struktur • Je možné navrhnout lock-free datové struktury. • Zajímavá algoritmika. • Obtížné, pokud chceme deterministické uvolňování paměti. • Vhodné pro prostředí s Garbage Collectorem (JAVA). IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 39/42 Další programátorská rozhraní IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 40/42 Alternativní API pro lock-free programování MCAS • Rozšíření standardní instrukce CAS pro použití s libovolně velkou datovou strukturou. Transakční paměť • Paměť je modifikována v jednotlivých transakcích. • Transakce seskupuje mnoho čtení a zápisů do paměti - je schopna obsáhnout komplexní modifikaci datových struktur. o Základním manipulovatelným objektem je slovo procesoru, tj. obsah jedné paměťové buňky. • Příklad: přesun prvku v dynamicky zřetězeném seznamu. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 41/42 Load-Link/Store-Conditional Dvojice instrukcí, která dohromady realizuje CAS. • LL načte hodnotu a SC ji přepise, pokud nebyla modifikována. Za modifikaci se považuje i přepsání na tutéž hodnotu. o LL/SC stejná síla jako CAS, avšak nemá ABA problém. • HW podpora: Alpha, PowerPC, MIPS, ARM Problémy • Změna kontextu se v praxi považuje za modifikaci místa. • Teoreticky není možné realizovat wait-free proceduru. o Obtížné ladění. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 42/42 I IB109 Návrh a implementace paralelních systémů Pokročilá rozhraní pro implementaci paralelních aplikací Jiří Barnat Jiný způsob programování v prostředí se sdílenou pamětí Nevýhody POSIX Threads a Lock-free přístupu 9 Na příliš nízké úrovni • Vhodné pro systémové programátory • „Příliš složitý přístup na řešení jednoduchých věcí." Co bychom chtěli o Paralelní konstrukce na úrovni programovacího jazyka • Prostředek vhodný pro aplikační programátory 9 Snadné vyjádření běžně používaných paralelních konstrukcí IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 2/54 OpenMP IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 3/54 Myšlenka OpenMP Myšlenka • Programátor specifikuje co chce, nějak se to má udělat. • Náznak deklarativního přístupu v imperativním programování. Realizace o Programátor informuje překladač o zamýšlené paralelizaci uvedením značek ve zdrojovém kódu a označením bloků. 9 Při překladu překladač sám doplní nízkoúrovňovou realizaci paralelizace. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 4/54 Styl programování s OpenMP OpenMP nabízí o Pragma direktivy překladače #pragma omp direktiva [seznam klauzulí] • Knihovní funkce • Proměnné prostředí Překlad kódu • Překladač podporující standard OpenMP • při překladu pomocí GCC je nutná volba -fopenmp • g++ -fopenmp myapp.c • Podporováno nejpoužívanějšími překladači (i Visual C++) • Možno přeložit do sekvenčního kódu WWW http://www.openmp.org IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 5/54 Direktiva parallel - příklad v C++ 1 #include 2 main () 3 { 4 int nthreads, tid; 5 #pragma omp parallel private(tid) 6 { 7 tid = omp_get_thread_num() ; 8 printf ("Hello World from thread = °/„d\n", tid); 9 if (tid == 0) 10 { 11 nthreads = omp_get_num_threads(); 12 printf("Number of threads = %d\n", nthreads); 13 } 14 } 15 } IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 6/54 Direktiva parallel Použití o Strukturovaný blok, tj. {...}, následující za touto direktivou se provede paralelně. 9 Mimo paralelní bloky se kód vykonává sekvenčně. • Vlákno, které narazí na tuto direktivu se stává hlavním vláknem (master) a má identifikaci vlákna rovnou 0. Podmíněné spuštění • Klauzule: if (výraz typu bool) • Vyhodnotí-li se výraz na falše direktiva parallel se ignoruje a následující blok je proveden pouze v jedné kopii. Stupeň paralelismu • Počet vláken. 9 Přednastavený počet specifikován proměnnou prostředí. • Klauzule: num_threads (výraz typu int) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 7/54 Direktiva parallel - datová lokalita Klauzule: priváte (seznam proměnných) • Vyjmenované proměnné se zduplikují a stanou se lokální proměnné v každém vlákně. Klauzule: firstprivate (seznam proměnných) • Viz priváte s tím, že všechny kopie proměnných jsou inicializované hodnotou originální kopie. Klauzule: shared (seznam proměnných) o Vyjmenované proměnné budou explicitně existovat pouze v jedné kopii. • Přístup ke sdíleným proměnným nutno serializovat. Klauzule: default ([shared|none]) o shared: všechny proměnné jsou sdílené, pokud není uvedeno jinak. • none: vynucuje explicitní uvedení každé proměnné v klauzuli priváte nebo v klauzuli shared. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 8/54 Direktiva parallel - redukce Klauzule: reduction (operátor: seznam proměnných) o Při ukončení paralelního bloku jsou vyjmenované privátní proměnné zkombinovaný pomocí uvedeného operátoru. 9 Kopie uvedených proměnných, které jsou platné po ukončení paralelního bloku, jsou naplněny výslednou hodnotou. • Proměnné musejí být skalárního typu (nesmí být pole, struktury, atp.). Použitelné operátory: +, *, -, &, , " , && a IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 9/54 Direktiva for Použití • Iterace následujícího for-cyklu budou provedeny paralelně • Musí být použito v rámci bloku za direktivou parallel (jinak proběhne sekvenčně). o Možný zkrácený zápis: #pragma omp parallel for Klauzule: private, firstprivate, reduction • Stejné jako pro direktivu parallel. Klauzule: lastprivate o Hodnota privátní proměnné ve vláknu zpracovávající poslední iteraci for cyklu je uložena do kopie proměnné platné po skončení cyklu. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 10/54 Direktiva f or Klauzule: ordered Bloky označené direktivou ordered v těle paralelně prováděného cyklu jsou provedeny v tom pořadí, v jakém by byly provedeny sekvenčním programem. • Klauzule ordered je povinná, pokud tělo cyklu obsahuje ordered bloky. Klauzule: nowait • Jednotlivá vlákna se nesynchronizují po provedení cyklu. Klauzule: schedule (typ plánování [, velikost]) 9 Určuje jak budou iterace rozděleny/mapovány mezi vlákna. • Implicitní plánování je závislé na implementaci. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 11/54 Direktiva for - Plánování iterací static o Iterace cyklu rozděleny do bloků o specifikované velikosti. • Bloky staticky namapovány na vlákna (round-robin). • Pokud není uvedena velikost, iterace rozděleny mezi vlákna rovnoměrně (pokud je to možné). dynamic o Bloky iterací cyklu v počtu specifikovaném parametrem velikost přidělovány vláknům na žádost, tj. v okamžiku, kdy vlákno dokončilo předchozí práci. • Výchozí velikost bloku je 1. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 12/54 Direktiva f or - Plánovaní iterací guided • Bloky iterací mají velikost proporcionální k počtu nezpracovaných iterací poděleným počtem vláken. 9 Specifikována velikost k, udává minimální velikost bloku (výchozí hodnota 1). • Příklad: • k = 7, 200 volných iterací, 8 vláken • Velikosti bloků: 200/8=25, 175/8=21, ... , 63/8 = 7, ... runtime • Typ plánování určen až za běhu proměnnou OMP.SCHEDULE. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 13/54 Direktiva sections Použití • Strukturované bloky, každý označený direktivou section, mohou být v rámci bloku označeným direktivou sections provedeny paralelně. 9 Možný zkrácený zápis #pragma omp parallel sections • Umožňuje definovat různý kód pro různá vlákna. Klauzule: priváte, f irstprivate, reduction, nowait • Stejné jako v předchozích případech Klauzule: lastprivate • Hodnoty privátních proměnných v poslední sekci (dle zápisu kódu) budou platné po skončení bloku sections. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 14/54 Direktiva sections - příklad 1 #include 2 main () 3 { 4 #pragma omp parallel sections { #pragma omp section { printf("Thread A."); } #pragma omp section { printf("Thread B."); } 5 6 7 8 9 10 11 12 13 14 15 } } IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 15/54 Vnořování direktiv parallel Nevnořený paralelismus • Direktiva parallel určuje vznik oblasti paralelního provádění. • Direktivy for a sections určují jak bude práce mapována na vlákna vzniklé dle rodičovské direktivy parallel. Vnořený paralelismus • Při nutnosti paralelismu v rámci paralelního bloku, je třeba znovu uvést direktivu parallel. • Vnořování je podmíněné nastavením proměnné prostředí OMP_NESTED (hodnoty TRUE, FALŠE). • Typické použití: vnořené for-cykly o Obecně je vnořování direktiv v OpenMP poměrně komplikované, nad rámec tohoto tutoriálu. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 16/54 Direktiva barrier Bariéra 9 Místo, které je dovoleno překročit, až když k němu dorazí všechna ostatní vlákna. • Direktiva bez klauzulí, tj. #pragma omp barrier. • Vztahuje se ke strukturálně nejbližší direktivě parallel. 9 Musí být voláno všemi vlákny v odpovídajícím bloku direktivy parallel. Poznámka ke kódování 9 Direktivy překladače nejsou součástí jazyka. • Je možné, že v rámci překladu bude vyhodnocen blok, ve kterém je umístěna direktiva bariéry, jako neproveditelný blok a odpovídající kód nebude ve výsledném spustitelném souboru vůbec přítomen. 9 Direktivu barrier, je nutné umístit v bloku, který se bezpodmínečně provede (zodpovědnost programátora). IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 17/54 Direktiva single a master Direktiva single • V kontextu paralelně prováděného bloku je následující strukturní blok proveden pouze jedním vláknem, přičemž není určeno kterým. Klauzule: private, f irstprivate Klauzule: nowait • Pokud není uvedena, tak na konci strukturního bloku označeného direktivou single je provedena bariéra. Direktiva master 9 Speciální případ direktivy single. • Tím vláknem, které provede strážený blok, bude hlavní (master) vlákno. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 18/54 Direktiva critical a atomic Direktiva critical 9 Následující strukturovaný blok je chápán jako kritická sekce a může být prováděn maximálně jedním vláknem v daném čase. • Kritická sekce může být pojmenována, souběžně je možné provádět kód v kritických sekcích s jiným názvem. • Pokud není uvedeno jinak, použije se implicitní jméno. o #pragma omp critical [(name)] Direktiva atomic • Nahrazuje kritickou sekci nad jednoduchými modifikacemi (updaty) proměnných v paměti. o Atomicita se aplikuje najeden následující výraz. • Obecně výraz musí být jednoduchý (jeden load a store). • Neatomizovatelný výraz: x = y = 0; IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 19/54 Direktiva flush Problém (nestálé proměnné) • Modifikace sdílených proměnných v jednom vlákně může zůstat skryta ostatním vláknům. Řešení • Explicitní direktiva pro kopírování hodnoty proměnné z registru do paměti a zpět. • #pragma omp flush [(seznam)] Použití • Po zápisu do sdílené proměnné. • Před čtením obsahu sdílené proměnné. • Implicitní v místech bariéry a konce bloků (pokud nejsou bloky v režimu nowait). IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 20/54 Direktiva threadprivate a copyin Problém (thread-private data) o Při statickém mapování na vlákna je drahé při opakovaném vzniku a zániku vláken vytvářet kopie privátních proměnných. • Občas chceme privátní globální proměnné. Řešení o Perzistentní privátní proměnné (přetrvají zánik vlákna). 9 Při z nov u vytvoře ní vlákna, se proměnné znovupoužijí. • #pragma omp threadprivate (seznam) Omezení • Nesmí se použít dynamické plánování vláken. 9 Počet vláken v paralelních blocích musí být shodný. Direktiva copyin • Jako threadprivate, ale s inicializací. 9 Viz priváte versus f irstprivate. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 21/54 OpenMP knihovní funkce - Počet vláken void omp_set_num_threads (int num.threads) • Specifikuje kolik vláken se vytvoří při příštím použití direktivy parallel. • Musí být použito před samotnou konstrukcí parallel. • Je přebito klauzulí num_threads, pokud je přítomna. • Musí být povoleno dynamické modifikování procesů (OMP_DYNAMIC, omp_set_dynamic()). int omp_get_num_threads () • Vrací počet vláken v týmu strukturálně nejbližší direktivy parallel, pokud neexistuje, vrací 1. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 22/54 OpenMP knihovní funkce - Počet vláken a procesorů int omp_get_max_threads () • Vrací maximální počet vláken v týmu. int omp_get_thread_num () • Vrací unikátní identifikátor vlákna v rámci týmu. int omp_get_num_procs () 9 Vrací počet dostupných procesorů, které mohou v daném okamžiku participovat na vykonávání paralelního kódu. int omp_in_parallel () • Vrací nenula pokud je voláno v rozsahu paralelního bloku. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 23/54 OpenMP knihovní funkce- ontrola vytváření vláken void omp_set_dynamic (int dynamic_threads) int omp_get_dynamic() o Nastavuje a vrací, zda je programátorovi umožněno dynamicky měnit počet vláken vytvořených při dosažení direktivy parallel. Nenulová hodnota dynamic_threads značí povoleno. void omp_set_nested (int nested) int omp_get_dynamic() 9 Nastavuje a vrací, zda je povolen vnořený paralelismus. 9 Pokud není povoleno, vnořené paralelní bloky jsou serializovány. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 24/54 OpenMP knihovní funkce - Mutexy void omp_init_lock (omp_lock_t *lock) void omp_destroy_lock (omp_lock_t *lock) void omp_set_lock (omp_lock_t *lock) void omp_unset_lock (omp_lock_t *lock) int omp_test_lock (omp_lock_t *lock) void omp_init_nest_lock (omp_nest_lock_t *lock) void omp_destroy_nest_lock (omp_nest_lock_t *lock) void omp_set_nest_lock (omp_nest_lock_t *lock) void omp_unset_nest_lock (omp_nest_lock_t *lock) int omp_test_nest_lock (omp_nest_lock_t *lock) • Inicializuje, ničí, blokujícně čeká, odemyká a testuje - • - normální a rekurzivní mutex. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 25/54 Proměnné prostředí OMP_NUM_THREADS • Specifikuje defaultní počet vláken, který se vytvoří při použití direktivy parallel. OMP_DYNAMIC • Hodnota TRUE, umožňuje za běhu měnit dynamicky počet vláken. OMP_NESTED • Povoluje hodnotou TRUE vnořený paralelismus. • Hodnotou FALŠE specifikuje, že vnořené paralelní konstrukce budou serializovány. OMP .SCHEDULE 9 Udává defaultní nastavení mapování iterací cyklu na vlákna. o Příklady hodnot: "static,4", dynamic, guided. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 26/54 Intel's Thread Building Blocks (TBB) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 27/54 Thread Building Blocks Co je Intel TBB • TBB je C++ knihovna pro vytváření vícevláknových aplikací. • Založená na principu zvaném Generic Programming. • Vyvinuto synergickým spojením Pragma direktiv (OpenMP), standardní knihovny šablon (STL, STAPL) a programovacích jazyků podporující práci s vlákny (Threaded-C, Cilk). Generic Programming • Vytváření aplikací specializací existujících předpřipravených obecných konstrukcí, objektů a algoritmů. • Lze nalézt v objektově orientovaných jazycích (C++, JAVA). o V C++ jsou obecnou konstrukcí šablony (templates). • Queue Queue& range ) const { for( int i=range.begin(); i!=range.end(); ++i ) output[i] = (input[i-l]+input[i]+input[i+1])*(l/3.f); } }; Average avg; parallel_for ( blocked_range ( 1, n ), avg ); IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 32/54 Koncept dělení • Instance některých tříd je nutné za běhu (rekurzivně) dělit. 9 Zavádí se nový typ konstruktoru, dělicí konstruktor: X::X(X& x, split) • Dělicí konstruktor rozdělí instanci třídy X na dvě části, které dohromady dávají původní objekt. Jedna část je přiřazena do x, druhá část je přiřazena do nově vzniklé instance. • Schopnost dělit-se musí mít zejména rozsahy, ale také třídy, jejichž instance běží paralelně a přitom nějakým způsobem interagují, např. třídy realizující paralelní redukci. split • Speciální třída definovaná za účelem odlišení dělicího konstruktoru od kopírovacího konstruktoru. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 33/54 Koncept rozsahu Požadavky na třídu realizující rozsah o Kopírovací konstruktor R::R (const R&) • Dělicí konstruktor R::R (const R&, split) • Destruktor R::~R () • Test na prázdnost rozsahu bool R::empty() const • Test na schopnost dalšího rozdělení bool R: :is_divisible() const Předdefinované šablony rozsahů • Jednodimenzionální: biocked_range • Dvoudimenzionální: blocked_range2d IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 34/54 TBB: blockecLrange blockecLrange template class blockecLrange; 9 Reprezentuje nadále dělitelný otevřený interval [i, j). Požadavky na třídu Value specializující blocked_range o Kopírovací konstruktor Value::Value (const Valuefe) • Destruktor Value::"Value () • Operátor porovnání bool Value::operátor<(const Valuefe i, const Valuefe j) • Počet objektů v daném rozsahu (operátor —) size_t Value::operator-(const Valuefe i, const Valuefe j) • /c-tý následný objekt po / (operátor +) Value Value::operator*(const Valuefe i) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 35/54 TBB: blockecLrange Použití blocked_range 9 Nejdůležitější metodou je konstruktor. • Konstruktor specifikuje interval rozsahu a velikost největšího dále nedělitelného sub-intervalu: • blockecLrange(Value begin, Value end [, size_t grainsize] ) Typická specializace • blocked_range • Příklad: blocked_range(5, 17, 2) • Příklad: blocked_range(0, 11) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 36/54 parallel_f or 9 template void parallel_for( const Rangefe range, const Bodyfe body); Požadavky na třídu realizující tělo cyklu o Kopírovací konstruktor Body::Body (const Bodyfe) • Destruktor Body::"Body () • Aplikátor těla cyklu na daný rozsah - operátor () void Body::operator()(Rangefe range) const IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 37/54 TBB: paralleLreduce parallel_reduce 9 template void parallel_reduce( const Rangefe range, const Bodyfe body); Požadavky na třídu realizující tělo redukce • Dělicí konstruktor Body::Body (const Bodyfe, split) 9 Destruktor Body::"Body () • Funkce realizující redukci nad daným rozsahem - operátor () void Body::operator()(Rangefe range) o Funkce realizující redukci hodnot z různých rozsahů void Body:: join(Bodyfe to_be_joined) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 38/54 Možnosti dělení Třída Partitioner o Paralelní konstrukce mají třetí volitelný parametr, který specifikuje strategii dělení rozsahu. • parallel_f or Předdefinované strategie • simple.partitioner • Rekurzivně dělí rozsah až na dále nedělitelné intervaly. • Při použití blocked_range je volba grainsize klíčová pro vyvážení potenciálu a režie paralelizace. • auto_partitioner • Automatické dělení, které zohledňuje zatížení vláken. • Při použití blocked_range volí rozsahy větší, než je grainsize a tyto dělí pouze do té doby, než je dosaženo rozumného vyvážení zátěže. Volba minimální velikosti grainsize nezpůsobí nadbytečnou režii spojenou s paralelizací. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 39/54 Paralelně přistupované kontejnery - vector a queue c oncurrent _queue • template concurret_queue • Fronta, ke které může souběžně přistupovat více vláken. • Velikost fronty je dána počtem operací vložení bez počtu operací výběru. Záporná hodnota značí čekající operace výběru. • Definuje sekvenční, iterátory, nedoporučuje seje používat. concurrent_vector O tempate concurrent_vector • Zvětšovatelné pole prvků, ke kterému je možné souběžně přistupovat z více vláken a provádět souběžně zvětšování pole a přístup k již uloženým prvkům. o Nad vektorem lze definovat rozsah a provádět skrze něj paralelně operace s prvky uloženými v poli. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 40/54 Paralelně přistupované kontejnery - hash_map concurrent Jiashjiiap • template class concurrent_hash_map; Mapa, ve které je možné paralelně hledat, mazat a vkládat. Požadavky na třídu HashCompare o Kopírovací konstruktor HashCompare::HashCompare (const HashComparefe) 9 Destruktor HashCompare::"HashCompare () • Test na ekvivalenci objektů bool HashCompare::equal(const Key& i, const Key& j)const • Výpočet hodnoty h eso vací funkce size_t HashCompare::hash(const Key& k) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 41/54 Paralelně přistupované kontejnery - hash_map Objekty pro přístup k datům v concurrent_hash_map 9 Přístup k párům Klíč-Hodnota je skrze přistupovací třídy. • accessor - pro přístup v režimu read/write 9 const_accessor - pro přístup pouze v režimu read • Použití přistupovacích objektů umožňuje korektní paralelní přístup ke sdíleným datům. Příklad použití přistupovacího objektu • typedef concurrent_hash_map MyTable; MyTable table; MyTable::accessor a; table.insert( a, 4 ); a->second += 1; a.releaseQ ; IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 42/54 Paralelně přistupované kontejnery - hash_map Metody pro práci s concurrent Jiashjnap • bool find(const_accessor& result, const Key& key) const • bool find(accessor& result, const Key& key) • bool insert(const_accessor& result, const Key& key) O bool erase(const Key& key) Další způsoby použití o Iterátory pro procházení mapy. o Lze definovat rozsahy a s nimi pracovat paralelně. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 43/54 C++11 IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 44/54 CH—hli a vláknování Pozorování 9 C++11 má definované příkazy pro podporu vláken. • Není třeba používat externí knihovny jako je POSIX Thread. Jak je to možné • C++11 definuje virtuální výpočetní stroj. • Veškerá sémantika příkazů se odkazuje na tento virtuální výpočetní stroj. • Virtuální výpočetní stroje je paralelní, příkazy související s podporou vláken mohou bý součástí jazyka. • Přenos sémantiky z virtuálního výpočetního stroje na reálný HW je na zodpovědnosti překladače. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 45/54 Příklad - Vlákna a mutexy v C++11 #include #include std::mutex mylock; void func(int& a) { mylock.lock(); a++; mylock.unlockO ; } int main() { int a = 42; std::thread tl(func, std::ref(a)); std::thread t2(func, std::ref(a)); tl.join(); t2.join(); std::cout << a « std::endl; return 0; } IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 46/54 Zamykaní v C++11 Potencionální riziko uváznutí • Jazyk s plnou podporou mechanismu výjimek. o Vyvolání výjimky v okamžiku, kdy je vlákno v kritické sekci (uvnitř mutexu) pravděpodobně způsobí, že nebude vláknem volána metoda odemykající zámek svázaný s kritickou sekcí. Řešení • Využití principu RAM a OOP. 9 Zamčení mutexu realizováno vytvořením lokální instance vhodné předdefinované zamykací třídy. 9 Odemykání umístěno do destruktoru této třídy. • Destruktor je proveden v okamžiku opuštění rozsahu platnosti daného objektu. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 47/54 RAM zamykáni v C++11 Třída lock_guard 9 Obalení standardního zámku v RAM stylu. • Mutex na pozadí nelze „předat" jinému vláknu, nevhodné pro podmínkové proměnné. • Příklad použití: std::mutex m; void func(int& a) { std: :lock_guard l(m) ; a++; } Třída unique_lock 9 Obecnější předatelné RAM obalení mutexu. • Doporučené pro použití s podmínkovými proměnnými. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 48/54 Podporované aspekty Podpora vláknování v C++11 o Vlákna. 9 Mutexy a RAM zámky. 9 Podmínkové proměnné. o Sdílené futures (místa uložení dosud nespočítané hodnoty). Rozcestník • http://en.cppreference.com/w/cpp/thread. Jiné rychlé přehledy • http: //www. codeproj ect. com/Articles/598695/Cplusplus-threads- locks- and- condition-variables 9 http://stackoverflow.com/questions/6319146/ c 11- introduced- a- standardized-memory-model- what- does- it-mean- and- how- is- it- g IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 49/54 Atomicita zápisů Neatomicky • int x,y; Thread 1 x = 17; y = 37; Thread 2 cout « y « " "; cout << x << endl; Nemá definované chování. Správně atomicky • atomic x, y; Thread 1 x.store(17); y.store(37); Thread 2 cout « y.loadO « " "; cout << x.loadQ << endl; • Chování je definované, možné výstupy: 0 0, 0 17, 37 17 IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 50/54 Práce s paměťovým modelem v C++11 Paměťový model • Implicitní chování zachovává sekvenční konzistenci (automaticky vkládá odpovídající paměťové bariéry) • Riziko neefektivního kódu. Příklad 1 • atomic x, y; Thread 1 x. store (17, memory_order_relaxed) ; y. store (37,memory_order_relaxed) ; Thread 2 cout << y. load (memory _order .relaxed) << " " ; cout << x. load (memory_order.relaxed) << endl; 9 Sémantika povoluje v tomto případě i výstup: 37 0. IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 51/54 Práce s paměťovým modelem v C++11 - pokračovaní Paměťový model • Implicitní chování zachovává sekvenční konzistenci (automaticky vkládá odpovídající paměťové bariéry) • Riziko neefektivního kódu. Příklad 2 • atomic x, y; Thread 1 x. store (17,memory_order_release) ; y. store (37, memory _order_release) ; Thread 2 cout << y. load (memory_order.acquire) << " " ; cout << x. load (memory_order.acquire) << endl; • Acquire nepřeuspořádá operace load, Release - store IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 52/54 Jiné přístupy IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 53/54 Paralelní for cyklus Paralelní for cyklus • Nejčastější a nejednoduší metoda paralelizace. • Datová paralelizace. Jak a kde lze řešit paralelní for cyklus • http://parallel-for.sourceforge.net/ IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 54/54 r IB109 Návrh a implementace paralelních systémů Principy návrhu paralelních algoritmů Jiří Barnat Vícepráce programátora paralelních aplikací • Identifikovat souběžně proveditelné činnosti a jejich závislosti. • Mapovat souběžně proveditelné části práce do procesů. 9 Zajistit distribuci vstupních, vnitřních a výstupních dat. 9 Spravovat souběžný přístup k datům a sdíleným prostředkům. 9 Synchronizovat jednotlivé procesy v různých stádiích výpočtu tak, jak vyžaduje paralelní algoritmus. • Mít znalost přídavných programátorských prostředků související s vývojem paralelních algoritmů. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 2/39 Základy návrhu paralelních algoritmu IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 3/39 Návrh a realizace paralelního systému Problém Dekompozice Úlohy Mapování Procesy Vlákna Implementace Aplikace IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 4/39 Dekompozice a Úlohy Dekompozice • Proces rozdělení celé výpočetní úlohy na podúlohy. 9 Některé podúlohy mohou být prováděny paralelně. (Pod)úlohy • Jednotky výpočtu získané dekompozicí. o Po vyčlenění se považují za dále nedělitelné. • Mají uniformní/neuniformní velikost. • Jsou definované v době kompilace / za běhu programu. Příklad • Násobení matice A (r? x n) vektorem B • C[i] = ZUA[iJ}.B\J] IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 5/39 Graf závislostí 9 Zachycuje závislosti prováděných úloh. • Definuje relativní pořadí provádění úloh (částečné uspořádání). Vlastnosti a využití grafu 9 Orientovaný acyklický graf. • Graf může být nespojitý, či dokonce prázdný. • Úloha je připravena ke spuštění, pokud úlohy, na kterých závisí, dokončili svůj výpočet (topologické uspořádání). Příklady závislostí 9 Pořadí oblékání svršků. • Paralelní vyhodnocování výrazů v AND x AND (y OR z) IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 6/39 Granularita a Stupeň souběžnosti Granularita 9 Počet úloh, na který se problém dekomponuje. • Mnoho malých úloh - jemnozrnná granularita (fine-grained). • Málo větších úloh - hrubozrnná granularita (coarse-grained). • Každý problém má vnitřní hranici granularity. Stupeň souběžnosti 9 Maximální počet úloh, které mohou být prováděny souběžně. • Limitem je vnitřní hranice granularity. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 7/39 Průměrný stupeň souběžnosti Průměrný stupeň souběžnosti • Závislý na grafu závislostí a granularitě. • Mějme množství práce asociované k uzlům grafu. • Kritická cesta - cesta, na které je součet prací maximální. • Průměrný stupeň souběžnosti je podíl celkového množství práce vůči množství práce na kritické cestě. • Udává maximální zrychlení, pokud je cílová platforma schopna vykonávat souběžně maximální stupeň souběžnosti úloh. Pozorování • Zjemňování dekompozice může zvýšit stupeň souběžnosti. • Čím méně práce je na kritické cestě, tím větší je potenciál pro paralelizaci. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 8/39 Interakce úloh - Další omezení paralelizace Interakce úloh • Nezávislé úlohy mohou vzájemně komunikovat. • Obousměrná komunikace může snižovat stupeň souběžnosti (úlohy musí co-existovat ve stejný okamžik). • Komunikace úloh - neorientovaný graf interakcí. • Graf interakcí pokrývá graf závislostí (ověření splnění předpokladů pro spuštění úlohy je forma interakce). Příklad jednosměrné komunikace • Násobení matice vektorem (y = Ab) • Dekompozice na nezávislé úlohy dle řádků matice A. o Prvky vektoru b jsou čteny ze všech úloh, je nutné je vhodně distribuovat k jednotlivým úlohám. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 9/39 Techniky dekompozice IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 10/39 Techniky dekompozice Dekompozice o Fundamentální technika v návrhu paralelních algoritmů. Obecné dekompozice • Rekurzivní o Datová Specializované dekompozice • Průzkumová • Spekulativní • Hybridní IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 11/39 Rekurzivní dekompozice Vhodné pro problémy typu rozděl a panuj. Princip o Problém se dekomponuje na podúlohy tak, aby jednotlivé úlohy mohly být dekomponovány stejným způsobem jako rodičovská úloha. o Někdy je třeba restrukturalizovat úlohu. Příklad • Quicksort • Provede se volba pivota. • Rozdělení pole na prvky menší než a větší rovno než. • Rekurzivně se opakuje dokud je množina prvků neprázdná. o Hledání minima v lineárním poli. o Princip půlení prohledávaného pole. • Typický příklad restrukturalizace výpočtu. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 12/39 Datová dekompozice Základní princip • Data se rozdělí na části (data partitioning). o Úlohy se provádí souběžně nad jednotlivými částmi dat. Datová dekompozice podle místa o Vstupní data • Výstupní data • Vnitřní data o Kombinace Mapování dat na úlohy Funkce identifikující vlákno odpovědné za zpracování dat. Úlohy typu "Embarrassingly parallel" • Triviální datová dekompozice na dostatečný počet zcela nezávislých, vzájemně nekomunikujících úloh. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 13/39 Průzkumová dekompozice Princip Specializovaná technika paralelizace. • Vhodná pro prohledávací úlohy. • Prohledávaný prostor se rozdělí podle směru hledání. Vlastnosti 9 Při znalosti prohledávaného stavového prostoru lze dosáhnout optimálního vyvážení a zatížení procesorů. • Na rozdíl od datové dekompozice, úloha končí jakmile je nalezeno požadované. 9 Množství provedené práce se liší od sekvenční verze. • V případě, že graf není strom, je třeba řešit problém opakujících se konfigurací (riziko nekonečného výpočtu). Příklad • Řešení hlavolamu "patnáct" IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 14/39 Spekulativní dekompozice Princip Specializovaná technika paralelizace. • Vhodná pro úlohy se sekvencí datově závislých podúloh. • Úloha, která čeká na výstup předchozí úlohy, se spustí nad všemi možnými vstupy (výstupy předchozí úlohy). Vlastnosti o Provádí se zbytečná práce. • Nemusí být ve výsledku rychlejší jak serializovaná verze. o Vhodné pro úlohy, kde jistá hodnota mezivýsledku má velkou pravděpodobnost. • Vzniká potenciální problém při přístupu ke zdrojům (některé zdroje nemusí být sdílené v případě sekvenčního vykonávání úloh). Příklady 9 Spekulativní provádění kódu (větvení). IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 15/39 Hybridní dekompozice Kombinace různých způsobů dekompozice Příklad o Hledání minima v poli. • Sekvenční verze najde minimum v O(n). • Při použití datové a rekurzivní dekompozice lze trvání této úlohy zkrátit na 0(n/p + log(p)). 9 Vstupní pole se datově dekomponuje na p stejných částí. • Najdou se minima v jednotlivých částech v čase 0(r?/p). 9 Výsledky z jednotlivých třídění se zkombinují v čase 0(log(p)). 9 Teoreticky lze při dostatečném počtu procesorů nalézt minimum v čase 0(log(n)). 9 Tento styl paralelismu je obecně označován jako MAP-REDUCE. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 16/39 Techniky mapovaní a vyrovnávaní zátěže IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 17/39 Mapovaní úloh na vlákna/procesy. Mapování • Přiřazování úloh jednotlivým vláknům/procesům. o Optimální mapování bere v potaz grafy závislostí a interakce. • Ovlivňuje výkon aplikace. • Naivní mapování (úloha=proces/vlákno) Cíle mapování • Minimalizovat celkový čas řešení celé úlohy. • Redukovat prodlevy způsobené čekáním (idling) • Redukovat zátěž způsobenou interakcí o Redukovat režii spouštění, ukončovania přepínání • Vyrovnat zátěž na jednotlivé procesory • Maximalizovat souběžnost. • Minimalizovat zatížení systému (zatížení datových cest). • Využít dostupnost zdrojů použitých předchozí úlohou. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 18/39 Charakteristiky úloh, které ovlivňují mapovaní Způsob zadání úlohy • Statické zadání úloh - dekompozice problému na úlohy je dána v době kompilace, případně je přímo odvozena od vstupních dat. • Dynamické zadání úloh - nové úlohy jsou vytvářeny za běhu aplikace dle průběhu výpočtu, případně jako důsledek provádění původně zadaných úloh. Velikost úlohy • Relativní množství času potřebné k dokončení úlohy. 9 Uniformní vs. neuniformní. o Dopředná znalost/neznalost. Velikost dat asociovaných k úloze • Snaha o zachování lokality dat. • Různá data mají různou roli a velikost (vstupní/výstupní data u hlavolamu patnáct). IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 19/39 Charakteristiky interakcí, které ovlivňují mapování Statické vs Dynamické 9 Statické: Probíhají v předdefinovaném časovém intervalu, mezi předem známou množinou úloh. 9 Dynamické: Pokud předem neznáme počet interakcí, časový rámec interakcí, nebo participující úlohy. Další charakteristiky • Jednosměrná versus obousměrná interakce. • Mód přístupu k datům: Read-Only versus Read-Write. • Pravidelné versus nahodilé interakce. Režie související s mapováním do různých vláken/procesů • Uzpůsobení aplikace pro neočekávanou interakci. 9 Připravenost dat k odeslání / adresáta k přijetí. • Řízení přístupu ke sdíleným zdrojům. Optimalizace aplikace pro redukci prodlev. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 20/39 Schémata pro Statické Mapování Mapování založené na rozdělení dat • Bloková distribuce • Cyklická a blokově-cyklická distribuce • Náhodná distribuce bloků • Dělení grafu Mapování založené na rozdělení úloh o Dělení dle grafu závislostí úloh o Hierarchické dělení IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 21/39 Mapovaní založené na rozdělení dat Bloková distribuce datových polí Procesy svázány s daty rozdělenými na souvislé bloky. • Bloky mohou být vícerozměrné (redukce interakcí). • Příklad • Násobení matic A x B = C • Dělení matice C na 1- a 2-rozměrné bloky. Cyklická a blokově-cyklická distribuce datových polí o Nerovnoměrné množství práce spojené s jednotlivými prvky 9 =4> blokové dělení způsobuje nerovnoměrné zatížení. • Blokově-cyklická distribuce: dělení na menší díly a cyklické přiřazení procesům (round robin). 9 Zmenšování bloků vede k cyklické distribuci (blok je atomický prvek datového pole). IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 22/39 Mapovaní založené na rozdělení dat - pokračovaní Náhodná distribuce bloků 9 Zátěž související s prvky pole vytváří pravidelné vzory • =4> špatná distribuce v cyklickém rozdělení. • Náhodné přiřazení bloků procesům. Grafové dělení • Pro případy kdy je nevhodné organizovat data do polí (například drátové modely 3D objektů). • Data organizována jako graf. o Optimální dělení. Stejný počet vrcholů v jednotlivých částech. • Co možná nejmenší počet hran mezi jednotlivými částmi. • NP-úplný problém. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 23/39 Princip • Graf závislostí úloh. • Grafové dělení (NP-úplné). Speciální případy pro konkrétní tvar grafů Binární strom (rekurzivní dekompozice). Hierarchické mapování • Úlohové dělení nebere v potaz neuniformitu úloh. 9 Shlukování úloh do nad-úloh. • Definuje hierarchie (vrstvy). • Jiné mapovací a dekompoziční techniky na jednotlivých vrstvách. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů Schémata pro Dynamické Mapování Motivace • Statické mapování nedostatečné, neboť charakteristiky úloh nejsou známy v době překladu. Centralizovaná schémata dynamického mapování 9 Úlohy jsou shromažd ovány v jednom místě. • Dedikovaná úloha pro přiřazování úloh procesům. • Samo-plánování • Jakmile proces dokončí úlohu, vezme si další. • Blokové plánování Přístup ke shromaždišti úloh může být úzkým místem, • přidělování úloh po blocích. Příklad 9 Třídění prvků v n x n matici A • for (i=l; i P2, P2 -> P3, Ps -> Pa • Pi -> P2, ^2 -> IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 36/39 Redukce ceny komunikace 1/3 Komunikace v nesdíleném adresovém prostoru • Synchronizace posíláním zpráv. • Předávání dat posíláním zpráv. Komunikace ve sdíleném adresovém prostoru Synchronizace korektním přístupem ke sdíleným datům. • Předávání dat pomocí sdílených datových struktur. (FIFO) Obecné charakteristiky • Latence - doba potřebná pro doručení prvního bitu. • Přenosová rychlost - objem dat přenesených za jednotku času. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 37/39 Redukce ceny komunikace 2/3 Latence • Celková cena pro zahájení komunikace — rs • čas pro přípravu zprávy/dat • identifikace adresáta / routování • doba trvání vylití informace z cache do paměti případně na síťové rozhraní o Cena " hopů" (přeposílání uvnitř komunikační sítě) — th čas strávený na jednotlivých routerech v síti • doba, po kterou putuje hlavička zprávy z přijímacího na odesílací port Přenosová rychlost • Ovlivněno šířkou pásma r • Cena za přenos jednoho slova (word = 2 bajty) — tw = 1/r IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 38/39 Redukce ceny komunikace 3/3 Cena komunikace • m - délka zprávy ve slovech o I - počet linek, přes které zpráva putuje • ts + I * (th + mtw) Obecné metody redukce ceny • Spojování malých zpráv (amortizuje se hodnota rs) • Komprese (snižování hodnoty m) 9 Minimalizace vzdálenosti (snižování hodnoty /) Paketování (eliminace režie způsobené jednotlivými hopy) ts + I * (th + mtw) —> ts + lth + mtw IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 39/39 I IB109 Návrh a implementace paralelních systémů Kolektivní komunikační primitiva Jiří Barnat Kvantitativní parametry komunikace Komunikace (interakce) • Předávání informací mezi jednotlivými procesy Parametry komunikace • Latence — zpoždění související se započetím vlastní komunikace • Šířka pásma (bandwidth) — maximální množství dat přenesených za jednotku času • Objem — množství předávaných dat Cena komunikace 9 ts - latence, tw - šířka pásma, m - objem • ts + m * tw IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 2/55 Kvantitativní parametry komunikace Příklady • Za jak dlouho napustím hrníček vodou pomocí 2km dlouhé zahradní hadice? • Při konstantním čtení z paměti trvá získání kódu instrukce a příslušných operandů z paměti v průměru 5ns. Jaká je nejvyšší reálná rychlost vykonávání kódu uloženého v paměti 4GHz procesorem? [ 1/(5 * 10"9) = 0.2 * 109 = 200 MHz ] IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 3/55 Efektivita interakce Pozorování 9 Interakce jednotlivých úloh/procesů je nevyhnutelná • Interakce způsobuje prodlevy ve výpočtu o Režie související s interakcí by neměla být důvodem pro neefektivitu paralelního zpracování Závěr • Komunikační primitiva musí být co nejefektivnější V této přednášce • Popis různých typů komunikačních operací • Odvození ceny pro jednotlivé topologie IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 4/55 Topologie komunikační sítě Topologie o Fyzická/logická struktura komunikačních kanálů mezi jednotlivými participanty komunikace. Vlastnosti komunikační sítě • Průměr (délka maximální nejkratší cesty) o Konektivita (minimální počet disjunktních cest) • Stupeň (max. počet linek incidenčních s jedním vrcholem) • Cena • Výlučnost přístupu (použití jednou úlohou blokuje ostatní) • Rozšiřitelnost • Skálovatelnost IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 5/55 Sběrnice, Kliky Sběrnice • Sdílené médium Propustnost, klesá s počtem uzlů (je třeba cache) • Důležitost: model sdíleného adresového prostoru Kliky (úplné sítě) o Privátní neblokující spojení každého s každým 9 Cena: počet linek je kvadratický vůči N • Cena: stupeň každého uzlu je N — 1 9 Škálovatelné, za podmínky levného zvyšování stupně uzlu • Důležitost: abstraktní představa sítě, logická struktura IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 6/55 Prsteny, Hvězdice Prsten (kruh, řetěz, 1-rozměrná mřížka) • Uspořádání na uzlech o Privátní neblokující komunikace s 2 nejbližšími uzly 9 Důležitost: logická struktura komunikace, Pipeline model Hvězdice 9 Spojení přes jeden centrální uzel • Středový uzel může být úzkým místem • Lze hierarchicky vrstvit (hvězdice hvězdic) • Důležitost: Master-Slave model IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 7/55 Hyperkostka, Strom s aktivními vnitřními uzly Hyperkostka • Spojení n uzlů ve tvaru /o^n-rozměrné krychle o Stupeň uzlu je \0g2n • Průměr sítě je \0g2n • Počet linek 0(N • log(N)) • Postup konstrukce • binární označení uzlů s identifikátory 0 až 2log2ľl — 1 • linka existuje mezi uzly pokud se označení liší v jednom bitu • minimální vzdálenost uzlů odpovídá počtu odlišných bitů v označení uzlů Strom s aktivními vnitřními uzly o Strom, kde participanty komunikace jsou listy i vnitřní uzly • Kostra hyperkostky — Strom s maximální hloubkou \0g2n o Důležitost: Optimální šíření informací IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 8/55 Další topologie Jiné topologie • Z hlediska logického návrhu paralelní aplikace nezajímavé. Příklady • Obecné stromy 9 Přepojované sítě • Vícevrstvé sítě (cj-síť) • Mřížky 9 Cyklické mřížky (torrus) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 9/55 Jeden na všechny a všichni na jednoho IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 10/55 Jeden na všechny a všichni na jednoho One-To-AII Vysílání (OTA) o Úloha posílá několika/všem ostatním identická data • Ve výsledku je p kopií originální zprávy v lokálních adresových prostorech adresátů • Změna struktury dat: m i—>► p * m (rn-je velikost zprávy) All-To-One Redukce (ATO) 9 Duální operace k "One-To-AII" • Několik/všechny úlohy posílají data jedné úloze 9 Data se kombinují pomocí zvoleného asociativního operátoru 9 Ve výsledku je jedna kopie v adresovém prostoru cílové úlohy • mi ® A772 ... ® mp ^> m 9 Změna struktury dat: m * p i—>► m IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 11/55 OTA: Změna struktury dat □ /—1-\ /—1-\ □ /— □ /—1-\ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 12/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 12/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 12/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 13/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 13/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 13/55 OTA: Pro topologie prsten či řetěz Naivní způsob One-To-AII pro p procesů 9 Poslat p — 1 zpráv postupně ostatním procesům • Úzké místo: odesílatel • Síť je nevyužitá, komunikuje pouze jedna dvojice procesů Technika rekurzivního zdvojení (připomenutí) • Nejprve první proces pošle zprávu jinému procesu 9 Poté oba procesy pošlou zprávu jiné dvojici • Poté čtveřice procesů pošle zprávu jiné čtveřici • ... • První proces pošle nejvýše log(p) zpráv • Souběh zpráv na linkách sítě 9 Optimální vzdálenosti adresátů pro jednotlivá kola jsou p/2, p/4, p/8, p/16, ... IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 14/55 OTA: Pro topologii d-dimenzionální mřížka One-To-AII ve 2-rozměrné síti o p uzlech • Lze chápat jako yfp řetízků o yfp uzlech 9 V první fázi se propaguje informace do všech řetízků • V druhé fázi se souběžně propaguje informace v jednotlivých řetízcích • Celková cena: 2(/og"(y/p)) sekvenčně provedených operací One-To-AII v d-rozměrné síti • Stejný princip, velikost v jednom rozměru je p1^ • Celková cena: d{log{p1/d)) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 15/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka ô ó IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka 6 ô f f f f IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka o o o o ú ô 6 ó ô ô ô ô IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii hyperkostka Hyperkostka s 2a vrcholy • Aplikuje se algoritmus pro síť ve tvaru mřížky • d-dimenzionální síť s hloubkou sítě 2 • Každá fáze proběhne v konstantním čase (poslání 1 zprávy) • Nenastává souběžný přístup na žádnou z komunikačních linek • Celková cena: d Příklad 9 Jak proběhne One-To-AII na hyperkostce s dimenzí 5? IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 17/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 OTA: Pro hyperkostku o dimenzi 5 OTA: Pro hyperkostku o dimenzi 5 OTA: Pro hyperkostku o dimenzi 5 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 OTA: Pro hyperkostku o dimenzi 5 ATO: Duálně k OTA All-To-One Redukce pro p procesů • Probíhá duálně k operaci One-To-AII Příklad: ATO pro topologie prsten či řetěz • Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID • Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř ] [ □ 1_1 1_1 u 1-' □ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů • Probíhá duálně k operaci One-To-AII Příklad: ATO pro topologie prsten či řetěz 9 Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID • Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř 1 \ □ □ /-1-\ □ □ 1 □ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů • Probíhá duálně k operaci One-To-AII Příklad: ATO pro topologie prsten či řetěz • Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID • Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř • ... IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů • Probíhá duálně k operaci One-To-AII Příklad: ATO pro topologie prsten či řetěz • Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID • Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř /—1-\ □ /—1-\ □ /—1~\ /—1~\ _J 1 =s 1 /— □ /-1-\ /-l-\ □ /-1-\ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů • Probíhá duálně k operaci One-To-AII Příklad: ATO pro topologie prsten či řetěz • Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID • Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř /—1-\ □ /—1-\ □ /—1~\ /—1~\ □ /—1-\ □ /—1-\ /—1~\ □ /—1~\ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 Pozorování o One-To-AII procedury jsou si podobné • Jdou nahradit univerzální procedurou Univerzální algoritmy OTA vysílání a ATO Redukce o Předpokládají 2d uzlů (hyperkostka) • Každý uzel identifikován bitovým vektorem • AND a XOR bitové operace Cena 9 d(ts + mtw) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva Univerzální algoritmy - OTA vysílání (i) proč One-To-All(c/, id,X) (2) mask := 2d - 1 (3) for / := d — 1 downto 0 M mask := mas/c XO/? 2'' (5) if (/c/ /4/VD mas/c) = 0 (6) then if (id AND 2') = 0 (7) then msg_destination := /c/ XO/? 2' f<§; send X to msg_destination (9) else msg_source := /c/ XO/? 2' fi0; receive X from msg_source (11) fi ft 2; fi (13) end ft^; end IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 21/55 Univerzální algoritmy - OTA vysílání - libovolný odesílatel (i) proc General-One-To-All(c/, id, src, X) (Z) virtid := id XOR src (3) mask := 2d — 1 (4) for / := d — 1 downto 0 (5) mask := mask XOR 2' (6) if (virtid AND mask) = 0 (V then if (virtid AND 2') = 0 (8) then virt_destination := virtid XOR 2' (9) send X to (virt_destination XOR src) (10) else virt_source := virtid XOR 2' (H) receive X from (virt_source XOR src) (12) fi (13) fi (W end (15) end IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 22/55 Univerzální algoritmy - ATO Redukce (i) proč All-To-One(c/, id, m, X, sum) (2) for j := 0 to m — 1 do sum\J] := X[y] end (3) mask := 0 (4) for / := to d - 1 (5; if (id AND mask) = 0 (6) then if (/cf AND 2') = 0 f7j then msg_destination := /c/ XO/? 2 ^ send sl//t? to msg_destination (9) else msg_source := /c/ XO/? 2' fi0j receive X from msg_source (11) for 7 := 0 to a77 - 1 (i^ sumfy] := suat7[/] + X[y] (is; end (15) mask := mask XOR 2' (16) end (17) end IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva Všichni všem a všichni od všech IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 24/55 Všichni všem a všichni od všech AII-To-AII Vysílání • Všichni posílají informaci všem • Každá úloha posílá jednu zprávu všem ostatním úlohám • Ve výsledku je p kopií p originálních zpráv v lokálních adresových prostorech adresátů • Změna struktury dat: p*m^p*p*m AII-To-AII Redukce • Všichni posílají informaci všem, příchozí zprávy se kombinují • Každá úloha má pro každou jinou úlohu jinou zprávu • Změna struktury dat: p*p*m^p*m Naivní řešení 9 Sekvenční/násobné použití One-To-AII procedur o Neefektivní využití sítě IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 25/55 ATA Vysílání: Změna struktury dat □ /—1-\ /—1-\ □ /—1-\ □ /— IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 26/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 26/55 ATA Vysílání: Změna struktury dat □ /—1-\ /—1-\ □ /-1-\ □ /- IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 26/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 27/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 27/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 27/55 Prsten 9 1. fáze: každý uzel pošle informaci svému sousedovi • 2. až r?-tá fáze: uzly sbírají a přeposílají příchozí zprávy 9 Všechny linky jsou po celou dobu operace plně využité • Optimální algoritmus Řetěz • Vysílání zpráv sousedům na obě strany o Full-duplex linky =4> n — 1 fází • Half-duplex linky 2{n — 1) fází ATA Redukce o Zprávy po jedné posílány po kruhu tak, že zpráva pro nejvzdálenější uzel je poslána jako první o Při průchodu uzlem, se přikombinuje lokální zpráva pro adresáta právě procházející zprávy IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva Mřížka • 2 fáze - yfp řetízků o yfp uzlech • Po první fázi uzly mají uzly yfp částí z celkového počtu p částí zprávy 9 Příklad sítě 4x4, každý posílá své ID každému Hyperkostka • Rozšíření algoritmu pro sítě na d dimenzí • Po každé fázi (z celkového počtu d) je objem zpráv zdvojnásoben ATA Redukce • Duální postup • Po každé fázi je objem zpráv zredukován na polovinu IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 29/55 ATA Vysílání: Mřížka 03 02 6 01 Ó 00 o 07 11 15 •-O—o 06 O 05 O 04 O 10 o 09 -O 08 14 O 13 -O 12 O IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Vysíláni: Mřížka ATA Vysílání: Mřížka x3Q x3Q x3Q x3Q x3 = 03 07 11 15 x1 o xO x2| x2 O—O x1 o xO o—o x2 O x1 o xO O x2 O x2= 02 06 10 14 x1 O x1 = 01 05 09 13 xO O xO = 00 04 08 12 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Vysílání: Mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva 03 07 11 15 02 06 10 14 01 05 09 13 00 04 08 12 str. 30/55 ATA Vysílání: Mřížka X ^ X ^ X ^ X ^ O-O-O-O Ô O Ô Ô O x= 03 07 11 15 02 06 10 14 01 05 09 13 00 04 08 12 Ô 6 Ô 6 ô IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ~7m - 1 J IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA: Analýza ceny Kruh a lineární pole, p uzlů • T = (ts + twm)(p-l) 2D mřížka, p uzlů • 1. fáze (ts + mtw){^fp - 1) o 2. fáze (ts + A7?v/přw)(v^Ď - 1) • Celkem: 7 = 2ts(y/P ~ 1) + twm(p - 1) Hyperkostka, p — 2d uzlů a 7 = El°ÍiP(ts + 2/-1twm) • 7 = tslog p + tw/AT7(p - 1) Pozorování • Clen twm(p — 1) se vyskytuje vždy • Pipeline několika OTA operací IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 32/55 Všichni všem individuální komunikace IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 33/55 AII-To-AII individuální komunikace (ATA individuální) • Každá úloha posílá různá data ostatním úlohám • Dojde k výměně 2D pole zpráv (p x p) v ID prostoru (p) • Také označováno jako "totální výměna" • Změna struktury dat: P * (mi, . . . , nrip) \-± p * /T?i. p * AT?2• • • • - P * AT?p Příklad • Transpozice matice (AT[iJ] = A\J, /]) 9 Matice n x n mapována po řádcích na n úloh • Úloha j má k dispozici prvky [y, 0], [y, 1],... [y, n — 1] o Úloha j chce znát prvky [Oj], ... [n — 1J] IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva ATA Individuální: Změna struktury dat □ /—1-\ /-1-\ □ /- □ /-1-\ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 35/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 35/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 35/55 ATA individuální: Pro topologie Prsten či Řetěz Princip 9 Nejprve všechny úlohy pošlou jedním směrem zprávy pro zbývajících p — 1 úloh • V každém dalším kole každá úloha vyextrahuje zprávu, která je určena jí a zbývající zprávy přepošle • V posledním kole všechny úlohy přeposílají pouze jednu zprávu Analýza ceny • Počet kol je p — 1, všechny zprávy mají velikost m • T = ^~l(ts + twm(p-i)) = ts(p - 1) + EfJi1 itwm = (řs + twmp/2)(p - 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 36/55 ATA individuální: Pro topologii mřížky Princip • Síť je yfp řetízků o délce yfp 9 1. fáze: mezi řetízky se vymění v jednom směru zprávy tak, aby informace pro každý uzel v řetízku byla někde v řetízku obsažena • 2. fáze: v rámci řetízku se informace napropaguje na odpovídající místo Příklad • ATA individuální komunikace na síti 4x4 uzly Cena 9 Každá fáze distribuuje zprávy velikosti m^/p mezi yjp uzly 9 Cena jedné fáze (viz cena pro prsten): (ts + twmp/2)(^/p — 1) • T = (2ts + twmp)(^p - 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 37/55 ATA individuální: Pro topologii hyperkostky Princip 9 Aplikace algoritmu pro d-dimenzionální sítě o Podél jedné dimenze se posílá vždy p/2 zpráv Příklad • Krychle 2x2x2 uzlů Cena • V každé fázi vyměněno A7?p/2 dat • log p fází T = (ts + twmp/2)logp • Navíc v každé fázi uzly přeuspořádávají/třídí zprávy IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 38/55 ATA individuální: Pro topologii hyperkostky - optimalita Problém 9 Každý uzel posílá a přijímá m(p — 1) dat • Průměrná vzdálenost, na kterou data putují je (log p)/2 9 Celkový provoz na síti je p x m(p — 1) x (logp)/2 9 Počet linek v hyperkostce je p(logp)/2 • Optimální algoritmus by měl dosáhnout složitosti • Pro ATA individuální komunikaci není algoritmus pro sítě ve tvaru mříží optimální na sítích ve tvaru hyperkostky T twpm(p - l)(logp)/2 (plogp)/2 twm(p - 1) Závěr IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. ATA individuální: Optimální algoritmus pro hyperkostku (1) proč All-To-All-Personal(c/, id) (2) for / := lto 2d -1 (3) partner := id XOR i (4) send Micj to partner (5) receive Mpartner from partner (6) end (7) end Pozorování: • Systematická a symetrická volba partnera 9 Lze routovat tak, aby nedocházelo k blokování linek • E-cube routing: Cesta mezi 2 body je dána pozicí odlišných bitů těchto bodů, routuje se od nejméně významného bitu • Vyžaduje duplexní linky Cena: • T = (ts + twm)(p - 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 Operace kompletní redukce a prefixového součtu IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 42/55 Operace kompletní redukce Kompletní redukce (All reduce) • Úlohy si vzájemně vyměňují data, která se kombinují • Lze realizovat jako ATO redukci následovanou OTA vysíláním výsledku z předchozí redukce • Změna struktury dat: p * m i—>► p * m Sémantika a využití pro účely synchronizace • Úloha nemůže dokončit operaci, dokud všechny participující úlohy nepřispějí svým dílem Může být použito pro realizaci synchronizačního primitiva Implementace Naivně pomocí ATO a OTA, nebo o Modifikací operace ATA vysílání • rozdíl od ATA: zprávy se nekumulují, ale kombinují • Cena pro hyperkostku je T = (ŕs + twm)logp IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 43/55 Kompletní redukce: Změna struktury dat □ /—1-\ /—1-\ □ /—1-\ □ /— IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 44/55 Kompletní redukce: Změna struktury dat □ /—1-\ /—1-\ □ /—1-\ □ /— IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 44/55 Kompletní redukce: Změna struktury dat □ /—1-\ /—1-\ □ /-1-\ □ /- IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 44/55 Operace prefixového součtu Prefixový součet • Úlohy posílají data ostatním úlohám se stejným či menším ID o Data se kombinují (redukce) 9 Změna struktury dat: p * m i—>► p * m Příklad Data v jednotlivých uzlech: (3,1,4,0,2) • Kombinace pomocí operace součtu • Výsledná data (3,4,8,8,10) Implementace 9 Použití algoritmu pro ATA • Jak se pozná, že zpráva pochází od uzlu s menším ID? o Všechny posílaná data obohacena o identifikátor původce IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 45/55 Scatter and Gather IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 46/55 Scatter and Gather Scatter (též označováno jako ,,ScanM) • Jedna úloha posílá unikátní zprávu každé další úloze • One-To-AII individuální (personalized) komunikace o Na rozdíl od OTA vysílání se žádná data se neduplikují • Změna struktury dat: (mi,..., mp) i—>► mi,..., mp Gather (též označováno jako ■■Concatenation") • Jedna úloha sbírá unikátní data od ostatních úloh • All-To-One individuální (personalized) komunikace • Na rozdíl od ATO redukce se nevyskytuje kombinace dat • Změna struktury dat: mi,..., mp i—>► (mi,..., mp) Implementace o Využití algoritmů pro ATO a OTA 9 Celkem log p fází, s každou fází se objem dat zvětšuje • T = ts(logp) + twm(p - 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 47/55 Scatter: Změna struktury dat □ /—1-\ á /-1-\ □ /- □ /- IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 48/55 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 48/55 Scatter: Změna struktury dat □ /—1-\ /—1-\ □ /— □ /—1-\ IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 48/55 Gatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 49/55 Gatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 49/55 Gatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 49/55 Cyklický posun IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 50/55 Permutace Permutace 9 Obecnější komunikační primitiva • Současně probíhající OTO přerozdělování dat • Jedna úloha posílá data jedné jiné úloze Příklad o Cyklický posun o q (circular q-shift) • p úloh • Úloha / posílá data úloze (/ + q) modp Použití • Specifické maticové operace • Vyhledávání vzorů v textu či obrazu IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 51/55 Cyklický posun - Sítě ve tvaru mřížek 1-dimenzionální • Intuitivně: rotace o q pozic • Směr rotace závislý na q, určí se dle výrazu min(q, p — q) Dvourozměrné sítě • Akcelerace cyklického posunu s využitím druhé dimenze než, ve které probíhá posun • Jedna dimenze má rozměr yfp uzlů o Posun v druhé dimenzi akceleruje o yfp kroků Cena 9 Nejvzdálenější posun v jedné dimenzi je y/p/2 • T = (ts + twm)(y/p) Příklad • Síť 4x4 uzly, cyklický posun o 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 52/55 Cyklický posun - Síť ve tvaru hyperkostky Princip • Mapování lineárního pole na hyperkostku dimenze d • Zrcadlený šedý kód (reflected Grey code): i = G(/, d) • G(0,1) = 0 • G(l,l) = l • G(/, x + 1) = if / < 2X G(/, x) else 2X + G(2X+1 - 1 - /, x) • q se vyjádří jako součet mocnin čísla 2 • Posun proběhne v tolika fázích, kolik je členů v součtu Cena • Uzly ve vzdálenosti mocniny čísla 2, jsou od sebe vzdáleny nejvýše 2 kroky (vlastnost kódu) • Členů v součtu je nejvýše log p 9 Komunikace probíhá bez blokování linek 9 T = (ts + mtw)(2log p) • Se zpětným posunem je počet sčítanců max. (logp)/2 • T = (ts + mtw)(logp) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 53/55 Binary Reflected Grey code IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 54/55 Práce na doma Nebodovaný domácí úkol 9 Projděte si probraná komunikační primitiva, a znovu odvoďte jejich cenu pro jednotlivé topologie. IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 55/55 I IB109 Návrh a implementace paralelních systémů Programování aplikací pro prostředí s distribuovanou pamětí Jiří Barnat Principy programování s předáváním zpráv IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 2/60 Vymezení prostředí Paradigma - předávání zpráv Nesdílený adresový prostor • Explicitní paralelismus Pozorování o Data explicitně dělena a umístěna do jednotlivých lokálních adresových prostorů. • Datová lokalita je klíčová vlastnost pro výkon. 9 Komunikace vyžaduje aktivní účast komunikujících stran. • Existují efektivně implementované podpůrné knihovny. • Programátor je zodpovědný za paralelizaci algoritmu. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 3/60 Struktura programů s předáváním zpráv Asynchronní paradigma • Výpočet začne ve stejný okamžik (synchronně), ale ... o Probíhá asynchronně (různá vlákna různou rychlostí). • Možnost synchronizace v jednotlivých bodech výpočtu. 9 Neplatí "Trojúhelníková nerovnost" v komunikaci. Další vlastnosti • Vykazuje nedeterministické chování. • Těžší prokazování korektnosti. • Možnost provádění zcela odlišného kódu na jednotlivých procesních jednotkách. • Typicky však "Single program multiple data". • Každá procesní jednotka má jednoznačnou identifikaci. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 4/60 Send a Receive - Základní stavební kameny IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 5/60 Send a Receive send(void *sendbuf, int nelems, int dest) receive(void *recvbuf, int nelemns, int src) • sendbuf - ukazatel na bafr (blok paměti), kde jsou umístěna data připravená k odeslání. • recvbuf - ukazatel na bafr (blok paměti), kam budou umístěna přijatá data. o nelems - počet datových jednotek, které budou poslány, či přijaty (délka zprávy). o dest - adresát odesílané zprávy, tj. ID toho, komu je zpráva určena. • src - odesilatel zprávy, tj. ID toho, kdo zprávu poslal, nebo toho, od koho chci zprávu přijmout. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 6/60 Příklad na send a receive Příklad 9 Paralelní systém s 2 procesy 1 PO Pl 2 3 a = 100; receive (&a, 1, 0); 4 send(&a, 1, 1); printf ("Vo^n", a); 5 a = 0; Výstup a efektivita • Co by mělo být na výstupu procesu Pl? • Asynchronní sémantika send() a receive(). o Nutné z důvodu zachování výkonu aplikace. • Co může být na výstupu procesu Pl? IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 7/60 Blokující nebafrované operace Blokující operace • Operace send() ukončena až tehdy, je-li to bezpečné vzhledem k sémantice, tj. že příjemce obdrží to, co bylo obsahem odesílaného bafru v okamžiku volání operace send(). • Ukončení operace sendO nevynucuje a negarantuje, že příjemce již zprávu přijal. • Operace receive() skončí po přijetí dat a jejich umístění na správné místo v paměti. Nebafrované operace o Operace send() skončí až po dokončení operace komunikace, tj. až přijímací proces zprávu přijme. 9 V rámci operací send() a receive() před samotným přenosem dat probíhá synchronizace obou participujících stran (handshake). IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 8/60 Blokující nebafrované operace - problémy Prodlevy o Způsobeno synchronizací před vlastní komunikací. • Proces, který dosáhne bodu, kdy je připraven komunikovat čeká, až do stejného bodu dospěje i druhý proces. • Volání send() a receive() ve stejný okamžik nelze garantovat na úrovni kódu. • Nemá velký vliv, pokud dominuje čas komunikace. Uváznutí (deadlock) 1 PO 2 3 send(&a, 1, 1); 4 receive(&b, 1, 1); Pl send(&a, 1, 0); receive(&b, 1, 0); IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 9/60 Blokující bafrované operace Bafr v bafrované komunikaci o Extra paměť zdánlivě mimo adresový prostor procesů. • Mezisklad zpráv při komunikaci. Bafrované komunikační operace • Operace send() skončiv okamžiku, kdy odesílaná data kompletně překopírována do bafru. • Případná modifikace posílaných dat po skončení operace send(), ale před započetím vlastní komunikace se neprojeví. • Volání send(), vlastní komunikace a následné volání receiveQ na přijímací straně se nemusí časově překrývat. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 10/60 Blokující bafrované operace - problémy Režie související s bafrováním o Eliminace prodlev za cenu režie bafrování. • Ve vysoce synchroniích aplikacích může být horší než používání blokujících nebafrovaných operací. Velikost bafrů • Pokud odesílatel generuje zprávy rychleji, než je příjemce schopen zprávy přijímat, velikost bafrů může neúměrně růst (problém producent-konzument). • Pokud je velikost pro bafry omezená, může docházet (a to nedeterministicky) k situaci, kdy je předem daná velikost bafrů nedostatečná (buffer overflow). o Případné samovolné blokování odesílatele do té doby, než odesílatel přijme nějaká data a bafry se uvolní, může vést k uváznutí, podobně jako v případě nebafrované blokující komunikace. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 11/60 Blokující bafrované operace - problémy Uváznutí (i bez blokování odesílatele) 1 PO Pl 2 3 receive(&b, 1, 1); receive(&b, 1, 0); 4 send(&a, 1, 1); send(&a, 1, 0); Asymetrický model blokující bafrované komunikace • Neexistence odpovídajících prostředků pro bafrovanou komunikaci na úrovni komunikační vrstvy. • Operace send() je blokující nebafrovaná. 9 Přijímací proces je přerušen v běhu a zpráva je přijata do bafru, kde čeká, dokud přijímací proces nezavolá odpovídající operaci receive(). • Dedikované vlákno pro obsluhu komunikace. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 12/60 Neblokující operace Motivace • Komunikace, která nezpůsobuje prodlevy. Neblokující operace • Volání funkce může skončit dříve, než je to sémanticky bezpečné. • Existuje funkce na zjištění stavu komunikující operace. 9 Program nesmí modifikovat odesílaná data, dokud komunikace neskončí. • Po dobu trvání komunikace program může vykonávat kód. o Překrývání výpočtu a komunikace. HW Realizace o DMA IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 13/60 Přehled komunikačních módů Blokující Neblokující Bafrované send skončí jakmile jsou data nakopírována do bafru send skončí jakmile je inicializován DMA přenos Nebafrované send skončí až po skončení odpovídajícího receive send skončí ihned, odešle se pouze požadavek na komunikaci Sémantiku operací nelze porušit Korektní dokončení operací nutné zjišťovat opakovaným dotazováním se IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 14/60 Message Passing Interface IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 15/60 Message Passing Interface Standardizuje syntax a sémantiku komunikačních primitiv • Přes 120 knihovních funkcí 9 Rozhraní pro C, Fortran 9 MPI verze 1.2 • MPI verze 2.0 (Paralelní l/O, C++ rozhraní, ...) • Existují různé implementace standardu o mpich • LAM/MPI • Open MPI • http://www.mpi-forum.org/ IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 16/60 Minimální použití MPI MPI funkce Význam MPI_Init MPI_Finalize MPI_Comm_size MPI_Comm_rank MPI_Send MPI_Recv Inicializuje MPI Ukončuje MPI Vrací počet participujících procesů Vrací identifikátor volajícího procesu Posílá zprávu Přijímá zprávu • Definice typů a konstant: #include "mpi.h" • Návratová hodnota při úspěšném volání fce: MPI_SUCCESS • Kompilace: mpicc, mpiCC, mpiC++ • Spuštění programu: mpirun IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 17/60 Inicializace a ukončení MPI knihovny Inicializace o Nastavuje MPI prostředí • Musí být voláno na všech procesorech • Musí výt voláno jako první MPI funkce • argv nesmí být modifikováno před voláním MPI_Init • MPI_Init(int *argc, char ***argv) Finalizace • Ukončuje MPI prostředí • Musí být voláno na všech procesech o Nesmí být následováno voláním MPI funkce • Provádí různé úklidové práce • int MPI FinalizeO IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 18/60 M PI komunikátory Komunikační domény • Sdružování participujících procesorů do skupin 9 Skupiny se mohou překrývat Komunikátory o Proměnné, které uchovávají komunikační domény • Typ MPI_Comm • Jsou argumentem všech komunikačních funkcí MPI • Výchozí komunikátor: MPI_C0MM_W0RLD Zjišťování velikosti domény a identifikátoru v rámci domény • int MPI_Comm_size(MPI_Comm comm, int *size) 9 int MPI_Comm_rank(MPI_Comm comm, int *rank) • rank je identifikátor procesu v dané doméně o rank číslo v intervalu [0,size-l] IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 19/60 Hello World 1 #include "mpi.h" 2 3 main (int arge, char *argv[]) 4 { 5 int npes, myrank; 6 7 MPI_Init (&argc, &argv); 8 MPI_Comm_size(MPI_COMM_WORLD, &npes); 9 MPI_Comm_rank(MPI_COMM_WORLD, tonyrank); 10 11 printf("Hello World! (%d out of %d)", 12 myrank,npes); 13 14 MPI_Finalize(); 15 } IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 20/60 Posílání zpráv int MPI_Send(void *t>uf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) • Odešle data odkazovaná ukazatelem buf • Na data se nahlíží jako na sekvenci instancí typu datatype • Odešle se count po sobě jdoucích instancí • dest je rank adresáta v komunikační doméně určené komunikátorem comm • tag o Přiložená informace typu int v intervalu [0,MPI_TAG_UB] • Pro příjemce viditelná bez čtení obsahu zprávy • Typicky odlišuje typ zprávy IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 21/60 Korespondence datových typů MPI a C M PI datový typ Odpovídající datový typ v C MPI_CHAR signed char MPI_SH0RT signed short int MPI_INT signed int MPI_L0NG signed long int MPI_UNSIGNED_CHAR unsigned char MPI_UNSIGNED_SHORT unsigned short int MPI_UNSIGNED unsigned int MPI_UNSIGNED_LONG unsigned long int MPI_FL0AT float MPI_DOUBLE double MPI_L0NG_D0UBLE long double MPI_BYTE — MPI_PACKED — IB109 Návrh a implementace paralelních systémů: Programování a plikací pro prostředí s distribuovanou pamětí str. 22/60 int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status) 9 Přijme zprávu od odesílatele s rankem source v komunikační doméně comm s tágem tag 9 source může být MPI_ANY_SOURCE • tag může být MPI_ANY_TAG • Zpráva uložena na adrese určené ukazatelem buf • Velikost bafru je určena hodnotami datatype a count • Pokud je bafr malý, návratová hodnota bude MPI_ERR_TRUNCATE IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 23/60 Přijímání zpráv - MPI_Status MPI_Status typedef struct MPI_Status { int MPI_SOURCE; int MPI_TAG; int MPI_ERROR; • Vhodné zejména v případě příjmu v režimu MPI_ANY_SOURCE nebo MPI_ANY_TAG • MPI_Status drží i další informace, například skutečný počet přijatých dat (délka zprávy) int MPI_Get_count(MPI_Status *status, MPI_Datatype datatype, int *count) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 24/60 Posílání a přijímání zpráv - sémantika MPI_Recv 9 Volání skončí až jsou data umístěna v bafru Blokující receive operace MPI_Send • MPI standard připouští 2 různé sémantiky 1) Volání skončí až po dokončení odpovídající receive operace 2) Volání skončí jakmile jsou posílaná data zkopírována do bafru • Změna odesílaných dat je vždy sémanticky bezpečná 9 Blokující send operace Možné důvody uváznutí • Jiné pořadí zpráv při odesílání a přijímání • Cyklické posílání a přijímání zpráv (večeřící filozofové) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 25/60 Současné posílání a přijímání zpráv MPI_Sendrecv • Operace pro současné přijímání i odesílání zpráv 9 Nenastává cyklické uváznutí • Bafry pro odesílaná a přijímaná data musí být různé int MPI_Sendrecv ( void *sendbuf, int sendcount, MPI_Datatype senddatatype, int dest, int sendtag, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, int source, int recvtag, MPI_Comm comm, MPI Status *status) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 26/60 Současné posílání a přijímání zpráv - Sendrecv_replace Problémy MPI_Sendrecv • Bafry pro odesílaná a přijímaná data zabírají 2x tolik místa • Složitá manipulace s daty díky 2 různým bafrům MPI_Sendrecv_replace • Operace odešle data z bafru a na jejich místo nakopíruje přijatá data int MPI_Sendrecv_replace ( void *buf, int count, MPI_Datatype datatype, int dest, int sendtag, int source, int recvtag, MPI_Comm comm, MPI Status *status) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 27/60 Neblokující komunikace IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 28/60 int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request) int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request) MPI_Request • Identifikátor neblokující komunikační operace 9 Potřeba při dotazování se na dokončení operace IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí Dokončení neblokujících komunikačních operací int MPI_Test(MPI_Request *request, int *flag, MPI_Status *status) Nulový flag znamená, že operace ještě probíhá • Při prvním volání po dokončení operace se naplní status, zničí request a flag nastaví na true int MPI_Wait(MPI_Request *request, MPI_Status *status) o Blokující čekání na dokončení operace • Po dokončení je request zničen a status naplněn int MPI_Request_free(MPI_Request *request) • Explicitní zničení objektu request • Nemá vliv na probíhající operaci IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 30/60 Neblokující operace - poznámky Párování • Neblokující a blokující send a receive se mohou libovolně kombinovat Uváznutí 9 Neblokující operace řeší většinu problémů s uváznutím o Neblokující operace mají vyšší paměťové nároky 9 Později zahájená neblokující operace může skončit dříve IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 31/60 Kolektivní komunikace IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 32/60 Kolektivní operace • Množina participujících procesů je určena komunikační doménou (MPI_Comm). • Všechny procesy v doméně musí volat odpovídající MPI funkci. o Obecně se kolektivní operace nechovají jako bariéry, tj. jeden proces může dokončit volání funkce dříve, než jiný proces vůbec dosáhne místa volání kolektivní operace. • Forma virtuální synchronizace. Nepoužívají tágy (všichni vědí jaká operace se provádí). • Pokud je nutné specifikovat zdrojový, či cílový proces, musí tak učinit všechny participující procesy a jejich volba cílového, či zdrojového procesu musí být shodná. • MPI podporuje dvě varianty kolektivních operací • posílají se stejně velká data (např. MPI_Scatter) • posílají se různě velká data (např. MPI_Scatterv) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 33/60 Bariéra int MPI_Barrier(MPI_Comm comm) • Základní synchronizační primitivům. • Volání funkce skončí pokud všechny participující procesy zavolají MPI_Barrier. • Není nutné, aby volaná funkce byla "na stejném místě v programu". IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 34/60 Kolektivní komunikační primitiva a MPI Operace Jméno MPI funkce OTA vysílání AT O redukce ATA vysílání ATA redukce Kompletní redukce Gather Scatter ATA zosobněná komunikace MPI_Bcast MPI_Reduce MPI_Allgather M Pl_Reduce_scatter MPI_Allreduce MPI_Gather MPI_Scatter MPI Alltoall IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 35/60 Všesměrové vysílání - OTA int MPI_Bcast (void *t>uf, int count, MPI_Datatype datatype, int source, MPI_Comm comm) • Rozesílá data uložená v bafru buf procesu source ostatním procesům v doméně comm. o Kromě buf musí být parametry funkce shodné ve všech participujících procesech. o Parametr buf na ostatních procesech slouží pro identifikaci bafru pro příjem dat. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 36/60 int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_0p op, int target, MPI_Comm comm) • Data ze sendbuf zkombinována operací op do recvbuf procesu target. • Všichni participující musí poskytnout recvbuf i když výsledek uložen pouze na procesu target. • Hodnoty count, datatype, op, target musí být shodné ve všech volajících procesech. 9 Možnost definovat vlastní operace typu MPI_0p. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 37/60 Operátory redukce Operace Význam Datové typy MPI_ _MAX Maximum C integers and floating points MPI_ _MIN Minimum C integers and floating points MPI_ _SUM Součet C integers and floating points MPI_ _PR0D Součin C integers and floating points MPI_ _LAND Logické AND C integers MPI_ _BAND Bitové AND C integers and byte MPI_ _L0R Logické 0R C integers MPI_ _B0R Bitové 0R C integers and byte MPI_ _LX0R Logické X0R C integers MPI_ _BX0R Bitové X0R C integers and byte MPI_ _MAXL0C Maximum a minimální pozice s maximem Datové dvojice MPI_ _MINL0C Minimum a minimální pozice s minimem Datové dvojice IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 38/60 Datové páry a Kompletní Redukce MPI datové páry C datový typ MPI _2INT int, int MPI _SH0RT_INT short, int MPI _L0NG_INT long, int MPI. _L0NG_D0UBLE_INT long double, int MPI. _FL0AT_INT float, int MPI. _DOUBLE_INT double, int int MPI_Allreduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_0p op, MPI_Comm comm) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 39/60 Prefixový součet int MPI_Scan(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_0p op, MPI_Comm comm) • Provádí prefixovou redukci. • Proces s rankem / má ve výsledku hodnotu vzniklou redukcí hodnot procesů s rankem 0 až / včetně. • Jinak shodné s redukcí. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 40/60 e int MPI_Gather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, int target, MPI_Comm comm) • Všichni posílají stejný typ dat. 9 Cílový proces obdrží p bafrů seřazených dle ranku odesílatele. • recvbuf, recvcount, recvbuf platné pouze pro proces s rankem target. o recvcount je počet odeslaných dat jedním procesem, nikoliv celkový počet přijímaných dat. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 41/60 Allgather int MPI_Allgather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, MPI_Comm comm) • Bez určení cílového procesu, výsledek obdrží všichni. • recvbuf, recvcount, recvdatattype musí být platné pro všechny volající procesy. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 42/60 Vektorová varianta Gather int MPI_Gatherv(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvdatatype, int target, MPI_Comm comm) • Odesílatelé mohou odesílat různě velká data (různé hodnoty sendcount). • Pole recvcounts udává, kolik dat bylo přijato od jednotlivých procesů. • Pole displs udává, kde v bafru recvbuf začínají data od jednotlivých procesů. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 43/60 Vektorová varianta Allgather int MPI_Allgatherv(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvdatatype, MPI Comm comm) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 44/60 Scatte int MPI_Scatter(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, int source, MPI_Comm comm) • Posílá různá data stejné velikosti všem procesům. int MPI_Scatterv(void *sendbuf, int *sendcounts, int *displs, MPI_Datatype senddatatype, void *recvbuf, int recvcounts, MPI_Datatype recvdatatype, int source, MPI_Comm comm) o Posílá různá data různé velikosti všem procesům. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 45/60 Alltoall int MPI_Alltoall(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, MPI_Comm comm) • Posílá stejně velké části bafru sendbuf jednotlivým procesům v doméně comm. • Proces / obdrží část velikosti sendcount, která začíná na pozici sendcount * i. • Každý proces má v bafru recvbuf na pozici recvcount * i data velikosti recvcount od procesu /. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 46/60 Vektorová varianta Alltoall int MPI_Alltoallv(void *sendbuf, int *sendcounts, int *sdispls, MPI_Datatype senddatatype, void *recvbuf, int *recvcounts, int *rdispls, MPI_Datatype recvdatatype, MPI_Comm comm) • Pole sdispl určuje, kde začínají v bafru sendbuf data určená jednotlivým procesům. • Pole sendcounts určuje množství dat odesílaných jednotlivým procesům. • Pole rdispls a recvcounts udávají stejné informace pro přijatá data. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 47/60 Skupiny, komunikátory a topologie IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 48/60 Dělení komunikační domény int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm) 9 Kolektivní operace, musí být volána všemi. o Parametr color určuje výslednou skupinu/doménu. • Parametr key určuje rank ve výsledné skupině. • Při shodě key rozhoduje původní rank. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 49/60 Mapovaní procesů Nevýhody "ručního11 mapování • Pravidla mapování určena v době kompilace programu. • Nemusí odpovídat optimálnímu mapování. o Nevhodné zejména v případech nehomogenního prostředí. Mapování přes MPI • Mapování určeno za běhu programu. • MPI knihovna má k dispozici (alespoň částečnou) informaci o síťovém prostředí (například počet použitých procesorů v jednotlivých participujících uzlech). 9 Mapování navrženo s ohledem na minimalizaci ceny komunikace. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 50/60 Kartézské topologie int MPI_Cart_create ( MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart) o Pokud je v původní doméně comm_old dostatečný počet procesorů, tak vytvoří novou doménu comm_cart s virtuální kartézskou topologií. • Funkci musí zavolat všechny procesy z domény comm_old. 9 Parametry kartézské topologie • ndims - počet dimenzí • dims [] - pole rozměrů jednotlivých dimenzích • periods[] - pole příznaků cyklické uzavřenosti dimenzí • Příznak reorder značí, že ranky procesů se mají v rámci nové domény vhodně přeuspořádat. • Nepoužité procesy označeny rankem MPI_COMM_NULL. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 51/60 Koordináty procesorů v kartézských topologiích • Komunikační primitiva vyžadují rank adresáta. 9 Překlad z koordinátu (coords []) do ranku int MPI_Cart_rank (MPI_Comm comm_cart, int *coords, int *rank) 9 Překlad z ranku na koordináty • maxdims je velikost vstupního pole coords [] int MPI_Cart_coord(MPI_Comm comm_cart, int rank, int maxdims, int *coords) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 52/60 Dělení kartézských topologií int MPI_Cart_sub(MPI_Comm comm_cart, int *keep_dims, MPI_Comm *comm_subcart) • Pro dělení kartézských topologií na topologie s menší dimenzí. 9 Pole příznaků keep_dims určuje, zda bude odpovídající dimenze zachována v novém dělení. Příklad • Topologie o rozměrech 2x4x7. • Hodnotou keep_dims = {true,false,true}. • Vzniknou 4 nové domény o rozměrech 2x7. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 53/60 Případová studie implementace verifikačního nástroje DiVinE IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 54/60 DiVinE-Cluster 9 Softwarový nástroj pro verifikaci protokolů (LTL MC). • Problém detekce akceptujícího cyklu v grafu. o Algoritmy paralelně prochází graf konečného automatu. • Standardní průzkumová dekompozice. Algoritmus MAP o Detekuje, zda existuje akceptující vrchol, který je svůj vlastní předchůdce. Algoritmus OWCTY • Označuje vrcholy, které nejsou součástí akceptujícího cyklu • nemají přímé předchůdce (neleží na cyklu), • nemají akceptující předky (neleží na akceptujícím cyklu). IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 55/60 Co bylo špatně Obecně a Při testování na standardním Ethernetu, na malém počtu počítačů, některé nedokonalosti zůstaly neodhaleny. Konkrétní problémy • Po inicializaci některých počítačů, aktivita těchto počítačů zabránila inicializaci ostatních počítačů - obrovské prodlevy při startu výpočtu. 9 Kombinace posílaných zpráv (bafrování na aplikační úrovni) • Příliš časté vylívání- komunikovaly se prázdné bafry. • Vylití všech bufferů najednou - náhlá velká zátěž sítě (contention). Používání časových známek a vylívání na základě času -netriviální režie způsobená ověřováním zda uplynulo dané množství času. • Příliš časté dotazování se na příchozí zprávy. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 56/60 Runtime (sec) IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 57/60 Výsledky optimalizací □5 35 — 30 h 8 25 h ® 20 h optimized OWCTY, 64*2 CPU cores original OWCTY, 64*2 CPU cores ± 300 400 500 Runtime (sec) ± 600 700 IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 58/60 Paralelní výkon nástroje DiVinE Nodes Total cores Runt MAP ime (s) OWCTY Effi MAP ciency OWCTY 1 1 956.8 628.8 100% 100% 16 16 73.9 42.5 81% 92% 16 32 39.4 22.5 76% 87% 16 64 20.6 11.4 73% 86% 64 64 19.5 10.9 77% 90% 64 128 10.8 6.0 69% 82% 64 256 7.4 4.3 51% 57% Table: Efficiency of MAP and OWCTY IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 59/60 Domácí úkol (4 body) Zadání • Napište MPI aplikaci, ve které si participující procesy mezi sebou zvolí jednoho velitele. • Volba musí být realizována pomocí generování náhodných čísel a jejich výměny mezi jednotlivými MPI procesy. 9 Při spuštění tato aplikace vypíše autorovo UČO. • Kód spustitelný a přeložitelný na nymf e50. Odevzdání Odevzdání • Termín do 8. 5. 2013 23:59. 9 Odevzdávárna v ISu, zabaleno programem TAR a komprimováno GZIPem: IB109_02_učo.tar.gz 9 Archiv obsahuje sbalený adresář IB109_02_učo. 9 Povinně obsahuje Makefile. • Provedení make uvnitř adresáře přeloží a spustí aplikaci. • Nesprávné odevzdání jde na vrub studenta. IB109 Návrh a implementace paralelních systémů: Programování aplikací pro prostředí s distribuovanou pamětí str. 60/60 IB109 Návrh a implementace paralelních systémů Analytický model paralelních programů Jiří Barnat Analytický model paralelních programů Vyhodnocování sekvenčních algoritmů • Časová a prostorová složitost • Funkce velikosti vstupu Vyhodnocování paralelních algoritmů • Paralelní systém = algoritmus + platforma • Složitost 9 Přínos paralelismu • Přenositelnost • . .. V této kapitole • Jak posuzovat výkon paralelních algoritmů a systémů IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 2/35 Režie (overhead) paralelních programů IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 3/35 Režie (overhead) paralelních programů N-násobné zrychlení • S použitím r?-násobných HW zdrojů, lze očekávat r?-násobné zrychlení výpočtu. • Nastává zřídka z důvodů režií paralelního řešení. • Pokud nastane, je jeho důvodem často neoptimální řešení sekvenčního algoritmu. Důvody 9 Režie - interakce, prostoje, složitost paralelního algoritmu Nerovnoměrné zvyšování HW zdrojů Zvýšení počtu procesorů nepomůže, pokud aplikace není závislá na čistém výpočetním výkonu IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 4/35 Režie (overhead) paralelních programů Komunikace • Cena samotné komunikace. • Příprava dat k odeslání, zpracování přijatých dat. Prostoje (Lelkování, Idling) • Nerovnoměrná zátěž na jednotlivá výpočetní jádra. 9 Čekání na zdroje či data. • Nutnost synchronizace asynchronních výpočtů. Větší výpočetní složitost paralelního algoritmu 9 Sekvenční algoritmus nejde paralelizovat (DFS postorder). • Typicky existuje vícero paralelních algoritmů, je nutné charakterizovat, čím se platí za paralelismus. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 5/35 Metriky výkonosti IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 6/35 Otázky • Jak měřit výkon/kvalitu paralelního algoritmu? • Podle čeho určit nejlepší/nejvhodnější algoritmus pro danou platformu? Čas výpočtu - sekvenční algoritmus • Doba, která uplyne od spuštění výpočtu do jeho ukončení. • T s Čas výpočtu - paralelní algoritmus • Doba, která uplyne od spuštění výpočtu do doby, kdy skončí poslední z paralelních výpočtů. • Zahrnuje distribuci vstupních i sběr výstupních dat. • T p IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů Celková režie paralelismu (Total overhead) Celková režie: 9 Označujeme Tq 9 Veškeré elementy způsobující režii paralelního řešení. 9 Celkový čas paralelního výpočtu bez času potřebného pro výpočet problému optimálním sekvenčním řešením. • Paralelní a sekvenční algoritmy mohou být zcela odlišné. • Sekvenčních algoritmů může existovat víc. • 7~s čas výpočtu nejlepšího sekvenčního algoritmu (řešení). Funkce celkové režie • Jaký je čas výpočtu jednotlivých procesů? 9 Doba od skončení výpočtu jednoho procesu do skončení celého paralelního výpočtu se považuje za režii (idling). • T0 = pTP - Ts IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 8/35 Zrychlení (Speed-up) Základní přínos paralelizace 9 Problémy jdou vždy řešit sekvenčním algoritmem. • Paralelizací lze dosáhnout pouze zrychlení výpočtu. • Ostatní výhody jsou diskutabilní a těžko měřitelné. Základní míra účinnosti samotné paralelizace • Poměr časů potřebných k vyřešení úlohy na jedné procesní jednotce a p procesních jednotkách. o Uvažuje se vždy čas nejlepšího sekvenční algoritmu. • V praxi se často (a nesprávně) používá čas potřebný k vyřešení úlohy paralelním algoritmem spuštěném na jedné procesní jednotce. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 9/35 Teoretická hranice zrychlení 9 S použitím p procesních jednotek je maximální zrychlení p. Super-lineární zrychlení • Jev, kdy zrychlení je větší jak p. Pozorování o Zrychlení lze měřit i asymptoticky. Příklad - sčítání n čísel s použitím n procesních jednotek. • Sekvenčně je potřeba 0(r?) operací, čas 0(r?) • Paralelně je potřeba 0(r?) operací, ale v čase Q(log n) • Zrychlení S = 0(^) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 10/35 Super-lineárnř zrychlení Falešné super-lineární zrychlení • Uvažme datovou distribuci na 2 procesní jednotky, a operaci kvadratickou ve velikosti dat. 2 9 Zrychlení S = -Ay^ — 4 při použití 2 procesních jednotek. V 2 ) • Problém - neuvažován optimální sekvenční algoritmus. Skutečné super-lineární zrychlení o Větší agregovaná velikost cache pamětí. • Při snížení množství dat na jeden procesní uzel se účinnost cache pamětí zvýší. • Výpočet je na ^ datech víc jak p-krát rychlejší. Super-lineární zrychlení v závislosti na instanci problému 9 Průzkumová dekompozice úlohy při hledání řešení. Paralelní verze může vykonat menší množství práce. • V konkrétní instanci lze paralelní prohledávání simulovat i sekvenčním algoritmem, obecně ale nelze. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 11/35 Amdahlův zákon Otázka • Jaké je největší možné zrychlení systému, pokud se paralelizací urychlí pouze část výpočtu? Amdahlův zákon (1-P)+ sP 9 P - podíl systému, který je urychlen paralelizací • Sp - zrychlení dosažené paralelizací nad daným podílem Příklad • Paralelizací lze urychlit 4-násobně 30% kódu, tj. P = 0.3 a SP = 4. 9 Maximální celkové zrychlení Smax je 1 1 1 5 =_=_=_= 1 29 max (i_0.3) + ^3 0.7 + 0.075 0.775 IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 12/35 Fakta • Pouze ideální paralelní systém s p procesními jednotkami může dosahovat zrychlení p. • Část výpočtu prováděná na jednom procesoru je spotřebována režií. Procesor nevěnuje 100% výkonu řešení problému. Efektivita • Lze definovat jako podíl zrychlení S vůči počtu jednotek p. _ S _ Ts/Tp Ts •E=^= - T P P PTP 9 Zrychlení je v praxi < p, efektivita v rozmezí (0,1 • " Podíl času, po který jednotka vykonává užitečný kód." IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 13/35 Efektivita - příklady Příklad 1 • Jaká je efektivita sčítání n čísel na n procesorech? • 5 = 0^) • E = 0(f) = 0(^) Příklad 2 • Na kolik se zkrátí 100 vteřinový výpočet při použití 12 procesorů při 60% efektivitě? • 0-6 = ÍS =* *=ofí2 x = 13.88 IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 14/35 Cena Cena řešení problému na daném paralelním systému • Součin počtu procesních jednotek a doby paralelního výpočtu: C = p x T p • Označována také jako "množství práce", které paralelní systém vykoná, nebo jako "pTp produkt". 9 Alternativně lze použít pro výpočet účinnosti (E = ^-). Cenově optimální paralelní systém o Cena sekvenčního výpočtu odpovídá nejlepšímu T$- o Paralelní systém je cenově optimální, pokud cena řešení roste asymptoticky stejně rychle jako cena sekvenčního výpočtu. • Cenově optimální systém musí mít efektivitu rovnou 0(1). Příklad • Sčítání n čísel na n procesorech 9 C = Q(nlog n), není cenově optimální IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 15/35 Cena - příklad • Uvažme n procesorový systém, který třídí (řadí) seznam n čísel v čase (log n)2 9 Nejlepší sekvenční algoritmus má 7~s = n log n • S = —— E = log n ' log n 9 C — n(log n)2 9 Není cenově optimální, ale pouze o faktor log n 9 Uvažme, že v praxi p << n (p je mnohem menší než n) 9 TP = n(log n)2/p a tedy S = ^ • Konkrétně: n = 210, log n = 10 a p = 32 S = 3.2 • Konkrétně: n = 220, /o# n = 20 a p = 32 S = 1.6 • Závěr: cenová optimalita je nutná IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 16/35 Vliv granularity na cenovou optimalitu IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 17/35 Vliv granularity na cenovou optimalitu Tvrzení • Volbou granularity lze ovlivnit cenu paralelního řešení. Pozorování • V praxi p << n, přesto navrhujeme algoritmy tak, aby granularita byla až na úrovni jednotlivých položek vstupu, tj. předpokládáme p — n. Deškálování (scale-down) • Uměle snižujeme granularitu (vytváříme hrubší úlohy). 9 Snižujeme overhead spojený s komunikací. • Může ovlivnit cenu a cenovou optimalitu. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 18/35 Vliv granularity na cenovou optimalitu Příklad 1) • Sčítání n čísel na p procesorech (r? = 16, p = 4) • Mapování (/ modp), tj. (r?/p) čísel na 1 procesor. • Simulace prvních logp kroků stojí (n/p)log p operací, tj. proběhne v čase 0((r?/p)logp). Následně simulace původního algoritmu probíhá lokálně v paměti jednoho procesoru, tj. v čase 0(r?/p). • Celkový Tp je Q{{n/p)log p) • Cena C = Q(nlogp), tj. není cenově optimální o Původní 7~p bylo Q(log n), změna o faktor ^(^-^) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 19/35 Vliv granularity na cenovou optimalitu Příklad 2) 9 Sčítání n čísel na p procesorech (r? = 16, p = 4) o Necht n a p jsou mocniny dvojky (r? a p jsou soudělné) • Mapování (/ mod p) o Každá jednotka nejprve sečte data lokálně v čase 0(r?/p) • Problém redukován na sčítání p čísel na p procesorech • Celkový Tp je 0(r?/p + log p) • Cena C = 0(r? + plogp), • Cenově optimální, pokud n > p log p (cena C = 0(r?)) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 20/35 Škálovatelnost paralelních programů IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 21/35 Škálovatelnost paralelních programů Fakta 9 Programy jsou testovány na malých vstupních datech na systémech s malým počtem procesních jednotek. • Použití deškálovaní zkresluje měření výkonu aplikace. • Algoritmus, který vykazuje nejlepší výkon na testovaných datech, se může ukázat být tím nejhorším algoritmem, při použití na skutečných datech. Odhad výkonu aplikace nad reálnými vstupními daty a větším počtu procesních jednotek je komplikovaný. Škálovatelnost 9 Zachování výkonu a efektivity při zvyšování počtu procesních jednotek a zvětšování objemu vstupních dat. Závěr • Je třeba uvážit analytické techniky pro vyhodnocování výkonu a škálová ní. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 22/35 Charakteristiky škálovánŕ- Efektivita Efektivita paralelních programů: E = S = T s = 1 P pTP 1 + Ij Celková režie (To) 9 Přítomnost sekvenční části kóduje nevyhnutelná. Pro její vykonání je třeba čas ŕser/a/. Po tuto dobu jsou ostatní procesní jednotky nevyužité. • T0 > (p - l)tseriai 9 Tq roste minimálně lineárně vzhledem k p, často však i asymptoticky více. Úloha konstantní velikosti (7~s fixní) • Se zvyšujícím se p, efektivita nevyhnutelně klesá. 9 Nevyhnutelný úděl všech paralelních programů. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 23/35 Charakteristiky škálovánŕ- Příklad Problém • U kol: Sečíst n čísel s využitím p procesních jednotek, o Uvažme cenově optimální verzi algoritmu. • Tp = (± + logp). • Lokální operace a komunikace stojí 2 jednotky času. Charakteristiky řešení • TP = %+2logp o c —_a_ • 3 - £+2/ogp • E = n IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 24/35 Při zachování T$ o Rostoucí počet procesních jednotek snižuje efektivitu. Při zachování počtu procesních jednotek • Rostoucí 7~s (velikost vstupních dat) má tendenci zvyšovat efektivitu. Škálovatelné systémy • Efektivitu lze zachovat při souběžném zvyšování 7~s a p. • Zajímáme se o poměr, ve kterém se Í5 a p musí zvyšovat, aby se zachovala efektivita. • Lim menši pomer IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 25/35 Izoefektivita jako metrika škálování Vztahy • T p • S = • E = = Ts+T0(W,p) p Is. — pTs TP S _ P W - velikost vstupních dat Ts+T0(W,p) TS TS+T0(W,P) - 1+T0(W,P)/TS Konstantní efektivita • Efektivita je konstantní, pouze pokud To{W,p)/7~s je konstantní. • Úpravou vztahu pro efektivitu: T s — jz^To{W, p). 9 Při zachování míry efektivity lze E/(l — E) označit jako konstantu K. Funkce izoefektivity (stejné efektivity) Ts = KT0(W,p) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 26/35 Izoefektivita jako metrika škálování Funkce izoefektivity Ts = KT0(W,p) Pozorování 9 Při konstantní efektivitě, lze 7~s vyjádřit jako funkci p 9 Vyjadřuje vztah, jak se musí zvýšit T§ při zvýšení p • Nižší funkce říká, že systém je snáze škálovatelný • Isoefektivitu nelze měřit u systémů, které neškálují IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 27/35 Izoefektivita jako metrika škálování- příklad Příklad • Součet n čísel na p procesorech • E = l+(2plogp)/n l+T0(W,p)/Ts • T0 = 2p log p • Funkce izoefektivity: T$ = K2p log p • Funkce izoefektivity: 0(p log p) • Při zvýšení procesních jednotek z p na p' se pro zachování efektivity musí zvětšit velikost problému o faktor (p' log p')/(plog p). IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 28/35 Cenová optimalita a izoefektivita Optimálni cena • Pro cenově optimální systémy požadujeme pTp — 0(7"s). • Po dosazení ze základních izo vztahů dostáváme: TS + T0(W, p) = G{TS) Cenová optimalita může být zachována pouze pokud: • režie je nejvýše lineární vůči složitosti sekvenčního algoritmu, tj. funkce T0{W,p) G 0{TS) o složitost sekvenčního algoritmu je minimálně tak velká jako režie, tj. funkce 7~s G Q(Tq( W, p)) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 29/35 Spodní odhad na izoefektivitu Izoefektivita • Čím nižší/menší funkce, tím lepší škálovatelnost. • Snaha o minimálni hodnotu izofunkce. Sublineární izoefektivita 9 Pro problém tvořený N jednotkami práce je optimálni cena dosažitelná pouze pro maximálně N procesních jednotek. o Přidáváním dalších jednotek vyústí v idling některých jednotek a snižování efektivity. • Aby se efektivita nesnižovala musí množství práce růst minimálně lineárně vzhledem k p. Funkce izoefektivity nemůže být sublineární. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 30/35 Minimální doba výpočtu Otázka • Jaká je minimální možná doba výpočtu (Tpm) při dostupnosti dostatečného počtu procesních jednotek? Pozorování mm • Při rostoucím p se Tp asymptoticky blíží k T p • Po dosažení Tpm se Tp zvětšuje spolu s p. Jak zjistit 7™"? 9 Necht po je kořenem diferenciální rovnice • Dosazení po do vztahu pro Tp dává hodnotu Tp mm ap+2logP, dTP Příklad - součet n čísel p procesními jednotkami • T p • Po = dp n 2 Tpm = 2logn = Q(logn) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 31/35 Asymptotická analýza paralelních programů Algoritmus AI A2 A3 A4 P n2 log n n \/ň TP 1 n y/ň y/ňlog n S n log n log n y/ňlog n y/ň E log n n 1 log n 1 pTP n2 n log n „1.5 n log n Otázky • Jaký algoritmus je nejlepší? • Použily jsme vhodné odhady složitosti? • Je dostupná odpovídající paralelní architektura? IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 32/35 Závě Návrh paralelních algoritmů ač složitostně neoptimálních je nedílnou a důležitou částí práce programátora paralelních aplikací. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 33/35 Shrnutí IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 34/35 Co jsme se v kurzu dozvěděli Paralelní HW platformy 9 Principy fungování HW systémů se sdílenou pamětí. • Komunikace v systémech s distribuovanou pamětí. Nástroje paralelního programování • Standardy a knihovny pro implementaci paralelních aplikací. POSIX Threads, OpenMP, MPI (OpenMPI) • Principy fungování těchto knihoven Lock-Free datové struktury, Kolektivní komunikace Algoritmizace o Principy návrhu paralelních algoritmů. • Analytické posuzování paralelních řešení. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 35/35