- (často se dělá na topologii kostky)
- pokud alespoň jedna je
- pokud je více, tak preferovanou hodnotu (např menší)
- pokud není nic = “je v klidu”
- časová složitost: $O(n)$
- počet procesorů: $O(2n-1)$
- cena: $O(n^2)$ → není optimální
- podobné jako předchozí, ale uzly udržují více prvků, které sekvenčně seřadí
- listových procesů je $\log n$
- $r = \frac{n}{\log n}$
- $O(r \log r) = O(\frac{n}{\log n} \log (\frac{n}{\log n})) = O(\frac{n}{\log n} (\log n - \log (\log n))) = O(n - \frac{n}{\log n} \log(\log n))$
- druhá část velmi malá, jde k lineární složitosti
- logaritmický počet procesorů → je optimální
- “paralelní verze algoritmu quicksort”
- “nášlapný granát jak sviňa”
- v listech sekvenční sort
- potřeba najít v dobrém čase medián
- Medián mediánu - není hledaný medián, ale je to podobné
- EREW - exclusive read exclusive write
- PRAM
- První procesor zapíše nejdříve množinu $Less$ na začátek
- další procesor si spočítá $|Less|$ všech předchozích procesů a pak zapíše svůj $Less$
- První procesor zapíše $Equal$ množinu až na pozici která je součet velikostí všech $Less$ množin $= \sum_i |Less_i|$
- záleží jestli je seřazená nebo ne
- JE seřazená → $t(n) = O(n)$ a $c(n) = O(n)$
- NENÍ seřazená → $t(n) = O(\log n)$ a $c(n) = O(\log n)$
- počet procesorů $N$
- posloupnost rozdělíme na $N+1$ částí
- každý procesor zjistí, jestli prvek je za hranicí dané posloupnosti daného procesoru
- $g = \left\lceil \frac{ \log (n+1) }{ \log (N+1) } \right\rceil = \left\lceil \log_{N+1}(n+1) \right\rceil$
- “nášlapná mina”: EREW 1.krok $O(\log N)$
-
- krok = čtení
-
- krok = zápis
- každý jeden listový uzel má 1 hodnotu
- $n \times n$ procesů
- data cestují nejdříve do prvku na diagonále a pak do koncového prvku
- $90 \degree$ cesta
- zároveň obsahují cílový prvkem (kam cestují), není na slidech…
- $n$ je počet řádků / sloupců
- není optimální
- každé zápis i čtení je jinde, takže je to v pohodě
- $t(n) = O(n)$ (ale se zpožděním)
- synchronní model paralelního výpočtu
- sdílená paměť (komunikace procesorů)
- všechny stroje vykonávají stejný program, synchronní práce
- Na zkoušce:
- or s Common - dáme 0 a
or se všemi
- and -||- 1 a
and
- xor - neuděláme v jednom kroku, musí být stromeček
- u EREW problém souběhu čtení