Autogen: Automatic discovery of efficient recursive divide-&-conquer algorithms for solving dynamic programming problems

被引：11

作者：

Chowdhury, Rezaul ^{[1
]}

Ganapathi, Pramod ^{[2
]}

Tschudi, Stephen ^{[3
]}

Tithi, Jesmin Jahan ^{[4
]}

Bachmeier, Charles ^{[5
]}

Leiserson, Charles E. ^{[5
]}

Solar-Lezama, Armando ^{[5
]}

Kuszmaul, Bradley C. ^{[6
]}

Tang, Yuan ^{[7
]}

机构：

[1] Computer Science Department, Stony Brook University, Stony Brook,NY,11794, United States

[2] Bengaluru, Karnataka, India

[3] Google Inc., 1600 Amphitheatre Pkwy, Mountain View,CA,94043, United States

[4] Intel Corporation, SC12, 3600 Juliette Ln, Santa Clara,CA,95054, United States

[5] MIT Computer Science and Artificial Intelligence Laboratory, Cambridge,MA,02139, United States

[6] 37 Vaille Ave, Lexington,MA,02421, United States

[7] School of Software, Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai, China

来源：

ACM Transactions on Parallel Computing | 2017年 / 4卷 / 01期

基金：

美国国家科学基金会;

关键词：

Cache memory - Energy efficiency - Problem solving - Iterative methods;

D O I：

10.1145/3125632

中图分类号：

学科分类号：

摘要：

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. © 2017 ACM.

引用