-
Analýza algoritmů
- počet procesorů: p(n)
- čas k řešení úlohy v krocích: t(n)
- cena paralelního řešení: c(n) = p(n) * t(n)
-
Optimální cena
c(n)optim = tseq(n)
-
Zrychlení, efektivnost, složitost
- tseq(n) / t(n)
- tseq(n) / c(n)
- počet procesorů
-
Počet procesorů
- Počet procesorů p je odvozen on délky vstupu n.
- p(n) = {1, c, log(n), n, n.log(n), n2, ..., nr, rn}
-
Optimální sekvenční algoritmus - platí pro řadicí
- Algoritmy založené na porovnávání prvku.
- p(n) = 1
- t(n) = O(n.log n)
- c(n) = O(n.log n)
-
Algoritmy řazení
- Enumeration sort
- Odd-even transposition sort
- Odd-even merge sort
- Merge-splitting sort
- Pipeline Merge sort
- Minimum Extraction sort
- Bucket sort
- Median Finding and Splitting
-
Enumeration sort
- Princip: výsledná pozice prvku je dána počtem prvků, které jsou menší
- Topologie: mřížka n krát n, řádky a sloupce jsou binární stromy v poli
- Procesory: registry A, B, RANK
- t(n) = O(log n)
- p(n) = n2
- c(n) = O(n2. log n), což není optimální
-
Odd-even transposition sort
- Princip: paralelní bubble-sort, porovnávají se jen sousedé a mohou se přehodit
- Topologie: lineární pole n procesorů
- Procesory: obsahují jediný registr s hodnotou prvku
- t(n): O(n)
- p(n): n
- c(n): O(n2), což není optimální
-
Odd-even merge sort
- Princip: řadíme posloupnost o délce n=2m
- Topologie: kaskáda sítí 1x1, 2x2, 4x4, ...
- Procesory: 2 vstupy a 2 výstupy, porovná vstupy a dá na výstupy high a low
- t(n): O(m2) = O(log2n)
- p(n): n.log2n
- c(n): O(n.log4n)
-
Merge-splitting sort
- Princip: varianta odd-even sortu, každý procesor řadí krátkou posloupnost
- Topologie: lineární pole procesorů p(n) < n
- Procesory: obsahují m prvků, které umí seřadit optimálním sekvenčním algoritmem
- c(n) = O(n.log(n)) + O(n.p), optimální pro p =< log(n)
-
Pipeline Merge sort
- Princip: rozděleno na několik kroků, první spojuje posloupnosti délky 1, pak 2, atd.
- Topologie: linární pole procesorů p(n) = log(n) + 1
- Procesory: umí spojovat dvě seřazené posloupnosti O(n)
- t(n): O(n)
- c(n): O(n).O(log(n) + 1) = O(n.log(n)), což je optimální
-
Minimum Extraction sort
- Princip: stromem odebírá vždy nejmenší prvek
- Topologie: strom s n listy, log(n) + 1 úrovněmi a 2n − 1 procesory
- Procesory: listový procesor obsahuje prvek posloupnosti, nelistové prvky umí porovnat syny
- t(n): O(n)
- c(n): O(n2), což není optimální
-
Bucket sort
- Princip: stromem spojené procesory, které řadí menší posloupnosti a pak spojení
- Topologie: strom s m listy, kde n = 2m
- Procesory: listové procesory řadí krátkou posloupnost, ostatní spojují syny – O(n)
- t(n): O(n)
- c(n) = O(n.log(n)) – optimální
-
Median Finding and Splitting
- Princip: dělí posloupnost mediánem až na dvojice, které porovná
- Topologie: strom s m listy, kde n = 2m
- Procesory: listové procesory porovnají dvojici, ostatní vyberou medián a rozdělí posloupnost – O(n)
- t(n): O(n)
- c(n): O(n.log(n)) – optimální
-
Select (medián)
- Sequential select
- Parallel select
- Parallel splitting
-
Sequential select
- Princip: hledá k-tý nejmenší prvek v posloupnosti S; je-li k=|S|/2, jde o medián
- t(n) = O(n)
-
Parallel select
- Princip: k-tý nejmenší prvek v posloupnosti S; EREW PRAM s N procesory P1..Pn; používá sdílené pole M o N prvcích
- t(n): O(n/N) pro n > 4, N < n/log n
- p(n): N
- c(n): t(n).p(n) = O(n), což je optimální
-
Parallel splitting
- Krok 4 algoritmu Parallel select
- t(n): O(log N + n/N) = O(n/N) pro dostatečně malé N
- c(n): O(n), což je optimální
-
Řazení na SIMD bez společné paměti
|
|
