On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms

The lower bound comes from the intuitive strategy of making each $a_i$ as large as possible, i.e. if $q=\lfloor \frac{T}{L}\rfloor$, then assign $a_1,\mathrm{\dots },a_q=\sqrt{L}$ and $a_{q+1}=\sqrt{T-qL}$. In this case, . To show the optimality of this strategy, we show that any other configuration is suboptimal.

Consider any other assignment of $a_1,\mathrm{\dots },a_n$ that is not just a permutation of the same values. By assumption, any such assignment must have at least two non-zero values . Let $k=a_i+a_j$. If $k\le \sqrt{L}$, since $k^2>a_i^2+a_j^2$, there exists some $c\in {ℝ}^{+}$ such that $c^2=a_i^2+a_j^2$ and , showing that our assignment $a_1,\mathrm{\dots },a_n$ does not minimize ${\sum }_{i=1}^n{a}_i$.

Alternatively, if $k>\sqrt{L}$, then (the last step follows from the fact that $f(x)=x^2+{(k-x)}^2$ defines an upwards-facing parabola with an axis of symmetry about $x=\frac{k}{2}$). This means that there exists some such that ${\sqrt{L}}^2+c^2=a^2+b^2$ and , again showing that our assignment $a_1,\mathrm{\dots },a_n$ does not minimize ${\sum }_{i=1}^n{a}_i$. $◀$

The following property captures the relation between subsets of $L$-vertices and their number of distinct $R$-vertex predecessors:

Consider the $W$-cover of $G$ as defined in Section 3. As any $R$-vertex can be a member of at most two distinct $W_i$’s we have:

By definition, each vertex in $L$ has a distinct pair of $R$-vertex predecessors which, by construction, are both included in exactly one set $W_i$. Let $a_i$ be the number of vertices from $L^{\prime }$ with both predecessors in $W_i$. By the assumptions we have:

By Lemma 1, for any $W_i$, each interacting pair of $R$-vertices in it are the predecessors of a distinct $L$-vertex belonging to the tree sub-CDAG of a distinct $R$-vertex. From the assumption that vertices in $L^{\prime }$ belong to at most $\rho$ distinct roots, we have:

Furthermore, from Lemma 1, we know that vertices in $|R^{\prime }\cap W_i|$ can interact to produce at most ${|R^{\prime }\cap W_i|}^2/4$ vertices in $L^{\prime }$. Thus,

By (1), (4),  (2), (3), and Lemma 2 (in this order) we have:

$◀$ Lemma 3 allows us to claim that to compute a set of $L$-vertices, it is necessary to access a minimum number of $R$ vertices, which, due to the non-recomputation assumption, must either be in the cache or loaded into it using a read I/O operation.

We prove the result for $B=1$. The result then trivially generalizes for a generic $B$.

The fact that $I{O}_G(n,M,1)\ge n$ follows trivially from our assumption that the input is initially stored in the slow memory and therefore must be loaded into the cache at least once using $n$ read I/O operations.

Let $𝒞$ be any computation schedule for the sequential execution of $𝒜$ using a cache of size $M$ in which no value corresponding to any vertex of $G$ is computed more than once. We partition $𝒞$ into non-overlapping segments ${𝒞}_1,{𝒞}_2,\mathrm{\dots }$ such that during each ${𝒞}_i$ exactly $8M^{1.5}$ values corresponding to distinct $L$-vertices, denoted as $L_i$, are evaluated. Since $|L|=\left(n^3-n\right)/6$ there are $\lfloor \left(\frac{n^3}{6}-\frac{n}{6}\right)\frac{1}{8M^{1.5}}\rfloor$ such segments. Given $L_i$, we refer to the set of $R$-vertices to whom at least one of the vertices in $L_i$ belongs as $R_i$. These correspond to vertices which are active during ${𝒞}_i$. For each interval, we denote as $h_i$ the number of $R$-vertices whose value is completely evaluated during ${𝒞}_i$. As no value is computed more than once ${\sum }_i{h}_i=|R|=n\left(n+1\right)/2$. Let $g_i$ denote the number of I/O operations executed during ${𝒞}_i$. We consider two cases:

• $\mathrm{■}$

  The vertices of $L_i$ belong to at least $4M+1$ distinct $R$-vertices: For each of the $4M+1-h_i$ values corresponding to $R$-vertrices that were partially computed in ${𝒞}_i$, a partial accumulator of the values corresponding to their leaves computed during ${𝒞}_i$ must either be in the cache at the end of ${𝒞}_i$ or must be written into slow memory by means of a write I/O operation. Hence, $g_i\ge 4M+1-M-h_i$.

