Parallel Algorithms: Difference between revisions

* Spawn creates threads

* Threads expire at Join

* <code>$</code> represents the number of the thread

* <code>PS Ri Rj</code> is an atomic prefix sum

** Stores Ri + Rj in Ri

** Stores the original value of Ri in Rj

* exclusive-read exclusive-write (EREW)

* concurrent-read exclusive-write (CREW)

* concurrent-read concurrent-write (CRCW)

** Arbitrary CRCW - an arbitrary processor writing succeeds

** Priority CRCW - the lowest numbered processor writing succeeds

** Common CRCW - writing succeeds only if all processors write the same value

* Does not reveal how the algorithm will run on PRAMs with different number of proc

* Fully specifying allocation requires an unnecessary level of detail

* Other resources call this Brent's theorem

* <math>x</math> is the work and <math>d</math> is the depth

* A parallel algorithm is ''work-optimal'' if W(n) grows asymptotically the same as T(n).

* A work-optimal parallel algorithm is ''work-time-optimal'' if T(n) cannot be improved by another work-optimal algorithm.

* If T(n) is best known and W(n) matches it, this is called ''linear-speedup''

* Good serial algorithms: Poly time

* Good parallel algorithm: poly-log <math>O(\log ^c n)</math> time, poly processors

* Prefix sum

* Largest element

* Nearest-one element

* Compaction

* Array A[1..n] of elements

* Associative binary operation, denoted * (e.g. addition, multiplication, min, max)

* Array B containing B(i) = A(1) * ... * A(i)

* Merging: Given two sorted arrays, A and B, create a sorted array C consisting of elements in A and B

* Ranking: Given an element x, find <math>Rank(x, A) = i</math> defined such that <math>A(i) \leq x \leq A(i+1)</math>

** Note the book sometimes uses <math>Rank(i,B)</math> to denote <math>Rank(A(i), B)</math>.

* Given an algorithm for merging, we know A(i) belongs in C(j) so Rank(A(i), B) = j-i

* Given an algorithm for ranking, we get A(i) belongs in C(j) where j = Rank(A(i), B) + i

* Partition the input into p jobs of size approx. n/p

* Do small jobs concurrently using a separate (possibly serial) algo for each.

* We do not need to compute A_end or B_end. Just continue merging until we hit some index where (i % x)=0 in A or B.

* Algo A: <math>W_1(n)</math> work, <math>T_1(n)</math> time

* Algo B: Work <math>W_2(n) > W_1(n)</math>. Time <math>T_2(n) < T_1(n)</math>. Faster but less efficient.

* Algo 1 runs in <math>O(\log n)</math> iterations each taking <math>O(\log n)</math> time and <math>O(n)</math> work. Each iteration reduces the size to (3/4)m.

* Algo 2 runs in <math>O(\log n)</math> time and <math>O(n\log n)</math> work.

* Run Algo 1 for <math>O(\log \log n)</math> rounds then run algo 2.

** Total time is <math>O(\log n \log \log n)</math> and work is <math>O(n)</math>

* Partition elements into rows of <math>\log n</math> size

* For each row, find the median within the row

* Find the median of medians (MoM) in <math>O(n)</math>

* Put all rows with median <= MoM above and all rows with median >= Mom below

* Now <math>m/4</math> elements are smaller and <math>m/4</math> are larger

** Known as the reducing lemma

; Accelerating Cascades

* What we have:

** Algorithm 1 has <math>O(\log n)</math> iterations.  

:: Each iteration reduces a size m instance in <math>O(\log m)</math> time and <math>O(m)</math> work to an instance of size <math>\leq 3m/4</math>

** Algorithm 2 runs in <math>O(\log n)</math> time and <math>O(n \log n)</math> work.

* Step 1: Use algo 1 to reduce from n to <math>n / \log n</math>

* Step 2: Apply algorithm 2

* Partition A into n/r subarrays <math>B_1,...,B_{n/r}</math>

** Sort each subarray separately using serial bucket sort (counting sort)

** Compute number(v,s)  # of elements of value v in <math>B_s</math> for <math>0\leq v \leq r-1</math> and <math>1 \leq s \leq n/r</math>

** Compute serial(i) = # of elements in the block <math>B_s</math> such that A(j)=A(i) and <math> j < i </math> <math>1 \leq j \neq n</math>

* Run prefix sum on number(v,1),number(v,2),...,number(v,n/r) into ps(v,1), ps(v,2),..., ps(v,n/r)

* Compute prefix sums of cardinality(0),.., cardinality(r-1) into global_ps(0),...,global_ps(r-1)

* The rank of element <math>i</math> is <math>1+serial(i)+ps(v,s-1)+global_ps(v-1)</math>

* Step 1:<math>T=O(r),\;W=O(r)</math> per subarray.

