parallel algorithm course 06

reiview

\(T_1(n)=O(n)\)

\(T_\infty(n)=O(log^k(n))\)

model: shared memory model

---

core alg

• map \(\text{n}\to \text{n}\)

• reduce \(\text{n} \to 1\)

• scan: compact (based on scan)

• list ranking

• sort alg

• radix sort, sample sort

goal

• complexity optimal

• dependency –

• symetric – (symetry: hard to find independency) using rand (find independent set) or odd-even

thinking

• case to general

• forward-backward

• bit-wise thinking

• matrix thinking

pattern

• divide and conquer

• independent set

• random

• jump

OpenMP

• pipeline: serial \(\to\) independent \(\to\) group \(\to\) parallel

• data racing, using syncronization

• Pseudo random number generator