• $\mathrm{■}$

  The vertices of $L_i$ belong to at most $4M$ distinct $R$-vertices: By Lemma 3, the vertices in $L_i$ have at least $4M$ $R$-vertex predecessors, of whom at most $h_i$ are computed during ${𝒞}_i$. As the considered schedule’s values are not computed more than once, each of the remaining $4M-h_i$ values corresponding to predecessor vertices of $L_i$ must either be in the cache at the beginning of ${𝒞}_i$, or read into the cache by means of a read I/O operation. Hence, $g_i\ge 4M-M-h_i.$

The I/O requirement of the algorithm is obtained by combining the cost of each non-overlapping segment:

$◀$ By Theorem 4, we have that for $M\le c{n}^2$, for a sufficiently small constant value $c>0$, computations of CDAGs in $𝒢\left(n\right)$ in which no value is recomputed require $\mathrm{\Omega }\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O operations.

Suppose for every $v_{i,j}\in A$, $D$ contains a vertex internal to the tree-CDAG rooted at $v_{i_k,j_k}$. As the tree-CDAGs of different $R$-vertices are disjoint, this would imply $|D|\ge |A|$.

Otherwise, there must be some $v_{i,j}\in A$, such that $D$ does not contain any of its internal vertices. Let $L_{i,j}=\{l_0,l_1,\mathrm{\dots },l_{j-i-1}\}$ denote the set of $L$-vertices corresponding to $v_{i,j}$. It is sufficient to show that there are $j-i$ vertex disjoint paths from the inputs of $G$ to vertices in $L_{i,j}$. By construction, each leaf $l_k\in L_{i,j}$ has a predecessor belonging to a unique column $c_{i+k}$. In turn, each of these predecessors is connected through its internal tree-CDAG to the input vertex in the same column ($v_{i+k,i+k}$). In this manner, $j-i$ paths $\left(v_{i+k,i+k}\to v_{i,i+k}\to l_k\right)$ for $0\le k\le j-i-1$ are obtained. Since each path contains $R$-vertices from a different column, and the tree-CDAGs of different $R$-vertices are disjoint, the paths outlined above are vertex-disjoint. $◀$

To simplify our analysis, we only consider parsimonious execution schedules such that each time an intermediate result is computed, the result is then used to compute at least one of the values of which it is an operand before being removed from the memory (either the cache or slow memory). Any non-parsimonious schedule $𝒞$ can be reduced to a parsimonious schedule ${𝒞}^{\prime }$ by removing all the steps that violate the definition of parsimonious computation. ${𝒞}^{\prime }$ has therefore less computational or I/O operations than $𝒞$. Hence, restricting the analysis to parsimonious computations leads to no loss of generality.

We prove the result for the case $B=1$. The result then trivially generalizes for a generic $B$. The fact that $I{O}_{𝒜}(n,M,1)\ge n$ follows trivially from our assumption that input is initially stored in slow memory and therefore must be loaded into the cache at least once using $n$ read I/O operations.

Let $L(x)$ be the set of $L$-vertices in $G$ whose predecessor $R$-vertices both correspond to some subproblems $S(i,j)$ such that $x\le j-i$. By the construction, for each subproblem $S(i,j)$ the corresponding tree sub-CDAG has $\max \{0,j-i-2x\}$ such $L$-vertices. Since the sub-CDAGs corresponding to each $S(i,j)$ do not share vertices, we have:

Let $𝒞$ be any computation schedule for the sequential execution of $𝒜$ using a cache of size $M$. We partition $𝒞$ into segments ${𝒞}_1,{𝒞}_2,\mathrm{\dots }$ such that during each ${𝒞}_l$ exactly $6M^{1.5}$ values corresponding to distinct vertices in $L(3M)$ are computed from their operands (i.e., not read from the cache). Let $L_l$ denote the set of vertices corresponding to these values. Below we argue that the number $g_l$ of I/O operations executed during each of the $\lfloor |L(3M)|/6M^{1.5}\rfloor$ non-overlapping segments ${𝒞}_l$ is at least $2M$, from whence the statement follows.

