====== N-AP 16 ======

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

Jednoprocesorové počítače, počítače s menším počtem procesorů, masivně paralelní počítače; distribuované systémy. Sdílená, distribuovaná a distribuovaná sdílená paměť; další alternativy. 

**Modulární sestava počítače s jedním procesorem**
{{:mgr-szz:ap-ap:PC_sbernice.png|}}

Jednotlivé komponenty komunikují po sběrnici, což je standardizovaný způsob přenosu informace mezi dvěma nebo více zařízeními.

==== Postup činnosti počítače  ====

  - procesor vyšle adresu paměťové buňky 
  - paměť vyšle její obsah 
  - procesor jej přečte a považuje za kód instrukce 
  - procesor dekóduje instrukci a hledá, co potřebuje k provedení 
  - pokud je nutno, požádá stejným způsobem o další hodnoty z paměti 
  - provede instrukci 
  - uloží výsledek 

**Fyzická struktura - žlutě chipset**
{{:mgr-szz:ap-ap:chipset.png|}}

==== Pipelining (proudové zpracování) ====

Překrývání instrukcí v různých fázích rozpracovanosti.

Pokud lze zpracování proudu hodnot rozdělit do několika fází, které jsou pro všechny hodnoty podobné a zvolíme sekce tak, aby zpracování v nich trvalo stejně dlouho:

{{:mgr-szz:ap-ap:pipelining.png|}}


=== Běžný rozklad instrukcí (pětiúrovňový pipelining): ===

  - **Instruction Fetch** instrukce je načtena z paměti
  - **Instruction Decode** instrukce je rozeznána (dekódována)
  - **Operand Fetch** jsou připraveny operandy (načteny z registrů  a/nebo paměti)
  - **Execute** instrukce je provedena
  - **Writeback** výsledky jsou zapsány zpět (do registrů a/nebo paměti)

Jednotlivé instukce jsou zpracovány paralelně, s posunem o jednu fázi pipeline.

==== Architektury mikroprocesorů ====

Dva základní přístupy, CISC a RISC (dále např. MISC, VLIW).

=== Complex Instruction Set Computer ===

  * IBM 1962
  * Snaha o univerzální architekturu
  * vyplnění sémantické mezery mezi assemblerem a vyššími programovacími jazyky
  * obsáhlá instrukční sada, dlouho trvající instrukce (desítky, stovky taktů)

Příklady:
PDP 11, VAX, IBM 370, Intel 80x86, Motorola 680x0,…
Princip:
Nedělej programem to, co může udělat hardware 

**Důvody existence**
  * Velikost a rychlost paměti
  * Přímá podpora překladačů
  * Adresování

  * složité instrukce (mikroprogramy), dekomponovány na jednodušší – mikroinstrukce
  * instrukce jsou emulovány, jednodušší návrh HW, lze snadno změnit instrukční sadu

Všechny strojové instrukce, které jsou postupně načítané z operační paměti, jsou rozkládány na různě dlouhou sekvenci takzvaných mikroinstrukcí a činnost celého procesoru je řízena mikrořadičem doplněným většinou mikroprogramovou pamětí.

=== Reduced Instruction Set Computer ===

První RISC: CDC 6600 (Seymour Cray) – první pol. 60. let.

**Podmínky vzniku**
  * Zavedení vyrovnávacích pamětí (cache)
  * Dramatický pokles ceny a vzrůst velikostí hlavních pamětí (rychlost přístupu k paměti a velikost programu už nejsou kritické)
  * Lepší pipelining
  * Kvalitně optimalizující překladače

**Charakteristika**
  * Jednotná délka instrukcí
  * Pečlivý výběr skutečně používaných instrukcí
  * Jednoduché adresní módy
  * Architektura Load/Store (jediné operace, které interagují s pamětí, počet instrukcí tedy vlastně může být vyšší)
  * Dostatek registrů
  * „Odložené“ skoky (delayed branches) (provede se až po následující instrukci)

Ideál první generace – jedna instrukce každý tik hodin, dnes více instrukcí za tik.

