Research
Autogen: An Algorithm to Discover Dynamic Programming Algorithms with Optimal Data Locality
Dynamic Programming (DP) is one of the most important classes of computer science problems. There are three major approaches to solve DP problems: (1) Looping algorithms, (2) Tiled looping algorithms, and (3) Recursive divide-and-conquer (D&C) algorithms. The advantages and disadvantages of these approaches are as shown in the table. It is easy to see from the table that recursive D&C is the best way to solve dynamic programming.
New DP problems are encountered every day by computational scientists. It is easy to design inefficient looping algorithms to solve DP problems. In contrast, it is extremely difficult, even for experts, to design recursive D&C algorithms. It is computationally infeasible to design efficient algorithms for solving hundreds of DP problems on a wide variety of computer architectures. To this end, we design an expert algorithm that can replace algorithm experts. We design an algorithm we call Autogen that takes an inefficient looping algorithm for a given DP problem as input automatically outputs an efficient recursive D&C algorithm as shown in the figure below.
Consider the chain matrix multiplication DP problem as an example. It is easy to write a looping algorithm for solving the problem but the algorithm is hopelessly inefficient. Our Autogen algorithm can take this algorithm and automatically design an efficient recursive D&C algorithm as follows.
A schematic representation of the complicated autodiscovered recursive divide-and-conquer algorithm for the chain matrix multiplication problem is shown below. In the diagram, the red region represents the write region and the blue region represents the read region.
We present two versions of Autogen: (1) Inductive Autogen algorithm [PPoPP 2016], and a more powerful and efficient (2) Deductive Autogen algorithm [TOPC 2017]. Autogen can automatically design efficient DP algorithms in less than a second even for problems that perform $\Theta \left( n^6 \right)$ work. The complexity of the algorithms designed by the Autogen algorithm is shown in the following table. Cache complexity of an algorithm (see Frigo et al.'s Cache-Oblivious Algorithms [TALG 2012]) represents the total number of cache misses (or I/O misses or page faults) between two levels of memory and it is a measure of communication. In the cache complexities, $M$ denotes the cache size and $B$ denotes the cache line size. The recursive D&C algorithms for most problems given in the table have optimal cache complexity. Span of an algorithm (see Chapter 27 in CLRS 3rd Edition) represents the execution time on a machine with an infinite number of processors. Span is a measure of parallel running time and scalability. The recursive D&C algorithms for some problems have better span than their iterative counterparts and for some other problems, the span is worse.
| Feature | Looping algorithm | Tiled looping algorithm | Recursive D&C algorithm |
| Cache-oblivious? | ✔ | ✘ | ✔ |
| Architecture-independent? | ✔ | ✘ | ✔ |
| Cache-adaptive? | ✘ | ✘ | ✔ |
| Cache-efficient? | ✘ | ✔ | ✔ |
| Energy-efficient? | ✘ | ✔ | ✔ |
| Bandwidth-efficient? | ✘ | ✔ | ✔ |
New DP problems are encountered every day by computational scientists. It is easy to design inefficient looping algorithms to solve DP problems. In contrast, it is extremely difficult, even for experts, to design recursive D&C algorithms. It is computationally infeasible to design efficient algorithms for solving hundreds of DP problems on a wide variety of computer architectures. To this end, we design an expert algorithm that can replace algorithm experts. We design an algorithm we call Autogen that takes an inefficient looping algorithm for a given DP problem as input automatically outputs an efficient recursive D&C algorithm as shown in the figure below.
Consider the chain matrix multiplication DP problem as an example. It is easy to write a looping algorithm for solving the problem but the algorithm is hopelessly inefficient. Our Autogen algorithm can take this algorithm and automatically design an efficient recursive D&C algorithm as follows.
A schematic representation of the complicated autodiscovered recursive divide-and-conquer algorithm for the chain matrix multiplication problem is shown below. In the diagram, the red region represents the write region and the blue region represents the read region.
We present two versions of Autogen: (1) Inductive Autogen algorithm [PPoPP 2016], and a more powerful and efficient (2) Deductive Autogen algorithm [TOPC 2017]. Autogen can automatically design efficient DP algorithms in less than a second even for problems that perform $\Theta \left( n^6 \right)$ work. The complexity of the algorithms designed by the Autogen algorithm is shown in the following table. Cache complexity of an algorithm (see Frigo et al.'s Cache-Oblivious Algorithms [TALG 2012]) represents the total number of cache misses (or I/O misses or page faults) between two levels of memory and it is a measure of communication. In the cache complexities, $M$ denotes the cache size and $B$ denotes the cache line size. The recursive D&C algorithms for most problems given in the table have optimal cache complexity. Span of an algorithm (see Chapter 27 in CLRS 3rd Edition) represents the execution time on a machine with an infinite number of processors. Span is a measure of parallel running time and scalability. The recursive D&C algorithms for some problems have better span than their iterative counterparts and for some other problems, the span is worse.
| Looping algorithm | Autogen-discovered recursive D&C algorithm | ||||
| Problem | Work | Serial cache complexity | Span | Serial cache complexity | Span |
| Chain matrix multiplication | $\Theta\left(n^{3}\right)$ | $\Theta\left(n^{3}\right)$ | $\Theta\left(n^{2}\right)$ | $\Theta\left( \frac{n^{3}}{B \sqrt{M}}\right)$ | $\Theta\left(n^{\log 3}\right)$ |
| Gap problem | |||||
| Function approximation | $\Theta\left( \frac{n^{3}}{B} \right)$ | ||||
| Protein accordion folding | $\Theta\left( n \log n \right)$ | ||||
| Floyd Warshall's all-pairs shortest path | $\Theta\left( n \log n \right)$ | $\Theta\left( n \log^2 n \right)$ | |||
| Edit distance / sequence alignment | $\Theta\left(n^{2}\right)$ | $\Theta\left( \frac{n^{2}}{B} \right)$ | $\Theta\left( n \right)$ | $\Theta\left( \frac{n^{2}}{B M}\right)$ | $\Theta\left( n^{\log 3} \right)$ |
| Binomial coefficient | |||||
| Bitonic traveling salesperson | |||||
| Spoken-word recognition | $\Theta\left( n^2 \right)$ | ||||
| Multi-instance Viterbi algorithm | $\Theta\left(n^{3} t\right)$ | $\Theta\left( \frac{n^{3} t}{B} \right)$ | $\Theta\left( n t \right)$ | $\Theta\left( \frac{n^{3} t}{B \sqrt{M}}\right)$ | $\Theta\left( n t \right)$ |