Parallel Computation

A parallel computer can perform multiple operations simultaneously, as opposed to sequential computers

We focus on massive parallelism

In theoretical work, the Parallel Random Access Machine is also used, where idealized processors with a simple instruction set interact via shared memory

Here, we look at a simpler model based on Boolean circuits

We take each gate to be an individual processor, and so define the processor complexity of a circuit to be its size, and the parallel time complexity to be its depth

As in our exploration of Circuit Complexity, we look at circuit families to handle variable sized inputs

To make sure this corresponds to the standard PRAM computation model, we also impose a uniformity requirement, so that all circuits in a family can be easily obtained

Definition: A family of circuits $(C_0,C_1,\dots )$ is uniform if some log space transducer $T$ outputs $⟨C_n⟩$ when $T$‘s input is $1^n$

We consider the simultaneous size-depth circuit complexity $(f(n),g(n))$

Example:
Say $A$ is the language over $\{0,1\}$ of all strings with an odd number of $1$s

We can test membership with a standard $x\oplus y$ gate, which can be written with standard operations as $(x\wedge \neg y)\vee (\neg x\wedge y)$

To generalize to $n$ variables, we could make a sequence of circuits, which uses $(O(n),O(n))$ size-depth

Or even better, we can construct a binary tree of $\oplus$ gates, for a size-depth complexity of $(O(n),O(\log n))$

Example:
The Boolean matrix multiplication function takes $2m^2=n$ variables representing $A=\{a_{ik}\}$ and $B=\{b_{ik}\}$, and outputs $m^2$ values representing $C=\{c_{ik}\}$ where $c_{ik}={\bigvee }_j(a_{ij}\wedge b_{jk})$

The circuit for this function has gates $g_{ijk}$ for each $a_{ij}\wedge b_{jk}$, and for every $i,k$ a binary tree of $\vee$ gates to compute the outer expression

Each tree has $m-1$ $\vee$ gates with $\log m$ depth, so this circuit has size $O(m^3)=O(n^{3/2})$ and depth $O(\log n)$

We extend this example to calculate the transitive closure of $A$, the matrix $A\vee A^2\vee \cdots \vee A^m$

This matrix is closely related to the $PATH$ problem (the canonical $\mathrm{NL}$-complete problem), where we view $A$ as an adjacency matrix of a directed graph

The computation of $A^i$ can be represented with a binary tree of size $i$ and depth $\log i$, hence computing $A^m$ takes $(O(n^2),O({\log }^{2}n))$

We make circuits for each $A^i$ which adds another factor of $m$ to the size and an additional layer of depth (but not a factor)

Hence the size-depth complexity of transitive closure is $(O(n^{5/2}),O({\log }^{2}n))$

It turns out that many interesting problems have complexity $(O(n^k),O({\log }^{k}n))$ for some $k$, and can therefore be considered highly parallelizable

Definition: Let ${\mathbf{NC}}^i$ be the class of languages that can be decided by a uniform family of circuits with polynomial size and $O({\log }^{i}n)$ depth

$\mathbf{NC}$ is the class of languages in ${\mathrm{NC}}^i$ for some $i$
Functions computed by such families are called NC computable

$\mathrm{NC}$ stands for Nick’s class (Nick Pippenger)

A small note is that this is not quite the standard definition for ${\mathrm{NC}}^1$

Theorem: ${\mathrm{NC}}^1\subseteq \mathrm{L}$

On input $w$ of length $n$, as needed the algorithm can construct the $n$th circuit and evaluate the circuit with a depth-first search

Since the circuit depth is logarithmic, we can store the path and partial results in logarithmic space

Theorem: $\mathrm{NL}\subseteq {\mathrm{NC}}^2$

Let $A$ be a language (encoded into $\{0,1\}$) decided by an $\mathrm{NL}$ machine $M$

We construct a uniform circuit family $(C_0,C_1,\dots )$ for $A$

Note that a configuration of $M$ on $w$ in a log space machine describes the state, the contents of the work tape, and the positions of both the input and the work tape heads, but not $w$ itself

This means that there are polynomially many configurations, and we can make the edges match a computation on $w$ by looking at the transition function and the head position on $w_i$

Thus, we can output a circuit that computes the transitive closure of a graph $G$ that matches the computation graph for $M$ and then outputs the position indicating the presence of such a path

This circuit has polynomial size and $O({\log }^{2}n)$ depth (as explained in our earlier example)

That this can be done by a log space transducer is a bit unintuitive, but keep in mind we can be flexible with the output representation of a circuit

Theorem: $\mathrm{NC}\subseteq \mathrm{P}$

A polynomial time algorithm can just run the log space transducer to generate $C_n$ and then simulate it on an input of length $n$

$\mathrm{P}=\mathrm{NC}$ would imply all polynomial time solvable problems are highly parallelizable, which seem unlikely

Definition: A language $B$ is P-complete if $B\in P$ and every $A$ in $P$ is log space reducible to $B$

Theorem: If $A{\le }_{L}B$ and $B\in \mathrm{NC}$ then $A\in \mathrm{NC}$

This follows because $\mathrm{NC}$ circuit families can compute log space reductions

Theorem: $CIRCUIT\text{-}VALUE=\{⟨C,x⟩\mid C\text{ is a Boolean circuit and }C(x)=1\}$ is $\mathrm{P}$-complete

We’ve already seen how to reduce a language to a circuit when we first introduced circuit complexity

We reduce a language $A$ in $\mathrm{P}$ on input $w$ by producing a circuit simulating $A$ and passing in that circuit and $w$ to $CIRCUIT\text{-}VALUE$

We can do this reduction in log space because the circuit has a simple and repetitive structure, so $CIRCUIT\text{-}VALUE$ is $\mathrm{P}$-complete