Let $A$ denote the set of vertices corresponding to the values computed during ${𝒞}_l$. Clearly $L_l\subseteq A$. Let $D$ denote the set of vertices corresponding to either the at most $M$ values that are either stored in the cache or the values that are read into the cache during ${𝒞}_l$ by means of read I/O operations. Thus $g_l=|D|-M$. In order to be possible to compute the values corresponding to vertices in $A$ during ${𝒞}_l$ there must be no paths from input vertices of $G$ to vertices in $A$, that is, $D$ must be a dominator set of $A$.

We refer to the set of $R$-vertices to whom at least one of the vertices in $L_l$ belongs as $R_l$. These correspond to vertices which are active during ${𝒞}_l$. We consider three mutually exclusive cases:

1. (a)

   At least one of the values corresponding to a vertex $v^{\prime }$ in $R_l$ is entirely computed during ${𝒞}_l$. That is no accumulator of the values corresponding to the leaves of $v^{\prime }$ is in the cache or it is loaded in it by means of an read I/O operation during ${𝒞}_l$. Thus, $v^{\prime }\in A$ and $D$ do not include any non-leaf vertex internal to the tree-sub-CDAG rooted in $v^{\prime }$. Since $L_l\subseteq L\left(3M\right)$, by definition, $v$ corresponds to a subproblem $S(i,j)$ such that $j-i\ge 3M$. From Lemma 6, $|D|\ge 3M$ which implies $g_j\ge 2M$.

2. (b)

   $|R_l|>4M$: As none of the values in $R_l$ is entirely computed during ${𝒞}_l$ (case (a)), and as we are considering parsimonious computations, for each value $R_l$ at least one partial accumulator of its value is either in the cache at the beginning (resp., end) of ${𝒞}_l$ or is loaded into the cache during (resp., saved to the slow memory) during it. Hence $g_l\ge 4M-2M$.

3. (c)

   $|R_l|\le 4M$: By Lemma 3, the vertices in $L_l$ have at least $3M$ distinct $R$-vertices predecessors. Since $L_l\subseteq L\left(3M\right)$ by definition, all such $R$ vertices corresponds to subproblems $S(i,j)$ where $j-i\ge 3M$. As the values of these vertices are either in the cache at the beginning of ${𝒞}_l$, or read to the cache during ${𝒞}_l$, or computed during ${𝒞}_l$, $D$ must be dominator set for the corresponding vertices. From Lemma 6, we can thus conclude $|D|\ge 3M$ from whence $g_l\ge 2M$.

$◀$

By Theorem 7, we have that for $M\le c_{1}n$, where $c_1$ is a sufficiently small positive constant value, computations of CDAGs in $𝒢\left(n\right)$ require $\mathrm{\Omega }\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O operations. This is in contrast with the result given in Theorem 4 for schedules with no recomputation that exhibit I/O complexity $\mathrm{\Omega }\left(\frac{n^3}{\sqrt{M}B}\right)$ for values of $M$ up to $c_2{n}^2$ for an appropriately chosen constant $c_2$.

When allowing recomputation, if , where $c_1$ is a sufficiently small positive constant, the number of I/O operations executed by Valiant’s DP-Closure Algorithm asymptotically matches our lower bound in Theorem 7. Thus, for , allowing recomputation does not asymptotically change the required number of I/O operations. On the other hand, if $M>2n$, our lower bound simplifies to $\mathrm{\Omega }(n/B)$, diverging from the complexity of Valiant’s DP-closure Algorithm.

In Theorem 8, we show how for any algorithm corresponding to $G=𝒢(n)$ given a cache memory of suitable size $M\ge 2n$, there exists an execution schedule in which the results of subproblems are computed according to a recursive top-down order that executes only $\lceil n/B\rceil +1$ I/O operations, thus asymptotically matching the general lower bound given in Theorem 7. Crucially, such a schedule involves the recomputation of intermediate results in order to reduce the number of I/O operations otherwise necessary, as established in Theorem 4.

The proposed schedule follows the steps outlined in Algorithm 4: in the initialization phase the $n$ I/O values are read into the cache using $\lceil n/B\rceil$ read I/O operations. These values are held in the cache until the very end of the schedule, occupying $n$ out of the $M\ge 2n$ available memory locations. Once the final result $S(1,n)$ is computed, it is written to the secondary memory by means of a write I/O operation.

