PRL 32. Distribuované a paralelní algoritmy - algoritmy řazení, select.

Card Set Information

Author:
hrbi
ID:
223256
Filename:
PRL 32. Distribuované a paralelní algoritmy - algoritmy řazení, select.
Updated:
2013-06-10 18:07:33
Tags:
prl
Folders:

Description:
szz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. 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)
  2. Optimální cena
    c(n)optim = tseq(n)
  3. Zrychlení, efektivnost, složitost
    • tseq(n) / t(n)
    • tseq(n) / c(n)
    • počet procesorů
  4. 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}
  5. 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)
  6. 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
  7. 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í
  8. 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í
  9. 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)
  10. 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)
  11. 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í
  12. 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í
  13. 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í
  14. 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í
  15. Select (medián)
    • Sequential select
    • Parallel select
    • Parallel splitting
  16. Sequential select
    • Princip: hledá k-tý nejmenší prvek v posloupnosti S; je-li k=|S|/2, jde o medián
    • t(n) = O(n)
  17. 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í
  18. 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í
  19. Řazení na SIMD bez společné paměti

What would you like to do?

Home > Flashcards > Print Preview