Sekvenční a paralelní zpracování informací. Typy paralelního zpracování informací

Paralelní zpracování dat

Informatika, kybernetika a programování

Automatická detekce souběžnosti. Stupeň a úrovně paralelismu. Typy paralelismu. Výkon paralelního VS závisí na mnoha faktorech a do značné míry na architektuře a struktuře systému nakreslete strukturu paralelního systému a vysvětlete: na stupni a úrovni paralelismu v systému; z organizace přenosu dat mezi paralelními procesory; ze spínacího systému; z interakce procesorů a paměti; o vztahu mezi hardwarem a implementace softwaru makro operace.

Přednáška 1

Paralelní zpracování dat

Plán

1. Tierparalelní forma algoritmu.

2. Automatická detekce paralelismu.

3. Stupeň a úrovně rovnoběžnosti.

4. Typy rovnoběžnosti.

Rovnoběžnost to je schopnost současně provádět několik aritmetických, logických nebo servisních operací. Navíc operace mohou být jak velkoblokové, tak maloblokové.

Výkon paralelních WAN závisí na mnoha faktorech a do značné míry na architektuře a struktuře systému.(nakreslete strukturu paralelního systému a vysvětlete):

Od stupně a úrovně paralelismu v systému;

Od organizace přenosu dat mezi paralelními procesory;

Ze spínacího systému;

Z interakce procesorů a paměti;

Ze vztahu mezi hardwarovou a softwarovou implementací makrooperace.

Paralelní zpracování může být založeno na různých principech:

Prostorový paralelismus;

Časová rovnoběžnost:

1. Potrubí.
2. Vektorizace.
3. Matice.
4. Systolický.
5. Organizace struktury zpracování datového toku.
6. Organizace systému na základě struktury hyperkrychle.
7. Dynamická restrukturalizace letadla.

Popis každého algoritmu je hierarchický na základě vlastnosti vnoření. Při programování alokujteúrovně vnoření:úkoly, úkoly, dílčí úkoly (procesy), makrooperace, operace.Nesting určuje hloubku paralelizace a je jednou z důležitých vlastností algoritmů při analýze paralelních výpočetních modelů.

1. Tierparalelní forma algoritmu

Nejobecnější formou reprezentace algoritmů je informační-kontrolní graf algoritmu,který odráží datovou závislost mezi příkazy algoritmu a nepodmíněnými a podmíněnými skoky v programu. Takový graf implicitně obsahuje všechny typy paralelismu pro zvolený způsob řešení úlohy.Specifičtější formou reprezentace paralelismu úloh je aparát vrstvené paralelní formy (LPF).

Algoritmus v stupňovitě paralelní formaje reprezentován ve formě vrstev a nulová vrstva zahrnuje na sobě nezávislé operátory (větve).

Graf lze označit přechody , což znamená přenos výsledků výpočtu primitivní operace z jedné vrstvy do operace z další vrstvy. Úrovně jsou rozděleny přechody. Může být"prázdné" přechody A „prázdné“ primitivní operace. Prázdná operace odpovídá uložení výsledku získaného v předchozí vrstvě. V sekvenčním řetězci aktivit může být prázdná aktivita umístěna do libovolné úrovně.

Při konstrukci JPF spoléhají na základní sada primitivní operace (PNO). Víceúrovňová paralelní forma se vyznačuje následujícím parametry:

1. Délka počítání (počet vrstev) L.

2. Šířka i-tého patra - b i.

3. Šířka grafu víceúrovňové paralelní formy B = max (bi).

4. Průměrná šířka grafu JPF St .

5. Faktor plnění i -tý stupeň k i .

6. Koeficient rozptylu operací v grafu - Q j i , j BNO , kde je počet j -tý typ operací v i-tá úroveň.

7. Minimální požadovaný počet kalkulaček (od BNO) pro implementaci algoritmu reprezentovaného tímto grafem v JPF.

8. Minimální doba řešení algoritmu (součet dob ​​odezvy kalkulátorů s maximálním počtem výpočtů pro každou vrstvu) Tmin.

9. Konektivita algoritmu (počet mezivýsledků, které musí být uloženy během implementace algoritmu) S .

2. Automatická detekce souběžnosti

Existují dva způsoby, jak vytvořit paralelní algoritmus: přímo z příkazu problému nebo transformací sekvenčního algoritmu.

Metody sestavení paralelního algoritmu ze sekvenčního jsou založeny na výběru typických často se vyskytujících konstrukcí v sekvenčním algoritmu, které jsou podle určitých pravidel nahrazeny paralelními. (To umožňuje do určité míry zvýšit stupeň paralelismu ztraceného algoritmem při programování v sekvenčním jazyce.)

Charakter změny míry paralelismu při přípravě počítačového programu je znázorněn na Obr. 2.2.

potenciální paralelismus

Metoda

řešení

Původní text

Strojový program

Rýže. 2.2. Změna potenciálního paralelismu během vývoje programu:

1 paralelní programovací systém;

2 sekvenční programování a

vektorizační kompilátor

I přes nižší úroveň paralelismu dosaženého při konstrukci paralelního algoritmu převodem ze sériového je tato metoda široce používána, protože umožňuje použít drahé aplikační programy vyvinuté a odladěné pro sériové DOD.

