Invited Talk by Dr. Pramod Ganapathi on Automatic Discovery of Efficient Divide-&-Conquer Algorithms for Dynamic Programming Problems
In our vision of the not-so-distant future of computing, machines will take the responsibility of designing and implementing most machine-specific highly efficient nontrivial algorithms with provable correctness and performance guarantees. To this end, we take a significant step toward giving computers the abilities of algorithm design and problem-solving.
We present Autogen -- an algorithm that for a wide class of dynamic programming (DP) problems automatically discovers highly efficient parallel recursive divide-and-conquer algorithms from inefficient iterative descriptions of DP recurrences. Autogen analyzes the set of DP table locations accessed by the iterative algorithm when run on a DP table of small size and automatically identifies a recursive access pattern and a corresponding provably correct recursive divide-and-conquer algorithm for solving the DP recurrence. We use Autogen to autodiscover efficient algorithms for several well-known problems. Our experimental results show that several autodiscovered algorithms significantly outperform the existing iterative/loop-based algorithms. To the best of our knowledge, Autogen is the first algorithm that can automatically discover new nontrivial divide-and-conquer algorithms.
Thursday, August 9, 2018 - 11:00 to 12:00