=== Superskalární procesory ===

  * vícenásobné procesní jednotky (aritmetické - ALU, floating point - FPU,...)
  * snaha o zvyšování výpočetního výkonu
  * čipy, které dokázaly v každém strojovém cyklu začít zpracovávat větší množství instrukcí
  * mikroprocesory většinou vybaveny dvěma či větším množstvím relativně samostatně pracujících instrukčních pipeline a někdy i větším množstvím aritmeticko-logických jednotek
  * jednotky pro bitové posuny a rotace (barrel shifter) nezávislé na ALU
  * jednotky pro komunikaci s operační pamětí atd.

=== Very Long Instruction Word (VLIW) ===

  * obdoba superskalárních (mnoho jednotek)
  * paralelizace pod kontrolou překladače
  * instrukce pevné délky, podobně jako u RISC
  * délka těchto instrukcí řádově několik desítek i stovek bitů
  * každé instrukční slovo je rozděleno do většího množství polí (fields), přičemž v každém poli je umístěn kód jedné operace
  * jednotky pro bitové posuny a rotace (barrel shifter) nezávislé na ALU
  * jednotky pro komunikaci s operační pamětí atd.

=== Architecture with Non-sequential Dynamic Execution Scheduling (ANDES) ===

  * vychází z předpokladu, že zpomalení je způsobeno čekáním na data
  * vícenásobné fronty instrukcí (celočíselná, adresní, floating point)
  * nezávislá pipeline pro každou frontu
  * instrukce vybírány podle **připravenosti**
  * není dodrženo pořadí instrukcí v programu
  * **dokončení** instrukcí zajišťuje správné uspořádání
  * spekulativní skoky: výpočet pokračuje předpovězenou větví, nečeká na výsledek instrukce

**Porovnání architektur RISC, CISC a VLIW**
{{:mgr-szz:ap-ap:srovnani_architektur.png|}}

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

===Small-scale multiprocessing===
  * 2–16 procesorů
  * převážně SMP (sdílená paměť)

===Large-scale multiprocessing===
  * > 100 (i tisíce) procesorů
  * zpravidla distribuovaná paměť

====Architektura=====
  * Single Instruction Multiple Data, SIMD
  * Multiple Instruction Multiple Data, MIMD

===Architektura SIMD===
  * procesory synchronizovány (všechny vykonávají vždy stejnou instrukci, analogie vektorových procesorů)
  * jednoduché procesory
  * jednodušší programovací model

{{:mgr-szz:ap-ap:schema_simd.png|}}

===Architektura MIMD===
  * plně asynchronní systém
  * procesory zcela samostatné (není třeba speciální výroba (off-the-shelf))
  * výhody - vyšší flexibilita a teoreticky i efektivita
  * nevýhody - explicitní synchronizace a složitější programování

{{:mgr-szz:ap-ap:schema_mimd.png|}}


===Programovací modely===
  * Single Program Multiple Data, SMPD
  * Multiple Programs Multiple Data, MPMD

===Komunikační modely===
  * sdílená paměť (Shared Memory Architecture)
  * předávání zpráv (Message passing)

==Sdílená paměť==
  * paměť oddělená od procesorů
  * uniformní přístup k paměti
  * nejsnazší propojení - sběrnice
  * "levná" komunikace
  * složité prokládání výpočtu a komunikace (aktivní čekání)

==Předávání zpráv==
  * každý procesor "viditelný"
  * vlastní paměť u každého procesoru
  * explicitní komunikace - předávání zpráv
  * vysoká cena komunikace (výměny dat)
  * možnost prokládání výpočtů a komunikace

===== 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 to 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.

=== Paralelní / distribuované zpracování ===
Konkurentní výpočty (srovnání rychlosti a spolehlivosti meziprocesorové komunikace):
  * při velmi vysokých komunikačních rychlostech, řádově srovnatelných s rychlostí přístupu do paměti, se jedná o paralelní zpracování.
  * je-li rychlost komunikace nižší, potom se jedná o distribuované zpracování.
  * paralelním systémem je z tohoto hlediska multiprocesor a multipočítač.
  * počítačová síť je systém distribuovaný.

**Distribuovaný systém je sestava nezávislých počítačů, které jsou z pohledu uživatele jednotným systémem.** 

== Dva základní aspekty: ==
  * autonomní hardware (fyzicky oddělené stroje).
  * uživatelé si myslí, že komunikují s jedním systémem.

===== Paměť =====

==== Obecně ====
Organizace paměti:
  * řádky a sloupce (matice) adresa má dvě části 
  * page mode - naráz čtena skupina souvisejících bytů

Vlastnosti paměti:
  * přístupová doba (memory access time) - vystav řádek plus vystav sloupec plus vystav data
  * cyklus paměti (memory cycle time) - určuje, jak často lze data číst
  * obojí závisí na typu paměti (dynamická vs. statická)

=== Vyrovnávací paměť ===
  * hit poměr - udává efektivitu paměti, poměr čtení z cache vůči všem operacím
  * velikosti 4 KB–16MB
  * Organizace: řáadky pevné délky, 16–128 bytů

Typy:
  * **přímo adresovatelná (direct mapped):**
    * statické mapování (každý řádek vyrovnávací paměti odpovídá předem určeným oblastem hlavní paměti)
    * rychlé
    * jednoduché obvody
    * potenciálně neefektivní

  * **plně asociativní (fully-associative):**
    * dynamické mapování (každý řádek zná adresu bloku, současný dotaz na všechny ř., výběr ř. pro zneplatnění)
    * velmi složité (drahé) obvody
    * velmi efektivní

  * **množinově (částečně) asociativní (set-associative):**
    * množina přímo adresovatelných vyrovnávacích pamětí
    * kombinace lepších vlastností obou extrémních přístupů

==== Sdílená paměť ====

{{:mgr-szz:ap-ap:shared_mem.gif|}}

  * globální prostor
  * procesory operují odděleně, ale nad sdílenými zdroji
  * změny v paměti jsou viditelné všem
==== Distribuovaná paměť ====

{{:mgr-szz:ap-ap:distributed_mem.gif|}}

  * procesory mají vlastní paměť, operují zvlášť
  * přístup k datům jiného procesoru a synchronizace je ošetřena programově


==== Distribuovaná sdílená paměť ====

{{:mgr-szz:ap-ap:hybrid_mem.gif|}}

  * kombinace předchozích
  * zřejmě perspektivní přístup
  * vysoká škálovatelnost, nicméně rovněž velké nároky na programování

  * distribuovaný systém - cluster (lokální paměť každého uzlu, vzdálená od ostatnícb)
  * fikce jedné rozsáhlé paměti
  * HW řešení - principy virt. paměti, transparentní
  * SW řešení - knihovna, programátor musí přízpůsobit (netransparentní)

==== Nonuniform memory access architecture (NUMA) ====

  * přístup k různým fyzickým adresám trvá různou dobu
  * umožňuje vyšší škálovatelnost
  * potenciálně nižší propustnost
  * koherence vyrovnávacích pamětí - ccNUMA

{{:mgr-szz:ap-ap:numa.gif|}}

==== Cache-only memory access architecture (COMA) ====
  * NUMA s charakterem vyrovnávací paměti - postrádá "domovskou" paměť, každý procesor má část sdílené p.
  * pouze zdánlivá hierarchie (?)
  * systém musí hlídat, že má jedinou kopii
  * experimentální

====== Použitá literatura a weby ======

https://is.muni.cz/auth/el/1433/jaro2011/IA039/um/procesory2011.PDF
https://is.muni.cz/auth/el/1433/jaro2011/IA039/um/parallel2011.PDF
http://www.root.cz/clanky/architektury-mikroprocesoru/
http://www.root.cz/clanky/architektura-vliw-aneb-pokus-o-prekonani-problemu-architektur-cisc-a-risc/
http://kfe.fjfi.cvut.cz/~voltr/arch/jednoprocesory.pdf
http://kfe.fjfi.cvut.cz/~voltr/arch/cpu.pdf  
https://computing.llnl.gov/tutorials/parallel_comp/
http://www1.osu.cz/~prochazka/ds/P2.pdf
http://en.wikipedia.org/wiki/Cache-only_memory_architecture

~~DISCUSSION~~