** Total: <math>T=O(r),\; W=O(n)</math>

* Step 2: <math>r</math> computations each <math>T=O(\log(n/r)),\; W=O(n/r)</math>

** Total <math>T=O(\log n),\; W=O(n)</math>

* Step 3: <math>T=O(\log r),\; W=O(r)</math>

* Step 4: <math>T=O(1)\; W=O(n)</math>

* Total: <math>T=O(r + \log n),\; W=O(n)</math>

* Running time is not poly-log

* The integer sorting algorithm runs in <math>O(r+\log n)</math> time and <math>O(n)</math> work

* The integer sorting algorithm can be applied to run in time <math>O(k(r^{1/k}+\log n))</math> and work <math>O(kn)</math>

* Each node has 2-3 ordered children

* For any internal node, every directed path to a leaf is the same length

* ''search(a)''

* ''insert(a)''

* ''delete(a)''

* Deletion: discard(a)

** Delete connection between a and parent of a

** If parent has 1 child

*** If parent's sibling has 2 children, move child to sibling and discard(parent)

*** If parent's sibling has 3 children, take one child from sibling

* 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>.

** 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.

* 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)

** Time is <math>O(\log n \log k)</math> without pipelining

** With pipelining, complexity is <math>O(\log n + \log k)</math>

* There are <math>\log k</math> waves of the absorb procedure.

* Apply pipelining to make the time <math>O(\log n + \log k)</math>

* Compare every pair of elements in A[1...n]

* Split A into <math>\sqrt{n}</math> subarrays

* Find the max of each subarray recursively

* Find the max of all subarrays in <math>O(n)</math> using the constant time algo

* <math>T(n) \leq T(\sqrt{n}) + c_1</math>

* <math>W(n) \leq \sqrt{n}W(\sqrt{n}) + c_2 n</math>

* <math>T(n) = O(\log \log n)</math>, <math>W(n) = O(n\log \log n)</math>

* Step 1: Partition into blocks of size <math>\log \log n</math>. Then we have <math>n/ \log \log n</math> blocks.

** Apply serial linear time algorithm to find maximum of each block

** <math>O(\log \log n)</math> time and <math>O(n)</math> work.

* Step 2: Apply doubly log algorithm to <math>n / \log \log n</math> maxima.

** <math>O(\log \log n)</math> time and <math>O(n)</math> work.

* Step 1: Using aux array B of size <math>b^{7/8}</math>. Independently fill with random elements from A

* Step 2: Find the max <math>m</math> in array B in <math>O(1)</math> time and <math>O(n)</math> work

** Last 3 pulses of the recursive doubly-log time algorithm:

** Pulse 1: B is partitioned into <math>n^{3/4}</math> blocks of size <math>n^{1/8}</math> each. Find the max of each block.

** Pulse 2: <math>n^{3/4}</math> maxima are partitioned into <math>n^{1/2}</math> blocks of size <math>n^{1/4}</math> each.

** Pulse 2: Find the max m of <math>n^{1/2}</math> maxima in <math>O(1)</math> time and <math>O(n)</math> work.

* Step 3: While there is an element larger than m, throw the new element into an array of size <math>n^{7/8}</math>.

: Compute the maximum of the new array.

* Step 1 takes <math>O(1)</math> time and <math>O(n^{7/8})</math> work

* Step 2 takes <math>O(1)</math> time and <math>O(n)</math> work

* Each time Step 3 takes <math>O(1)</math> time and <math>O(n)</math> work

* With high probability, we only need one iteration (see theorem below) so the time is <math>O(1)</math> and work is <math>O(n^{7/8})</math>

