5,337
edits
Parallel Algorithms: Difference between revisions
→Parallel Algorithms
| Line 245: | Line 245: | ||
====Parallel Algorithms==== | ====Parallel Algorithms==== | ||
Assume concurrent read model | Assume concurrent read model | ||
* Insert: Suppose | * Insert: Suppose we want to insert sorted elements <math>c_1,...,c_k</math> into a tree with n elements. | ||
** Insert element <math>c_{k/2}</math>. | ** Insert element <math>c_{k/2}</math>. | ||
** Then insert in parallel <math>(c_1,...,c_{k/2-1})</math> and <math>(c_{k/2+1},...,c_k)</math> | ** Then insert in parallel <math>(c_1,...,c_{k/2-1})</math> and <math>(c_{k/2+1},...,c_k)</math> | ||
** Time is <math>O(\log k \log n)</math> using <math>k</math> processors. | ** Time is <math>O(\log k \log n)</math> using <math>k</math> processors. | ||
* Deletion: Suppose we want to delete sorted elements <math>c_1,...,c_k</math> | |||
** Backwards Insertion | |||
** for t=0 to <math>\log k</math> | |||
*** if <math>i \equiv 2^t (\operatorname{mod}2^{t+1})</math> | |||
**** discard(c_i) | |||
===Pipelining=== | ===Pipelining=== | ||