V sekvenčním programu existují zjevné i skryté paralelní zpracování.

Při analýze programu je sestaven graf toku dat. Pro detekci explicitního paralelismu procesů jsou analyzovány sady vstupních (čtených) proměnných R a výstupní (zaznamenatelné) proměnné W každý proces.

Explicitní mezi procesy lze detekovat paralelní zpracování i a j (i ≠ j ) splňující následující podmínky:

vstup z jednoho procesu nesmí být modifikován (zapsán) ​​jiným procesem

žádné dva procesy by neměly měnit sdílené proměnné

a) RjWj=;

b) WjRj=;

c) WjWj=;

Skrytý paralelní zpracování vyžaduje určitý druh transformační procedury pro sériový program, aby jej bylo možné provádět paralelně. Transformace může být následující:

a) snížení výšky stromů aritmetických výrazů (obr. 2.3). Pro aritmetické výrazy s n proměnné nebo konstanty, snížení výšky stromu umožňuje dosáhnout rychlejšího zpracování objednávky O(n/log2n ) použitím O(n) procesory;

b) transformace lineárních rekurentních vztahů;

((a + b) + c) + d

(a + b) + (c + d)

Rýže. 2.3. Snížení výšky stromu

c) výměna operátorů;

d) transformace bloků podmíněných přechodů a cyklů do kanonické formy;

e) rozdělení cyklů.

Paralelní architektury dosah vysoký výkon, pokud transformace paralelismu bere v úvahu zvláštnosti architektury letadla, na kterém má být algoritmus proveden.

Při převodu paralelismu programy berou v úvahu: 1) rozložení dat v paměti; 2) adresování paměti (indexování); 3) volba datové trasy (způsob připojení procesorů a paměti).

Obr.2.4. Úložný prostor

posunové matice

Jako příklad uvažování rozložení v paměti si vezměme paměť s diagonálním adresováním. Pro zajištění paralelního zpracování matic musí být prvky jejich řádků a sloupců rozděleny mezi paměťová zařízení procesorů tak, aby je bylo možné číst a zpracovávat současně. V tomto případě je matice uložena s posunem (obr. 2.4).

Každý algoritmus obsahuje po sobě jdoucí (skalární) sekce. Je prokázáno, že délka těchto skalárních segmentů je určujícím faktorem při implementaci algoritmu na paralelním letadle.

3. Stupeň a úrovně rovnoběžnosti

Stupeň rovnoběžnosti(D) je pořadí počtu paralelních zařízení v systému při implementaci algoritmu úlohy za předpokladu, že počet procesorů (procesorů) není omezen.(Existuje další definicestupně rovnoběžnostije počet procesorů víceprocesorového systému podílejících se na provádění programu paralelně v každém okamžiku t.)

1) Nízký stupeň: 2 až 10 procesorů.

2) Střední stupeň: 10 až 100 procesorů.

3) Vysoký stupeň: 100 až 10 4 procesory.

4) Super vysoký stupeň: od 10 4 až 106 procesorů.

Rýže. 2.5. Profil souběžnosti

Grafické znázornění parametru D(t ), jak se nazývají funkce časuprofil souběžnosti programu. Změny ve vytížení procesoru během doby pozorování závisí na mnoha faktorech (algoritmus, dostupné zdroje, stupeň optimalizace poskytovaný kompilátorem atd.). Na Obr. Obrázek 2.5 ukazuje typický profil souběžnosti.

V aplikační programy existuje široká škála potenciálního paralelismu. Ve výpočetně náročných programech lze v každém cyklu paralelně spustit 500 až 3500 aritmetické operace pokud k tomu existuje existující výpočetní prostředí. Nicméně i správně navržený superskalární procesor je schopen podporovat 2 až 5,8 instrukcí za cyklus. Tento pokles je způsoben především komunikačními a systémovými náklady.

Míra paralelismu výrazně ovlivňuje: architekturu letadla, zejména přepínací systém, organizaci interakce mezi procesory pracujícími paralelně a způsoby výměny dat mezi procesory a pamětí. Silnější vliv na výkon výpočetních prostředků než stupeň paralelismu má úroveň paralelismu.

Zvážit algoritmický a schematický úrovně paralelismu.

Existují následujícíalgoritmické úrovně paralelismu:

1. Pracovní úroveň:

a) mezi úkoly;

b) mezi fázemi úkolu.

2. Úroveň programu:

a) mezi částmi programu(části jednoho úkolu se provádějí na sadě kalkulaček);

b) v rámci cyklů.

(Pokud jednotlivé iterace v cyklu na sobě nezávisí. Např : Pro I:=1 až N do A(I):=B(I) + C(I))

3. Úroveň příkazu:

a) mezi fázemi provádění příkazu.

4. Aritmetická a číslicová úroveň:

a) mezi prvky vektorové operace;

b) uvnitř logické obvody ALU.

Každá z úrovní se vyznačuje určitými vlastnostmi, na jejichž základě byly vyvinuty speciální struktury výpočetních zařízení. Příkazová úroveň je implementována v libovolném moderní počítače včetně osobních počítačů.