{{ hidden | Proof |

* Vector of vertices which point to an index in edges

* Vector of edges e.g. (1,2)

* Vector of pointers to identical edges e.g. index of (1,2) -> index of (2,1)

* A vertex <math>r</math>

* Select a direction for each edge to make our graph a tree with root <math>r</math>

* Step 1: For every edge <math>(u,v)</math>, add two edges <math>u \rightarrow v</math> and <math>v \rightarrow u</math>

* Step 2: For every directed edge <math>u \rightarrow v</math>, set a pointer to another directed edge from <math>v</math>, <math>next(u \rightarrow v)</math>

** If our edge is 1 -> 2, then the next edge is the immediate next edge of edge 2->1 in our edges array  

** If edge 2 -> 1 is the last edge coming out of 2, then the next edge is the first edge coming out of 2

** Now we have an euler cycle (or euler tour) among the edges

* Step 3: <math>next(u_{r,1} \rightarrow r) = NIL </math>

* Step 4: Apply a list ranking algorithm to the edges.

* Step 5: Delete the edge between every two vertices with the lower ranking

* Every step except 4, list ranking, is a local operation which is constant time and linear work

* Requires a list ranking algorithm

* Step 1: For every edge pardo, if e is a tree edge, distance(e) = 1 else distance(e) = 0

* Step 2: List ranking

* Step 3: For every edge e: u->v, preorder(v) = n-distance(e) + 1

* Each element will eventually point to the cashier

* Distance will always be correct

** If next[i] = NIL then distance is to the cashier

** Otherwise the distance is <math>2^k</math>

; Complexity

* <math>O(log (n) log log (n)) time</math>

* <math>O(n)</math> work

* Assign each element a unique tag, such as the index in the array

* Convert the tag to binary. For each element i, tag(i)!=tag(next(i)).

* Let k be the index of the rightmost bit (where 0 is the rightmost bit) differing between tag(i) and tag(next(i))

* Let b be the bit in tag(i) differing from tag(next(i))

* Set the new tag to <code>(k<<1) + b</code>

* ''Uniform Density'' If node <math>i</math> is not in S, then one of the <math>r</math> nodes following i will be in <math>S</math>

* ''Uniform Sparcity'' If node <math>i</math> is in <math>S</math> then node <math>next(i)</math> is not in <math>S</math>

# Apply the deterministic coin tossing algorithm to give each element a tag in <math>[0,...,2*\log n - 1]</math>

# For each element i in parallel, if i is a local maximum then add it to <math>S</math>

* No two leaves have the same parent (stem)

* The parent of a stem cannot be the stem of another leaf

* Number leaves according to a DFS using the Euler tour algorithm.<br>

* Let <math>S_1</math> be nodes in <math>S</math> whose parents are not in <math>S</math>.

; Let <math>L_1</math> be leaves in <math>L</math> whose parents are in <math>S_1</math>.

* Apply parallel rakes to leaves in <math>L_1</math>, unless the parent is the root.

* Apply parallel rakes to leaves in <math>L - L_1</math>, unless the parent is the root.

* Repeat Step 2 until the tree is a 3-node binary tree

* Pointer Graph

* Supervertices

* The supervertex graph

* Hookings

* Parallel pointer jumping

* Hookings - Each root hooks itself the the minimal adjacent root. If there are no adjacent stars, then this rooted star quits.

* Parallel pointer jumping - Each vertex performs pointer jumping until every vertex points to the root, forming a rooted star.

# The pointer graph always consists of rooted trees.

# After <math>\log n</math> iterations, all vertices are contained in rooted stars that quit.

#: Each connected component is represented by a single rooted star.

* We need <math>O(\log n)</math> iterations

** Hookings take <math>O(1)</math> time and <math>O(n+m)</math> work

** Pointer jumping takes <math>O(\log n)</math> time and <math>O(n\log n)</math> work

* For adjacency matrix, in total we need <math>O(\log^2 n)</math> time and <math>O(n^2\log n)</math> work since we have a processor per <math>n^2</math> possible edges.

* For incidence lists, we need <math>O(\log^2 n)</math> time and <math>O(n\log^2 n + m\log n)</math> work since we have a processor per edge.

# Probe quitting: each rooted star whose supervertex is not adjacent to any other quits

# Hooking on smaller: each rooted star hooks onto a smaller vertex of another supervertex which is not a leaf

#* Note that this is not unique. Requires arbitrary CRCW.

# Hooking non-hooked-upon: every rooted star not hooked upon in step 2 hooks to another vertex in another supervertex which is not a leaf

# Parallel pointer jumping: one round of parallel pointer jumping

* The pointer graph always consists of rooted trees.

* For every vertex which is not a leaf, <math>D(v) \leq v</math>

* Time <math>O(\log n)</math>

* Work <math>O((n+m)\log n)</math>

{{ hidden | Proof |

 

* MTCU - Master Thread Control Unit - runs in serial mode

* TCU Cluster - Thread Control Unit

* Spawn broadcasts your spawn code in the block to every thread control unit (TCU).

* Data is shared through the interconnection network

* <math>LSTRM</math> - length of sequence of round trips to memory

* <math>R</math> - time for round trip to memory

* <math>QD</math> - queuing delay

** If multiple threads access the same memory module, they are queued at the memory module

* [https://stanford.edu/~rezab/dao/ Stanford CME323 Distributed Algorithms Lectures 1-3]

* [http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf Uzi Vishkin ENEE651/CMSC751 Classnotes]

* [https://www.amazon.com/Introduction-Parallel-Algorithms-Joseph-JaJa/dp/0201548569?sa-no-redirect=1&pldnSite=1 Introduction to Parallel Algorithms (Joseph Jaja, textbook)]

* [https://www.cs.cmu.edu/~guyb/papers/BM04.pdf Parallel Algorithms by Guy E. Blelloch and Bruce M. Maggs (CMU)]