parallel algorithm course 05

parallel algorithm
note
Author

furyton

Published

April 6, 2022

linked list

omp task

array pool

use array to simulate linked list

e.g. 1

find prev using next

e.g. 2

find index

prev

jump

repeat:
par-for i from 0 to n-1:
    if NULL: continue
    if prev[i] != empty:
        rank[i] += rank[prev[i]] # initial all 1 except head is 0
        prev[i] = prev[prev[i]] # use 2 copies to avoid data racing

\(T_1(n)=O(n\cdot log(n))\)

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

Wyllie’s Alg: jump

e.g. Tree

similar: binary lifting

improve Wyllie’s Alg

\(O(n\cdot log(n))\rightarrow O(n)\)

  • step 1: shrink \(n\rightarrow m\)

  • step 2: call Wyllie’s Alg \(O(m\cdot log(m))\)

  • step 3: restore \(m\rightarrow n\)

target \(m\rightarrow \frac{n}{log(n)}\)

independent set \(\forall i \in I,N(i) \notin I\)

symetry break

  • random flip coin, keep or remove

  • resolve confict

# producing independent set

par-for i=1..n
    F[i] = RND(0 or 1)
par-for i=1..n
    if F[i]=F[N[i]]=1: # data racing. need 2 copies
        F[i] = 0

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

\(T_\infty(n)=O(1)\)

\(\mathbb{E}|I|=\frac{n}{4}\)

\([n]/I\rightarrow \frac{3}{4}n\) repeat \(loglog(n)\) times \(\frac{n}{log(n)}\)

  1. initialized with 1 except head

  2. repeatedly remove an independent set \(S\) til #rest=\(\frac{n}{logn}\) (change next[prev[i]] to next[i], add counter[i] to counter[next[i]] forall \(i\in S\))

  3. call Wyllie’s Alg

  4. reverse

quick sort: choose 1 pivot, sample 1

v.s.

sample sort: randomly choose \(p-1\) pivots, sample \(k\cdot p+1\)

compact operator