Domov › Služby › Typy paralelismu. Klasifikace systémů paralelního zpracování dat

Typy paralelismu. Klasifikace systémů paralelního zpracování dat

Ministerstvo školství a vědy Ruské federace

FSBEI HPE "Bryansk State Engineering and Technology

akademie"

Katedra informačních technologií

Sekvenční a paralelní zpracování informací

Výpočetní a grafická práce č.1

disciplínou

"Technologie zpracování informací"

Možnost č. 16

RGR-02068025.230400.084

Bryansk 2015

Úvod 3

Paralelní zpracování informací 4

Systémy sdílené paměti 6

Paralelní zpracování SQL 7

Sekvenční zpracování informací 9

10 jednoduchých dávkových systémů

Reference 13

Úvod

Tato výpočetní a grafická studie zkoumá sekvenční a paralelní zpracování informací. U každého z nich jsou uvedeny příklady.

Sekvenční zpracování informací je sekvenční průchod informace ze vstupu na výstup řadou transformací (fází), takže v každém časovém období (specifickém pro daný blok) je transformace provedena pouze v jednom funkčním bloku a informace přichází až z předchozího bloku.

Paralelní zpracování informací je model zpracování informací, podle kterého informace procházejí řadou transformací v určitých funkčních blocích, takže v daném okamžiku jsou zpracovávány současně (paralelně) v několika blocích.

Paralelní zpracování informací

Paralelní zpracování dat, ztělesňující myšlenku současného provádění několika akcí, má dvě varianty: potrubí a paralelismus.

Paralelní zpracování. Pokud určité zařízení provede jednu operaci za jednotku času, pak provede tisíc operací za tisíc jednotek. Pokud předpokládáme, že existuje pět stejných nezávislých zařízení schopných pracovat současně, pak systém pěti zařízení může provést stejných tisíc operací ne za tisíc, ale za dvě stě jednotek času. Podobně systém N zařízení vykoná stejnou práci za 1000/N jednotek času. Podobné analogie lze nalézt i v životě: když jeden voják vykope zahradu za 10 hodin, pak rota padesáti vojáků se stejnými schopnostmi, pracujících současně, zvládne stejnou práci za 12 minut - princip paralelismu v akci!

Zpracování dopravníků. Co je potřeba k sečtení dvou reálných čísel reprezentovaných v plovoucí řádové čárce? Spousta malých operací, jako je porovnávání objednávek, zarovnání objednávek, přidávání mantis, normalizace atd. Procesory prvních počítačů prováděly všechny tyto „mikrooperace“ pro každou dvojici argumentů jednu po druhé, dokud nedosáhly konečného výsledku, a teprve poté přistoupily ke zpracování další dvojice členů.

Myšlenkou zpracování potrubí je izolovat jednotlivé fáze provádění obecné operace a každá fáze po dokončení své práce předá výsledek další a současně přijímá novou část vstupních dat. Zřejmý nárůst rychlosti zpracování dosáhneme kombinací dříve rozložených operací. Předpokládejme, že v operaci je pět mikrooperací, z nichž každá je provedena v jedné časové jednotce. Pokud existuje jedno nedělitelné sériové zařízení, pak zpracuje 100 párů argumentů v 500 jednotkách. Pokud je každá mikrooperace rozdělena do samostatné fáze (nebo jinak nazývané fáze) dopravníkového zařízení, pak v páté časové jednotce, v různých fázích zpracování takového zařízení, bude umístěno prvních pět párů argumentů. , a celá sada sto párů bude zpracována za 5 + 99 = 104 jednotek času - zrychlení oproti sériovému zařízení je téměř pětinásobné (podle počtu stupňů dopravníku).

Zdálo by se, že zpracování potrubí lze úspěšně nahradit obyčejným paralelismem, pro který duplikujeme hlavní zařízení tolikrát, kolik stupňů potrubí má být přiděleno. Ve skutečnosti pět zařízení v předchozím příkladu zpracuje 100 párů argumentů za 100 jednotek času, což je rychlejší než doba běhu potrubního zařízení! Pětinásobným navýšením počtu zařízení tedy výrazně zvyšujeme jak objem zařízení, tak i jeho cenu. Představte si, že by se automobilka rozhodla odstranit montážní linku při zachování rychlosti výroby automobilů. Pokud dříve bylo na montážní lince současně tisíc vozů, pak je analogicky s předchozím příkladem nutné naverbovat tisíc týmů, z nichž každý je schopen kompletně sestavit vůz od začátku do konce, provádění stovek různých typů operací, a to ve stejnou dobu, kdy bylo auto předtím na montážní lince.

Paralelismus v počítačové architektuře dnes překvapí málokoho. Všechny moderní mikroprocesory používají nějakou formu paralelního zpracování. V jádře Pentium 4 lze současně provádět až 126 mikrooperací v různých fázích provádění. Tyto myšlenky se přitom samy objevily již velmi dávno. Zpočátku byly implementovány v nejvyspělejších, a tedy jednotlivých počítačích své doby. Poté, po patřičném vývoji technologie a levnější výrobě, se sestoupilo k počítačům střední třídy a dnes je to vše plně vtěleno do pracovních stanic a osobních počítačů.

Výkon mnoha aplikací běžících na jednoprocesorových počítačových systémech lze výrazně zlepšit použitím nástrojů pro paralelní zpracování. Dále jsou uvedeny základní pojmy paralelního zpracování a víceprocesorové počítačové architektury.

