IB109 Návrh a implementace paralelních systémů Organizace kurzu a úvod Jiří Barnat Sekce Organizace kurzu IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 2/32 Organizace kurzu Místo a čas Středa 16:00-17:40, A217 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 Požadavky na úspěšné ukončení předmětu Z,K: bodové hodnocení testu nad 50% ZK: bodové hodnocení testu nad 60%(E), 67%(D), 75%(C), 82%(B), 90%(A) IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 3/32 Cíl kurzu IB109 Cílem předmětu je seznámit studenty s Problematikou programování paralelních aplikací. Programátorskými prostředky pro vývoj paralelních aplikací. Možnostmi studia tématu na FI. Úspěšný absolvent kurzu Umí identifikovat paralelně proveditelné úlohy. 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. Má představu o tom, co se děje v zákulisí použitých knihoven pro podporu programování paralelních aplikací. Umí tyto knihovny správně použít. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 4/32 Organizace kurzu Osnova: 1 21/02 — Úvod, organizace kurzu, motivace 2 28/02 — Práce s daty ve sdílené paměti 3 07/03 — Zrušeno 4 14/03 — POSIX Threads 1 5 21/03 — POSIX Threads 2 6 28/03 — Lock-Free programování 7 04/04 — OpenMP, TBB, C++11 8 11/04 — Principy návrhu paralelních algoritmů 9 18/04 — Zrušeno 10 25/04 — Předávání zpráv v distribuované paměti, MPI 11 02/05 — Kolektivní komunikace 12 09/05 — Složitostní analýza paralelních programů 13 16/05 — Zkouška – 1. termín IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 5/32 Předpoklady a kontext na FI IB109 Úvodní kurz určený pro bakalářské studium. Povinný v rámci oboru Paralelní a distribuované systémy Předpoklady 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/32 Kontext v rámci FI 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 technologíí CUDA. PA150 – Principy operačních systémů Vlákna, procesy, monitory, semafory, synchronizace. Hierarchie pamětí. IA039 – Architektura superpočítačů a intenzivní výpočty Procesory. Paralelní počítače. Překladače. MPI. PVM a koordinační jazyky. Profilování a měření výkonu. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 7/32 Kontext v rámci FI – pokr. IV100 – Paralelní a distribuované výpočty 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í nejkratší 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/IA169 – Úvod do validace a verifikace Model checking, verifikace paralelních programů. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 8/32 Kontext v rámci FI Laboratoře na FI SITOLA PARADISE SYBILA Projekty 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/32 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/32 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 Multithreded, Parallel, and Distributed Programming) http://renoir.csc.ncsu.edu/CSC495A http://www.hlrs.de/organization/par/par_prog_ws Parallel Programing Workshop (MPI, OpenMP) Domovské stránky projektů MPI, TBB, OpenMP, . . . Online tutoriály . . . IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 11/32 Sekce Motivace IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 12/32 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 Napříč všemi úrovněmi, od implementace registru až po koexistenci rozsáhlých výpočetně distribuovaných aplikací. Chtěný pro zvýšení výkonu. Nutný kvůli prostorové distribuci. Vykoupený složitostí návrhu a pořizovací cenou. Souběžnost v Computer Science Specifikace, implementace a analýza paralelních a distribuovaných systémů. Inherentně sekvenční algoritmy, složitostní třída NC. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 13/32 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í úlohy (velký objem výpočtů, nepřijatelná latence). Bezpečnost 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/32 Výpočetních platformy – abstraktně Abstraktní model výpočetního systému Procesor - Datová cesta - Datové úložiště Všechny části systému mohou být úzkým místem vůči výkonnosti aplikace jako celku. 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/32 Procesory Procesory 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/32 Moore’s Law IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 17/32 Trend ve vývoji procesorů Pozorování Výrobcům procesorů se nedaří zvyšovat výkon jednoho jádra. 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. Čá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 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/32 Datové cesty Role paralelismu v komunikaci 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ě Šiřka 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/32 Paměť Fakta 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ěť Cache I/O zařízení Magnetické/optické mechaniky IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 20/32 Cache Cache paměť obecně: Kopie části dat v rychleji dostupném místě. 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 I/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/32 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). Větší režie na udržení konzistence. Příklady Disková pole Peer-to-Peer sítě NUMA architektury Více procesorové počítače s více paměťovými moduly uspořádanými tak, že přístup jednoho procesoru do různých paměťových modulů je různě rychlý. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 22/32 Sekce Paralelní výpočty IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 23/32 Paralelismus z pohledu OS Multitasking na jednom výpočetním jádru Aplikace se v běhu na CPU jádru střídají. Na jednom CPU zdánlivě "běží"více aplikací. Jednotka plánování OS je proces. Multitasking na více výpočetních jádrech Různé aplikace přiřazeny na různá výpočetní jádra. Jinak standardní multitasking na každém jednom jádře. Jednotka plánování OS je proces. Multitasking a multithreading Každá aplikace může mít více výpočetních vláken. Vlákna se v běhu na jednom CPU jádru střídají. Vlákna jedné aplikace mohou běžet na různých jádrech. Jednotka plánování OS je vlákno. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 24/32 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 Nezávislý souběh dvou a více SISD, SIMD přístupů. 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. 25/32 Distribuovaný systém Distribuovaný/paralelní systém Specifikován po částech (procesy). 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. 26/32 Příklad distribuovaného systému IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 27/32 Vybrané problémy distribuovaných systémů Jevy Nekonzistentní vize konzistentního světa. Vzájemná interference Rizika Race-condition, nedeterministické chování. Uváznutí (Deadlock, Livelock) Stárnutí, hladovění (Starving) Přetečení buferů, problém producent-konzument. Zbytečná ztráta výkonu (aktivní čekání). IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 28/32 Vývoj paralelních systémů je náročnější Důvody: Nutnost specifikace souběžných úkolů. Nutnost specifikace koordinace úkolů. Paralelní algoritmy. Nedostačující vývojová prostředí. 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í. 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. 29/32 Vývoj paralelních systémů je náročnější Důvody: Nutnost specifikace souběžných úkolů. Nutnost specifikace koordinace úkolů. Paralelní algoritmy. Nedostačující vývojová prostředí. 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í. 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. 29/32 Sekce HPC IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 30/32 HPC HPC (High Performance Computing) Oblast Computer Science Výpočty na vysoce paralelních platformách Nejvýkonější počítač světa [Jaro 2018] National Supercomputing Center in Wuxi TFLOPS: 93 014 Nejvýkonější počítač světa [Jaro 2010] Roadrunner TFLOPS: 1 105 Více viz www.top500.org. IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 31/32 Nejvýkonnější počítače IB109 Návrh a implementace paralelních systémů: Organizace kurzu a úvod str. 32/32 IB109 Návrh a implementace paralelních systémů Programování v prostředí 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 Kombinace Rizika paralelních výpočtů na soudobých procesorech 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. 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 Víc jader emituje větší zbytkové teplo. Takt jednoho jádra bývá nižší. 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. 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 Existují v kontextu jednoho procesu. V rámci rodičovského procesu sdílí výpočetní prostředky. Komunikace probíhá přes sdílené datové struktury. Účelem interakce je spíše 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 data = 1; p -> data = 2; cout «(p->data)«endl; 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/34 Atomicita operací Pozorování Jednoduchý příkaz ve vyšším programovacím jazyce neodpovídá nutně jedné instrukci procesoru. 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/34 Atomicita operací Příklad 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; P0 { P1 { a = a + 10; a = a + 20; } } Demonstrujte proložení instrukcí, které vyústí v jinou hodnotu, než 30. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 6/34 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; P0 { P1 { usleep 200; a = 1; a = 0; usleep 200; } } 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/34 Uváznutí 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 P0 { P1 { 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/34 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; P0 { P1 { while (true) {; while (a == 0) { }; a++; a–; ...; }... } } Vlákno P1 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/34 Thread-safe a re-entrantní procedury Thread-safe procedura 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/34 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 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/34 Thread-safe a re-entrantní procedury Nebezpečné akce vzhledem k paralelnímu zpracování Nekontrolovaný přístup ke globálním proměnným a haldě. Uchovávání stavu procedury do globálních proměnných. Alokace, dealokace zdrojů globálního rozsahu (soubory, . . . ). Nepřímý přístup k datům skrze odkazy nebo ukazatele. 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 thread-safe. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 12/34 Procedura, která není thread-safe *myStructure p; *myStructure function() { p=new myStructure; return p; } P0 { P1 { *myStructure x; *myStructure x; x=function(); x=function(); } } IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 13/34 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“. Veškeré modifikace a neatomická čtení globálních proměnných musí být serializovány. Kritická sekce Část kódu, jehož provedení je neproložitelné instrukcemi jiného vlákna. Realizace kritické sekce musí být odolná vůči plánování. Zamykání Vlákno vstupující do volné kritické sekce, svým vstupem znemožní přístup ostatním vláknům (sekci tzv. zamkne). Ostatní vlákna čekají před vstupem do kritické sekce. Při odchodu z kritické sekce, je zámek uvolněn, získá ho náhodně jedno z čekajících vláken. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 14/34 Zamykání a související pojmy Jednoduché řešení zámku Sdílená atomicky přistupovaná bitová proměnná, jejíž hodnota indikuje přítomnost procesu/vlákna v přidružené kritické sekci. Manipulována při vstupu a výstupu z/do kritické sekce. Vyžaduje podporu HW pro atomickou manipulaci. Aktivní čekání – spinlock Dokud neuspěje, vlákno opakovaně zkouší vstoupit do kritické sekce (tj. po tuto dobu neustále provádí tentýž kód). 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. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 15/34 Rizika zamykání Rizika Uváznutí, stárnutí, snížení výkonnosti. Přístup ke sdíleným globálním proměnným Manipulace se zámkem 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, z principu nelze odstranit. Petersonův algoritmus (spinlock, user-space) Spravedlivý algoritmus pro řízení vzájemného vyloučení. Nezpůsobuje stárnutí ani uváznutí. Vyžaduje atomické zápisy do proměnných. Citlivý na provádění instrukcí mimo pořadí. IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 16/34 Sekce POSIX Thread API IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 17/34 Historie a POSIX standard Historie SMP systémy Vlákna implementována jednotlivými výrobci HW IEEE POSIX 1003.1c standard IEEE POSIX 1003.1c Programátorský model semaforů a provádění operací v kritické sekci 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/34 Základní dělení funkcionality Správa vláken Vytváření, oddělování a spojování vláken Funkce na nastavení a zjištění stavu vlákna Vzájemná vyloučení (mutexes) Vytváření, ničení, zamykání a odemykání mutexů Funkce na nastavení a zjištění atributů spojených s mutexy Podmínkové/podmíněné proměnné (conditional variable) Slouží pro komunikaci/synchronizaci vláken Funkce na vytváření, ničení, “čekání na” a “signalizování při” specifické hodnotě podmínkové proměnné Funkce na nastavení a 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/34 POSIX standard Přes 60 API funkcí #include Překlad s volbou -pthread Mnemotechnické předpony funkcí pthread_, pthread_attr_ pthread_mutex_, pthread_mutexattr_ pthread_cond_, pthread_condattr_ pthread_key_ Pracuje se skrytými objekty (Opaque objects) Objekty v paměti, o jejichž podobě programátor nic neví. 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/34 Atributy objektů Idea 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 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í str. 21/34 Správa vláken Vytváření vlákna Každý program má jedno hlavní vlákno Další vlákna musí být explicitně vytvořena programem Každé vlákno (i vytvořené) může dále vytvářet další vlákna Vlákno vytvářeno funkcí pthread_create 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 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/34 Správa vláken int pthread_create ( pthread_t *thread_handle, const pthread_attr_t *attribute, void * (*thread_function)(void *), void *arg); thread_handle odkaz na vytvořené vlákno attribute odkaz na atributy vytvořeného vlákna (NULL pro přednastavené nastavení atributů) thread_function ukazatel na funkci nového vlákna arg ukazatel na parametry funkce thread_function 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/34 Správa vláken Ukončení vlákna nastává Voláním funkce pthread_exit Pokud skončí hlavní funkce rodičovského vlákna jinak než voláním pthread_exit Je-li zrušeno jiným vláknem pomocí pthread_cancel Rodičovský proces je ukončen (násilně nebo voláním exit) void pthread_exit (void *value) Ukončuje běh vlákna 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/34 Správa vláken – příklad 1 #include 2 #include 3 #define NUM_THREADS 5 4 5 void *PrintHello(void *threadid) 6 { printf("%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,&mutex); ... 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. 9/44 Sekce Další funkce v POSIX Threads IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 10/44 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. Případné použití globálních proměnných musí být bezstavové a prováděno v kritické sekci. 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. 11/44 Implementace TSD Standardní řešení Pole indexované jednoznačným identifikátorem vlákna. Vlákna musí mít rozumně velké identifikátory. 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. 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. 12/44 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. 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. 13/44 POSIX Klíče – použití Zničení klíče a asociovaných ukazatelů int pthread_key_delete (ptrhead_key_t key) Nevolá žádné destructor funkce. Programátor je zodpovědný za dealokaci objektů před zničením klíče. Funkce na získání a nastavení hodnoty asociovaného ukazatele void * pthread_getspecific (ptrhead_key_t key) int pthread_setspecific ( ptrhead_key_t key, const void *value) IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 14/44 Různé ptrhead_t pthread_self () Vrací unikátní systémový identifikátor vlákna int pthread_equal (pthread_t thread1, pthread_t thread2) Vrací nenula při identitě vláken thread1 a thread2 pthread_once_t once_control = PTHREAD_ONCE_INIT; int pthread_once(pthread_once_t *once_control, void (*init_routine)(void)); 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. 15/44 Další funkce v POSIX Threads Plánování (scheduling) vláken Není definováno, většinou je výchozí politika dostačující. POSIX Threads poskytují funkce na definici vlastní politiky a priorit vláken. 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ů. Read-Write zámky. IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 16/44 Sekce Typické konstrukce IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 17/44 Č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. 18/44 Čtenáři a písaři – Řešení Řešení s použitím POSIX Threads Čtení a modifikace dat bude probíhat v kritické sekci. Přístup do kritické sekce bude řízen pomocí funkcí pthread_*. 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. 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. 19/44 Čtenáři a písaři – Implementace Jednoduché řešení Použít jeden pthread_mutex_t pro kritickou sekci. Vylučuje souběžný přístup vláken-čtenářů. Lepší řešení Implementujeme nový typ zámku – rwlock_t Funkce pracující s novým zámkem rwlock_rlock(rwlock_t *l) – vstup vlákna-čtenáře rwlock_wlock(rwlock_t *l) – vstup vlákna-písaře rwlock_unlock(rwlock_t *l) – opuštění libovolným vláknem Funkce rwlock implementovány s využitím podmínkových proměnných z POSIX Thread API. IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 20/44 Čtenáři a písaři – Implementace KS KS KS KS unlock unlock unlock unlock rlock wlock wlock wlock wlock sleep sleeprlock rlock sleep unlock rlock KS IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 21/44 Č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 *l) { 11 l->readers = l->writer = l->pending_writers = 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. 22/44 Čtenáři a písaři – Implementace 16 17 void rwlock_rlock (rwlock_t *l) { 18 pthread_mutex_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 pthread_mutex_unlock(&(l->lock)); 24 } 25 IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 23/44 Čtenáři a písaři – Implementace 26 27 void rwlock_wlock (rwlock_t *l) { 28 pthread_mutex_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 pthread_mutex_unlock(&(l->lock)); 36 } 37 IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 24/44 Čtenáři a písaři – Implementace 38 39 void rwlock_unlock (rwlock_t *l) { 40 pthread_mutex_lock(&(l->lock)); 41 if (l->writer>0) 42 l->writer=0; 43 else if (l->readers>0) 44 l->readers–; 45 pthread_mutex_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. 25/44 Čtenáři a písaři – Příklady použití Počítání minima 2122 ... 2123 rwlock_rlock(&rw_lock); 2124 if (my_min < global_min) { 2125 rwlock_unlock(&rw_lock); 2126 rwlock_wlock(&rw_lock); 2127 if (my_min < global_min) { 2128 global_min = my_min; 2129 } 2130 } 2131 rwlock_unlock(&rw_lock); 2132 ... Hašovací tabulky . . . IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 26/44 Bariéry Specifikace problému Synchronizační primitivum 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. 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. 27/44 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. 28/44 Bariéry – Implementace 12 void barrier (barrier_t *b, int nr_threads) { 13 pthread_mutex_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. 29/44 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 Dolní odhad na dobu běhu bariéry je tedy O(n), kde n je počet vláken participujících na bariéře Možné řešení Implementace bariéry metodou binárního půlení Teoretický dolní odhad na bariéru je O(n/p + log p), kde p je počet procesorů Cvičení 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. 30/44 Chyby, krom nezamykaného přístupu ke globální proměnné Typické chyby – situace 1 Vlákno V1 vytváří vlákno V2 V2 požaduje data od V1 V1 plní data až po vytvoření V2 V2 použije neinicializovaná data Typické chyby – situace 2 Vlákno V1 vytváří vlákno V2 V1 předá V2 pointer na lokální data V1 V2 přistupuje k datům asynchronně V2 použije data, která už neexistují (V1 skončilo) Typické chyby – situace 3 V1 má vyšší prioritu než V2, čtou stejná data Není garantováno, že V1 přistupuje k datům před V2 Pokud V2 má destruktivní čtení, V1 použije neplatné data IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 31/44 Ladění programů s POSIX vlákny Valgrind 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. 32/44 Rozšíření POSIX Threads – nepovinná dle standardu Barriéry pthread_barrier_t pthread_barrierattr_t _init(...), _destroy(...), _wait(...) Read-Write zámky pthread_rwlock_t 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. 33/44 Sekce Další způsoby synchronizace IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 34/44 Synchronizace procesů Problém – jak synchronizovat procesy Mutexy z POSIX Threads dle standardu slouží pouze pro synchronizaci vláken v rámci procesu. 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. POSIX semafory (v rámci procesu) 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. 35/44 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 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. 36/44 Monitory Monitor Synchronizační primitivum 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 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. 37/44 Sekce Vlákna v MS Windows IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 38/44 Vlákna v MS Windows Vyšší programovací jazyk C++11 JAVA ... POSIX Thread pro Windows Existuje knihovna poskytující POSIX Thread interface. Nativní rozhraní MS Windows 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. 39/44 Windows vs. POSIX Threads – Funkce Windows POSIX Threads Pouze jeden typ Každý objekt má svůj vlastní typ HANDLE (např. pthread_t, pthread_mutex_t,...) Jedna funkce pro jednu činnost. Různé funkce pro manipulaci (např. WaitForSingleObject) s různými objekty a jejich atributy. Typově jednodušší rozhraní Typová kontrola parametrů (bez typové kontroly), čitelnost funkcí, lepší čitelnost kódu. závislá na jménech proměnných. IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 40/44 Win32 vs. POSIX Threads – Synchronizace Windows 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. 41/44 Win32 vs. POSIX Threads – Základní mapování Windows POSIX Threads CreateThread pthread_create pthread_attr_* ThreadExit pthread_exit WaitForSingleObject pthread_join pthread_attr_setdetachstate pthread_detach SetPriorityClass SetThreadClass Pouze nepřímo mapovatelné. setpriority sched_setscheduler sched_setparam pthread_setschedparam ... IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 42/44 Win32 vs. Linux/UNIX – Mapování synchronizace Windows Linux threads Linux processes Mutex PThread Mutex System V semafor Kritická sekce PThread Mutex — Semafor PThread podm. proměnné System V semafor POSIX semafor Událost PThread podm. proměnné System V semafor POSIX semafor IB109 Návrh a implementace paralelních systémů: POSIX Threads – pokračování, Win32 Threads str. 43/44 Win32 vs. UNIX – Pozorování Pozice vláken ve MS Windows Silnější postavení než vlákna v Linuxu. Synchronizační prostředky fungují i mezi procesy. Vlákna ve vlákně (Processes-Threads-Fibers) User-mode scheduling (UMS) – kooperativní plánování. Výhody jednoho typu Jednou funkcí lze čekat na nekonkrétní vlákno. 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. 44/44 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. 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 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á konstrukce/instrukce Minimální prodlevy související s přístupem k datům Neexistuje uváznutí, je garantována živost Algoritmicky obtížnější uvažování 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 Pojmy 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 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 Článek: Wait-Free Synchronization (1991) Ukázal, že konstrukce jako test-and-set swap fetch-and-add 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é vhodné jsou (např. CAS). Dijkstrova cena za distribuované počítání (2003) http://www.podc.org/dijkstra/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 false; } 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. O ú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 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. False – 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 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. Vlákno A nepozná, že se hodnota objektu měnila. 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. 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. 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 InterlockedCompareExchange(...) 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 :%%ecx,(%%edx)": "=a"(cmpValue) : "d"(&v), "a"(cmpValue), "c"(exValue)); return cmpValue; } GCC – zabudované funkce 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 Sekce WRRM Mapa – Příklad IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 11/42 WRRM Mapa Write Rarely Read Many Mapa Zprostředkovává překlad jedné entity na jinou. (Klíč→Hodnota). 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í 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í Probíhá zcela bez zamykání. Operace zápisu 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 Obecné použití schématu CAS na WRRMMap by vyžadovalo atomickou změnu relativně rozsáhlé oblasti paměti. 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. Vlákno B udělá kopii mapy, vloží nový klíč a dokončí operaci. Vlákno A vloží nový klíč. 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 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. 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á. 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* template class WRRMMap { typedef std::pair*,unsigned> Data; Data* pData_; . . . } 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 *pOld->first. 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í 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 WRRMMap { 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 Umíme atomicky realizovat počítání odkazů, je tedy navrhované řešení korektní? Problém Zvýšení a snížení čítače 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áž. Procedura Update bude provádět změny struktury jen tehdy, 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 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 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. Volání procedur Update je málo – nevadí. Update Není wait-free, interferuje s procedurou Lookup. Volání procedur Lookup je mnoho – problém. Čeho jsme dosáhli 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 Sekce Hazardní ukazatele aneb tak trochu “Lock-Free Garbage Collector” IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 27/42 Hazardní ukazatele Motivace Dealokace datových struktur v kontextu lock-free programování je obtížná. Ukazatel na datový objekt nerozliší, zda je možné, objekt uvolnit z paměti, či nikoliv. Čítače použití ukazatelů nejsou dobré řešení. Princip řešení pomocí hazardních ukazatelů Vlákna vystavují ostatním vláknům seznam ukazatelů, které momentálně používají – tzv. hazardní ukazatele. 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 Procedura update vytvoří kopii mapy, modifikuje ji, nahradí touto kopií aktuální mapu a starou mapu dealokuje. Dealokace staré mapy může interferovat s probíhající procedurou Lookup jiného vlákna. Řešení WRRM Mapa udržuje seznam ukazatelů, které jsou momentálně používány nějakým vláknem v proceduře Lookup. Lookup – vkládá a odebírá ukazatel do seznamu. 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 Záznam seznamu obsahuje ukazatel a příznak validity: int active_ void* pHazard_ Metoda Acquire() Vytvoří nebo znovu použije neplatný objekt seznamu a vrátí volajícímu ukazatel na tento objekt. 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 listLen_; 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->pNext_) { // Try to reuse if (p->active_ or !CAS(&p->active_,0,1)) continue; return p; } int oldLen; // Increment the length do { oldLen = listLen_; } while (!CAS(&listLen_,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í. 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 Scan(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; // delete it if (&*i != &rlist.back()) //and dequeue it *i = rlist.back(); // replace it with the last one rlist.pop_back(); // dequeue the last one } else { ++i; } } }; 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 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. 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 Sekce 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. 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 LL/SC Load-Link/Store-Conditional Dvojice instrukcí, která dohromady realizuje CAS. LL načte hodnotu a SC ji přepíše, pokud nebyla modifikována. Za modifikaci se považuje i přepsání na tutéž hodnotu. 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. Obtížné ladění. IB109 Návrh a implementace paralelních systémů: Implementace Lock-Free datových struktur str. 42/42 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 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 Paralelní konstrukce na úrovni programovacího jazyka Prostředek vhodný pro aplikační programátory 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 Sekce 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, ne jak se to má udělat. Náznak deklarativního přístupu v imperativním programování. Realizace Programátor informuje překladač o zamýšlené paralelizaci uvedením značek ve zdrojovém kódu a označením bloků. 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í 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í Strukturovaný blok, tj. {...}, následující za touto direktivou se provede paralelně. 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 false direktiva parallel se ignoruje a následující blok je proveden pouze v jedné kopii. Stupeň paralelismu Počet vláken. 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: private (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 private s tím, že všechny kopie proměnných jsou inicializované hodnotou originální kopie. Klauzule: shared (seznam proměnných) 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]) shared: všechny proměnné jsou sdílené, pokud není uvedeno jinak. none: vynucuje explicitní uvedení každé proměnné v klauzuli private 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) Při ukončení paralelního bloku jsou vyjmenované privátní proměnné zkombinovaný pomocí uvedeného operátoru. 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ě). Možný zkrácený zápis: #pragma omp parallel for Klauzule: private, firstprivate, reduction Stejné jako pro direktivu parallel. Klauzule: lastprivate 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 for 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]) 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 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 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 for – Plánování iterací guided Bloky iterací mají velikost proporcionální k počtu nezpracovaných iterací poděleným počtem vláken. 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ě. Možný zkrácený zápis #pragma omp parallel sections Umožňuje definovat různý kód pro různá vlákna. Klauzule: private, firstprivate, 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 5 { 6 #pragma omp section 7 { 8 printf("Thread A."); 9 } 10 #pragma omp section 11 { 12 printf("Thread B."); 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, FALSE). Typické použití: vnořené for-cykly 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 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. Musí být voláno všemi vlákny v odpovídajícím bloku direktivy parallel. Poznámka ke kódování 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. 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, firstprivate Klauzule: nowait Pokud není uvedena, tak na konci strukturního bloku označeného direktivou single je provedena bariéra. Direktiva master 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 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. #pragma omp critical [(name)] Direktiva atomic Nahrazuje kritickou sekci nad jednoduchými modifikacemi (updaty) proměnných v paměti. Atomicita se aplikuje na jeden 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) 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í Perzistentní privátní proměnné (přetrvají zánik vlákna). Při znovuvytvoření vlákna, se proměnné znovupoužijí. #pragma omp threadprivate (seznam) Omezení Nesmí se použít dynamické plánování vláken. Počet vláken v paralelních blocích musí být shodný. Direktiva copyin Jako threadprivate, ale s inicializací. Viz private versus firstprivate. 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 () 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 – Kontrola vytváření vláken void omp_set_dynamic (int dynamic_threads) int omp_get_dynamic() 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() Nastavuje a vrací, zda je povolen vnořený paralelismus. 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 FALSE specifikuje, že vnořené paralelní konstrukce budou serializovány. OMP_SCHEDULE Udává defaultní nastavení mapování iterací cyklu na vlákna. 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 Sekce 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). V C++ jsou obecnou konstrukcí šablony (templates). Queue Queue& range ) const { for( int i=range.begin(); i!=range.end(); ++i ) output[i] = (input[i-1]+input[i]+input[i+1])*(1/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í Koncept dělení Instance některých tříd je nutné za běhu (rekurzivně) dělit. 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 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í: blocked_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: blocked_range blocked_range template class blocked_range; Reprezentuje nadále dělitelný otevřený interval [i,j). Požadavky na třídu Value specializující blocked_range Kopírovací konstruktor Value::Value (const Value&) Destruktor Value::˜Value () Operátor porovnání bool Value::operator<(const Value& i, const Value& j) Počet objektů v daném rozsahu (operátor −) size_t Value::operator-(const Value& i, const Value& j) k-tý následný objekt po i (operátor +) Value Value::operator+(const Value& i) IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 35/54 TBB: blocked_range Použití blocked_range Nejdůležitější metodou je konstruktor. Konstruktor specifikuje interval rozsahu a velikost největšího dále nedělitelného sub-intervalu: blocked_range(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 TBB: parallel_for parallel_for template void parallel_for( const Range& range, const Body& body); Požadavky na třídu realizující tělo cyklu Kopírovací konstruktor Body::Body (const Body&) Destruktor Body::˜Body () Aplikátor těla cyklu na daný rozsah – operátor () void Body::operator()(Range& range) const IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 37/54 TBB: parallel_reduce parallel_reduce template void parallel_reduce( const Range& range, const Body& body); Požadavky na třídu realizující tělo redukce Dělicí konstruktor Body::Body (const Body&, split) Destruktor Body::˜Body () Funkce realizující redukci nad daným rozsahem – operátor () void Body::operator()(Range& range) Funkce realizující redukci hodnot z různých rozsahů void Body::join(Body& 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 Paralelní konstrukce mají třetí volitelný parametr, který specifikuje strategii dělení rozsahu. parallel_for 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 concurrent_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 se je používat. concurrent_vector 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. 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_hash_map template class concurrent_hash_map; Mapa, ve které je možné paralelně hledat, mazat a vkládat. Požadavky na třídu HashCompare Kopírovací konstruktor HashCompare::HashCompare (const HashCompare&) Destruktor HashCompare::˜HashCompare () Test na ekvivalenci objektů bool HashCompare::equal(const Key& i, const Key& j)const Výpočet hodnoty hešovací 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 Přístup k párům Klíč-Hodnota je skrze přistupovací třídy. accessor – pro přístup v režimu read/write 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.release(); 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_hash_map bool find(const_accessor& result, const Key& key) const bool find(accessor& result, const Key& key) bool insert(const_accessor& result, const Key& key) bool erase(const Key& key) Další způsoby použití Iterátory pro procházení mapy. 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 Sekce C++11 IB109 Návrh a implementace paralelních systémů: Pokročilá rozhraní pro implementaci paralelních aplikací str. 44/54 C++11 a vláknování Pozorování 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.unlock(); } int main() { int a = 42; std::thread t1(func, std::ref(a)); std::thread t2(func, std::ref(a)); t1.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 Zamykání v C++11 Potencionální riziko uváznutí Jazyk s plnou podporou mechanismu výjimek. 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 RAII a OOP. Zamčení mutexu realizováno vytvořením lokální instance vhodné předdefinované zamykací třídy. 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 RAII zamykání v C++11 Třída lock_guard Obalení standardního zámku v RAII 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 Obecnější předatelné RAII 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 Vlákna. Mutexy a RAII zámky. Podmínkové proměnné. 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.codeproject.com/Articles/598695/Cplusplus-threads-locks-and-condition-variables http://stackoverflow.com/questions/6319146/ c11-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 Thread 2 x = 17; cout « y « " "; y = 37; cout « x « endl; Nemá definované chování. Správně atomicky atomic x, y; Thread 1 Thread 2 x.store(17); cout « y.load() « " "; y.store(37); cout « x.load() « 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; 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čování 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 Sekce 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 IB109 Návrh a implementace paralelních systémů Principy návrhu paralelních algoritmů Jiří Barnat Více-práce programátora paralelních aplikací Identifikovat souběžně proveditelné činnosti a jejich závislosti. Mapovat souběžně proveditelné části práce do procesů. Zajistit distribuci vstupních, vnitřních a výstupních dat. Spravovat souběžný přístup k datům a sdíleným prostředkům. 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 Sekce Základy návrhu paralelních algoritmů 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 ? Dekompozice Aplikace ImplementaceProcesy Problém Úlohy Mapování Vlákna 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. Některé podúlohy mohou být prováděny paralelně. (Pod)úlohy Jednotky výpočtu získané dekompozicí. 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 (n × n) vektorem B C[i] = n j=1 A[i, j].B[j] IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 5/39 Závislosti úloh Graf závislostí 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 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čily svůj výpočet (topologické uspořádání). Příklady závislostí 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 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 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. 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 Sekce Techniky dekompozice IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 10/39 Techniky dekompozice Dekompozice Fundamentální technika v návrhu paralelních algoritmů. Obecné dekompozice Rekurzivní 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 Problém se dekomponuje na podúlohy tak, aby jednotlivé úlohy mohly být dekomponovány stejným způsobem jako rodičovská úloha. 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á. Hledání minima v lineárním poli. 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). Úlohy se provádí souběžně nad jednotlivými částmi dat. Datová dekompozice podle místa Vstupní data Výstupní data Vnitřní data 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 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é. 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 Provádí se zbytečná práce. Nemusí být ve výsledku rychlější jak serializovaná verze. 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 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 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 O(n/p + log(p)). Vstupní pole se datově dekomponuje na p stejných částí. Najdou se minima v jednotlivých částech v čase O(n/p). Výsledky z jednotlivých třídění se zkombinují v čase O(log(p)). Teoreticky lze při dostatečném počtu procesorů nalézt minimum v čase O(log(n)). 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 Sekce Techniky mapování a vyrovnávání zátěže IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 17/39 Mapování úloh na vlákna/procesy. Mapování Přiřazování úloh jednotlivým vláknům/procesům. 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í Redukovat režii spouštění, ukončování a 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í mapování 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. Uniformní vs. neuniformní. 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é Statické: Probíhají v předdefinovaném časovém intervalu, mezi předem známou množinou úloh. 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. 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 Dělení dle grafu závislostí úloh Hierarchické dělení IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 21/39 Mapování 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 × B = C Dělení matice C na 1- a 2-rozměrné bloky. Cyklická a blokově-cyklická distribuce datových polí Nerovnoměrné množství práce spojené s jednotlivými prvky ⇒ 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). 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 Mapování založené na rozdělení dat – pokračování Náhodná distribuce bloků Zátěž související s prvky pole vytváří pravidelné vzory. ⇒ š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. 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 Mapování založené na rozdělení úloh 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. 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ů str. 24/39 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í Úlohy jsou shromažď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 Třídění prvků v n × n matici A for (i=1; i p log p (cena C = Θ(n)) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 20/35 Sekce Š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 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álování 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 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 p = TS pTP = 1 1 + TO TS Celková režie (TO) Přítomnost sekvenční části kódu je nevyhnutelná. Pro její vykonání je třeba čas tserial . Po tuto dobu jsou ostatní procesní jednotky nevyužité. TO > (p − 1)tserial TO roste minimálně lineárně vzhledem k p, často však i asymptoticky více. Úloha konstantní velikosti (TS fixní) Se zvyšujícím se p, efektivita nevyhnutelně klesá. 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 Úkol: Sečíst n čísel s využitím p procesních jednotek. Uvažme cenově optimální verzi algoritmu. Tp = (n p + log p). Lokální operace stojí 1, komunikace 2 jednotky času. Charakteristiky řešení TP = n p + 2log p S = n n p +2log p E = 1 1+ 2plog p n IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 24/35 Charakteristiky škálování – Škálovatelný systém Při zachování TS Rostoucí počet procesních jednotek snižuje efektivitu. Při zachování počtu procesních jednotek Rostoucí TS (velikost vstupních dat) má tendenci zvyšovat efektivitu. Škálovatelné systémy Efektivitu lze zachovat při souběžném zvyšování TS a p. Zajímáme se o poměr, ve kterém se TS a p musí zvyšovat, aby se zachovala efektivita. Čím menší poměr TS/p tím lepší škálovatelnost. IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 25/35 Izoefektivita jako metrika škálování Vztahy TP = TS +TO(W ,p) p W – velikost vstupních dat S = TS TP = pTS TS +TO(W ,p) E = S p = TS TS +TO(W ,p) = 1 1+TO(W ,p)/TS Konstantní efektivita Efektivita je konstantní, pouze pokud TO(W , p)/TS je konstantní. Úpravou vztahu pro efektivitu: TS = E 1−E TO(W , p). Při zachování míry efektivity lze E/(1 − E) označit jako konstantu K. Funkce izoefektivity (stejné efektivity) TS = KTO(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 = KTO(W , p) Pozorování Při konstantní efektivitě, lze TS vyjádřit jako funkci p Vyjadřuje vztah, jak se musí zvýšit TS 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 = 1 1+(2p log p)/n = 1 1+TO(W ,p)/TS TO = 2p log p Funkce izoefektivity: TS = K2p log p Funkce izoefektivity: Θ(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′)/(p log p). IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 28/35 Cenová optimalita a izoefektivita Optimální cena Pro cenově optimální systémy požadujeme pTP = Θ(TS). Po dosazení ze základních izo vztahů dostáváme: TS + TO(W , p) = Θ(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 TO(W , p) ∈ O(TS) složitost sekvenčního algoritmu je minimálně tak velká jako režie, tj. funkce TS ∈ Ω(TO(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ální hodnotu izofunkce. Sublineární izoefektivita Pro problém tvořený N jednotkami práce je optimální cena dosažitelná pouze pro maximálně N procesních jednotek. 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 (Tmin P ) při dostupnosti dostatečného počtu procesních jednotek? Pozorování Při rostoucím p se TP asymptoticky blíží k Tmin P . Po dosažení Tmin P se TP zvětšuje spolu s p. Jak zjistit Tmin P ? Nechť p0 je kořenem diferenciální rovnice dTP dp . Dosazení p0 do vztahu pro TP dává hodnotu Tmin P . Příklad – součet n čísel p procesními jednotkami TP = n p + 2log p, dTP dp = − n p2 + 2 p p0 = n 2 , Tmin P = 2log n = Θ(log n) IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 31/35 Asymptotická analýza paralelních programů Algoritmus A1 A2 A3 A4 p n2 log n n √ n TP 1 n √ n √ nlog n S n log n log n √ nlog n √ n E log n n 1 log n√ n 1 pTP n2 n log n n1.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ěr 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 Sekce 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 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 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 IB109 Návrh a implementace paralelních systémů Paralelizace grafových algoritmů Jiří Barnat Sekce Grafové algoritmy IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 2/38 Grafové pojmy a reprezentace grafu Základní pojmy Neorientovaný/orientovaný graf Hrany, vrcholy, incidentní vrcholy hrany, sousednost Cesta, dosažitelnost, cyklus, acyklický graf Souvislost, podgraf, kompletní graf, les, strom, DAG Váhy na hranách, minimální kostra Řídké a husté grafy Reprezentace grafu Explicitní: Matice sousednosti a vah Explicitní: Seznam následníků (řídké grafy) Implicitní: Funkce pro enumeraci následníků IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 3/38 Minimální kostra: Primův Algoritmus proc PRIM_MIN_KOSTRA(V , E, w, r) W := {r} d[r] := 0 forall v ∈ (V − W ) if (r, v) ∈ E then d[v] := w(r, v) else d[v] := ∞ fi while W = V do vyber u tak, aby d[u] = min{d[v] | v ∈ V − W } W := W ∪ {u} forall v ∈ (V − W ) d[v] := min{d[v], w(u, v)} od end IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 4/38 Minimální kostra: Primův Algoritmus Limity paralelizace Souběžné zpracování více pivotů je nekorektní Iterace while musí být serializovány Paralelizace Mapování vrcholů na procesy Jednotlivé procesy identifikují kandidáty na pivota ATO redukce kandidátů OTA broadcast pivota Lokalizovaný update prvků d[v] (cyklus forall) IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 5/38 Nejkratší cesty z jednoho vrcholu: Dijkstrův algoritmus proc DIJKSTRA_SINGLE_SOURCE(V , E, w, s) W := {s} forall v ∈ (V − W ) if (s, v) ∈ E then l[v] := w(s, v) else l[v] := ∞ fi while (W = V ) do vyber u tak, aby l[u] = min{l[v] | v ∈ V − W } W := W ∪ {u} forall v ∈ (V − W ) l[v] := min{l[v], l[u] + w(u, v)} od end IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 6/38 Nejkratší cesty mezi všemi vrcholy: Dijkstrův algoritmus Princip Násobné provedení Dijkstrova algoritmu pro výpočet nejkratších cest vedoucích z jednoho vrcholu Paralelizace dělením vstupu Vrcholy grafu mapovány na procesy Každý proces provádí sekvenční výpočet nejkratších cest z vrcholů jemu přidělených Při replikaci dat, není třeba komunikace Neškáluje pro p > n Paralelizace dělením vstupu a paralelizací operací Vrcholy grafu mapovány na skupiny procesorů Každá skupina procesorů provádí paralelní algoritmus pro detekci nejkratších cest z jednoho vrcholu Škáluje i pro p > n IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 7/38 Nejkratší cesty mezi všemi vrcholy: Floydův algoritmus proc FLOYD_ALL_PAIRS(Matice sousednosti A) D0 := A for k := 1 to n do for i := 1 to n do for j := 1 to n do d (k) i,j := min(d (k−1) i,j , d (k−1) i,k + d (k−1) k,j ) od od od end IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 8/38 Nejkratší cesty mezi všemi vrcholy: Floydův algoritmus Paralelizace Pro výpočet prvků d(k) je třeba prvky d(k−1) Vzhledem k datovým závislostem nelze paralelizovat vnější for cyklus Dekompozice vnitřních cyklů dle hodnot proměnných i a j Při p procesech se matice velikosti n × n dekomponuje na √ p × √ p bloků o velikosti n/ √ p × n/ √ p Návrh implementace Pro výpočet prvku di,j potřeba prvky z řádku j a sloupku i Procesy odešlou jimi zpravovaná data verze k − 1 ostatním procesům ve stejném řádku či sloupku, poté přijmou data verze k − 1 od těchto procesů, a spočítají hodnoty verze k IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 9/38 Nejkratší cesty mezi všemi vrcholy: Floydův algoritmus Naivní implementace Prostoje při čekání data od všech okolních procesů Implementace s použitím modelu pracovní linky (pipeline) Proces Pi,j se při komunikaci nesynchronizuje s ostatními, nečeká až všichni obdrží data z předchozí iterace čas: t+0: + t+1: + + t+2: + + t+3: + + t+4: + t+5: + IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 10/38 Tranzitivní uzávěr (relace dosažitelnosti) Princip výpočtu Matice dosažitelnosti (matice hodnot typu Bool) Při ohodnocení hran hodnotou 1, lze použít libovolný algoritmus pro výpočet nejkratších cest mezi všemi vrcholy Dijkstrův či Floydův algoritmus Nenulová hodnota di,j znamená existenci cesty Modifikace Floydova algoritmu d (k) i,j := d (k−1) i,j ∨ (d (k−1) i,k ∧ d (k−1) k,j ) IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 11/38 Řídké grafy Výhody Algoritmy mohou pracovat bez maticové reprezentace Složitosti algoritmů přestávají mít dolní odhad V2 Složitosti algoritmů mají dolní odhad V + E Paralelizace Celkový výkon paralelního algoritmu výrazně ovlivněn dělením grafu IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 12/38 Řídké grafy: Maximální nezávislá množina Definice Vrcholy u, v jsou nezávislé, pokud neexistuje hrana (u, v) Maximální nezávislá množina vrcholů, je množina po dvou nezávislých vrcholů, kterou nelze rozšířit o další vrchol tak, aby zůstala nezávislá proc MAXIMAL_INDEPENDENT_SET(V , E) I := ∅; C := V while (C = ∅) do vyber vrchol u z množiny kandidátů C I := I ∪ {u} forall (v ∈ C) if (u, v) ∈ E then C := C − {v} fi od end IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 13/38 Řídké grafy: Maximální nezávislá množina Problém paralelizace Jak souběžně zvolit více vrcholů, aby byla garantována jejich nezávislost? Řešení 1) Vrcholům se přiřadí náhodná čísla 2) Paralelně se identifikují vrcholy, jejichž všichni sousedé v množině kandidátů mají přiřazena čísla větší než je číslo testovaného vrcholu 3) Identifikované vrcholy se přidají do nezávislé množiny a jejich sousedé se odstraní z množiny kandidátů 4) Opakuje se 2)-3) dokud není množina kandidátů prázdná IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 14/38 Řídké grafy: Nejkratší cesty z jednoho vrcholu Modifikace Dijsktrova algoritmu Pro určení vrcholu u s minimální hodnotou l[u] lze použít prioritní frontu, která upřednostňuje vrcholy s menší hodnotou l Frontu lze udržovat za cenu log n (binární halda) Operaci pro aktualizaci hodnot sousedů vybraného vrcholu u lze provést efektivně pomocí seznamu následníků Paralelizace zachovávající optimální množství práce Jeden proces udržuje prioritní frontu (extrahuje minima) Ostatní procesy provádí aktualizace hodnot l Synchronizace po zpracování každého vrcholu Je-li l[u] aktuální minimální hodnota vybraného vrcholu, je korektní souběžně zpracovávat všechny vrcholy v takové, že l[v] = l[u], nebo přesněji l[v] ≤ l[u] + m, kde m je minimální cena hrany IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 15/38 Řídké grafy: Nejkratší cesty z jednoho vrcholu Paralelizace nezachovávající optimální množství práce Souběžné zpracování všech vrcholů z fronty Některým vrcholům v může být přiřazena nesprávná hodnota l[v] Nesprávná hodnota je detekována v okamžiku výpočtu správné hodnoty Vrcholy v, jejichž hodnota je nesprávná, jsou znovu zařazeny do fronty se správnou hodnotou l[v] Některé vrcholy zpracovány opakovaně (dochází k postupnému vylepšování hodnoty l[v]) IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 16/38 Řídké grafy: Detekce cyklu v orientovaném grafu Sekvenční algoritmus Prohledávání grafu do hloubky (DFS) Přítomnost cyklu detekována hranou vedoucí z aktuálně zkoumaného vrcholu do vrcholu na zásobníku Paralelní algoritmus Lze řešit asymptoticky optimálně bez použití DFS Topologické uspořádání: u < v jestliže (u, v) ∈ E Vrcholy grafu lze topologicky uspořádat pouze pokud graf neobsahuje cyklus IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 17/38 Řídké grafy: Detekce cyklu v orientovaném grafu proc CYCLE_DETECTION(V , E) Q := ∅ CV := V forall v ∈ V indegree(v) = {(u, v) ∈ E} if (indegree(v) = 0) then Q := Q ∪ {v} fi while (Q = ∅) do u := Extract(Q) CV := CV − {u} forall v ∈ ADJ(u) indegree(v) := indegree(v) − 1 if (indegree(v) = 0) then Q := Q ∪ {v} fi od if (CV = ∅) then Output(“Cycle detected”) fi end IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 18/38 Sekce Detekce akceptujícího cyklu IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 19/38 Akceptující cyklus IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 20/38 Detekce akceptujícího cyklu Algoritmus Nested DFS Dvojí prokládané prohledávání do hloubky 1. hledání identifikuje akceptující stavy 2. hledání testuje akceptující stavy na sebe-dosažitelnost Pokud se obě DFS procedury správně prokládají, algoritmus je korektní a pracuje v lineárním (optimálním) čase 2. hledání je spuštěno v okamžiku opuštění akceptujícího vrcholu 1. procedurou (DFS postorder) 2. hledání je omezeno na vrcholy dosažitelné z daného akceptujícího vrcholu a dosud nenavštívené v předchozích voláních 2. procedury IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 21/38 Detekce akceptujícího cyklu Problém Výpočet DFS postorderu je inherentně sekvenční problém Optimální paralelní a škálovatelný algoritmus pro výpočet DFS-postorderu není znám (a pravděpodobně neexistuje) Nested DFS není použitelné na paralelních platformách IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 22/38 Algoritmus OWCTY Idea Odstranění vrcholů, které nemohou být na akceptujícím cyklu Vlastnosti vrcholů na akceptujícím cyklu musí být dosažitelné z nějakého akceptujícího vrcholu musí mít alespoň jednoho předchůdce Realizace Paralelní procedury pro odstraňování vrcholů Reachability Elimination Procedury se opakují dokud se nedosáhne pevného bodu Neprázdný graf indikuje přítomnost akceptujícího cyklu IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 23/38 OWCTY IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 OWCTY IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 24/38 MAP Algoritmus Idea Pokud je nějaký akceptující vrchol svým předchůdcem, pak existuje akceptující cyklus Vypočítat a uchovávat všechny předchůdce daného vrcholu je nákladné. Množinu všech předchůdců budeme reprezentovat pouze největším (v nějakém uspořádání) vrcholem z dané množiny. Pokud je akceptující vrchol svým maximálním předchůdcem, leží na akceptujícím cyklu. Realizace Propagace maximálních akceptujících předchůdců (MAP). Pokud je vrchol propagován do sebe sama, je nalezen akceptující cyklus. Pokud se to nestane, odstraní se iniciální akceptující vrcholy. Propagaci je možné provádět paralelně. IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 25/38 MAP IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 1st iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 MAP 2nd iteration IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 26/38 Porovnání algoritmů Složitost Optimalita Časná detekce Nested DFS O(N+M) Ano Ano OWCTY Algorithm O(N.(N+M)) Ne Ne MAP Algorithm O(N.N.(N+M)) Ne Ano N – počet vrcholů M – počet hran Možný první dojem: Nové algoritmy jsou k ničemu. IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 27/38 Co bychom očekávali při použití paralelního HW Systémy se sdílenou pamětí Redukce času potřebného k detekci akceptujícího cyklu. Systémy s distribuovanou pamětí (klastry, gridy) Agregovaná paměť by měla umožnit analýzu větších grafů. Redukce času potřebného k detekci akceptujícího cyklu. IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 28/38 Systémy se sdílenou pamětí Použitý Hardware 16-core server (8x AMD dual core) 64 GB RAM Algoritmy/Nástroje SPIN Nested DFS Implementace optimalizována téměř 20 let Znám pro svou obrovskou rychlost DiVinE Algoritmus OWCTY Realizace implementace: implementace studenty FI Otázka Může neoptimální OWCTY algoritmus v praxi porazit optimální Nested DFS? IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 29/38 Škálovatelnost OWCTY SPIN: 1 Core: 238 sec 2 Cores: 343 sec DiVinE: Cores Runtime (sec) Efficiency 1 738 100% 2 392 94% 4 235 78% 8 170 54% 16 106 43% IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 30/38 Systémy se sdílenou pamětí Otázka Může neoptimální OWCTY algoritmus v praxi porazit optimální Nested DFS? IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 31/38 Systémy se sdílenou pamětí Otázka Může neoptimální OWCTY algoritmus v praxi porazit optimální Nested DFS? Ano IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 31/38 Systémy s distribuovanou pamětí Použitý Hardware Klastr 64 výpočetních uzlů Každý uzel má 2x dual-core CPU a 4 GB RAM Myri-10G síťové spojení DiVinE Cluster Algoritmy OWCTY a MAP Síťová vrstva vyladěna expertem na klastrové počítání Otázky Je síťová komunikace úzkým místem? Může klastr porazit systémy se sdílenou pamětí? Je možné analyzovat extrémně velké grafy? IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 32/38 Škálovatelnost OWCTY Cores Runtime (sec) Efektivita 1 631.7 100% 64 13.3 74% 128 7.4 67% 256 5.0 49% IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 33/38 Škálovatelnost MAPu Cores Runtime (sec) Efektivita 1 1052.5 100% 64 23.0 72% 128 13.1 63% 256 8.9 46% IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 34/38 Systémy s distribuovanou pamětí Otázky Je síťová komunikace úzkým místem? Může klastr porazit systémy se sdílenou pamětí? Je možné efektivně analyzovat extrémně velké grafy? IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 35/38 Systémy s distribuovanou pamětí Otázky Je síťová komunikace úzkým místem? Ne nutně Může klastr porazit systémy se sdílenou pamětí? Je možné efektivně analyzovat extrémně velké grafy? IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 35/38 Systémy s distribuovanou pamětí Otázky Je síťová komunikace úzkým místem? Ne nutně Může klastr porazit systémy se sdílenou pamětí? Ano Je možné efektivně analyzovat extrémně velké grafy? IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 35/38 Systémy s distribuovanou pamětí Otázky Je síťová komunikace úzkým místem? Ne nutně Může klastr porazit systémy se sdílenou pamětí? Ano Je možné efektivně analyzovat extrémně velké grafy? Ano IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 35/38 Závěr 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ů: Paralelizace grafových algoritmů str. 36/38 Sekce Shrnutí IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 37/38 Co jsme se dozvěděli Paralelní HW platformy 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 Principy návrhu paralelních algoritmů. Ukázky paralelních řešení grafových problémů. IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 38/38 Sekce Shrnutí IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 1/2 Co jsme se dozvěděli Paralelní HW platformy 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 Principy návrhu paralelních algoritmů. Ukázky paralelních řešení grafových problémů. IB109 Návrh a implementace paralelních systémů: Paralelizace grafových algoritmů str. 2/2