Autogen

作者：Rezaul, Chowdhury; Pramod, Ganapathi; Stephen, Tschudi; Jesmin Jahan, Tithi; Charles, Bachmeier; Charles E., Leiserson; Armando, Solar-Lezama; Bradley C., Kuszmaul; Yuan, Tang

来源：ACM Transactions on Parallel Computing, 2017, 4(1): 1-30.

DOI：10.1145/3125632

<jats:p>
We present A
<jats:sc>utogen</jats:sc>
—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. A
<jats:sc>utogen</jats:sc>
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 A
<jats:sc>utogen</jats:sc>
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, A
<jats:sc>utogen</jats:sc>
is the first algorithm that can automatically discover new nontrivial divide-and-conquer algorithms.
</jats:p>

• 出版日期2017-3-31
• 单位复旦大学