Když více aplikací požaduje zpracování svých úloh na jednoprocesorovém počítači, veškerou práci musí udělat jeho jediný procesor. Účelem paralelního zpracování je obvykle zlepšit výkon aplikací. Když aplikace vydá požadavek na úlohu víceprocesorovému počítači, počítač rozdělí úlohu na logické dílčí úlohy a ty pak zpracuje paralelně pomocí více procesorů, čímž se zkrátí doba potřebná k dokončení úlohy. Počet dílčích úkolů vyplývajících z rozdělení jednoho velkého úkolu se nazývá stupeň paralelismu . Snížení doby zpracování informací potřebné k dokončení úkolu je přímo úměrné stupni paralelismu. Snaží se zvýšit výkon systémů s paralelním zpracováním tak, aby zajistili maximální výkon každého procesoru v systému.

4. ročník, 1. a 2. proud, 7. semestr

přednášky (34 hod.), test

Oddělení odpovědné za kurz: ASVK

Kompilátor programu: člen-kor. RAS, doktor fyziky a matematiky. Sciences Voevodin Vl.V.,

Přednášející: člen-kor. RAS, doktor fyziky a matematiky. Vědy Voevodin Vl.V.

anotace

Kurz pojednává o obecných otázkách organizace paralelních výpočtů. Jsou zvažovány vlastnosti architektur moderních paralelních výpočetních systémů, studovány základní metody a paradigmata programování v paralelních prostředích.

Pro 1. a 2. proud jsou diskutovány přístupy k harmonizaci architektury paralelních systémů a struktury algoritmů, otázky teorie analýzy struktury programů a algoritmů a modely v paralelním počítání.

Program

1. Velké úlohy a superpočítače. Paralelní a potrubní zpracování dat. Paralelnost a pipelineability v architektuře moderních vysoce výkonných počítačů. Skalární a vektorové příkazy. Skalární, potrubní a vektorová zařízení. Paměťová hierarchie v počítačích jako prostředek ke zvýšení rychlosti provádění programu, lokality výpočtů a lokality použití dat. Amdahlův zákon a jeho důsledky, superlineární zrychlení.

2. Hlavní třídy moderních paralelních výpočetních systémů. Počítače se sdílenou pamětí, příklady, důvody snížení výkonu v reálných programech. Architektury SMP, NUMA, ccNUMA. Přepínání procesorů a paměťových modulů, sběrnice, maticový přepínač, omega síť. Vector-pipeline výpočetní systémy, příklady, důvody snížení výkonu. Počítače s distribuovanou pamětí, příklady, důvody snížení výkonu. Topologie komunikace mezi procesory: hvězda, mřížka, trojrozměrný torus, binární hyperkrychle, jejich vlastnosti. Výpočetní clustery, příklady, latence a propustnost různých komunikačních technologií. Architektury s paralelismem na úrovni strojových instrukcí, VLIW, superskalarita.

3. Technologie paralelního programování. Tradiční sekvenční jazyky a paralelizační kompilátory, problémy. Speciální komentáře a pokyny k překladači, rozšíření existujících jazyků. Speciální paralelní programovací jazyky. Programování pomocí knihoven a rozhraní pro předávání zpráv. Paralelní oborové knihovny, specializované balíčky a softwarové systémy na vysoké úrovni. Technologie paralelního programování MPI, OpenMP, Linda.

4. Výkon paralelních výpočetních systémů. Všestrannost a specializace počítačů, výkon speciálních procesorů. Moorův zákon. Metody hodnocení výkonu. Zavedení jediného číselného parametru, Mflops, MIPS. Špičkový a skutečný výkon počítače. Linpack test a jeho varianty. Sady doplňkových testovacích programů STREAM a NPB.

5. Grafové modely programů. Kontrolní graf a graf informací o programu. Informace a provozní historie realizace programu. Algoritmický graf jako kompaktní parametrická forma reprezentace informační historie. Informační nezávislost operací a možnost jejich paralelního provádění. Délka kritické cesty grafu algoritmu jako míra míry rovnoběžnosti. Konečná a masivní rovnoběžnost, souřadnicová a šikmá rovnoběžnost. Transformace ekvivalentních programů, transformace elementárních cyklů.

6. Heterogenní distribuované výpočetní systémy. Metapočítače a metapočítače, existující projekty metapočítačů. Charakteristické vlastnosti metapočítačů. Koncept GRID, základní komponenty a služby, existující projekty segmentů GRID, koncept virtuální organizace.

Literatura

1. Voevodin V.V., Voevodin Vl.V. Paralelní počítání. – Petrohrad: BHV Petrohrad, 2002. - 608 s.

2. Koroljov L.N. Architektura elektronických počítačových procesorů. – M.: Nakladatelství. Fakulta výpočetní matematiky a matematiky Moskevské státní univerzity, 2003.

3. V.V. Paralelní výpočetní systémy. – M.: Nakladatelství Knowledge, 1999. – 320 s.

4. Materiály informačního a analytického centra pro paralelní výpočty Parallel.ru.

doplňková literatura

1. Antonov A.S. Paralelní programování pomocí technologie

MPI: Návod. – M.: Nakladatelství Moskevské státní univerzity, 2004. - 71 s.

Pod pojmem paralelní zpracování budeme rozumět simultánnímu provádění úloh, kroků úloh (položek), programů, podprogramů, smyček, operátorů a příkazů. Paralelní zpracování informací lze použít pro dva hlavní účely:

1. Zvyšování produktivity počítačů a letadel nikoli zlepšováním základny prvků, ale efektivní organizací výpočetních procesů.

2. Zajištění vysoké spolehlivosti letadel zdvojením počítačového vybavení.

Rýže. 5.1. Úrovně paralelismu

Zvýšení výkonu počítačů a počítačů je hlavním cílem použití paralelního zpracování, z tohoto důvodu mají počítače, jako jsou multiprocesorové servery, sálové počítače a superpočítače, paralelní architekturu.

