Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems
© 2017 ACM. 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 t...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134866 |
| _version_ | 1826190864361193472 |
|---|---|
| author | Chowdhury, Rezaul Ganapathi, Pramod Tschudi, Stephen Tithi, Jesmin Jahan Bachmeier, Charles Leiserson, Charles E Solar-Lezama, Armando Kuszmaul, Bradley C Tang, Yuan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Chowdhury, Rezaul Ganapathi, Pramod Tschudi, Stephen Tithi, Jesmin Jahan Bachmeier, Charles Leiserson, Charles E Solar-Lezama, Armando Kuszmaul, Bradley C Tang, Yuan |
| author_sort | Chowdhury, Rezaul |
| collection | MIT |
| description | © 2017 ACM. 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. |
| first_indexed | 2024-09-23T08:46:46Z |
| format | Article |
| id | mit-1721.1/134866 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:46:46Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1348662023-09-28T20:12:59Z Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems Chowdhury, Rezaul Ganapathi, Pramod Tschudi, Stephen Tithi, Jesmin Jahan Bachmeier, Charles Leiserson, Charles E Solar-Lezama, Armando Kuszmaul, Bradley C Tang, Yuan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2017 ACM. 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. 2021-10-27T20:09:33Z 2021-10-27T20:09:33Z 2017 2019-06-12T15:30:06Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/134866 en 10.1145/3125632 ACM Transactions on Parallel Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Chowdhury, Rezaul Ganapathi, Pramod Tschudi, Stephen Tithi, Jesmin Jahan Bachmeier, Charles Leiserson, Charles E Solar-Lezama, Armando Kuszmaul, Bradley C Tang, Yuan Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems |
| title | Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems |
| title_full | Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems |
| title_fullStr | Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems |
| title_full_unstemmed | Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems |
| title_short | Autogen: Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems |
| title_sort | autogen automatic discovery of efficient recursive divide 8 conquer algorithms for solving dynamic programming problems |
| url | https://hdl.handle.net/1721.1/134866 |
| work_keys_str_mv | AT chowdhuryrezaul autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT ganapathipramod autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT tschudistephen autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT tithijesminjahan autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT bachmeiercharles autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT leisersoncharlese autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT solarlezamaarmando autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT kuszmaulbradleyc autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems AT tangyuan autogenautomaticdiscoveryofefficientrecursivedivide8conqueralgorithmsforsolvingdynamicprogrammingproblems |