Úroveň paralelismu schématutoto je úroveň hardwaru, na které je paralelizováno zpracování dat nebo je organizováno paralelní zpracování.

Paralelní zpracování lze implementovat na následujících úrovních obvodů:

1. Na úrovni logických hradel a paměťových prvků.Tento nejnižší stupeňúroveň tranzistoru. Zde jsou paralelní logické obvody sestaveny z logických hradel ( LS ) (například: paralelní sčítačka).

2. Úroveň logických obvodů a jednoduchých automatů s pamětí.Paralelní elementární automat je sestaven z logických obvodů ( EA).

3. úroveň registru a integrované obvody Paměť.Na elementárních automatech se získávají paralelní mikroprocesorové obvody ( MP).

4. Úroveň základních mikroprocesorů.Paralelní makroprocesory jsou sestaveny z mikroprocesorů k provádění operací středního bloku ( MAPA).

5 . Úroveň makroprocesorů, které realizují velké operace.Zde je implementován paralelismus makro operací. Makroprocesory se používají k budování paralelních víceprocesorových systémů ( MPS).

6. Úroveň počítače, procesory a programy.Nejvyšší úroveň paralelismu z víceprocesorových systémů je paralelní výpočetní systémy ( VS).

4. Typy rovnoběžnosti

4.1. Přirozený paralelismus a

souběh mnoha objektů

V informačním grafu lze rozlišit „vertikální“ nezávislé podgrafy, které vzájemně nevyužívají žádné mezivýsledky získané implementací primitivních operací jiného podgrafu. Tento druh paralelismu se nazývá přirozený paralelismus nezávislých úloh.

Úkol má přirozený souběh, pokud je ve své původní formulaci redukován na operaci s vícerozměrnými vektory, vícerozměrnými maticemi nebo mřížkovými funkcemi (obr. 2.6). Mezivýsledky úloh se zde nepoužívají. Každá úloha je naprogramována nezávisle na ostatních. Tento typ paralelismu nevyžaduje integraci počítačů do komplexů. Zvýšení počtu nezávislých úloh v SOD však zvyšuje propustnost systému. Například: zpracování transakcí do DB na víceprocesorových serverech.

1 úkol

2 úkol

Rýže. 2.6. Informační graf úlohy charakterizované přirozeným paralelismem

Nebo já

Nebo já

Nebo já

Nebo já

Ori+1

Ori+1

Ori+1

Ori+1

1

ve 2

3

ve 4

Rýže. 2.7. Informační graf

úkol charakterizován

souběžnost množiny objektů

Paralelismus více objektůpředstavuje speciální případ přirozený paralelismus. Jeho význam je v tom, že úkolem je zpracovávat informace o různých, ale stejného typu objektů, zpracovávaných podle stejného nebo téměř stejného programu (obr. 2.7).

Zde relativně malou váhu zaujímá tzvintegrální operace. Počáteční operandy integrálních operací jsou vektory nebo funkce nebo množiny objektů a výsledkem je číslo. Například výpočet bodového součinu pro n-rozměrné vektory

zahrnuje dva typy operací: párový součin složek vektoru a potom „integrální operaci“ (operace na n-rozměrném vektoru) sčítající všechny složky tohoto vektoru.

Při paralelismu množiny objektů častěji než v obecném případě nastávají situace, kdy samostatné sekce výpočty se musí pro různé objekty provádět odlišně.

Například při hledání hodnot některých funkcí, omezených na určitou oblast. Hodnoty uvnitř oblasti pro všechny body se počítají podle jednoho vzorce a na hraničních bodech podle jiného.

Paralelnost množiny objektů je charakterizována následujícím parametry:

1. Celková délka programu L sečtou se délky všech operátorů ve všech větvích.

2. Průměrná délka programu L srov se vypočítá na základě pořadí úkolu.

Základní kvantitativní charakteristikaúkol, který má být paralelizován, jeúkolová pozice r (®) jedná se o počet parametrů pro paralelní zpracování (například počet složek vektoru, počet bodů, ve kterých je funkce zadána).

3. Hodnota divergence problému D

Pokud je program na zpracování informací pro všechny r objekty jsou tedy úplně stejné D =1 a čím více se od sebe programy různých objektů liší, tím více D.

4.2. Paralelnost nezávislých poboček

podstata souběh nezávislých pobočekspočívá v tom, že v programu pro řešení problému lze rozlišit samostatné části, nazývané větve. Pokud má CS odpovídající hardware, lze větve spouštět paralelně (obr. 2.8).

Programová větev Y nezáleží na pobočce x pokud:

Rýže. 2.8. Informační graf úlohy charakterizované

souběh nezávislých poboček

mezi nimi žádné funkční odkazy, tj. žádná ze vstupních proměnných větve Y není výstupní proměnnou větve X ani žádné větve závislé na X;

1. mezi nemají žádné spojení na pracovních polích paměti;
2. musí být splněnyPodle různé programy ;
3. nezávislý v řízení, tj. podmínka provádění větve Y by neměla záviset na vlastnostech generovaných během provádění větve X nebo větve na ní závislé.

4.3. Paralelnost sousedních provozů popř

