43 - Základní typy topologií paralelních a distribuovaných architektur a jejich vlastnosti

Question 1

Komunikace mezi procesory

Answer 1

Sdílená paměť
• Obtížně použitelná pro synchronizaci.
• Skutečná vs simulovaná.
• Všechny procesory mají přístup do celého paměťového prostoru.
• Řešení současného přístupu k jedné buňce:
○ EREW - Exclusive Read, Exclusive Write (velmi omezující)
○ CREW - Concurrent Read, Exclusive Write (časté, jednoduché)
○ !!! ERCW !!! - Exclusive Read, Concurrent Write (nedává smysl)
○ CRCW - Concurrent Read, Concurrent Write (složité)

!!! Předávání zpráv

• možnosti:
	○ kanály (synchronní x asynchronní (kapacita), jednosměrný x obousměrný (ACK))
	○ volání vzdálených procedur (RPC)
	○ všesměrové vysílání (broadcasting) (úmyslné posílání zpráv všem procesorům, záplava - na jednu zprávu odpoví procesy jinou b. zprávou)

* Každý procesor má vlastní adresový prostor.
* Také každý procesor má vlastní fyzickou paměť, přístup jinam komunikací.

Question 2

SDÍLENÁ PAMĚŤ A PŘEDÁVÁNÍ ZPRÁV U MIMD

Answer 2

Multiprocesory (Sdílená paměť)

• > multitasking - 1 cpu, přepínání kontextu, virtuální procesory
• > sdílená paměť - CPU mají svou cache, zbytek na sběrnici (boj), předávání zpráv může být v HW nebo simulace SW, těsně vázané

• Multicomputery (předávání zpráv) - Distribuované systémy
○ každý procesor má svou vlastní paměť
○ každý procesor má svůj adresový prostor

• > virtuální sdílená paměť - all chache, spojení caches komunikačními kanály, navenek se tváří jako jediný adresový prostor (CPU má svou paměť, ale je virtuálně spojena v simulovanou sdílenou, opět HW/SW simulované zasílání zpráv )
• > předávání zpráv - volně vázaná architektura, pořítačové sítě, propojeny pouze procesory, sdílená paměť simulovaná SW

Question 3

Topologie a propojovací sítě

Answer 3

Topologie

• Použití propojovacích sítí: propojit procesory se sdílenou pamětí nebo propojit spolu.
• Vlastnosti propojovací sítě ovlivňují vhodnost jednotlivých typů algoritmů a ovlivňují efektivnost toku dat

Statické propojovací sítě
• Všechny uzly jsou procesory.
• Všechny hrany jsou komunikační kanály.
• Pro architektury BEZ SDÍLENÉ PAMĚTI
• Vlastnosti
○ Průměr (diameter) - délka nejdelší cesty mezi nějakou dvojicí uzlů
§ je délka nejdelší z nejkratších cest mezi všemi dvojicemi uzlů
□ Tedy vezmu množinu všech nejkratších cest mezi dvojicemi uzlů a naleznu v ní tu nejdelší cestu.

	○ Konektivita (arc conectivity) - kolik hran musím odstanit aby vznikly dvě části?
		§ je minimální počet hran, které je nutné odstranit pro rozdělení na dvě části.

	○ Šířka bisekce (bisection width) - kolik hran určuje polovinu?
		§ je minimální počet hran, které spojují dvě přibližně stejně velké části sítě. (určuje, zda v síti nevzniká úzké místo - tzv. bottleneck)

Dynamické propojovací sítě
• Uzly jsou procesory, paměťové moduly nebo přepínače - Na rozdíl od statických sítí, kde jsou uzly procesory.
• Dynamické přepojování propojení - změna topologie za běhu
• Často implementují sdílenou paměť - Statické sítě jsou bez sdílené paměti.

Question 4

Statické propojovací sítě

Answer 4

Úplné propojení
• Průměr - 1
• Konektivita - p−1
• Šířka bisekce - p^2/4

Hvězda
• Průměr - 2
• Konektivita - 1
• Šířka bisekce - (p−1)/2

Lineární pole
	• Průměr - p
	• Konektivita - 1
	• Šířka bisekce - 1
Algoritmy
	• Lineární Enumeration Sort
	• Pipeline Merge Sort
	• Odd-Even Transposition Sort

d-rozměrná mřížka (mesh)
Kartézský součin d lineárních polí, z nichž každé má p^(1/d)  uzlů
Obvykle je d=2 (d jsou dimenze)
	• Průměr - dp^(1/d)
	• Konektivita - d
	• Šířka bisekce - 2p^((1−1/d))

k-ární d-rozměrná kostka
Průměr: d(k/2)
Konektivita: 2d
Šířka bisekce: 2k^(d − 1)

d-ární strom
• Průměr - 〖2log_d〗⁡〖((p+1)/2)〗
○ 2 protože v nejhorším případě musíme jít od listu až ke kořenu a zase dolů na druhou stranu stromu
○ log protože cesta od kořene k listům je logaritmická
○ (p+1)/2 protože počítáme logaritmus jenom z půlky uzlů.
• Konektivita - 1
Šířka bisekce - 1

Algoritmy
• Minimum Extraction Sort
• Bucket Sort
• Median Finding and Splitting

Question 5

Dynamické propojovací sítě

Answer 5

• Uzly jsou procesory, paměťové moduly nebo přepínače - Na rozdíl od statických sítí, kde jsou uzly procesory.
  
  • Dynamické přepojování propojení - změna topologie za běhu
  • Často implementují sdílenou paměť. (Statické sítě jsou bez sdílené paměti.)

Křížový přepínač (crossbar)
- v jednom okamžiku propojení p prvků
- neblokující
	• Průměr - 1
	• Konektivita - 1
	• Šířka bisekce - p

Sběrnice (bus)
• propojení pouze 2 prvků v jednom okamžiku
• Blokující
Algoritmy
• Lineární Enumeration Sort - používá sběrnici.

Víceúrovňové sítě
• spojují p procesorů s p paměťovými moduly pomocí p/2∗log(p) přepínačů.
• mohou blokovat i pokud různé procesory přistupují k různým pamětem (souboj o přepínače)