I have been investigating parallel algorithms to compute certain two-dimensional dynamic programming recursions (on natural parameters); see also here. Under certain assumptions, cases one and two can actually be computed in parallel -- and very well. However, if you assume that communicating array entries from one thread to another is more expensive than a normal memory access (as might be the case on real machines), these algorithms are no longer always strongly work-efficient¹. In fact, I conjecture that in this scenario there is no strongly work-efficient parallel algorithm general for these classes of problems, even if we consider only non-pathological recursions.
Towards proving this, I have made the following abstraction for the domain and parallel algorithms. Note that I assume here that such algorithms allocate computations of individual entries to processors in a deterministic way; I do not think the result changes if we allow nondeterminism/randomisation in this regard, but I have no proof.
Let $G_n = (V_n, \emptyset)$ with $V_n = \{(i,j) \mid 1 \leq i,j \leq n \}$ be a family of empty $n\times n$ grid graphs. Let furthermore $c : \mathbb{N} \to (V_n \to \{1,\dots,p\})$ a coloring for this family which asymptotically divides $V_n$ in equal parts, that is
$\qquad \displaystyle |\{v \in V_n \mid c(n)(v) = c_i\}| \underset{n \to \infty}{\longrightarrow} \frac{n^2}{p}$
for all colors $c_i \in \{1,\dots,p\}$.
The claim is that we can choose edges so that we create no circles and no node has more than linearly many incoming edges, but there are quadratically many edges whose nodes have different colors²:
(For any such coloring, ) There is a family of sets of directed edges $E_n = V_n \times V_n$ so that
- $((i,j), (i',j')) \in E_n \ \Longrightarrow i' \geq i \land j' \geq j$, that is edges do not point up or left³,
- for all $n \in \mathbb{N}$, $(V_n,E_n)$ has no directed cycles,
- $D_n := \max_{u \in V_n} \operatorname{indeg}(u) \in O(n)$ and
- $C_n := |\{(u,v) \in E_n \mid c(n)(u) \neq c(n)(v) \}| \in \Omega(n^2)$.
Is this (similar to) a known problem? Does it hold, and how can you (dis)prove it?
Example
Consider this coloring (which roughly corresponds to an algorithm I have investigated):
[source]
For edges as implied by the Levenshtein distance recursion, that is
$\qquad \displaystyle E_n = \bigcup_{1 \leq i,j \leq n}\{(i,j)\} \times \{(i-1,j), (i-1,j-1), (i,j-1) \} \cap \{1,\dots,n\}^2$,
we have $D_n = 3$ and $C_n = 8n-4$, so this is not the $E_n$ we are looking for. If we draw edges from every node to all others to its right, that is
$\qquad \displaystyle E_n = \{ ((i,j),(i,j')) \mid j' > j \}$,
we get $D_n = n-1$ and $C_n \geq \frac{3}{4}n^2$, so the coloring is defeated.
- "Strongly work-efficient" means here that the parallel algorithm on $p \in \mathbb{N}$ cores does not take more time than $\frac{T^s}{p}$ in the limit, with $T^s$ the runtime of a (good) sequential algorithm.
- That corresponds to a not-too-dense dependency structure of a recursion's domain which causes the parallel algorithm to communicate too many results between threads.
- That corresponds to case one. Case two can be modelled similarly by requiring $i' > i$.