Paralelní zpracování informací lze provádět na několika úrovních (obr. 5.1).

Je zřejmé, že čím nižší úroveň, tím jemnější fragmentace softwarových procesů, tím jemnější, jak se říká, “ zrnko paralelismu" Obecně je možné paralelismus implementovat jak na jedné úrovni, tak na několika současně. Nezávislé jednoprocesorové zpracování implementuje paralelismus na úrovni 1. Vektorové zpracování sestává z paralelního provádění smyček na úrovni 2 a může být provedeno na jednom nebo několika procesorech. Úrovně 3 a 4 odpovídají víceprocesorovým počítačům. Paralelismus úrovně 5 je typický pro vícestrojové výpočetní systémy.

Existují dva hlavní způsoby, jak organizovat paralelní zpracování:

· časová kombinace etap řešení různých problémů;

· současné řešení různých úkolů nebo částí jednoho úkolu;

První způsob- spojování fází řešení různých problémů v čase víceprogramové zpracování informace. Víceprogramové zpracování se již dlouho široce používá ke zlepšení výkonu počítačů a počítačů. Podrobná diskuse o víceprogramovém zpracování se vztahuje k tématu „Operační systémy“ a přesahuje rámec této učebnice.

Druhý způsob- současné řešení různých úloh nebo částí jedné úlohy - je možné pouze v případě, že existuje více zpracovatelských zařízení. V tomto případě se používají určité vlastnosti úloh nebo toků úloh, což umožňuje paralelizaci.

Lze rozlišit následující typy paralelismu, umožňující implementaci algoritmických vlastností jednotlivých úloh a jejich vláken.

1. Přirozený paralelismus nezávislých úloh.

2. Paralelnost objektů nebo dat.

3. Paralelnost úkolových nebo programových větví.

Podívejme se na tyto typy paralelismu.

1. Přirozený paralelismus nezávislých úloh spočívá v tom, že na vstupu počítačového systému je přijímán nepřetržitý proud nesouvisejících úkolů, tzn. řešení jakéhokoli problému nezávisí na výsledcích řešení jiných problémů. V tomto případě použití několika procesních zařízení s libovolným způsobem integrace (integrace do systému) zvyšuje výkon systému.

Typickým příkladem přirozeného paralelismu je příchod požadavků uživatelů na informační web. Každý požadavek generuje samostatnou proceduru pro její provedení, která nezávisí na jiných podobných procedurách.

2. Objektový nebo datový paralelismus nastává, když stejný (nebo téměř stejný) program musí zpracovávat určitou sadu dat vstupujících do systému současně.

Mohou to být například úlohy zpracování signálů z radarové stanice: všechny signály jsou zpracovávány pomocí stejného programu. Dalším příkladem je zpracování informací ze senzorů, které současně měří stejný parametr a jsou instalovány na několika podobných objektech.

Programy tohoto typu mohou mít různou velikost a složitost, od velmi jednoduchých obsahujících několik operací až po velké programy obsahující stovky a tisíce operací. V tomto případě je paralelního provádění operací dosaženo zvýšením počtu procesních zařízení, z nichž každé je schopno autonomně provádět sekvenci příkazů na samostatné sadě dat. Hlavním rysem takových programů (zejména programů pro zpracování vektorů a matic) je často to, že stejný příkaz musí být proveden na velké sbírce elementárních dat, která jsou nějakým způsobem propojena, a odpovídající operace může být provedena se všemi daty současně. V tomto případě se čas na řešení problému zkracuje úměrně počtu zpracovatelských zařízení.

3. Paralelnost úkolových nebo programových větví- jeden z nejběžnějších typů paralelismu při zpracování informací. Spočívá v tom, že při řešení jednoho problému lze oddělit jeho jednotlivé části - větve, které lze za přítomnosti více zpracovatelských zařízení provádět paralelně. V tomto případě pouze nezávislé pobočkyúkoly, tzn. takové jeho části, pro které jsou splněny tyto podmínky:

· žádná z výstupních hodnot těchto větví problému není vstupní hodnotou pro jinou takovou větev (nedostatek funkčních vazeb);

· podmínky pro provádění jedné větve nezávisí na výsledcích nebo charakteristikách získaných při provádění jiných větví (nezávislost na řízení).

Dobrou představu o paralelnosti větví poskytuje tier-paralelní forma (LPF) programu, jejíž příklad je znázorněn na obr. 5.2.

Program je prezentován ve formě sady poboček umístěných na několika úrovních - úrovních. Kruhy s čísly uvnitř označují větve. Délka větve je reprezentována číslem vedle kruhu a říká, kolik časových jednotek je tato větev vykonána. Šipky ukazují vstupní data a výsledky zpracování. Vstupní data jsou označena symbolem X, výstupní data symbolem Y. Symboly X mají nižší digitální indexy udávající čísla vstupních veličin; Symboly Y mají digitální indexy jak dole, tak nahoře; číslo nahoře odpovídá číslu větve, během které byl daný výsledek získán, a číslo dole znamená pořadové číslo výsledku získaného při implementaci této větve programu. Nezávislé větve úloh, které spolu nesouvisí, jsou umístěny na jedné úrovni, tzn. výsledky řešení libovolné větve dané vrstvy nejsou vstupními daty pro jinou větev stejné vrstvy.

Rýže. 5.2. Příklad víceúrovňového paralelního programu

Na Obr. 5.2 program obsahuje 9 větví umístěných na 3 úrovních. Pomocí tohoto obecně docela jednoduchého programu jako příkladu lze identifikovat výhody výpočetního systému, který zahrnuje několik procesních zařízení, a problémy, které se objevují.

