Two closely related models of parallel computation.
Circuits
Logic gates (AND/OR/not) connected by wires
important measures
number of gates
depth (clock cycles in synchronous circuit)
PRAM
\(P\) processors, each with a RAM, local registers
global memory of \(M\) locations
each processor can in one step do a RAM op or read/write to one global memory location
synchronous parallel steps
not realistic, but explores “degree of parallelism”
Essentially the same models, but let us focus on different things.
Logic gates (AND/OR/not) connected by wires
important measures
number of gates
depth (clock cycles in synchronous circuit)
bounded vs unbounded fan-in/out
\(AC(k)\) and \(NC(k)\): unbounded and bounded fan-in with depth \(O(\log^k n)\) for problems of size \(n\)
\(AC(k) \subset NC(k) \subset AC(k+1)\) using full binary tree
\(NC=\cup NC(k)=\cup AC(k)\)
Addition
consider adding \(a_i\) and \(b_i\) with carry \(c_{i-1}\) to produce output \(s_i\) and next carry \(c_i\)
Ripple carry: \(O(n)\) gates, \(O(n)\) time
Carry lookahead: \(O(n)\) gates, \(O(\log n)\) time
preplan for late arrival of \(c_i\).
given \(a_i\) and \(b_i\), three possible cases for \(c_i\)
if \(a_i=b_i\), then \(c_i=a_i\) determined without \(c_{i-1}\): generate \(c_1=1\) or kill \(c_i=0\)
otherwise, propagate \(c_i=c_{i-1}\)
write \(x_i=k,g,p\) accordingly
consider \(3 \times 3\) “multiplication table” for effect of two adders in a row.
pair propagates previous carry only if both propagate.
| \(x_i\) | ||||
| \(k\) | \(p\) | \(g\) | ||
| \(k\) | \(k\) | \(k\) | \(g\) | |
| \(x_{i-1}\) | \(p\) | \(k\) | \(p\) | \(g\) |
| \(g\) | \(k\) | \(g\) | \(g\) |
Now let \(y_0=k\), \(y_i = y_{i-1} \times x_i\)
constraints “multiplication table” by induction
| \(x_i\) | ||||
| \(k\) | \(p\) | \(g\) | ||
| \(k\) | \(k\) | \(k\) | \(g\) | |
| \(y_{i-1}\) | \(p\) | \(k\) | never | \(g\) |
| \(g\) | \(k\) | \(g\) | \(g\) |
conclude: \(y_i=k\) means \(c_i=0\), \(y_i=g\) means \(c_i=1\), and \(y_i=p\) never happens
so problem reduced to computing all \(y_i\) in parallel
Parallel prefix
Build full binary tree
two gates at each node
pass up product of all children
pass down product of all \(x_i\) preceding leftmost child
works for any associative function
various conflict resolutions (CREW, EREW, CRCW)
\(CRCW(k) \subset EREW(k+1)\)
\(NC = \cup CRCW(k)\)
PRAMs simulate circuits, and vice versa
So \(NC\) well-defined
differences in practice
CRCW can OR in \(O(1)\) time
EREW requires \(\log n\) time (info theory lower bound)
EREW needs \(\log n\) to find max
CRCW finds max in constant time with \(n^2\) processors
Compare every pair
If an item loses, write “not max” in its entry
Check all entries
If item is max (not overwritten), write its value in answer
in \(O(\log\log n)\) time with \(n\) processors
Suppose \(k\) items remain
Make \(k^2/n\) blocks of \(n/k\) items
quadratic time max for each: \((k^2/n)(n/k)^2=n\) processors total
recurrence: \(T(k)=1+T(k^2/n)\)
\(T(n/2^i)=1+T(n/2^{2i})\)
so \(\log\log n\) iters.
parallel prefix
using \(n\) processors
list ranking EREW
next pointers \(n(x)\)
\(d(x)+=d(n(x))\); \(n(x)=n(n(x))\).
by induction, sum of values on path to end doesn’t change
Idea:
We’ve seen parallel algorithms that are somewhat “inefficient”
do more total work (processors times time) than sequential
Ideal solution: arrange for total work to be proportional to best sequential work
Work-Efficient Algorithm
Then a small number of processors (or even 1) can “simulate” many processors in a fully efficient way
Parallel analogue of “cache oblivious algorithm”—you write algorithm once for many processors; lose nothing when it gets simulated on fewer.
Brent’s theorem
Different perspective on work: count number of processors actually working in each time step.
If algorithm does \(x\) total work and critical path \(t\)
Then \(p\) processors take \(x/p+t\) time
So, if use \(p=x/t\) processors, finish in time \(t\) with efficient algorithm
detail: assigning processors to tasks can be tricky if e.g. work emerges dynamically during execution
Work-efficient parallel prefix
linear sequential work
going to need \(\log n\) time
so, aim to get by with \(n/\log n\) processors
give each processor a block of \(\log n\) items to add up
reduces problem to \(n/\log n\) values
use old algorithm
each processor fixes up prefixes for its block
Work-efficient list ranking
harder: can’t easily give contiguous “blocks” of \(\log n\) to each processor (requires list ranking)
However, assume items in arbitrary order in array of \(n\) structs, so can give \(\log n\) distinct items to each processor.
use random coin flips to knock out “alternate” items
shortcut any item that is heads and has tails successor
requires at most one shortcut
and constant probability every other item is shortcut (and independent)
so by chernoff, 1/16 of items are shortcut out
“compact” remaining items into smaller array using parallel prefix on array of pointers (ignoring list structure) to collect only “marked” nodes and update their pointers
let each processor handle \(\log n\) (arbitrary) items
\(O(n/\log n)\) processors, \(O(\log n)\) time
After \(O(\log\log n)\) rounds, number of items reduced to \(n/\log n\)
use old algorithm
result: \(O(\log n \log\log n)\) time, \(n/\log n\) processors
to improve, use faster “compaction” algorithm to collect marked nodes: \(O(\log\log n)\) time randomized, or \(O(\log n/\log\log n)\) deterministic. get optimal alg.
How about deterministic algorithm? Use “deterministic coin tossing”
take all local maxima as part of ruling set.
Euler tour to reduce to parallel prefix for
inorder traversal of tree
computing depth in tree
numbering leaves
work efficient
plus and times nodes.
Idea
merge leaves into parents (good for bushy tree)
pointer jump degree-2 nodes (good for tall trees)
combine?
how “pointer jump” an operator?
Generalize problem:
“product lookahead”
Each tree edge has a label \((a,b)\)
meaning that if subtree below evaluates to \(y\) then value \((ay+b)\) should be passed up edge
Merging a single leaf
method for eliminating all left-child leaves
root \(q\) with right child \(p\) (product node) on edge labelled \((a_3,b_3)\)
\(p\) has left child edge \((a_1,b_1)\) leaf \(\ell\) with value \(v\)
right child edge to \(s\) with label \((a_2,b_2)\)
fold out \(p\) and \(\ell\), make \(s\) a child of \(q\)
what label of new edge?
prepare for \(s\) subtree to eval on \(y\).
choose \(a,b\) such that \(ay+b=a_3\cdot[(a_1v+b_1)\cdot(a_2y+b_2)]+b_3\)
Parallelize
keep tree full, so killing all leaves kills whole tree
collapse a leaf and pointer jump parent
problem: can’t do to both children at once
solution: number leaves in-order (Euler Tour)
three step process:
shunt odd-numbered left-child leaves
shunt odd-number right-child leaves
divide leaf-numbers by 2
guarantees never simultaneously shunt siblings
Parallelizing binary search
placing one item into a sorted array takes \(\log n\) time with 1 processor
but with \(k\) processors can improve to \(\log_k n\)
compare to \(k\) evenly spaced items
use concurrent OR to find out which pair I’m between in \(O(1)\) time
recurse
shows how to gain parallel speed by wasting work
in particular, can find in \(O(1)\) time with \(n\) processors
or even \(\sqrt{n}\) processors
CREW Merge sort:
merge two length-\(k\) sequences using \(k\) processors
each element of first seq. uses binary search to find place in second
so knows how many items smaller
so knows rank in merged sequence: go there
then do same for second list
\(O(\log k)\) time with \(k\) processors
handle all length-\(k\) lists in parallel with \(n\) processors
total time \(O(\sum_{i \le \lg n} \log 2^i)=O(\log^2 n)\) with \(n\) processors
Better with more processors?
use \(n^2\) processors to do all pairwise comparisons in parallel
For each item, count number of wins in parallel in \(O(\log n)\) time
This determines item’s rank in output list
Use same ideas with fewer processors?
Note can sort \(\sqrt{n}\) items in \(O(\log n)\) time
Use insights to improve merge?
Idea: nearby items in one list go to nearby places in merged list
So don’t do whole computation for every item
Break \(A\) into blocks and figure out roughly where each block goes in \(B\)
Then spread each block to exact right places in \(B\) (recursively)
Details: merge \(n\) items of \(A\) into \(m\) items of \(B\) in \(O(\log\log n)\) time using \(m+n\) processors
choose \(\sqrt{n}\) evenly spaced fenceposts \(\alpha_i\) among \(A\)
use \(\sqrt{m}\) processors to find exact location of each in \(B\)
total processors \(\sqrt{nm}\le \le \max(n,m) \le n+m\)
split \(B\) at locations of \(\alpha_i\)
now know \(\sqrt{n}\) items (between \(\alpha_i\) and \(\alpha_{i+1}\)) go in each split piece of \(B\)
So recurse: \(T(n)=2+T(\sqrt{n})=O(\log\log n)\)
Use in parallel merge sort: \(O(\log n \log\log n)\) with \(n\) processors.
Cole shows how to “pipeline” merges, get optimal \(O(\log n)\) time.
Qsort idea
\(\sqrt{n}\) pivots
sort all in \(O(\log n)\) time using \(n\) processors
binary search each item to locate position in pivots
recurse
\(T(n) = O(\log n) + T(\sqrt{n}) = O(\log n)\)
rigorous analysis messy
need to deal with variation in sizes of subproblems
Linear time sequential trivial.
Squaring adjacency matrix
\(\log n\) time to reduce diameter to 1
\(mn\) processors for first iter, but adds edges
so, \(n^3\) processors
and space to \(n^2\) even if initial graph is sparse
improvements to \(mn\) processors
But “transitive closure bottleneck” still bedevils parallel algs.
Even if just want to find \(s\)-\(t\) path we don’t know any better
Problem is that output has size \(n^2\) and we don’t know which part of it matters.
Basic approach:
Sets of connected vertices grouped as stars
One root, all others parent-point to it
Initially all vertices alone
Edge “live” if connects two distinct stars
Find live edges in constant time by checking roots
For live edge with roots \(u<v\), connect \(u\) as child of \(v\)
May be conflicts, but CRCW resolves
Now get stars again
Use pointer jumping
Note: may have chains of links, so need \(\log n\) jumps
Every live star attached to another
So number of stars decreases by 2
\(m+n\) processors, \(\log^2 n\) time.
Smarter: interleave hooking and jumping:
Maintain set of rooted trees
Each node points to parent
Hook some trees together to make fewer trees
Pointer jump (once) to make shallower trees
Eventually, each connected component is one star
More details:
“top” vertex: root or its children
detect top vertex in constant time
each vertex has label
find root label of each top vertex
Can detect if am star in constant time:
no pointer double reaches root
for each edge:
If ends both on top, different nonstar components, then hook smaller index component to larger
may be conflicting hooks; assume CRCW resolves
indices prevent cycles
If star points to non-star, hook it
do one pointer jump
Potential function: height of live stars and tall trees
Live stars get hooked to something (star or internal)
But never hooked to leaf. So add 1 to height of target
So sum of heights doesn’t go up
But now, every unit of height is in a tall tree
Pointer doubling decreases by at least 1/3
Total height divided each time
So \(\log n\) iterations
Summary: \(O(m+n)\) processors, \(O(\log n)\) time.
Improvements:
\(O((m+n)\alpha(m,n)/\log n)\) processors, \(\log n\) time, CRCW
Randomized \(O(\log n)\), \(O(m/\log n)\) processors, EREW
Randomization in parallel:
load balancing
symmetry breaking
isolating solutions
Classes:
NC: poly processor, polylog steps
RNC: with randomization. polylog runtime, monte carlo
ZNC: las vegas NC
immune to choice of R/W conflict resolution
Quicksort in parallel:
\(n\) processors
each takes one item, compares to splitter
count number of predecessors less than splitter
determines location of item in split
total time \(O(\log n)\)
combine: \(O(\log n)\) per layer with \(n\) processors
problem: \(\Omega(\log^2 n)\) time bound
problem: \(n\log^2 n\) work
Using many processors:
do all \(n^2\) comparisons
use parallel prefix to count number of items less than each item
\(O(\log n)\) time
or \(O(n)\) time with \(n\) processors
Combine with quicksort:
Note: single pivot step inefficient: uses \(n\) processors and \(\log n\) time.
Better: use \(\sqrt{n}\) simultaneous pivots
Choose \(\sqrt{n}\) random items and sort fully to get \(\sqrt{n}\) intervals
For all \(n\) items, use binary search to find right interval
recurse
\(T(n)=O(\log n)+T(\sqrt{n})=O(\log n + \frac12\log n+\frac14\log n + \cdots)=O(\log n)\)
Formal analysis:
consider root-leaf path to any item \(x\)
argue total number of parallel steps on path is \(O(\log n)\)
consider item \(x\)
claim splitter within \(\alpha\sqrt{n}\) on each side
since prob. not at most \((1-\alpha\sqrt{n}/n)^{\sqrt{n}} \le e^{-\alpha}\)
fix \(\gamma, d<1/\gamma\)
define \(\tau_k = d^k\)
define \(\rho_k = n^{(2/3)^k}\) \((\rho_{k+1}=\rho_k^{2/3})\)
note size \(\rho_k\) problem takes \(\gamma^k\log n\) time
note size \(\rho_k\) problem odds of having child of size \(>\rho_{k+1}\) is less than \(e^{-\rho_k^{1/6}}\)
argue at most \(d^k\) size-\(\rho_k\) problems whp
follows because probability of \(d^k\) size-\(\rho_k\) problems in a row is at most
deduce runtime \(\sum d^k\gamma_k = \sum (d\gamma)^{k}\log n = O(\log n)\)
note: as problem shrinks, allowing more divergence in quantity for whp result
minor detail: “whp” dies for small problems
OK: if problem size \(\log n\), finish in \(\log n\) time with \(\log n\) processors
trivial sequential algorithm
inherently sequential
from node point of view: each thinks can join MIS if others stay out
randomization breaks this symmetry
Randomized idea
each node joins with some probability
all neighbors excluded
many nodes join
few phases needed
Algorithm:
all degree 0 nodes join
node \(v\) joins with probability \(1/2d(v)\)
if edge \((u,v)\) has both ends marked, unmark lower degree vertex
put all marked nodes in IS
delete all neighbors
Intuition: \(d\)-regular graph
vertex vanishes if it or neighbor gets chosen
mark with probability \(1/2d\)
prob (no neighbor marked) is \((1-1/2d)^d\), constant
so const prob. of neighbor of \(v\) marked—destroys \(v\)
what about unmarking of \(v\)’s neighbor?
prob(unmarking forced) only constant as argued above.
So just changes constants
const fraction of nodes vanish: \(O(\log n)\) phases
Implementing a phase trivial in \(O(\log n)\).
Prob chosen for IS, given marked, exceeds \(1/2\)
suppose \(w\) marked. only unmarked if higher degree neighbor marked
higher degree neighbor marked with prob. \(\le 1/2d(w)\)
only \(d(w)\) neighbors
prob. any superior neighbor marked at most \(1/2\).
For general case, define good vertices
good: at least \(1/3\) neighbors have lower degree
prob. no neighbor of good marked \(\le (1-1/2d(v))^{d(v)/3} \le e^{-1/6}\).
So some neighbor marked with prob. \(1-e^{-1/6}\)
Stays marked with prob. 1/2
deduce prob. good vertex killed exceeds \((1-e^{-1/6})/2\)
Problem: perhaps only one good vertex?
Good edges
any edge with a good neighbor
has const prob. to vanish
show half edges good
deduce \(O(\log n)\) iterations.
Proof
Let \(V_B\) be bad vertices; we count edges with both ends in \(V_B\).
direct edges from lower to higher degree \(d_i\) is indegree, \(d_o\) outdegree
if \(v\) bad, then \(d_i(v) \le d(v)/3\)
deduce \[\sum_{V_B} d_i(v) \le \frac13 \sum_{V_B} d(v)=\frac13\sum_{V_B}( d_i(v)+d_o(v))\]
so \(\sum_{V_B} d_i(v) \le \frac12 \sum_{V_B} d_o(v)\)
which means indegree can only “catch” half of outdegree; other half must go to good vertices.
more carefully,
\(d_o(v)-d_i(v) \ge \frac13(d(v))=\frac13(d_o(v)+d_i(v))\).
Let \(V_G,V_B\) be good, bad vertices
degree of bad vertices is \[\begin{aligned} 2e(V_B,V_B)+e(V_B,V_G)+e(V_G,V_B) &= & \sum_{v\in V_B} d_o(v)+d_i(v)\\ &\le &3\sum(d_o(v)-d_i(v))\\ &= &3(e(V_B,V_G)-e(V_G,V_B))\\ &\le &3(e(V_B,V_G)+e(V_G,V_B)\end{aligned}\] Deduce \(e(V_B,V_B) \le e(V_B,V_G)+e(V_G,V_B)\). result follows.
Derandomization:
Analysis focuses on edges,
so unsurprisingly, pairwise independence sufficient
not immediately obvious, but again consider \(d\)-uniform case
prob vertex marked \(1/2d\)
neighbors \(1,\ldots,d\) in increasing degree order
Let \(E_i\) be event that \(i\) is marked.
Let \(E'_i\) be \(E_i\) but no \(E_j\) for \(j<i\)
\(A_i\) event no neighbor of \(i\) chosen
Then prob eliminate \(v\) at least \[\begin{aligned} \sum \Pr[E'_i \cap A_i] &= &\sum\Pr[E'_i]\Pr[A_i \mid E'_i]\\ &\ge &\sum \Pr[E'_i]\Pr[A_i]\end{aligned}\]
Wait: show \(\Pr[A_i \mid E'_i] \ge \Pr[A_i]\)
true if independent
measure \(\Pr[\neg A_i \mid E'_i] \le \sum \Pr[E_w \mid E'_i]\) (sum over neighbors \(w\) of \(i\))
measure \[\begin{aligned} \Pr[E_w \mid E'_i] &= &\frac{\Pr[E_w \cap E']}{\Pr[E'_i]}\\ &= &\frac{\Pr[(E_w \cap \neg E_1 \cap \cdots) \cap E_i]}{\Pr[(\neg E_1 \cap \cdots) \cap E_i]} \\ &= &\frac{\Pr[E_w \cap \neg E_1 \cap \cdots \mid E_i]}{\Pr[\neg E_1 \cap \cdots \mid E_i]} \\ &\le &\frac{\Pr[E_w \mid E_i]}{1-\sum_{j\le i}\Pr[E_j \mid E_i]}\\ &= &\Theta(\Pr[E_w])\end{aligned}\] (last step assumes \(d\)-regular so only \(d\) neighbors with odds \(1/2d\))
But expected marked neighbors \(1/2\), so by Markov \(\Pr[A_i]>1/2\)
so prob eliminate \(v\) exceeds \(\sum\Pr[E'_i]=\Pr[\cup E_i]\)
lower bound as \(\sum\Pr[E_i]-\sum\Pr[E_i \cap E_j] = 1/2-d(d-1)/8d^2 > 1/4\)
so \(1/2d\) prob. \(v\) marked but no neighbor marked, so \(v\) chosen
Generate pairwise independent with \(O(\log n)\) bits
try all polynomial seeds in parallel
one works
gives deterministic \(NC\) algorithm
with care, \(O(m)\) processors and \(O(\log n)\) time (randomized)
LFMIS P-complete.
We focus on bipartite; book does general case.
Last time, saw detection algorithm in \(\RNC\):
Tutte matrix
Sumbolic determinant nonzero iff PM
assign random values in \(1,\ldots,2m\)
Matrix Mul, Determinant in \(\NC\)
How about finding one?
If unique, no problem
Since only one nozero term, ok to replace each entry by a 1.
Remove each edge, see if still PM in parallel
multiplies processors by \(m\)
but still \(\NC\)
Idea:
make unique minimum weight perfect matching
find it
Isolating lemma: [MVV]
Family of distinct sets over \(x_1,\ldots,x_m\)
assign random weights in \(1,\ldots,2m\)
Pr(unique min-weight set)\(\ge 1/2\)
Odd: no dependence on number of sets!
(of course \(<2^m\))
Proof:
Fix item \(x_i\)
\(Y\) is min-value sets containing \(x_i\)
\(N\) is min-value sets not containing \(x_i\)
true min-sets are either those in \(Y\) or in \(N\)
how decide? Value of \(x_i\)
For \(x_i=-\infty\), min-sets are \(Y\)
For \(x_i=+\infty\), min-sets are \(N\)
As increase from \(-\infty\) to \(\infty\), single transition value when both \(X\) and \(Y\) are min-weight
If only \(Y\) min-weight, then \(x_i\) in every min-set
If only \(X\) min-weight, then \(x_i\) in no min-set
If both min-weight, \(x_i\) is ambiguous
Suppose no \(x_i\) ambiguous. Then min-weight set unique!
Exactly one value for \(x_i\) makes it ambiguous given remainder
So Pr(ambiguous)\(=1/2m\)
So Pr(any ambiguous)\(< m/2m=1/2\)
Usage:
Consider tutte matrix \(A\)
Assign random value \(2^{w_i}\) to \(x_i\), with \(w_i \in 1,\ldots,2m\)
Weight of matching is \(2^{\sum w_i}\)
Let \(W\) be minimum sum
Unique w/pr \(1/2\)
If so, determinant is odd multiple of \(2^W\)
Try removing edges one at a time
Edge in PM iff new determinant\(/2^W\) is even.
Big numbers? No problem: values have poly number of bits
\(NC\) algorithm open.
For exact matching, \(P\) algorithm open.