lokální paralelismus

Paralelnost sousedních operacíprobíhá, když jsou vstupní data pro aktuální operace získávána v dřívějších fázích výpočtu a konstrukce výpočetních nástrojů umožňuje kombinovat provádění několika operací, které spolu nesouvisí výstupními daty a výsledky.

Lokální paralelismus je charakterizován následujícím parametry:

1. Indikátor konektivity sousedních operacíje pravděpodobnost, že výsledek nějaké operace bude použit v operaci následující. Čím nižší je konektivita operace, tím větší je hloubka paralelismu sousedních operací. Obvykle má hodnota hodnoty 0,10,5.

2. Pravděpodobnost, že počínaje danou operací existuje řetězec délky nejméně l l

3. Pravděpodobnost, že počínaje jakoukoli operací v programu existuje řetězec přesně l operace, které lze provádět současně l

4. Hloubka paralelnosti sousedních operací L PSO je očekávání délky řetězce operací, které lze provádět současně

Lokální optimalizace programů spočívá v tom, že se podíváme na několik instrukcí, které je třeba provést za sebou, a změníme pořadí některých z nich, případně změníme počty registrů a paměťových buněk, abychom zajistili maximální možnou paralelnost sousedních operací.

Ve většině případů index konektivity sousedních operací nezávisí ani tak na problému, jako na kvalitě lokální optimalizace.

________________________________________________________________________________________________

Kurz "Organizace počítačů"

10 -

(projekt kurzu)

"> Přednáška " xml:lang="en-US" lang="en-US">6

">Paralelní zpracování dat

"> Paralelnost je schopnost provádět současně několik aritmetických, logických nebo obslužných operací. Navíc operace mohou být jak velkoblokové, tak maloblokové.

Paralelní zpracování může být založeno na různých principech:

Prostorový paralelismus;

Časová rovnoběžnost:

1. Potrubí.
2. ">Vektorizace.
3. "> Matrix.
4. "> Systolický.
5. "> Organizace struktury zpracování datového toku.
6. "> Organizace systému na základě struktury hyperkrychle.
7. "> Dynamická restrukturalizace letadla.

"> Popis každého algoritmu je hierarchický, založený na vlastnosti vnoření. Při programování se rozlišují úrovně vnoření: úkoly, úkoly, podúlohy (procesy), operace makra, operace.

"> 1. Tierparalelní forma algoritmu

"> Nejobecnější formou znázornění algoritmů je informačně-řídící graf algoritmu, specifičtější formou znázornění paralelnosti úloh je aparát stupňovité paralelní formy (LFP).

"> Algoritmus ve vícevrstvé paralelní formě je reprezentován ve formě vrstev a nulová vrstva zahrnuje na sobě nezávislé operátory (větve).

"> V grafu můžete označit přechody, což znamená přenos výsledků výpočtu primitivní operace z jedné vrstvy do operace z další vrstvy. Vrstvy jsou rozděleny podle přechodů. Mohou existovat „prázdné“ přechody a „prázdné“ primitivní operace.

"> Při konstrukci FNM vycházejí ze základního souboru primitivních operací (BNO).Vrstvaně paralelní forma je charakterizována následujícími parametry:

">1. Délka grafu (počet úrovní)" xml:lang="en-US" lang="en-US">L">.

">2. Šířka " xml:lang="en-US" lang="en-US">i">-tá úroveň - " xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">.

">3. Šířka grafu víceúrovňové paralelní formy" xml:lang="en-US" lang="en-US">B">= " xml:lang="en-US" lang="en-US">max">(" xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">).

">4. Průměrná šířka grafu JPF B;vertical-align:sub">cf "> ">.

">5. Faktor plnění" xml:lang="en-US" lang="en-US">i">té úrovni " xml:lang="en-US" lang="en-US">k;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> – ">.

"> 6. Koeficient rozptylu operací ve sloupci -" xml:lang="en-US" lang="en-US">O;vertical-align:super" xml:lang="en-US" lang="en-US">j;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> – ">, " xml:lang="en-US" lang="en-US">j"> BNO, kde "> - množství " xml:lang="en-US" lang="en-US">j">-tý typ operací v" xml:lang="en-US" lang="en-US">i">-tý stupeň.

"> 7. Minimální požadovaný počet kalkulaček (z BNO) pro implementaci algoritmu reprezentovaného tímto grafem v JPF.

"> 8. Minimální doba pro řešení algoritmu (součet časů odezvy kalkulátorů s maximálním počtem výpočtů pro každou vrstvu) T;vertical-align:sub" xml:lang="en-US" lang="en-US">min">.

"> 9. Konektivita algoritmu (počet mezivýsledků, které musí být uloženy v procesu implementace algoritmu) С.

">2. Automatická detekce souběžnosti

"> Existují dva způsoby, jak vytvořit paralelní algoritmus: přímo z výpisu problému nebo transformací sekvenčního algoritmu.

"> Metody sestavení paralelního algoritmu ze sekvenčního jsou založeny na výběru typických často se vyskytujících konstrukcí v sekvenčním algoritmu, které jsou podle určitých pravidel nahrazeny paralelními.