Předpokládejme, že délka i tý větev je reprezentována počtem časových jednotek t i které jsou nutné k jeho provedení. Pak si lze snadno spočítat, že spuštění celého programu na 1 procesoru zabere čas T 1:

T 1=S (10+20+15+30+55+10+15+25+15)=195

Pokud si představíme, že program je vykonáván dvěma procesory (procesory) pracujícími nezávisle na sobě, pak se čas potřebný k vyřešení problému zkrátí. Tato doba, jak je snadno vidět, se však bude lišit v závislosti na pořadí provádění nezávislých větví.

Vezměme si například tuto verzi programu znázorněnou na Obr. 5.2. Nechte procesor 1 provádět větve 1-3-4-6-7-9 a procesor 2 provádět větve 2-5-8. Na Obr. Obrázek 5.3 ukazuje časové diagramy provádění procesorových větví programu.

Rýže. 5.3. Dekompozice větví programu přes 2 procesory

Je snadné spočítat, že procesor 1 stráví 105 a procesor 2 - 100 jednotek času. V tomto případě existují dvě časová období, kdy je jeden z procesorů nucen nečinně – P1 s dobou trvání 10 jednotek a P2 s dobou trvání 5 jednotek času. Interval P1, během kterého pracuje pouze procesor 2, vznikl z toho důvodu, že větev 7 závisí na větvi 5 (v době, kdy je větev 6 dokončena, data Y 5 1 ještě nejsou připravena). Interval P1, během kterého pracuje pouze procesor 1, vznikl z důvodu ukončení počítání procesorem 2.

Na systému dvou procesorů tak bude náš program plně proveden za minimálně 105 jednotek času. Hodnota charakterizující zkrácení doby potřebné k vyřešení problému na několika procesorech ve srovnání s použitím jednoho procesoru se nazývá zrychlení počítání S a počítat jako

Koeficient paralelizace se pohybuje od 0 do 1 (od 0 do 100 %) a odráží efektivitu využití výpočetních zdrojů. V našem příkladu je snadné vypočítat zrychlení S= 195/105 = 1,86 a faktor paralelizace K p= 0,93. Jak vidíme, z důvodu výpadku jednoho z procesorů je zrychlení výpočtu výrazně menší než 2, tzn. počet použitých procesorů. Všimněte si, že v našem příkladu nebyla zohledněna časová zpoždění spojená s přepínáním kontextů programu (změnou větví) a přenosem dat z jedné větve do druhé. Vzhledem k algoritmickým vlastnostem programu však část výpočtů v intervalech P1 a P2 provádí pouze jeden procesor, tzn. vlastně sekvenční.

Uvažujme zobecněný případ programu, ve kterém je, algoritmicky, podíl sekvenčních výpočtů (poměr času sekvenčních výpočtů k celkovému výpočetnímu času programu) určitou hodnotou F. V tomto případě je doba provádění programu v systému od p procesorů nemůže být menší než

Tento poměr se nazývá Amdahlův zákon. Pomocí příkladu programu na obr. 5.2 vidíme, že podíl sekvenčních výpočtů je F= 15/195. Dosazením této hodnoty do vzorce Amdahlova zákona získáme pro soustavu dvou procesorů maximální zrychlení 1,86 krát, což odpovídá dříve vypočítané hodnotě.

Pro ilustraci fungování Amdahlova zákona uvádíme následující příklad. Nechť je podíl sekvenčních výpočtů v některém programu 10 %. Pak maximální zrychlení výpočtu na 100 procesorech nepřekročí 9,2. Koeficient paralelizace bude pouze 9,2 %. Na 10 procesorech bude zrychlení 5,3 a koeficient paralelizace 53 %. Je snadné vidět, že i tak malý zlomek sekvenčních výpočtů, již na teoretické úrovni, bez zohlednění nevyhnutelných prodlev ve skutečném počítači, vážně omezuje možnost škálování programu.

Určíme, jaký by měl být maximální podíl F sekvenční výpočty v programu tak, aby bylo možné získat předem stanovené zrychlení výpočtu S s maximálním koeficientem paralelizace K p. K tomu vyjadřujeme podíl sekvenčních výpočtů z Amdahlova zákona:

Vztah (5.6) určuje velmi důležité následek z Amdahlova zákona. Pro urychlení programu vq krát, je nutné zrychlit ne méně nežq krát ne méně než () část programu. Chcete-li například dosáhnout 100násobného zrychlení, musíte paralelizovat 99,99 % celého programu.

Kromě algoritmické paralelizace je pro řešení problému s paralelními větvemi pomocí několika procesních zařízení nezbytná vhodná organizace procesu, která určuje způsoby řešení problému a generuje potřebné informace o připravenosti každé větve. To vše je však poměrně snadno realizovatelné, když je doba provádění každé větve známa poměrně přesně. V praxi se to stává velmi zřídka: v nejlepším případě existuje jeden nebo druhý dočasný odhad. Proto je organizace optimálního nebo téměř optimálního pracovního plánu poměrně obtížným úkolem.

Je třeba také poznamenat, že existují určité potíže spojené s izolací nezávislých větví při vývoji programů. Přitom při řešení mnoha složitých problémů může pouze programování s výběrem nezávislých větví výrazně zkrátit dobu řešení. Obzvláště problémy maticové algebry, lineárního programování, spektrálního zpracování signálu, přímé a inverzní Fourierovy transformace atd. jsou vhodné pro paralelní zpracování tohoto typu.

Jednoduché výpočty ukazují, že konfigurace takových systémů mohou stát více než jeden milion amerických dolarů – jen pro zajímavost zjistěte, kolik stojí řekněme pouhé 4 TB RAM? Vyvstává řada přirozených otázek: Jaké úkoly jsou tak důležité, že vyžadují počítače v hodnotě mnoha milionů dolarů? Nebo jaké úkoly jsou tak složité, že dobré Pentium nestačí? Na tyto a podobné otázky bych rád našel rozumné odpovědi.

