\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt
2013 Lecture 29 Start

Parallel Algorithms

Two closely related models of parallel computation.

Circuits

PRAM

Essentially the same models, but let us focus on different things.

Circuits

Addition

Parallel prefix

PRAM

various conflict resolutions (CREW, EREW, CRCW)

PRAMs simulate circuits, and vice versa

differences in practice

parallel prefix

list ranking EREW

Work-Efficient Algorithms

Idea:

Brent's theorem

Work-efficient parallel prefix

Work-efficient list ranking

Euler tour to reduce to parallel prefix for

Expression Tree Evaluation

plus and times nodes.

Idea

Generalize problem:

Merging a single leaf

Parallelize

Sorting

Parallelizing binary search

CREW Merge sort:

Better with more processors?

Use same ideas with fewer processors?

Details: merge $n$ items of $A$ into $m$ items of $B$ in $O(\log\log n)$ time using $m+n$ processors

Use in parallel merge sort: $O(\log n \log\log n)$ with $n$ processors.

Qsort idea

Connectivity and connected components

Linear time sequential trivial.

Directed

Squaring adjacency matrix

Undirected

Basic approach:

Smarter: interleave hooking and jumping:

More details:

Potential function: height of live stars and tall trees

Summary: $O(m+n)$ processors, $O(\log n)$ time.

Improvements:

Randomization

Randomization in parallel:

Classes:

Sorting

Quicksort in parallel:

Using many processors:

Combine with quicksort:

Formal analysis:

Maximal independent set

trivial sequential algorithm

Randomized idea

Algorithm:

Intuition: $d$-regular graph

Prob chosen for IS, given marked, exceeds $1/2$

For general case, define good vertices

Good edges

Proof

Derandomization:

with care, $O(m)$ processors and $O(\log n)$ time (randomized)

LFMIS P-complete.

Perfect Matching

We focus on bipartite; book does general case.

Last time, saw detection algorithm in $\RNC$:

How about finding one?

Idea:

Isolating lemma: [MVV]

Proof:

Usage:

$NC$ algorithm open.

For exact matching, $P$ algorithm open. $\newcommand{\Wbar}{\overline W}$