EUVIMEDEUVIMED entdecken
Crossref

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 · 31.03.2017 · 4 (1) · 1-30

DOI: 10.1145/3125632 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, online erschienen am 05.10.2017. Verfasst von Rezaul Chowdhury und 8 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 53 Literaturangaben. Gefördert von: National Science Foundation, FoxConn, National Security Agency.

AbstractBibliografische AngabenZitieren

Abstract (Originalsprache)

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

Förderung

  • National Science Foundation
  • FoxConn
  • National Security Agency
  • U.S. Department of Energy

Zitieren

APA

Chowdhury, R., Ganapathi, P., Tschudi, S., Tithi, J. J., Bachmeier, C., Leiserson, C. E., Solar-Lezama, A., Kuszmaul, B. C., & Tang, Y. (2017). Autogen. ACM Transactions on Parallel Computing, 4(1), 1-30. https://doi.org/10.1145/3125632

Vancouver

Chowdhury R, Ganapathi P, Tschudi S, Tithi JJ, Bachmeier C, Leiserson CE, et al. Autogen. ACM Transactions on Parallel Computing. 2017;4(1):1-30. doi:10.1145/3125632

BibTeX
@article{Chowdhury2017,
  author = {Chowdhury, Rezaul and Ganapathi, Pramod and Tschudi, Stephen and Tithi, Jesmin Jahan and Bachmeier, Charles and Leiserson, Charles E. and Solar-Lezama, Armando and Kuszmaul, Bradley C. and Tang, Yuan},
  title = {Autogen},
  journal = {ACM Transactions on Parallel Computing},
  year = {2017},
  volume = {4},
  number = {1},
  pages = {1--30},
  doi = {10.1145/3125632}
}
Kostenlos starten →