====== Zadání ======

Technologie paralelních a distribuovaných systémů: Paralelní počítače, základní principy, propojovací sítě a jejich struktura. Gridy, OGSA, WSRF.

====== Vypracování ======

===== Paralelní počítače =====

Paralelní počítače vykonávají výpočty souběžně. Základní myšlenkou je dělba velikých problémů na menší, které je možné řešit souběžně (paralelně). Paralelní výpočty jsou poslední dobou využívány hlavně z důvodu nemožnosti škálovat víc výpočetní frekvenci. Paralelní výpočty jsou dnes uskutečňovány pomocí více-jádrových procesorů, více-procesorových počítačů, clusterů a gridů.

Multiprocessing:
  * small-scale - 2-16 procesorů, převážně SMP (sdílená paměť)
  * large-scale - víc než 100, možná tisíce procesorů, zpravidla distribuovaná paměť

Architektura:
  * SIMD - Single Instruction Multiple Data - procesory jsou jednoduché, synchronizované, všechny vždy vykonávají stejnou instrukci (analogie vektorových procesorů). Mají jednodušší programovací model.
  * MIMD - Multiple Instruction Multiple Data - plně asynchronní systém, procesory jsou zcela samostatné, není třeba speciální výroba. Vyšší flexibilita, teoreticky i efektivita, ale programovaní je složitější a je nutná explicitní synchronizace.

Programovací modely:
  * SPMD - Single Program Multiple Data
  * MPMD - Multiple Program Multiple Data

Komunikační modely:
  * sdílená paměť (Shared Memory Architecture) - paměť je oddělená od procesorů, přístup k paměti je uniformní. Nejsnažší propojení je sběrnice. Jedná se o "levnou" komunikaci, prokládání výpočtu a komunikace je složité (aktivní čekání)
  * předávání zpráv (Message passing) - každý procesor je viditelný a má vlastní paměť. Komunikace je explicitní (předávání zpráv). Cena komunikace je vysoká, ale je možné prokládat výpočet a komunikaci

Hybridní systémy:
  * Nonuniform Memory Access Architecture (NUMA) - přístup k různým fyzickým adresám trvá různou dobu. Umožňuje vyšší škálovatelnost, má potenciálně nižší propustnost.
  * Cache-only Memory Access Architecture (COMA) - experimentální NUMA s charakterem vyrovnávací paměti. Data putují k procesorům, které je používají. Pouze zdánlivá hierarchie, systém musí hlídat že má jedinou kopii.
  * Distributed Shared-Memory (DSM) - distribuovaný systém (cluster). Každý uzl má lokální paměť, paměť ostatních uzlů je vzdálená - napodobení jedné rozsáhlé paměti. Hardwarové řešení je transparentní a využívá principů virtuální paměti. Softwarové řešení je dostupné jako knihovna, je netransparentní, programátor musí program explicitně přispůsobit.

Koherence vyrovnávacích pamětí u multiprocesorových systémů je problém zabránění výskytu různých dat v různých vyrovnávacíh pamětích. Vyrovnávací paměti se musí dovědět o změně. Jsou různé metody:
  * založené na broadcastu:
    * snoopy cache - pro propojovací sítě s přirozeným broadcastem - sběrnice. Každý procesor sleduje všechny přístupy k paměti
  * adresářové metody

Reakce na změnu dat ve vzdálené (vyrovnávací) paměti je zneplatnění a v případě opětovného přístupu je přehrána ze vzdálené paměti. Přístup Update zajišťuje okamžité změny dat, ale zatěžuje sběrnici. Těžko říct jestli je lepší Update nebo Zneplatnění.

Rozšiřitelný systém je takový, pro který platí, že výkon roste lineárně s cenou a je zachován konstantní poměr cena/výkon. Alternativní parametr je míra rozšiřitelnosti:
  * změna výkonu přidáním procesoru
  * změna ceny přidáním procesoru
  * smysluplný rozsah počtu procesorů

===== Propojovací sítě =====

Rozšiřitelné propojovací sítě:
  * nízká cena rostoucí lineárně s počtem procesorů (<math>N</math>)
  * minimální latence nezávislá na <math>N</math>
  * propustnost rostoucí lineárně s <math>N</math>

