PP

Efektívnosť E(n, p) je definovaná ako E(n, p) = S(n, p) / p

Pre expanzívny paralelizmus platí:

Program pre dataflow počítač je v podobe data flow grafu.

Program pre data flow počítač

Zvýšeniu efektívnosti výpočtu pri sekvenčnom počitani bráni často nielen nedostatok procesorov, ale aj nedostatok pamäti.

Pre masívny paralelizmus platí:

Expanzivny paralelizmus, kde n = 2 je špeciálnym expanzívneho paralelizmus, ktorý sa nazýva rozdeľ a panuj.

Rozoznávame časovú a pamäťovú zložitosť algoritmov a problémov.

Cieľom realizácie paralelných výpočtov je zníženie času výpočtu a/alebo spracovanie veľkého množstva údajov.

Pri expanzívnom paralelizme je problém rekurzívne delený na n toho istého typu, kde n je z rozsahu 0 do 1.

Pri jednoduchom paralelizme, keď rozdelíme problém na p úloh, záleží na tom, aby bol čas potrebný pre realizáciu jednotlivých úloh približne rovnaký, pretože tieto úlohy sa realizujú sekvenčne jedna po druhej.

Pre expanzívny paralelizmus platí:

Medzi nevýhody implicitného paralelizmu patrí:

Ak má byť problém riešený paralelným spôsobom, potom

Pre SIMD platí:

Pre architektúru MISD platí:

S(n,p) = T(n,1)/T(n,p)

Pre prúdový paralelizmus platí, že problém P sa dekomponuje na množinu n podproblémov (úloh), ktoré sú riešené všetky naraz. v tom istom čase.

Pre dekompozíciu paralelných problémov platí:

Pre SM-MIMD platí:

Ak je problém nedostatočne škálovaterný, zvýšenie počtu procesorov už nevedie k zvýšeniu zrýchlenia.

Pre masívny paralelizmus platí:

Pre architektúru MISD platí:

Pri programovaní systémov reálneho času platí:

Výkonné paralelné výpočty sa uplatňujú predovšetkým pri modelovaní, simulácii a analýze zložitých technických, fyzikálnych a biologických systémov, s cielom skúmania ich vlastností a predpovedania ich správania,

Pre architektúru MISD platí:

Pri programovaní systémov reálneho času platí:

Program pre data flow počítač

Neohraničený paralelizmus znamená, že škálovanie paralelného počítača pridávaním ďalších procesorov neznižuje efektivitu paralelizácie.

Neohraničený paralelizmus algoritmu neberie do úvahy zdroje počítačového systému.

Pre škálovatelnosť v reálnom pr�­pade plat�­. že S(n,p) < p E(n,p) < 100%

Pre pamäťovú zložitosť algoritmov platí:

MIMD architektúry zvyčajne obsahujú viac procesných jednotike ako architektúry SIMD

Pre priemerný stupeň paralelizmu platí:

Čas vykonávania paralelného programu sa skladá z

Pre expanzívny paralelizmus platí:

Pri expanzívnom paralelizme, ak veľkosť problému nie je známa. ľahko dochádza k pretaženiu paralelnej architektúry v dôsledku vyčerpania zdrojov.

Embarrassingly parallel problems:

Pre ohraničenost paralelizmu platí:

Lineárna časová zložitosť algoritmu, formálne zapísaná ako 0(1), je na grafe reprezentovaná priamkou rovnobežnou s osou x, prechádzajúcou na ose y hodnotou 1, za predpokladu, že na ose y je uvedený počet operácii a na ose x je uvedené n.

Pri Gustafsonovom zákone nie je zrýchlenie paralelného počítania zhora ohraničené.

Gustafsonov zákon predpokladá, že veľkosť sekvenčnej časti výpočtu klesá so zväčšovaním sa rozmeru problému:

Efektívnosť E(n, p) je definovaná ako E(n, p) = T(n,1) / T(n,p)

Pre Flynnovu klasifikáciu platí, že

Implicitný paralelizmus umožňuje kompilátoru alebo interpreteru zdrojového kódu automaticky odhaľovať' inherentný paralelizmus vlastný určitým konštrukciám programu.

Prúdový paralelizmus je zväčša hrubozrnný paralelizmus a preto sa pri ňom architektúry MISD používajú zriedkavo.

Expanzívny paralelizmus môže byt'

Vykonaná práca wi v časovom intervale Δti je vyčísliteľná ako wi = SP(Δti) x Ati x r [ops] kde SP(Δti) je stupeň paralelizmu r je počet operácií vykonávaných na procesnom elemente za sekundu

Čas vykonávania paralelného programu sa skladá z času počítania, času komunikovania a času čakania

Explicitný paralelizmus umožňuje programátorovi pomocou špecializovaných direktív alebo volaní funkcií určených pre synchronizáciu, komunikáciu a dekompozíciu úloh realizovať paralelizáciu výpočtu.

MIMD architektúry zvyčajne obsahujú viac procesných jednotiek ako architektúry SIMD.

Pre jednoduchý paralelizmus platí:

Pre prúdový paralelizmus platí, že problém P sa dekomponuje na množinu n podproblémov (úloh), ktoré sú riešené jeden po druhom.

Pre stupeň paralelizmu SP platí:

Podlá Amdahlovho zákona zrýchlenie dosiahnuteľné na paralelnom počítači je závislé od počtu procesorov, ktoré sú k dispozícii pri paralelnom výpočte.

Priemerný stupeň paralelizmu (PSP) je priemerný počet procesných elementov, ktorý bol v určitom čase využívaný na realizáciu paralelného výpočtu.

Problém P sa dekomponuje na množinu n podproblémov (úloh), ktoré sú riešené všetky naraz, v tom istom čase.

Prúdový paralelizmus je zväčša hrubozrnný paralelizmus a preto sa pri ňom architektúry MISD používajú zriedkavo.

Cieľom realizácie paralelných výpočtov je zníženie času výpočtu a/alebo spracovanie veľkého množstva údajov.

Embarrasingly parallel problems je termín preložiteľný ako trápne paralelne problémy.

Podľa Amdahlovho zákona zrýchlenie dosiahnuteľné na paralelnom počítači môže byť značne ohraničené existenciou malej časti sekvenčného kódu, ktorý nemožno paralelizovať.

Podľa Amdahlovho zákona zrýchlenie dosiahnuteľné na paralelnom počítači je závislé od počtu procesorov, ktoré sú k dispozícii pri paralelnom výpočte:

Pre Single Instruction Single Data architektúru platí

Jednoduchý paralelizmus možno niekedy využiť pri prúdovom paralelizme pre zlepšenie vyváženosti pri prúdovom spracovaní.

Pre Gustafsonov zákon platí:

Pre masívny paralelizmus platí:

Pre zložitosť algoritmu:

Pre inherentný paralelizmus platí:

Ak veľkosť problému nie je známa, expanzívny paralelizmus treba riadiť počas vykonávania výpočtu.

Efektívnosť E(n,p) je definovaná ako E(n,p) = T(n,1)/T(n,p)

Pre škálovateľnosť v REALNOM pr�­pade plat�­, že: S(n,p) < p E(n,p) < 100%

Pre škálovateľnosť v REALNOM prípade platí, že: S(n,p) = p E(n,p) = 100%

Pre škálovateľnosť v IDEALNOM prípade platí, že: S(n,p) = p E(n,p) = 100%

Ak znížime časovú zložitosť algoritmu, môže sa stáť, že súčasne zvýšime jeho pamäťovú zložitosť.

Ohraničený paralelizmus algoritmu berie do úvahy zdroje počítačového systému:

Pre prúdový paralelizmus platí, že problém P sa dekomponuje na množinu n podproblémov (úloh),ktoré sú riešené jeden po druhom.

Maximálny stupeň paralelizmu (MSP) je maximálny počet procesných elementov, ktorý bolv určitom čase využívaný na realizáciu paralelného výpočtu.

Pre prúdový paralelizmus platí, že problém P sa dekomponuje na množinu n podproblémov (úloh), ktoré sú riešené všetky naraz v tom istom čase.

Flynnova klasifikácia posudzuje množstvo súčasne spracovávaných inštrukcií a súčasne spracovávaných dát:

Nie je možné súčasne znižovať pamäťovú aj časovú zložitosť riešenia problému:

Pre komunikátory platí:

Medzi funkcie kolektívnej komunikácie v rámci MPI patria:

Pre jednoduchý paralelizmus platí:

Pre SISD platí:

Pre karteziánsky komunikátor platí (skontrolovat spravnost)

Numerická efektívnosť je mierou kvality sekvenčného algoritmu berúc do úvahy spracovávané údaje

Pre optimálny paralelný algoritmus platí:

Pre škálovateľnosť v reálnom pr�­pade plat�­, že S(n, p) = p E(n, p) < 100%

Pre súbežné programovanie platí:

Pre programové modely založené na odovzdávaní správ platí:

Architektúra MIMD môže pozostávať z:

Ťažko paralelizovatelné sekvenčne časti kódu patria medzi náklady paralelného výpočtu

DM-MIMD podporuje škálovateľnosť horšie ako SM-MIMD

Pre architektúry DM-MIMD platí:

Najlepší sekvenčný algoritmus môže byť predsa len rýchlejší ako algoritmus, ktorý je paralelizovaný

Zníženie komunikačných nákladov pri realizácii paralelného výpočtu možno dosiahnuť

Pre komunikáciu v rámci MPI platí:

Pre architektúry VSM-MIMD platí

Pri jednoduchom paralelizme, keď rozdelíme problém na p úloh, záleží na tom, aby bol čas potrebný pre realizáciu jednotlivých úloh približne rovnaký

Pre grafový komunikátor platí:

Výkonná paralelná aplikácia nie je jednoducho vytvoriteľná s využitím jednoduchého paralelizmu.

Vzhľadom na obmedzený aplikačný záber, architektúra MISD sa používa zriedkavo.

Nech TN(n) je čas vykonávania najrýchlejšieho známeho sekvenčného algoritmu na jedno procesore, potom numerická efektívnosť = TN(n)/T(n,1)

Paralelizmus využívaný v systémoch reálneho času je zvyčajne jemnozrnnejší ako pri paralelných výpočtoch.

Amdahlovo pravidlo je metrika, ktorú možno považovať za metriku kvality programového kódu.

Cieľom programovania systémov reálneho času je uspokojenie požiadaviek na čas vykonávania a zabezpečenie spoľahlivosti z hľadiska správnosti funkcie.

Pre ohraničenosť paralelizmu platí:

Pri expanzívnom paralelizme je problém rekurzívne delený na n podproblémov toho istého typu.

Dekompozícia expanzívne paralelného problému sa nazýva hierarchická dekompozícia.

Pri programovaní výkonných paralelných výpočtov je základným cieľom dosiahnutie tých istých výsledkov ako na sekvenčnom počítači, avšak pomocou viacprocesorovej architektúry.

Pri jednoduchom paralelizme, keď rozdelíme problém na p úloh, nezáleží na tom, či je čas potrebný pre realizáciu jednotlivých úloh približne rovnaký, pretože všetky sa začínajú v rovnakom čase.

Jednoduchý paralelizmus je jemnozrnný.

Pre expanzívny a masívny paralelizmus platí.

Ak je problém inherentne paralelný, je možné zostaviť iba paralelný algoritmus.

Jedným z kľúčových problémov, ktoré je potrebné v súvislosti s paralelnými výpočtami riešiť, je vyvažovanie paralelného výpočtu.

Prúdový paralelizmus je zväčša hrubozrnný paralelizmus a preto sa pri ňom architektúry MIMD používajú zriedkavo

Pre neblokujúcu komunikáciu v rámci MPI platí:

Zrýchlenie S(n,p) je definovane ako S(n,p) = T(n,1) / T(n,p)

Maximálny stupeň paralelizmu (MSP) sa nemôže nikdy rovnať hodnote 1

Pre architektúru paralelného počítača SM-MIMD platí:

Novy komunikátor možno vytvoriť prostredníctvom funkcie

Efektívnosť E(n,p) je definovaná ako E(n,p) = S(n,p)/p

Pri inicializácii MPI:

Prúdový paralelizmus je zväčša hrubozrnný paralelizmus a preto sa pri ňom architektúry MIMD používajú zriedkavo

Pre škálovateľnosť v IDEALNOM pr�­pade plat�­, že: S(n,p) < p E(n,p) < 100%

Algoritmus s najpriaznivejšou časovou zložitosťou, ktorý je možno použiť na riešenie problému, určuje súčasne aj časovú zložitosť problému.

Výkonná paralelná aplikácia nie je jednoducho vytvoriteľná s využitím prúdového paralelizmu

Funkcia MPI_Wait slúži na:

Funkcia MPI_Test slúži na:

Funkcia MPI_Allgather slúži na:

Funkcia MPI_Gather slúži na:

Funkcia MPI_Scatter slúži na: