Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic Programs
We present AUTOGEN—an algorithm that for a wide class of dynamic programming (DP) problems automatically discovers highly efficient cache-oblivious 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 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 parallel looping and tiled loop-based algorithms. Also these algorithms are less sensitive to fluctuations of memory and bandwidth compared with their looping counterparts, and their running times and energy profiles remain relatively more stable. To the best of our knowledge, AUTOGEN is the first algorithm that can automatically discover new nontrivial divide-and-conquer algorithms.
Mon 14 Mar Times are displayed in time zone: Greenwich Mean Time : Belfast change
14:20 - 16:00: AlgorithmsMain conference at Mallorca+Menorca Chair(s): Lawrence RauchwergerTexas A&M University | |||
14:20 - 14:45 Talk | Articulation Point Guided Redundancy Elimination for Betweenness Centrality Main conference Lei WangInstitute of Computing Technology, Chinese Academy of Science, Fan YangInstitute of Computing Technology, Chinese Academy of Science, Liangji ZhuangInstitute of Computing Technology, Chinese Academy of Science, Huimin CuiInstitute of Computing Technology, Chinese Academy of Sciences, Fang LvInstitute of Computing Technology, Chinese Academy of Sciences, Xiaobing FengICT CAS Link to publication DOI | ||
14:45 - 15:10 Talk | Multi-Core On-The-Fly SCC Decomposition Main conference Vincent BloemenUniversity of Twente, Alfons LaarmanVienna University of Technology, Jaco van de PolUniversity of Twente Link to publication DOI | ||
15:10 - 15:35 Talk | A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization Main conference Ramakrishnan KannanGeorgia Institute of Technology, Grey BallardSandia National Laboratories, Haesun ParkGeorgia Institute of Technology Link to publication DOI | ||
15:35 - 16:00 Talk | Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic Programs Main conference Rezaul ChowdhuryStony Brook University, Pramod GanapathiStony Brook University, Jesmin Jahan TithiIntel, CA, USA, Charles BachmeierMIT, Bradley KuszmaulMIT, Charles E. LeisersonMIT, Armando Solar-LezamaMIT, Yuan TangFudan University Link to publication DOI |