43 - Základní typy topologií paralelních a distribuovaných architektur a jejich vlastnosti Flashcards
Komunikace mezi procesory
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í.
SDÍLENÁ PAMĚŤ A PŘEDÁVÁNÍ ZPRÁV U MIMD
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
Topologie a propojovací sítě
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.
Statické propojovací sítě
Ú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
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.)
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)