Abychom mohli posoudit složitost řešených problémů v praxi, vezměme si konkrétní oblast, například optimalizaci procesu výroby ropy. Máme podzemní zásobník ropy s určitým počtem vrtaných vrtů: jeden čerpá ropu na povrch a druhý vodu zpět. Pro odhad zásob ropy nebo pochopení potřeby dalších vrtů je nutné simulovat situaci v dané nádrži.

Přijmeme zjednodušené schéma, ve kterém je modelovaná oblast mapována do krychle, postačí však odhadnout počet nutných aritmetických operací. Rozumné velikosti kostek, při kterých lze získat věrohodné výsledky, jsou 100*100*100 bodů. V každém bodě krychle je nutné vypočítat od 5 do 20 funkcí: tři složky rychlost, tlak, teplota, koncentrace složek (voda, plyn a olej - to je minimální sada složek; u realističtějších modelů například jsou uvažovány různé frakce ropy). Dále se hodnoty funkcí zjišťují řešením nelineárních rovnic, což vyžaduje 200 až 1000 aritmetických operací. A konečně, pokud se studuje nestacionární proces, tzn. musíte pochopit, jak se tento systém chová v čase, pak se provede 100-1000 časových kroků. Co se stalo:

10 6 (body mřížky)*10(funkce)*500(operace)*500(časové kroky) = 2,5*10 12

2500 miliard aritmetické operace k provedení pouze jednoho výpočtu! A co změna parametrů modelu? Jak je to se sledováním aktuální situace při změně vstupních dat? Takové výpočty je nutné provádět mnohokrát, což klade velmi přísné požadavky na výkon používaných výpočetních systémů.

Příklady využití superpočítačů najdeme nejen v ropném průmyslu. Zde je jen malý výčet oblastí lidské činnosti, kde je použití superpočítačů opravdu nutné:

automobilový průmysl
produkce ropy a plynu
farmakologie
předpovídání počasí a modelování klimatických změn
seismický průzkum
design elektronických zařízení
syntéza nových materiálů
a mnoho, mnoho dalších

V roce 1995 byla karoserie Nissanu Maxima vyrobena o 10 % pevnější díky použití superpočítače Cray (The Atlanta Journal, 28. května 1995). S jeho pomocí byla nalezena nejen slabá místa těla, ale také nejúčinnější způsob, jak je odstranit.

Podle Marka Millera (Ford Motor Company) by Ford k provedení nárazových testů, při nichž skutečná auta narážejí do betonové zdi a současně změřil potřebné parametry, natáčel a následně zpracoval výsledky, potřeboval od 10 do 150 prototypů nových modelů s celkové náklady se pohybují od 4 milionů dolarů do 60 milionů dolarů. Použití superpočítačů snížilo počet prototypů o jednu třetinu.

Zcela nedávným příkladem je vývoj jednoho z největších světových rezervačních systémů Amadeus, který využívají tisíce agentur se 180 000 terminály ve více než stovce zemí. Instalace dvou serverů Hewlett-Packard T600 po 12 procesorech umožnila zvýšit provozní dostupnost centrálního systému na 99,85 % při současném zatížení cca 60 milionů požadavků denně.

A podobné příklady lze najít všude. Výzkumníci DuPont svého času hledali náhradu za chlorfluoruhlovodíky. Bylo nutné najít materiál, který by měl stejné pozitivní vlastnosti: nehořlavost, odolnost proti korozi a nízkou toxicitu, ale bez škodlivých účinků na ozonovou vrstvu Země. Během jednoho týdne byly na superpočítači provedeny potřebné výpočty s celkovými náklady asi 5 tisíc dolarů. Využití tradičních experimentálních výzkumných metod by si podle odborníků z DuPontu vyžádalo zhruba tři měsíce a 50 tisíc dolarů, a to nezohledňuje čas potřebný k syntéze a čištění potřebného množství látky.

Zvýšení výkonu počítače kvůli čemu?

Proč superpočítače počítají tak rychle? Možností odpovědi může být několik, z nichž dvě mají jasnou výhodu: vývoj základny prvků a použití nových řešení v architektuře počítače.

Pokusme se přijít na to, který z těchto faktorů je rozhodující pro dosažení rekordního výkonu. Vraťme se ke známým historickým faktům. Na jednom z prvních počítačů na světě - EDSAC, který se objevil v roce 1949 v Cambridge a měl čas 2 mikrosekundy (2 * 10-6 sekund), bylo možné provést 2 * n aritmetických operací za 18 * n milisekund , tedy v průměru 100 aritmetických operací za sekundu. Srovnejme s jedním výpočetním uzlem moderního superpočítače Hewlett-Packard V2600: čas hodin je přibližně 1,8 nanosekundy (1,8 * 10-9 sekund) a špičkový výkon je asi 77 miliard aritmetických operací za sekundu.

Co se stalo? Za půl století se výkon počítačů zvýšil o více než sedm set milionů jednou. Přitom nárůst výkonu spojený se zkrácením doby taktu ze 2 mikrosekund na 1,8 nanosekund je pouze asi 1000krát. Kde se vzal zbytek? Odpověď je zřejmá – využití nových řešení v počítačové architektuře. Hlavní místo mezi nimi zaujímá princip paralelního zpracování dat, který ztělesňuje myšlenku současného (paralelního) provádění několika akcí.

Paralelní zpracování dat na počítači

Paralelní zpracování dat, ztělesňující myšlenku současného provádění několika akcí, má dvě varianty: potrubí a skutečný paralelismus. Oba typy paralelního zpracování jsou intuitivní, takže si uděláme jen malá vysvětlení.