We argue that the invocation of the procedure COMPUTE$(i,n)$ uses at most $n$ cache memory locations, thus not requiring the execution of any additional I/O operation. Let $ℳ(j-i)$ denote the memory usage of an invocation of COMPUTE$(i,j)$. In the base case $ℳ(1)=1$, as COMPUTE simply combines and returns the values $S(i,i)$ and $S(j,j)$ which are already stored in the cache after the initialization phase. In the general case, due to the use of accumulators and to the sequence of recursive calls and the memory management used by the schedule, we have:

The lemma follows as $ℳ(n-1)=n-1$. $◀$

Interestingly, while the proposed computation schedule allows to achieve an asymptotic polynomial reduction of the number of I/O operations by a $\mathrm{\Theta }\left(\frac{n^2}{\sqrt{M}}\right)$ multiplicative factor using recomputation, this is at the cost of a exponential increase of the number of computation operations executed ($2^{𝒪(n)}$), in comparison with Valiant’s DP-Closure Algorithm which requires only $𝒪(n^3)$ computations.

We assume that the variables in $V$ can be referenced by index and that such index can be stored in a single memory word. We represent subsets of $V$ (the results of subproblems $S(i,j)$) using a one-hot encoding with $\lceil |V|/s\rceil$ memory words, where $s$ denotes the number of bits in a memory word. Thus, given the representation of one such subset in the memory, to check whether a variable $V_i$ is a member of the subset it is sufficient to access the $(imods)$-th bit of the $\lfloor i/s\rfloor$-th memory word.

We assume that each grammar rule is represented utilizing at most three memory words each used to represent the index of the left-hand side and at most two to represent the right-hand side (either the index of the two variables or the code for a terminal symbol).

The construction of the CDAG representing CYK’s execution for an input string $w$ with $n$ characters and a CFG in CNF $(V,ℛ,\mathrm{\Sigma },T)$, called $G_{CYK}(n,(V,ℛ,\mathrm{\Sigma },T))$, follows a recursive structure which uses as a basis $G=(V,E)\in 𝒢(n)$. We describe the necessary modification focusing on the sub-CDAG for a single $S(i,j)$ subproblem. A visual depiction of the ensuing description is provided in Figure 3:

• $\mathrm{■}$

  For the base of the construction, for each $S(i,i)$, the CDAG has $|V|/s$ vertices, each corresponding to the encoding of one of the possible variables of the grammar. These vertices serve as the input of the CDAG.

• $\mathrm{■}$

  Each $R$-vertex of $G$, corresponding to the computation of the solution of one of the subproblems $S(i,j)$, is replaced by $|V|/s$ vertices, each representing a part of the encoding of the set of variables $V$. We refer to this set of vertices as “variable roots” $\mathrm{𝑉𝑅}$.

• $\mathrm{■}$

  Consider a variable root $v$ corresponding to subproblem $S(i,j)$ and variable $A\in V$. $v$ forms the root of a binary tree, which has as its leaves vertices for each rule having $A$ as its left-hand side. We denote the set of these vertices as “grammar roots” $\mathrm{𝐺𝑅}$. Note that as only one variable can appear on the left-hand side of a rule, the trees composed in this way are vertex disjoint. Further, for each $S(i,j))$ there will be at least $\mathrm{\Gamma }/s$ such vertices.

• $\mathrm{■}$

  For each subproblem $S(i,j)$, consider one of its grammar roots $u$ corresponding to rule $\gamma \in {ℛ}_B$. $u$ forms the root of a binary tree combining the results of $j-i$ “leaf-vertices”. Each leaf vertex corresponds to a combination of the subproblems $S(i,k)$ and $S(k+1,j)$, for . Such a vertex has as predecessors the variable root vertices of subproblems $S(i,k)$ and $S(k+1,j)$ encoding the variables appearing in the right-hand side of rule $\gamma$.

Given the CDAG $G_{CYK}(n,(V,ℛ,\mathrm{\Sigma },T))$, we generalize the notion of rows (resp., columns) introduced in Section 3 by having row $r_i$ (resp. column $c_j$) include all vertices in $\mathrm{𝑉𝑅}$ corresponding to the encoding of the results of subproblems $S(i,j)$ for $1\le j\le n$ (resp., for $1\le i\le n$).The definition of $W$-cover generalizes to $G_{CYK}(n,(V,ℛ,\mathrm{\Sigma },T))$. We observe that a property analogous to that outlined in Lemma 1 holds for $G_{CYK}(n,(V,ℛ,\mathrm{\Sigma },T))$ as well:

Consider any set of $x$ $\mathrm{𝑉𝑅}$-vertices in $W_i$ containing $x_c$ vertices in column $i$ and $x-x_c$ vertices in row $i+1$. Since vertices in the same row (or column) don’t interact, there are at most $x\left(x-x_c\right)\le x^2/4$ interacting pairs.

Consider any two such distinct interacting pairs: $(v_{k,i}^A,v_{i+1,l}^B)$ and $(v_{m,i}^C,v_{i+1,n}^D)$ (where $v_{k,i}^A$ is a $\mathrm{𝑉𝑅}$-vertex corresponding to variable $A$ in row $k$ and column $i$). Any leaf produced by $(v_{k,i}^A,v_{i+1,l}^B)$ must correspond to a rule with right-hand side “AB”. From the assumption that every rule in $ℛ$ has a unique right-hand side, it follows that there is only one such rule and therefore $(v_{k,i}^A,v_{i+1,l}^B)$ must produce a single leaf.

To show that the leaves produced by $(v_{k,i}^A,v_{i+1,l}^B)$ and $(v_{m,i}^C,v_{i+1,n}^D)$ belong to distinct $GR$-vertices, consider the following two cases:

1. 1.

   If $k\ne m$ or $l\ne i$, it follows from Lemma 1 that the leaves produced belong to different roots, and therefore must also belong to different grammar roots.

2. 2.

   Otherwise, it must be the case that $A\ne C$ or $B\ne D$ (since the two interacting pairs are assumed to be distinct). It follows that the two leaves produced correspond to different rules in $ℛ$ and therefore belong to distinct grammar roots.

$◀$

We analyze the I/O complexity of any sequential computation for the CYK algorithm by analyzing the CDAG corresponding to the given CFG and the input string to be considered. We first state two results that correspond each to a modification of the results in Lemma 3 and, respectively, of Lemma 6 for the family of CDAG corresponding to execution of the CYK algorithm:

Consider the $W$-cover of $G_{CYK}(n,(V,ℛ,\mathrm{\Sigma },T))$ with the adapted definition for the CYK CDAG discussed in Section 5.2. As any $VR$-vertex can be a member of at most two distinct $W_i$’s we have:

By definition, each vertex in $L$ has a distinct pair of $VR$-vertex predecessors which, by construction, are both included in exactly one set $W_i$. Let $a_i$ be the number of vertices from $L^{\prime }$ with both predecessors in $W_i$. By the assumptions we have:

By Lemma 10, for any $W_i$, each interacting pair of $VR$-vertices in it are the predecessors of a distinct $L$-vertex belonging to the tree sub-CDAG of a distinct $GR$-vertex. From the assumption that vertices in $L^{\prime }$ belong to at most $\rho$ distinct roots, we have:

Furthermore, from Lemma 10, we know that vertices in $|R^{\prime }\cap W_i|$ can interact to produce at most ${|R^{\prime }\cap W_i|}^2/4$ vertices in $L^{\prime }$. Thus,

By (7), (10),  (8), (9), and Lemma 2 (in this order) we have:

$◀$

The proof follows a reasoning analogous to that used to prove Lemma 3 adapted for the CDAG $G_{CYK}(n,(V,ℛ,\mathrm{\Sigma },T))$ by using the property of $L$-vertices of the CYK CDAG states in Lemma 10 in place of Lemma 1.

The proof corresponds to the one of Lemma 6 where the tree sub-CDAGs rooted in $GR$-vertices are considered instead of the $R$ vertices of $𝒢(n)$.

A lower bound to the I/O complexity of the CYK algorithm can be obtained by following steps analogous to those used in the proof of Theorem 7 with opportune adjustments matching the modifications in the enhanced CDAG described in this section.

By Theorem 13, we have that for $M\le c_{1}n$, where $c_1$ is a sufficiently small positive constant value, computations of the CYK algorithm require $\mathrm{\Omega }\left(\frac{n^3\mathrm{\Gamma }}{\sqrt{M}B}\right)$ I/O operations. Note that if the considered CFG is such that $\mathrm{\Gamma }=\mathrm{\Theta }\left(|{ℛ}_B|\right)$ our lower bound shows a direct dependence of the I/O complexity of execution of the CYK algorithm on the size of the considered grammar. Indeed there are many possible grammars for which this is the case. Finally, while the result of Theorem 7 holds for computations with recomputation, it is also possible to obtain an I/O lower bound for schedules in which recomputation is not allowed by modifying the analysis given in Theorem 4.