"> Navzdory nižší úrovni paralelismu dosažené při konstrukci paralelního algoritmu převodem ze sériového algoritmu je tato metoda široce používána, protože poskytuje možnost používat drahé aplikační programy vyvinuté a odladěné pro sériové DOD.

"> V sekvenčním programu se rozlišuje mezi explicitním a implicitním paralelním zpracováním.

"> Při analýze programu je sestaven graf toku dat. K odhalení explicitní paralelnosti procesů jsou analyzovány sady vstupních (čtených) proměnných" xml:lang="en-US" lang="en-US">R"> a výstupní (zapisovatelné) proměnné" xml:lang="en-US" lang="en-US">W"> každého procesu.

">Skryté paralelní zpracování vyžaduje určitý druh transformační procedury pro sériový program, aby jej bylo možné provádět paralelně. Transformace může být následující:

"> a) snížení výšky stromů aritmetických výrazů (obr. 6.3);

"> b) transformace lineárních rekurentních vztahů;

"> c) nahrazení operátorů;

"> d) transformace bloků podmíněných přechodů a cyklů do kanonické formy;

"> e) rozdělení cyklů.

"> Paralelní architektury dosahují vysokého výkonu, pokud transformace paralelismu bere v úvahu zvláštnosti architektury letadla, na kterém má být algoritmus proveden.

"> Jako příklad zohlednění rozložení v paměti si vezměme paměť s diagonálním adresováním Pro zajištění paralelního zpracování matic je třeba prvky jejich řádků a sloupců rozmístit mezi paměťová zařízení procesorů tak, aby lze číst a zpracovávat současně.V tomto případě je matice uložena s posunem (obr.6.4).

"> Libovolný algoritmus obsahuje sekvenční (skalární) sekce. Je prokázáno, že délka těchto skalárních sekcí je určujícím faktorem při implementaci algoritmu na paralelním letadle.

"> 3. Stupeň a úrovně rovnoběžnosti

">Stupeň paralelismu"> (" xml:lang="en-US" lang="en-US">D">) "> toto je pořadí počtu paralelních zařízení v systému při implementaci algoritmu úlohy za předpokladu, že počet procesorů (procesorů) není omezen.

">1) Nízký stupeň: 2 až 10 procesorů.

">2) Průměrný stupeň: od 10 do 100 procesorů.

">3) Vysoký stupeň: 100 až 10;vertical-align:super">4 "> procesory.

"> 4) Super vysoký stupeň: od 10;vertical-align:super">4 "> až 10 ;vertical-align:super">6 "> procesorů.

">Grafické znázornění parametru" xml:lang="en-US" lang="en-US">D">(" xml:lang="en-US" lang="en-US">t">) jako funkce času se nazývá profil paralelismu programu. Obrázek 6.5 ukazuje typický profil paralelismu.

"> V aplikačních programech existuje široká škála potenciálního paralelismu. Ve výpočetně náročných programech lze paralelně provádět 500 až 3500 aritmetických operací v každém cyklu, pokud pro to existuje existující výpočetní prostředí. navržený superskalární procesor je schopen podporovat 2 až 5,8 příkazů za cyklus. Tento pokles je způsoben především náklady na komunikaci a systém.

Silnější vliv na výkon výpočetních prostředků než stupeň paralelismu má úroveň paralelismu.

Zvažte algoritmické a obvodové úrovně paralelismu.

Existují následující algoritmické úrovně paralelismu:

1. Úroveň úkolu:

a) mezi úkoly;

b) mezi fázemi úkolu.

2. Úroveň programu:

a) mezi částmi programu;

b) v rámci cyklů.

3. Úroveň příkazu (mezi fázemi provádění příkazu).

4. Aritmetická a číselná úroveň:

"> a) mezi prvky vektorové operace;

"> b) uvnitř logických obvodů ALU.

"> Každá z úrovní se vyznačuje určitými vlastnostmi, na základě kterých byly vyvinuty speciální struktury výpočetních nástrojů. Příkazová úroveň je implementována v každém moderním počítači, včetně osobních počítačů.

"> Úroveň paralelismu schématu je úroveň hardwaru, na které je paralelizováno zpracování dat nebo je organizováno paralelní zpracování.

">Paralelní zpracování lze implementovat na následujících úrovních obvodů:

"> 1. Na úrovni logických hradel a paměťových prvků (obr. 6.6).

"> 2. Úroveň logických obvodů a jednoduchých automatů s pamětí (obr. 6.7).

"> 3. Úroveň registrů a integrovaných paměťových obvodů (obr. 6.8).

4. Úroveň elementárních mikroprocesorů (obr. 6.9).

"> 5. Úroveň makroprocesorů, které realizují velké operace (obr. 6.10).

6. Úroveň počítačů, procesorů a programů (obr. 6.11).

">4. Typy rovnoběžnosti

"> 4.1 Přirozená rovnoběžnost a

">paralelnost mnoha objektů

V informačním grafu lze rozlišit „vertikální“ nezávislé podgrafy, které vzájemně nevyužívají žádné mezivýsledky získané implementací primitivních operací jiného podgrafu. Tento druh paralelismu se nazývá přirozený paralelismus nezávislých úloh.

Problém má přirozenou paralelitu, pokud je ve své původní formulaci redukován na operaci s vícerozměrnými vektory, vícerozměrnými maticemi nebo mřížkovými funkcemi (obr. 6.12).

Paralelismus množin objektů je speciálním případem přirozeného paralelismu. Jeho smyslem je, že úkolem je zpracovávat informace o různých, ale stejného typu objektů zpracovávaných podle stejného nebo téměř stejného programu (obr. 6.13).

"> Zde zabírají relativně malou váhu tzv. integrální operace. Při rovnoběžnosti množiny objektů častěji než v obecném případě dochází k situacím, kdy se jednotlivé úseky výpočtů musí pro různé objekty provádět odlišně.

">4.2 Paralelnost nezávislých poboček

Podstata paralelismu nezávislých větví spočívá v tom, že v programu lze pro řešení problému alokovat nezávislé části, nazývané větve. Pokud má CS odpovídající hardware, lze větve spouštět paralelně (obr. 6.14).

">Programová větev Y je nezávislá na větvi X, pokud:

">- mezi nimi nejsou žádné funkční vazby, tj. žádná ze vstupních proměnných větve Y není výstupní proměnnou větve X ani žádné větve závislé na X;

"> - není mezi nimi žádná souvislost z hlediska polí pracovní paměti;

">- musí být spouštěny různými programy;

">- jsou nezávislé v ovládání, tj. podmínka pro provedení větve Y by neměla záviset na znacích generovaných během provádění větve X nebo větve, která na ní závisí.

">4.3 Paralelnost sousedních operací popř

">místní paralelismus

Paralelnost sousedních operací nastává, když jsou vstupní data pro aktuální operace získávána v dřívějších fázích výpočtu a konstrukce výpočetních nástrojů umožňuje kombinovat provádění několika operací, které spolu nesouvisí výstupními daty a výsledky.

Lokální optimalizace programů spočívá v tom, že se podíváme na několik instrukcí, které je třeba provést za sebou, a změníme pořadí některých z nich, případně změníme počty registrů a paměťových buněk, abychom zajistili maximální možnou paralelnost sousedních operací.

Ve většině případů index konektivity sousedních operací nezávisí ani tak na problému, jako na kvalitě lokální optimalizace.

">5. Model úlohy

Model úloh je vytvořen pro srovnávací analýza struktury paralelních počítačů. Proto by měl mít dosti obecný charakter a popisovat pouze složení forem paralelismu a typů spojení.

Každý model problému je zpravidla sestaven na základě analýzy modelované třídy problémů. Na základě výsledků analýzy jsou algoritmy transformovány na paralelní pohled. Zkoumaný algoritmus lze reprezentovat jako program skládající se ze sekvence sekcí tří typů (obr. 6.15):

1. skalární řezy (SC);
2. sekce s paralelismem nezávislých větví (BT);
3. vektorové grafy (VC).

Model úlohy je soubor parametrů charakterizujících paralelní program

Při konstrukci modelu úlohy je hlavním cílem určit relativní dobu jejího provedení při implementaci studovaným algoritmem.

"> Obr. 6.15. Poměr celkového počtu výpočtů přiřaditelných různým částem algoritmu v modelu problému

" xml:lang="en-US" lang="en-US">W">ck

" xml:lang="en-US" lang="en-US">Hmot

" xml:lang="en-US" lang="en-US">W">vk

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">sk

" xml:lang="en-US" lang="en-US">m;vertical-align:sub" xml:lang="en-US" lang="en-US">t

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">vk

" xml:lang="en-US" lang="en-US">A

" xml:lang="en-US" lang="en-US">In

" xml:lang="en-US" lang="en-US">C

množství výpočtu

relativní délka

Ministerstvo školství a vědy Ruské federace

Federální státní rozpočtová vzdělávací instituce vyššího odborného vzdělávání „Bryansk State Engineering and Technology

akademie"

Ústav informačních technologií

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

Sídlištní a grafické práce č. 1

disciplínou

"Technologie zpracování informací"

Možnost číslo 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

Jednoduché dávkové systémy 10

Reference 13

Úvod

V tomto výpočtu a grafickém, sekvenčním a paralelním zpracování informací je uvažováno. U každého z nich jsou uvedeny příklady.

Sekvenční zpracování informace je sekvenční přechod informace ze vstupu na výstup řadou transformací (fází), takže v každém časovém intervalu (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 provádění několika akcí současně, má dvě varianty: zřetězené a paralelní.

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 takových nezávislých zařízení, která mohou pracovat současně, pak systém pěti zařízení dokáže provést stejných tisíc operací za ne 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, kteří pracují současně, udělá stejnou práci za 12 minut - princip paralelismu v akci!

Potrubí. Co je potřeba k sečtení dvou reálných čísel reprezentovaných v plovoucí řádové čárce? Celá řada malých operací, jako je porovnání objednávek, zarovnání objednávek, přidání mantisy, normalizace atd. Procesory prvních počítačů prováděly všechny tyto „mikrooperace“ pro každou dvojici argumentů postupně jeden po druhém, 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 vyčlenit samostatné fáze provádění společné operace a každá fáze po dokončení své práce přenese výsledek na další a současně přijme novou část vstupních dat. Díky kombinaci dříve rozmístěných operací získáme zřejmý nárůst rychlosti zpracování. Předpokládejme, že operaci lze rozdělit do pěti 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ů pro 500 jednotek. Pokud je každá mikrooperace rozdělena do samostatné fáze (nebo jinak řečeno - fáze) dopravního zařízení, pak v páté časové jednotce v jiné fázi zpracování takového zařízení bude prvních pět párů argumentů být nalezen a celá sada sto párů bude zpracována za 5 + 99 = 104 jednotek času - zrychlení ve srovnání se sekvenčním zařízením téměř pětinásobné (podle počtu kroků potrubí).

Zdá se, že zpracování potrubí lze úspěšně nahradit běžným paralelismem, pro který by mělo být hlavní zařízení duplikováno tolikrát, kolik má být přidělen počet stupňů potrubí. Pět zařízení z předchozího příkladu skutečně zpracuje 100 párů argumentů za 100 jednotek času, což je rychlejší než potrubní zařízení! Pětinásobným navýšením počtu zařízení tedy výrazně zvyšujeme jak množství zařízení, tak i jeho cenu. Představte si, že se automobilka rozhodla odstranit montážní linku a přitom zachovat tempo 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ý je schopen kompletně sestavit vůz od začátku do konce, provádění stovek různých operací, a to ve stejnou dobu, jakou bylo auto předtím na montážní lince.

Dnes už málokoho překvapí paralelismus v počítačové architektuře. Všechny moderní mikroprocesory používají nějakou formu paralelního zpracování. V jádru Pentium 4 různé fáze provedení může být současně až 126 mikrooperací. Samotné tyto myšlenky se však objevily již velmi dávno. Zpočátku byly zavedeny v nejvyspělejších, a tedy samostatných počítačích své doby. Poté, po řádném rozvoji technologií a levnější výrobě, sestoupily do počítačů střední třídy a nakonec, dnes je to vše plně ztělesněno v pracovních stanicích a osobních počítačích.

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í informací. Následují hlavní koncepty paralelního zpracování a architektura víceprocesorových počítačů.

Když více aplikací požaduje, aby byly jejich úlohy zpracovány na jednoprocesorovém počítači, veškerou práci musí vykonávat tento jediný procesor. Účelem paralelního zpracování je obvykle zlepšení výkonu aplikace. Když aplikace vydá požadavek na úlohu pro víceprocesorový počítač, počítač rozdělí úlohu na logické dílčí úlohy a ty pak zpracuje paralelně pomocí více procesorů, což zkrátí dobu provedení ú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 rychlost systémů s paralelním zpracováním takovým způsobem, aby zajistili maximální výkon každého procesoru v systému.

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

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

Kompilátor programu: Člen korespondent RAS, doktor fyziky a matematiky. Sciences Voevodin Vl.V.,

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

anotace

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

Program

2. Hlavní třídy moderních paralelních výpočetních systémů. Počítače s sdílená paměť, příklady, důvody pro snížení výkonu na skutečné programy. SMP architektury, NUMA, ccNUMA. Spínací procesory a paměťové moduly, sběrnice, maticový přepínač, síť omega. Vektorové dopravníkové výpočetní systémy, příklady, příčiny degradace výkonu. Počítače s distribuovanou pamětí, příklady, příčiny 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 rozličný komunikační technologie. Architektury s paralelismem na úrovni strojových instrukcí, VLIW, superskalární.

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í jazyky. Speciální jazyky paralelní programování. Programování pomocí knihoven a rozhraní pro předávání zpráv. Paralelní oborové knihovny, specializované balíčky a softwarové systémy vysoká úroveň. 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. Test Linpack a jeho varianty. Sady komplementárních testovací programy, STREAM a NPB.

5. Grafové modely programů. Kontrolní graf a graf informací o programu. Informace a provozní historie implementace 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 hromadná rovnoběžnost, souřadnicová a šikmá rovnoběžnost. Ekvivalentní transformace programů, elementární transformace cykly.

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

Literatura

2. Koroljov L.N. Architektura procesorů elektronických počítačů. – M.: Ed. fakulty VMK MGU, 2003.

3. V. V. Kornějev. Paralelní výpočetní systémy. - M.: Nakladatelství "Znalosti", 1999. - 320s.

4. Materiály Informačního a analytického centra pro paralelní počítání Parallel.ru

doplňková literatura

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

Způsoby, jak zlepšit výkon letadla, jsou zakotveny v jeho architektuře. Jednak se jedná o sadu procesorů, paměťových bloků, vstupních/výstupních zařízení a samozřejmě způsobů jejich připojení, tzn. komunikační prostředí. Na druhou stranu jsou to skutečné akce letadla k vyřešení určitého problému, a to jsou operace na příkazy a data. To je vlastně celý základní základ pro paralelní zpracování. Paralelní zpracování, ztělesňující myšlenku provádění několika akcí současně, má několik druhů: superskalární, potrubí,SIMD- rozšíření,Hyper závitování, vícejádrový. V zásadě jsou tyto typy paralelního zpracování intuitivní, takže uděláme jen malé vysvětlení. 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 takových nezávislých zařízení, která mohou pracovat současně, pak stejných tisíc operací může systém pěti zařízení provést 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, kteří pracují současně, udělá stejnou práci za 12 minut (paralelní zpracování dat), a to i s písně (paralelní zpracování příkazů).

Potrubí . Co je potřeba k sečtení dvou reálných čísel reprezentovaných v plovoucí řádové čárce? Celá řada malých operací, jako je porovnání objednávek, zarovnání objednávek, přidání mantisy, normalizace atd. Procesory prvních počítačů prováděly všechny tyto „mikrooperace“ pro každou dvojici argumentů postupně jeden po druhém, 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 vyčlenit samostatné fáze provádění společné operace a každá fáze po dokončení své práce přenese výsledek na další a současně přijme novou část vstupních dat. Díky kombinaci dříve rozmístěných operací získáme zřejmý nárůst rychlosti zpracování.

Superskalární. Stejně jako v předchozím příkladu se pouze při stavbě potrubí používá několik hardwarových a softwarových implementací funkčních jednotek, například dvě nebo tři ALU, tři nebo čtyři vzorkovací zařízení.

Hyper závitování. Slibný směr ve vývoji moderních mikroprocesorů založených na vícevláknové architektuře. Hlavní překážkou zvyšování produktivity zvyšováním funkčních zařízení je organizace efektivního zatížení těchto zařízení. Pokud dnešní programovací kódy nejsou schopny načíst všechny funkční jednotky, pak je možné umožnit procesoru vykonávat více než jednu úlohu (vlákno), takže se načítají další vlákna - koneckonců všechna FIS (podobně jako multitasking).

Vícejádrový. Je možné samozřejmě implementovat multiprocessing na úrovni čipu, tzn. umístěte několik procesorů na jeden čip (Power 4). Pokud ale vezmeme mikroprocesor spolu s pamětí jako jádro systému, pak více takových jader na jednom čipu vytvoří vícejádrovou strukturu. V krystalu jsou zároveň integrovány funkce (například rozhraní síťových a telekomunikačních systémů), pro jejichž realizaci se obvykle používají čipsety (Motorola MPC8260, procesory Power 4).

Implementace vysoce výkonné výpočetní techniky se v současnosti ubírá čtyřmi hlavními směry.

1. Vector-pipeline počítače. Zřetězené funkční jednotky a sada vektorových instrukcí jsou dvě vlastnosti takových strojů. Na rozdíl od tradičního přístupu pracují vektorové instrukce na celých polích nezávislých dat, což umožňuje efektivně načítat dostupné pipeline, tzn. příkaz jako A=B+C může znamenat přidání dvou polí místo dvou čísel. Charakteristickým představitelem tohoto trendu je rodina vektorových dopravníkových počítačů CRAY, kam patří např. CRAY EL, CRAY J90, CRAY T90 (v březnu 2000 americká společnost TERA koupila divizi CRAY od Silicon Graphics, Inc.) .

2. Masivně paralelní počítače se sdílenou pamětí. Myšlenka sestavení počítačů této třídy je triviální: vezmeme sériově vyráběné mikroprocesory, dodáme každému jeho vlastní lokální paměť, propojíme jej přes nějaké komunikační médium – to je vše. Taková architektura má spoustu výhod: je-li potřeba vysoký výkon, lze přidat více procesorů, jsou-li finance omezené nebo požadované výpočetní výkon, pak je snadné zvolit optimální konfiguraci atd.

Existuje však také rozhodující „mínus“, který mnoho „plusů“ redukuje na nic. Faktem je, že je nezávislý, ale spíše kombinací předchozích tří. Z několika procesorů (tradičních nebo vector-pipeline) a společné paměti pro ně vytvoříme výpočetní uzel. Pokud přijímaný výpočetní výkon nestačí, zkombinujeme několik uzlů s vysokorychlostními kanály. Tato architektura se nazývá shluk SV1, HP Příklad, Slunce StarFire, NEC SX-5, nejnovější modely IBM SP2

3. Paralelnípočítače se sdílenou pamětí. Všechno RAM takové počítače sdílí několik stejných procesorů. To odstraňuje problémy předchozí třídy, ale přidává nové – počet procesorů, které mají přístup ke sdílené paměti, nelze z čistě technických důvodů zvětšit. Tento směr zahrnuje mnoho moderních víceprocesorových SMP počítačů nebo například jednotlivých uzlů počítačů HP Příklad a slunce StarFire.

4. klastrové systémy. Poslední směr, přísně vzato, není nezávislý, ale spíše kombinací předchozích tří. Z několika procesorů (tradičních nebo vector-pipeline) a společné paměti pro ně vytvoříme výpočetní uzel. Pokud přijímaný výpočetní výkon nestačí, zkombinujeme několik uzlů s vysokorychlostními kanály. Tato architektura se nazývá shluk, a podle tohoto principu CRAY SV1, HP Příklad, Slunce StarFire, NEC SX-5, nejnovější modely IBM SP2 a další. Právě tento směr je v současnosti nejperspektivnější pro navrhování počítačů s rekordními ukazateli výkonu.