N-AP 18
Zadání
Distribuované systémy, dekompozice úloh, „hrubý‟ paralelismus.
Distribuované systémy
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:
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ý.
Distribuce dat
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.
Distribuce řízení
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ů.
MPI (Message Passing Interface)
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.
PVM (Parallel Virtual Machine)
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.
Základní třídy příkazů
Ří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
Koordinační jazyk Linda
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
Dekompozice úloh
„Hrubý‟ paralelismus
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.
Použitá literatura a weby