Toggle Dark-Mode
Zrychlení
> 1 = teoreticky nemůže nastat
v praxi:
není optimální sekvenční algoritmus
špatně spočítání procesorů (jsou v práci zapojeny jednotky, které přenáší věci do paměti)
změna = ostré uspořádání; NEjsou stejné prvky v posloupnosti
není konkrétní algoritmus, ale spíše typ algoritmů
každý prvek spočítá kolik prvků je menších a zapíše se na výslednou pozici
dělá se pomocí mřížky procesorů
počet procesorů je $p^2$ vůči
některé procesory dělají zbytečnou práci
některé zbytečně pracují, některé se flákají
lineární propojení procesorů
jako bubble sort - Ale velmi paralelizovaný!
lineární časová složitost!
speciální topologie
každý procesor má 2 vstupní kanály a 2 výstupní
na každém kanálu dostane 1 hodnoty, ty umí porovnat
na horní výstup L dá menší výstup
na dolní H dá větší
n x n
2 posloupnosti n do jedná posloupnosti 2n
2 sítě, n/2 * n/2
první síť dostane vždy liché, a druhá vždy sudé
nejmenší prvek je nejmenší, zbytek se musí porovnat
neumí nic seřadit, umí jen spojit!
→ musí se udělat kaskáda sítí 1x1, 2x2, 4x4, …
problém s počtem procesorů a časovou složitostí
čas: $O(\log ^2 n)$
cena: $O(n \cdot \log^4 n)$ - není optimální
předzpracování = každý procesor si svoji posloupnost seřadí svým optimálním algoritmem
následné spojování seznamů
pro počet procesorů, že levá strana $O((n \log n)/p)$ je závažnější, tak má optimální cenu (pro $p \leq \log n$)
natvrdo počet procesorů $p(n) = \log n + 1$ (měl by mít optimální cenu)lineární pole procesorů (uvnitř spojeny 2 komunikačními kanály)
paměť bude u procesorů, né u komunikačních linek
procesor očekává 2 kratší seřazené procesory a spojí je do větších posloupnosti
střídá výstup nahoře a dole
první procesor dává posloupnost jeden prvek na střídačku nahoru a dolů
poslední taky jiný
procesory začínají práci v různé okamžiky a končí práci v různé okamžiky
procesor můe začít pracovat, pokud na 1 vstupu má celou posloupnost a na druhé má aspoň jeden prvek!
nejdřív se musí zpracovat daná “dvojice” než jde na další
pokud začne spojovat 2 posloupnosti musí nejdřív dokončit!
jiná architektura!
sběrnice = procesor může přenést jednu hodnotu přenést lib. procesoru, ale pouze jednomu! - dost podobné moderní architektuře pckaždý procesor registr X (prvek který se stará) a Y (postupně všechny prvky), C (registr s počtem prvků menších než daný prvek)
není optimální cena $O(n^2)$
podle zapojení stoupá s počtem procesorů
procesory v 2D mřížce = $O(\sqrt{n})$
procesory v 3D
čas: $O(n)$ = platí, ale pouze pokud sběrnice má konst. čas složitost - od určitého počtu procesorů, nestihne dojít v 1 cyklu (např. počet proc. $> 1000$)