SC16 Salt Lake City, UT

DS9. Automatic Discovery of Efficient Divide-and-Conquer Algorithms for Dynamic Programming Problems


Student: Pramod Ganapathi (Stony Brook University)
Advisor: Rezaul Chowdhury (Stony Brook University)
Abstract: We show that it is possible to develop algorithm(s) / framework(s) to automatically / semi-automatically discover algorithms that are simultaneously nontrivial, simple, fast, portable, and robust, which can be used to solve to a wide class of dynamic programming (DP) problems. We present AutoGen -- an algorithm that given any blackbox implementation of a DP recurrence from a wide class of DP problems can automatically discover a fast recursive divide-and-conquer algorithm for solving that problem on a shared-memory multicore machine. [Published in PPoPP 2016] We present AutoGen-Wave -- a framework for computer-assisted discovery of fast divide-and-conquer wavefront versions of the algorithms already generated by AutoGen. [Under review] As a first step toward extending AutoGen to handle DP recurrences with irregular data-dependent dependencies, we design an efficient cache-oblivious parallel algorithm to solve the Viterbi recurrence. [Accepted for Euro-Par 2016]

Summary: pdf
Presentation: pdf
Poster: pdf


Doctoral Showcase Index