Vlastnosti sítí:
  * topologie - jednorozměrné (nejhorší vlastnosti), dvourozměrné (kruh, hvězda, strom - špatná redundance, mřížka, torus), třírozměrné (akceptovatelná cena, složitá konstrukce), hyperkrychle (zajímavá topologie se snadným nalezením uzlů pokud použijeme binární číslování, plně propojené (vynikající poloměr ale neakceptovatelná cena)
  * přepínání dat (pohyb dat mezi uzly) - přepínaní packetů, store-and-forward (jednoduché přeposlání packetu po uložení, má vysokou latenci), přepínání obvodů (3 fáze: ustavení spojení, přenos, ukončení; nižší latence), virtuální propojení (cut-through, správy rozdělené do kontinuálně posílaných bloků (flow control digits - flits), pokud jsou buffery dost velké tak odpovídá přepínání okruhů), směrování červí dírou (wormhole routing, případ když buffery mají délku flits, latence nezávisí na vzdálenosti, podporuje replikaci packetů pro broadcast a multicast), virtuální kanály (sdílení fyzických kanálů, několik bufferů nad kanálem použitelné pro přetížená spojení a zábranu deadlocku a garanci propustnosti systémovým datům)
  * směrování dat (hledání cesty mezi uzly) - statické směrování (zdrojové nebo distribuované), adaptivní směrování (vždy distribuované)

U propojovací sítě rozlišujeme:
  * velikost sítě - počet uzlů <math>N</math>
  * stupeň uzlu <math>d</math>
  * poloměr sítě <math>D</math> (nejdelší nejkratší cesta)
  * bisection width <math>B</math>
  * redundance sítě <math>A</math> (minimální počet hran které je nutno odstranit aby se síť rozpadla na 2)
  * cena <math>C</math> - počet komunikačních linek v síti

Bisection width (šířka rozpůlení) je minimální počet hran, které je nutno odstranit aby se síť rozpadla na 2. Bisection bandwidth (propustnost při rozpůlení) je celková kapacita (propustnost) odstraněných linek. Ideální stav je když bisection bandwidth vztažená na procesor je v systému konstantní.

===== Gridy, OGSA, WSRF =====

Grid je seskupení (výpočetních, úložních, ...) různorodých počítačových zdrojů za účelem jednotného cíle. Grid je neinteraktivní distributivní systém, který je zatěžován velkým množstvím výpočtů nebo dat. Grid se odlišuje od tradičních vysoko-výkonových výpočetních systémů jako clustery tím, že je míň úzce seskupen, je heterogenní a geograficky rozmístěný. Běžně je grid využíván na různorodé úkoly. Grid je možné vybudovat pomocí běžně dostupného software označovaného jako middleware.

Middleware je použit na rozdělení běhu programu na spracovávaných datech na všechny účastněné počítače, kterých můžou být stovky až tisíce. Samotný výpočet probíhá distribuovaně.

Gridy byly v historii využívány na intenzivní vědecké, matematické, nebo akademické problémy skrz dobrovolnictví a využívají se například na objevování léků, ekonomické předpovědi, seizmické analýzy a jiné.

Pro zajištění koordinace na celém gridu, obzvlášť pokud jde o koordinaci toku dat byly vyvinuty grid workflow systémy.

Jednou z výhod použití gridu je možnost přístupu k dobrovolnícké výpočetní síle, ovšem jisté riziko představuje důvěryhodnost takových počítačů, což zvyšuje náročnost návrhu gridové aplikace. Jiným problémem je odpojení uzlů od gridu v neočekávané momenty, jelikož grid může běžet i na přenosných počítačích. Na druhou stranu poskytnuté počítače vyjadřují jistou důvěru že aplikace gridu nebude provádět žádné škodlivé nebo zlomyslné operace.

Některé gridy (BOINC) využívají výpočetní výkon uzlů pouze pokud nejsou uzly zatěžovány.

Open Grid Services Architecture (OGSA) popisuje service-oriented architekturu výpočetního gridu pro komerční a vědecké využití. OGSA je založeno na webových službách (WSDL, SOAP). OGSA grid má následovné schopnosti:
  * služby infrastruktury
  * služby managementu vykonávání
  * datové služby
  * služby správy zdrojů
  * služby bezpečnosti
  * služby samosprávy
  * informační služby

Web Services Resource Framework (WSRF) je rodina specifikací pro webové služby.

====== Předměty ======

[[https://is.muni.cz/auth/predmet/fi/jaro2012/IA039|FI:IA039]] Architektura superpočítačů a intenzivní výpočty (jaro 2012), prof. RNDr. Luděk Matyska, CSc.

====== Použitá literatura ======

Wikipedia

====== Vypracoval ======

DevelX - Martin Jurča

stav - 100 %