Mimochodem, průkopníkem v paralelním zpracování datových toků byl akademik A.A. Samarsky, který provedl výpočty nutné k simulaci jaderných výbuchů na počátku 50. Samarsky tento problém vyřešil usazením několika desítek mladých dam se sčítacími stroji ke stolům. Slečny si mezi sebou předávaly data jednoduše slovy a na sčítacích strojích zapisovaly potřebná čísla. Tak byl zejména vypočítán vývoj tlakové vlny. Bylo hodně práce, slečny byly unavené a Alexander Andrejevič mezi ně chodil a povzbuzoval je. Dalo by se říci, že to byl první paralelní systém. Přestože výpočty pro vodíkovou bombu byly provedeny mistrně, jejich přesnost byla velmi nízká, protože v použité mřížce bylo málo uzlů a doba výpočtu byla příliš dlouhá.

Zdálo by se, že zpracování potrubí lze úspěšně nahradit obyčejným paralelismem, pro který duplikujeme hlavní zařízení tolikrát, kolik stupňů potrubí má být přiděleno. Ve skutečnosti pět zařízení v předchozím příkladu zpracuje 100 párů argumentů za 100 jednotek času, což je rychlejší než doba běhu potrubního zařízení! Co se děje? Odpověď je jednoduchá: pětinásobným zvýšením počtu zařízení výrazně zvýšíme jak objem zařízení, tak i jeho cenu. Představte si, že by se automobilka rozhodla odstranit montážní linku při zachování rychlosti výroby automobilů. Pokud dříve bylo na montážní lince tisíc vozů současně, pak je analogicky s předchozím příkladem nutné naverbovat tisíc týmů, z nichž každý (1) je schopen kompletně sestavit vůz od začátku. dokončit provedením stovek různých typů operací a (2) to udělat ve stejnou dobu, kdy bylo auto předtím na montážní lince. Dokážete si představit cenu takového auta? Ne? Souhlasím, je to těžké, až na to, že mě napadá Lamborghini, ale proto vzniklo zpracování na montážní lince...

Stručná historie vzniku paralelismu v počítačové architektuře

Paralelismus v počítačové architektuře dnes překvapí málokoho. Všechny moderní mikroprocesory, ať už je to Pentium III nebo PA-8700, MIPS R14000, E2K nebo Power3, používají ten či onen typ paralelního zpracování. V jádře Pentium 4 lze současně provádět až 126 mikrooperací v různých fázích provádění. Na prezentacích nových čipů a v tiskových zprávách korporací je to prezentováno jako nejnovější slovo v technologii a špičce ve vědě, a to skutečně platí, pokud vezmeme v úvahu implementaci těchto principů v miniaturních hranicích jednoho čipu. .

Tyto myšlenky se přitom samy objevily již velmi dávno. Zpočátku byly implementovány v nejvyspělejších, a tedy jednotlivých počítačích své doby. Poté, po patřičném vývoji technologie a levnější výrobě, se sestoupilo k počítačům střední třídy a dnes je to vše plně vtěleno do pracovních stanic a osobních počítačů.

Abychom se ujistili, že všechny hlavní novinky v architektuře moderních procesorů jsou skutečně využívány již od dob, kdy neexistovaly ani mikroprocesory, ani koncept superpočítačů, udělejme si krátký exkurz do historie, počínaje téměř od zrodu prvních počítačů .

IBM 701 (1953), IBM 704 (1955): bit-paralelní paměť, bit-paralelní aritmetika.
Všechny úplně první počítače (EDSAC, EDVAC, UNIVAC) disponovaly bitově sekvenční pamětí, ze které se slova četla postupně bit po bitu. Prvním komerčně dostupným počítačem využívajícím bit-paralelní paměť (na CRT) a bit-paralelní aritmetiku byl IBM 701 a nejoblíbenějším modelem byl IBM 704 (150 prodaných kopií), který byl kromě výše uvedených i prvním použít feritová jádra a hardwarový zesilovač s pohyblivou řádovou čárkou.

IBM 709 (1958): nezávislé I/O procesory.
Procesory prvních počítačů si vstup/výstup řídily samy. Rychlost nejrychlejšího externího zařízení, kterým v té době byla magnetická páska, však byla 1000krát nižší než rychlost procesoru, takže procesor byl během I/O operací v podstatě nečinný. V roce 1958 K počítači IBM 704 bylo připojeno 6 nezávislých vstupně/výstupních procesorů, které po obdržení příkazů mohly pracovat paralelně s hlavním procesorem a samotný počítač byl přejmenován na IBM 709. Tento model se ukázal jako překvapivě úspěšný, protože cca 400 kopie se prodávaly i s úpravami, poslední byla vypnuta v roce 1975 - 20 let existence!

IBM STRETCH (1961): předvídání, stripování paměti.
V roce 1956 IBM podepisuje smlouvu s Los Alamos Scientific Laboratory na vývoj počítače STRETCH, který má dvě zásadně důležité funkce: předvídání pro načítání instrukcí a prokládání paměti do dvou bank, aby vyhovovaly nízké rychlosti načítání paměti a rychlosti provádění.

ATLAS (1963): příkazový kanál.
Princip dopravníku pro provádění příkazů byl poprvé použit ve stroji ATLAS vyvinutém na univerzitě v Manchesteru. Provádění příkazu je rozděleno do 4 fází: načtení instrukce, výpočet adresy operandu, načtení operandu a provedení operace. Pipelining umožnil zkrátit dobu provádění příkazu z 6 μs na 1,6 μs. Tento počítač měl obrovský dopad jak na architekturu počítače, tak na software: jako první používal víceprogramový OS založený na využití virtuální paměti a systému přerušení.

CDC 6600 (1964): nezávislá funkční zařízení.
Control Data Corporation (CDC) s přímou účastí jednoho ze svých zakladatelů, Seymoura R. Craye, vyrábí počítač CDC-6600 - první počítač, který používal několik nezávislých funkčních jednotek. Pro srovnání s dneškem uvádíme některé parametry počítače:

čas hodin 100ns,
výkon 2-3 miliony operací za sekundu,
RAM je rozdělena do 32 bank po 4096 60bitových slovech,
paměťový cyklus 1µs,
10 nezávislých funkčních jednotek.

Stroj zaznamenal obrovský úspěch na vědeckém trhu a aktivně vytlačil stroje od IBM.

CDC 7600 (1969): funkční zařízení nezávislá na dopravníku.
CDC uvádí na trh počítač CDC-7600 s osmi nezávislými zřetězenými funkčními jednotkami – kombinací paralelního a zřetězeného zpracování. Hlavní parametry:

hodiny 27,5 ns,
10-15 milionů operací/s,
8 dopravníkových jednotek,
2-úrovňová paměť.

ILLIAC IV (1974): maticové procesory.

Projekt: 256 procesorových prvků (PE) = 4 kvadranty 64PE, rekonfigurovatelnost: 2 kvadranty 128PE nebo 1 kvadrant 256PE, takt 40ns, výkon 1Gflop;

práce začaly v roce 1967, do konce roku 1971 byl vyroben systém 1 kvadrantu, v roce 1974. byla uvedena do provozu, dolaďování probíhalo do roku 1975;

centrální část: řídicí jednotka (CU) + matice 64 PE;

Řídicí jednotka je jednoduchý počítač s nízkým výkonem, který řídí matici PE; všechny matice PE pracovaly v synchronním režimu a v každém okamžiku prováděly stejný příkaz přijatý z řídicí jednotky, ale na svých vlastních datech;
PE měl vlastní ALU s plnou sadou instrukcí, OP - 2Kwords 64 bitů, paměťový cyklus 350ns, každý PE měl přímý přístup pouze ke svému OP;
síť pro předávání dat: dvourozměrný torus s horizontálním posunem o 1 podél hranice;

Navzdory výsledku ve srovnání s projektem: náklady jsou 4x vyšší, je vyroben pouze 1 kvadrant, takt je 80ns, reálný výkon je až 50Mflop - tento projekt měl obrovský dopad na architekturu následných strojů postavených na podobný princip, zejména: PEPE, BSP, ICL DAP.

Hierarchie paměti.
Hierarchie paměti přímo nesouvisí s paralelismem, ale rozhodně se týká těch vlastností architektury počítačů, které mají velký význam pro zvýšení jejich výkonu (vyhlazení rozdílu mezi rychlostí procesoru a dobou přístupu do paměti). Hlavní úrovně: registry, cache paměť, RAM, disková paměť. Doba vzorkování pro úrovně paměti z diskové paměti do registrů se snižuje, cena za 1 slovo (bajt) se zvyšuje. V současné době je taková hierarchie podporována i na osobních počítačích.

Co se nyní ve světě používá?

Jakými směry se v současnosti ubírá vývoj výkonné výpočetní techniky? Existují čtyři hlavní směry.

Předpokládejme, že ve vašem programu je zlomek operací, které je třeba provést postupně, f, kde 0

Pokud je 9/10 programu prováděno paralelně a 1/10 je stále sekvenční, pak je v zásadě nemožné dosáhnout zrychlení více než 10krát, bez ohledu na kvalitu implementace paralelní části kódu a počet použitých procesorů (je zřejmé, že 10 se získá pouze v případě, kdy je doba provádění paralelní části 0).

Podívejme se na problém z druhé strany: jakou část kódu je potřeba zrychlit (a tedy předběžně prozkoumat), abychom získali zadané zrychlení? Odpověď lze nalézt v důsledku Amdahlova zákona: za účelem urychlení provádění programu v q krát je nutné zrychlit ne méně než q krát ne méně než (1-1/ q) část programu. Pokud tedy chcete zrychlit program 100x oproti jeho sekvenční verzi, pak potřebujete neméně zrychlit alespoň na 99,99 % kódu, který téměř vždy tvoří významnou část programu!

Z toho plyne první závěr - před důkladným přepracováním kódu pro přechod na paralelní počítač (a každý superpočítač je takový zvláště), musíte pečlivě přemýšlet. Pokud jste po posouzení algoritmu zabudovaného v programu zjistili, že podíl sekvenčních operací je velký, pak zjevně nemůžete počítat s výrazným zrychlením a musíte přemýšlet o nahrazení jednotlivých komponent algoritmu.

V některých případech není sekvenční charakter algoritmu tak obtížné změnit. Řekněme, že program má následující fragment pro výpočet součtu n čísel:

S = 0 Do i = 1, n s = s + a(i) EndDo (totéž lze provést v jakémkoli jiném jazyce)

Svou povahou je přísně sekvenční, protože při i-té iteraci cyklu je vyžadován výsledek z (i-1)té a všechny iterace se provádějí jedna po druhé. Máme 100% sekvenční operace, což znamená, že používání paralelních počítačů nemá žádný efekt. Přitom cesta ven je zřejmá. Protože ve většině reálných programů (otázka: proč ve většině a ne ve všech?) není podstatný rozdíl v tom, v jakém pořadí se čísla sčítají, zvolíme jiné schéma sčítání. Nejprve najdeme součet dvojic sousedních prvků: a(1)+a(2), a(3)+a(4), a(5)+a(6) atd. Všimněte si, že s tímto schématem lze všechny páry přidat současně! V dalších krocích budeme postupovat přesně stejným způsobem a získáme verzi paralelního algoritmu.

Zdálo by se, že v tomto případě byly všechny problémy vyřešeny. Představte si ale, že procesory, které máte k dispozici, jsou ve svém výkonu heterogenní. To znamená, že nastane okamžik, kdy někteří z nich stále pracují, zatímco jiní již vše udělali a zbytečně čekají. Pokud je rozptyl ve výkonu počítače velký, pak bude účinnost celého systému při rovnoměrném zatížení procesoru extrémně nízká.

Ale pojďme dále a předpokládejme, že všechny procesory jsou stejné. Jsou problémy pryč? Znovu ne! Procesory dokončily svou práci, ale výsledek musí být přenesen do jiného, aby mohl pokračovat v procesu sčítání... a přenos nějakou dobu trvá... a v tuto chvíli jsou procesory opět nečinné...

Jedním slovem, zajistit, aby paralelní výpočetní systém nebo superpočítač pracoval s maximální účinností na konkrétním programu, není, upřímně řečeno, snadný úkol, protože je nutné pečlivě koordinovat strukturu programů a algoritmů s vlastnostmi architektury paralelního výpočetní systémy.

Závěrečná otázka. Je podle vás pravdivé tvrzení: čím výkonnější počítač, tím rychleji dokáže vyřešit daný problém?

Konečná odpověď. Ne, to není pravda. To lze vysvětlit jednoduchým každodenním příkladem. Když jeden bagrista vykope jámu 1m*1m*1m za 1 hodinu, tak dva podobní bagristi to udělají za 30 minut - můžete tomu věřit. Jak dlouho bude trvat 60 kopáčů, aby tuto práci provedli? Za 1 minutu? Samozřejmě že ne! Počínaje určitým bodem se budou jednoduše vzájemně zasahovat, nezrychlují, ale zpomalují proces. V počítačích je to stejné: pokud je úkol příliš malý, strávíme více času distribucí práce, synchronizací procesů, sestavováním výsledků atd., než přímo užitečnou prací.

Je naprosto jasné, že ne všechno je tak jednoduché...

Laboratoř paralelních informačních technologií, Výzkumné výpočetní centrum MSU

Paralelní zpracování

Paralelní zpracování je model pro současné provádění aplikačního procesu skupinou procesorů. Existují tři způsoby, jak implementovat paralelismus:
-1- SIMD metoda práce s jedním příkazovým tokem a několika datovými toky, ve které všechny procesory pracující pod stejným programem zpracovávají svá vlastní datová pole pod kontrolou hlavního procesoru;
-2- MIMD metoda práce s více příkazovými toky a vícenásobnými datovými toky, při které procesory pracují podle svých programů nezávisle na sobě, jen občas spolu komunikují;
-3- MISD způsob práce s více příkazovými toky a jedním datovým tokem.

V angličtině: Paralelní zpracování

Finam Financial Dictionary.

Podívejte se, co je „Paralelní zpracování“ v jiných slovnících:

Paralelní zpracování- Jeden z typů zpracování informací, kdy lze provádět několik operací současně. Na rozdíl od vědomého zpracování, které obvykle probíhá postupně, tento typ zpracování probíhá bez vědomého úsilí. Například čtení těchto ... ...

- (paralelní zpracování) Způsob práce na počítači, ve kterém se dvě nebo více částí programu neprovádějí postupně, ale paralelně. Přísně vzato lze tuto metodu použít pouze na počítačích, které mají dvě nebo více... Slovník obchodních podmínek

paralelní zpracování- - Tematika telekomunikací, základní pojmy EN paralelní zpracování...

paralelní zpracování- lygiagretusis apdorojimas statusas T sritis automatika atitikmenys: angl. paralelní zpracování vok. Parallelverarbeitung rus. paralelní zpracování, f pranc. traitement en parallèle, m … Automatikos terminų žodynas

paralelní zpracování informací- model zpracování informací v mozku, podle kterého informace procházejí řadou transformací v určitých „funkčních blocích“ mozku tak, že jsou v každém okamžiku zpracovány současně (paralelně) v několika... ... Skvělá psychologická encyklopedie

PARALELNÍ ZPRACOVÁNÍ INFORMACÍ- Viz zpracování informací, paralelní...

Metoda pro paralelní zpracování dat velkým počtem procesorů implementující metodu MIMD organizace paralelismu. V angličtině: Massively Parallel Processing Anglická synonyma: MPP Viz také: Paralelní zpracování Financial Dictionary Finam... Finanční slovník

ZPRACOVÁNÍ, PARALELNÍ- Zpracování informací, při kterém se současně nebo paralelně provádí více než jedna sekvence operací zpracování. Zpracování může zahrnovat extrémně nízké úrovně, nesymbolické komponenty, jako jsou ty, které se používají v... ... Výkladový slovník psychologie

paralelní potrubí- lygiagretusis konvejerinis apdorojimas statusas T sritis radioelektronika atitikmenys: engl. paralelní potrubí vok. Parallel Pipelineverarbeitung, fr rus. paralelní potrubí, f pranc. traitement de pipeline parallèle, m... Radioelektronikos terminų žodynas

simultánní zpracování- paralelní zpracování - [L.G. Anglicko-ruský slovník informačních technologií. M.: State Enterprise TsNIIS, 2003.] Témata informační technologie obecně Synonyma paralelní zpracování EN simultánní zpracování ... Technická příručka překladatele

knihy

Paralelní zpracování dat
Paralelní zpracování dat, A. O. Latsis. Tutoriál poskytuje hloubkový systematický přehled technologií paralelního zpracování dat. Hlavní pozornost je věnována tradičním softwarovým technologiím paralelního programování...

Oblíbené v kategorii: