Distribuované systémy, dekompozice úloh, „hrubý‟ paralelismus.

• V distribuovaném systému probíhá distribuované zpracování. Na distribuovaném výpočtu spolupracuje nějaká podmnožina spojených procesorů.
• Každý procesor provádí svůj vlastní instrukční tok a zpracovává svá vlastní lokální data. Pokud se musí data vyměnit, děje se mechanismem zasílání zpráv.
• Výpočet realizovaný propojenou skupinou procesorů s přímým přístupem ke sdílené paměti nazýváme paralelní zpracování a takový systém se nazývá paralelní systém nebo těsně vázaný systém.

Dva základní aspekty:

• Autonomní hardware (fyzicky oddělené stroje).
• Uživatelé si myslí, že komunikují s jedním systémem.

Při konstrukci distribuovaného systému by mělo být splněno několik cílů:

• Měl by umožnit jednoduché spojení uživatelů a zdrojů (většinou výpočetních).
• Měl by skrýt fakt, že zdroje jsou distribuovány po síti (transparentnost).
• Měl by být otevřený.
• Měl by být škálovatelný.

Data mohou být distribuována dvojím způsobem:

• Duplicitou dat – vytvořením kopie množiny dat v každém uzlu, ve kterém ji algoritmus využívá. Problémem duplicity je trvalé zajišťování konzistence všech kopií.
• Rozložením dat - rozložením množiny dat na části, které jsou uchovávány pouze v určitých uzlech a ostatním uzlům jsou dostupné pouze zprostředkovaně, výměnou zpráv.

Obě metody lze kombinovat. Celou databázi lze např. rozložit a určité její prvky přitom duplikovat.

• O distribuovaném řízení mluvíme v případě koexistence řady souběžných procesů, mezi nimiž neexistuje žádná pevná hierarchie, neexistuje žádný hlavní algoritmus, který globálně řídí celý systém.
• Mohou existovat určité funkce, které mohou být prováděny pouze v určitých uzlech – potřebujeme distribuovaný algoritmus k identifikaci těchto uzlů
• Určitá rozhodnutí formou dosažení shody (na hodnotě, na společné akci, na vzájemném vyloučení kritických sekcí apod.) mezi skupinou uzlů.

Je komunikační rozhraní pro meziprocesorovou komunikaci v paralelních programech.
Vlastnosti:

• Přenositelnost, vazba na různé programovací jazyky, nezávislé implementace
• Nezávislá optimalizace na různé architektury, standardizováno.
• Funkcionalita – snaha pokrýt všechny aspekty meziprocesorové komunikace.
• Skupiny, kontext, tagy, synchronní, asynchronní zprávy, …
• Určena pro clustery i gridy.

Byl vyvinut na přelomu 80. a 90. let s cílem vytvářet virtuální superpočítač. Znamenal první krok pro vývoj distribuovaného počítaní. Síť byla tvořena démony pvmd běžícími na různých počítačích s různými OS a knihovny přilinkované k programům. Výpočetní model byly samostatné úlohy řešené na jednotlivých procesorech s komunikací pomocí zpráv.

• Řízení procesů (každý proces má identifikátor s info o úloze a umístění v PVM, vydáván master PVM démonem - poteciální slané místo, je jeden)
• Posílání zpráv (zprostředkováno pvmd démony, musí zajistit převod dat mezi různými architekturami)
• Přijímání zpráv
• Správa bufferů
• Skupinové operace (tvorba skupin procesů, není nutná synchronizace)
• Informace
• Signály

• pracuje se sdílenou tabulí přístupnou všem procesům zpracovávajícím úlohu
• číst, zapsat a mazat může každý proces
• má charakter asociativní paměti
• pomocí zápisu speciální n-tice do tabulky lze procesy i vytvářet
• jde o jednoduchý přístup

Paralelní programování rozděluje celkový problém do úkolů pro jednotlivé procesory a synchronizuje běh jednotlivých úkolů tak, aby na konci vznikl smysluplný výsledek.

Paralelní programování lze nahlížet také ze dvou úhlů:

• Implicitní paralelismus – o paralelizaci se stará kompilátor nebo nějaký jiný systém a automaticky alokuje práci procesorům.
• Explicitní paralelismu – programátor sám určí rozdělení práce.

Dekompozici úloh lze provádět ze dvou úhlů:

• Doménová In this type of partitioning, the data associated with a problem is decomposed. Each parallel task then works on a portion of of the data.

• Funkční In this approach, the focus is on the computation that is to be performed rather than on the data manipulated by the computation. The problem is decomposed according to the work that must be done. Each task then performs a portion of the overall work.

Uzitecne video: http://www.dailymotion.com/video/xksorx_introduction-to-parallel-programming-02-parallel-decomposition-methods-clay-breshears-intel-software_tech#.URuIRB000hY

Granularita paralelismu na úrovni samostatných úloh pro jednotlivé OS, kdy si jednotlivé úlohy pouze zasílají zprávy. Používá se MPI nebo PVM, distribuovaná paměť. Jednotlivé podproblémy sú nezávislé od výsledkov iných podproblémov (tzn., že oneskorenie pri výpočte jedného nemá vplyv na iný výpočet). Takéto počítanie nazývame vysokopriepustné počítanie (vhodne pre volne-viazane PC siete).

Jemný paralelismus, hrubý paralelismus, granularita výpočtů Granularita paralelních výpočtů udává poměr mezi množstvím výpočtů prováděných jedním uzlem ku množství komunikace mezi jednotlivými uzly.
Jemný praralelismus (vysoká granularita) označuje situaci, kdy velikost jednotlivých výpočtů je relativně malá (délka kódu, procesorový čas). Uzly spolu často komunikují, vyměňují si malé objemy dát.
Hrubý paralelismus (nízká granularita) je opakem jemného paralelismu. Data se vyměňují po delších sekvencích výpočtů a větších časových úsecích.
S rostoucí granularitou lze výpočet rozdělit mezi více uzlů a zvyšuje se potenciál pro zrychlení. Tím se ale také zvětšuje režije a množství komunikace. Pro optimální výkon je potřeba nalézt kompromis mezi těmito dvěma extrémy.

http://www1.osu.cz/~prochazka/ds/P2.pdf https://computing.llnl.gov/tutorials/parallel_comp