3577880
| Question | Answer |
| Druhy taxonomií par. struktur | z hlediska: - toků instrukcí a dat - organizace paměti - propojovacích sítí |
| Paralelní architektury z hlediska toků instrukcí a dat (2) a rozdíly mezi nimi | SIMD (implicitně synchronizovaný) – všechny procesory provádějí stejné instrukce (nebo nic – např. při větvení programu) MIMD (musí se expl. synchr.) – procesory pracují asynchronně ! jsou asympt. výpočetně ekvivalentní = alg. pro jednoho jde simulovat na druhém |
| Par. arch. z hlediska organizace paměti (3) | - sdílená paměť (SMP, UMA) - read/write - distribuovaná paměť (NUMA) - každý má svou paměť pro R/W, k ostatním procesorům posílá Send/Receive žádosti - virtuálně sdílená paměť (CacheCoherent-NUMA) - fyzicky je distribuovaná, virtualizace řeší komunikaci - procesor „neví, kam sahá“ |
| Par. arch. z hlediska propojovacích sítí | Pro sdílenou paměť - multiprocesorová sběrnice - křížová přepínač (~šachovnice) - nepřímá propojovací síť (~míň přepínačů) permutační síť Pro distr. paměť - 2D mřížka sběrnic - křížový přepínač - vícestupňová nepřímá prop. síť - přímá propojovací síť |
| RAM model | Random Access Machine - výpočetní jednotka s uživ. def. prog. - páska pro vstupy a páska pro zápis - neomezený počet pam. buněk - všechny instrukce trvají konstantní čas časová složitost alg. = #provedených instr. prostorová složitost alg. = #použitých paměťových buněk |
| PRAM model | Parallel Random Access Machine model - neomezený # procesorů RAM - neomezený # sdílených paměťových buněk -každý P má soukromou paměť a zná svůj index - každý P může přistupovat do sdíl. pam. v konst. čase - 3 typy instrukcí: čtení, lokální op., zápis - komunikace přes R/W sdílené pam. - P1 má aktivační registr pro active/idle procesory |
| Co znamená (n,p) pro PRAM? | p = # aktivních procesorů n = prostorová složitost = # použitých buněk sdílené paměti |
| Co je paralelní časová složitost? | čas výpočtu na P1 výpočet trvá, dokud se P1 nezastaví (ostatní skončily) - jednotkový model: R/W/L trvají čas 1 globální model: R/W trvají d>1, L trvá čas 1 |
| K čemu je PRAM model? | slouží jako zkušební model - jestliže nějaký problém nemá rozumné řešení na PRAM, nemá rozumné řešení na jiném par. stroji - je idealizací existujících par. počítačů se sdílenou pam. |
| Typy ošetření konfiktů při přístupech do sdílené paměti | - Exclusive Read Exclusive Write (EREW) PRAM: žádné 2 procesory nesmějí R/W do téže pam. buňky najednou. - Concurrent Read Exclusive Write (CREW) PRAM: současná čtení téže pam. buňky povolena, ale jen 1 proc. smí zapisovat - Concurrent Read Concurrent Write (CRCW) PRAM: Povoleny zápisy i čtení najednou více procesorům |
| Jak se řeší zápis při CRCW? | – prioritní: procesory mají pevnou prioritu a ten s nejvyšší zapisuje – náhodný – shodný: povolí zápis všem, pokud mají stejnou hodnotu (řeší algoritmus) |
| Výpočetní síla podmodelů PRAM | Priority ≥ Arbitrary ≥ Common ≥ CREW ≥ EREW A ≥ B znamená, že A je výpočetně silnější než B, jakýkoliv alg. napsaný pro B poběží beze změny na A s tímtéž par. časem (předpokl. stejné arch. parametry) |
| Kdy je algoritmus plně paralelní? | Jestliže T(n,p) = O(1) && C(n,p) = O(SU(n)) <=> p = O(SU(n)) |
| Věta o simulaci velkých PRAM na menších PRAM stejného typu (méně procesorů), zachovávající paralelní cenu | Necht’ A je PRAM(n, p) algoritmus s časem t = T(n, p) a necht’ p' < p. Pak A lze simulovat pomocí PRAM(n, p') algoritmu na PRAM téhož typu v čase T(n, p') = O(tp/p'). Pozn.: simulující proc. potřebuje p/p'krát víc soukr. paměti než simulovaný Pozn#2: je třeba speciálně ošetřit write u Priority CRCW |
| Každý PRAM(n,p) alg. s cenou C(n,p) lze provést sekvenčně v jakém čase? | t = O(C(n,p)) |
| Věta o simulaci velkých PRAM na malých PRAM téhož typu (s malou pamětí) | Necht’ A je PRAM(n, p) algoritmus s časem t a necht’ m < n. Pak A lze simulovat PRAM(m, max(p, m)) algoritmem na PRAM téhož typu v čase t' = O(tn/m). Předpokl., že simuljící procesory mají dostatečně velké lok. paměti pro uložení sdílených dat. |
| Simulace CRCW s prioritním systémem (čím nižší ID proc. tím vyšší priorita) na EREW | Jeden krok P-CRCW-PRAM(n,p) algoritmu lze simulovat pomocí EREW-PRAM(n*p,p) algoritmu v O(log p) krocích (když chtějí přistoupit do paměti, vloží požadavek do pomocného pole každé pam. buňky, které je organizováno jako bin. strom, odtud ke kořeni probublá výherce) druhá verze potřebuje jen n+3p paměti navíc, vkládá se č. procesoru, č. buňky, pak se to lex. seřadí v log čase a pokračuje to velkou magií, slajdy 31+ |
| Co znamená, že je PRAM algoritmus s polylogaritmickým časem robustní vzhledem k PRAM robustní? | Má-li polylogaritmický čas na jednom modelu PRAM, bude mít polylogaritmický čas na kterémkoli jiném |
| Co je to APRAM? | Asynchronní PRAM -neexistují centrální hodiny - operace R/W/L jako na PRAM - nutná explicitní – bariérová – synchronizace - doba přístupu do pam. není jednotková APRAM výpočet = posloupnost globálních fází, ve kt. proc. pracují asynch., oddělených barier. synchr. - 2 proc nemohou přistupovat do téže buňky sdíl. pam. v téže glob. fázi, pokud jeden z nich zapisuje |
| Výkonostní parametry APRAM lokální operace, globální R/W, k po sobě jdoucích globálních R/W, bariérová synchronizace | lokální operace: 1 globální R/W: d k po sobě jdoucích glob. R/W: d+k-1 bariérová synchronizace: B(p) - d a B jsou neklesajícími funkcemi p - přepokládáme, že 2 ≤ d ≤ B(p) ≤ p, ale v praxi je B(p) = O(d log p) nebo B(p) = O(d log p/ log d). - po sobě jdoucí globální R/Ws jsou zřetězeny |
| Implementace bariéry (APRAM) pomocí centrálního čítače | Centrální čítač inicializovaný na 0 a na příchozí fázi, procesy přistupují ve vzájemném vyloučení 1 Proces dorazí k bariéře, zkontroluje, zda je v příchozí fázi a inkrementuje čítač 2 Je-li čítač < p, deaktivuje se. 3 Jinak nastaví bariéru do odchozí fáze a aktivuje ostatní procesy. 4 Poslední aktivovaný proces nastaví bariéru do příchozí fáze 5 B(p) = Θ(dp) |
| Implementace bariéry (APRAM) pomocí binárního redukčního stromu | Každý proces: 1 dorazí k bariéře a zkontroluje, zda je v příchozí fázi, 2 čeká, až skončí redukce v jeho podstromu, 3 po jejím skončení pošle signál rodiči 4 kořen stromu počká na redukci z obou podstromů a přepne do odchozí fáze, 5 procesy se aktivují ve zpětném pořadí 6 B(p) = Θ(d log p) |
| Simulace PRAM na APRAM | - triviální - za každou glob. R a W vlož bariéru - nezachovává operační složitost Jeden PRAM cyklus <RLW> lze na APRAM simulovat v čase 2B(p) + 2d + 1 = O(B(p)). - operace zachovávající operační složitost EREW PRAM algoritmus mající čas t při použití p procesorů lze simulovat na APRAM v čase O(B(p) * t) s p/B(p) procesory. |
Want to create your own Flashcards for free with GoConqr? Learn more.