On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms

Lorenzo De Stefani, Vedant GuptaarXiv 2024 · OpenReview

Abstract: Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an $\Omega\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where $n$ denotes the size of the input and $M$ denotes the size of the available fast memory (cache). When recomputation is allowed, we show the same bound holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge 2n$, we show an $\Omega\left(n/B\right)$ I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.

Introduction

In modern high-performance computing, the primary performance bottleneck is often not the raw computational power of the CPU, but rather the cost of moving data between large, slow memory (RAM or disk) and small, fast cache. This data movement, or I/O complexity, significantly impacts energy consumption and execution time. While the time complexity of dynamic programming (DP) algorithms like Matrix Chain Multiplication or the Cocke-Younger-Kasami (CYK) algorithm is well-understood, their I/O complexity—especially under the possibility of recomputing intermediate values—has remained less explored. This paper establishes asymptotically tight lower bounds for the I/O complexity of a broad class of DP algorithms.

Methodology: Modeling Dependencies with CDAGs

To analyze data movement, the researchers modeled DP algorithms using Computational Directed Acyclic Graphs (CDAGs). In these graphs, each node represents an intermediate calculation, and edges represent dependencies. This allows for a formal analysis of data "flow" through the memory hierarchy.

The study defines a "Prototype DP Algorithm" that captures the dependency structure common to many problems, such as Boolean Parenthesization and Optimal Binary Search Trees.

Figure 1: Representation of the subproblem dependency structure (CDAG) for the Prototype Algorithm.

The theoretical framework utilizes the Red-Blue Pebble Game, where "red" pebbles represent data in cache ($M$) and "blue" pebbles represent data in slow memory. By analyzing "dominator sets"—bottleneck nodes that must reside in cache for computation to progress—the authors derive fundamental limits on I/O operations.

Key Insights: The Recomputation Advantage

A significant finding of this work is the impact of recomputation. Traditionally, recomputing values is avoided to save time. However, this paper demonstrates that if the cache size $M$ is large enough to hold the input (specifically $M \ge 2n$), allowing the CPU to recompute intermediate values can drastically reduce I/O complexity. In this scenario, the I/O cost drops from a cubic-style bound to a linear bound ($\Omega(n/B)$), representing a massive asymptotic improvement in data movement efficiency.

Furthermore, the authors identified a unified structure among several classic DP problems. Matrix Chain Multiplication, Optimal Polygon Triangulation, and others share nearly identical dependency CDAGs, allowing for a single generalized proof to cover the entire family.

Key Results and Tightness

The paper provides several tight bounds (where upper and lower bounds match asymptotically) for I/O complexity ($IO$):

  1. Standard DP (No Recomputation): For the family of algorithms including Matrix Chain Multiplication, the I/O cost is $\Omega\left(\frac{n^3}{B\sqrt{M}}\right)$.
  2. Standard DP (With Recomputation):
    • Small Cache ($M < cn$): The cubic-style bound $\Omega\left(\frac{n^3}{B\sqrt{M}}\right)$ still holds.
  3. Large Cache ($M \ge 2n$): The bound drops to $\Omega(n/B)$.
  4. CYK Algorithm: The complexity is scaled by the grammar size $\Gamma$ (number of distinct right-hand sides), resulting in a bound of $\Omega\left(\frac{n^3 \Gamma}{B\sqrt{M}}\right)$.
Figure 4: Analysis of rows, columns, and W-covers within the CDAG structure to derive I/O lower bounds.

These bounds are shown to be tight, as existing cache-oblivious algorithms, such as Valiant’s DP-Closure, achieve these theoretical limits.

Conclusion and Future Work

This research provides a rigorous foundation for understanding the data movement costs of a wide range of dynamic programming algorithms. While it highlights the surprising benefits of recomputation for large caches, it also notes limitations. The results apply to a specific family of CDAG structures, and a general theory for determining the effectiveness of recomputation on arbitrary graphs is still a subject for future research. Extending these techniques to more complex recursive algorithms remains a promising direction for developing communication-efficient computing systems.

Summary updated

Abstract

Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an $\Omega\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where $n$ denotes the size of the input and $M$ denotes the size of the available fast memory (cache). When recomputation is allowed, we show the same bound holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge 2n$, we show an $\Omega\left(n/B\right)$ I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.
BibTeX
@misc{stefani2024i,
  author = {Lorenzo De Stefani and Vedant Gupta},
  title = {{On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms}},
  year = {2024},
  eprint = {2410.20337},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.20337},
}
Figure