{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T10:03:32Z","timestamp":1766311412851,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,3,31]],"date-time":"2017-03-31T00:00:00Z","timestamp":1490918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1162196, CCF-1439084, CNS-1553510, CCF-1314547, CNS-1409238, IS-1447786, ACI-1053575"],"award-info":[{"award-number":["CCF-1162196, CCF-1439084, CNS-1553510, CCF-1314547, CNS-1409238, IS-1447786, ACI-1053575"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"FoxConn"},{"DOI":"10.13039\/100009226","name":"National Security Agency","doi-asserted-by":"publisher","award":["H98230-14-C-1424"],"award-info":[{"award-number":["H98230-14-C-1424"]}],"id":[{"id":"10.13039\/100009226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0008923"],"award-info":[{"award-number":["DE-SC0008923"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"<jats:p>\n            We present A\n            <jats:sc>utogen<\/jats:sc>\n            \u2014an 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\n            <jats:sc>utogen<\/jats:sc>\n            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\n            <jats:sc>utogen<\/jats:sc>\n            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\n            <jats:sc>utogen<\/jats:sc>\n            is the first algorithm that can automatically discover new nontrivial divide-and-conquer algorithms.\n          <\/jats:p>","DOI":"10.1145\/3125632","type":"journal-article","created":{"date-parts":[[2017,10,6]],"date-time":"2017-10-06T12:48:39Z","timestamp":1507294119000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Autogen"],"prefix":"10.1145","volume":"4","author":[{"given":"Rezaul","family":"Chowdhury","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pramod","family":"Ganapathi","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Tschudi","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesmin Jahan","family":"Tithi","sequence":"additional","affiliation":[{"name":"Intel Corporation, Santa Clara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles","family":"Bachmeier","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bradley C.","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Oracle"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Tang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,10,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"PAPI. 2017. Performance Application Programming Interface (PAPI). http:\/\/icl.cs.utk.edu\/papi\/.  PAPI. 2017. Performance Application Programming Interface (PAPI). http:\/\/icl.cs.utk.edu\/papi\/."},{"key":"e_1_2_1_2_1","unstructured":"XSEDE. 2017. Extreme Science and Engineering Discovery Environment (XSEDE). http:\/\/www.xsede.org\/.  XSEDE. 2017. Extreme Science and Engineering Discovery Environment (XSEDE). http:\/\/www.xsede.org\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44520-X_48"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/640075.640077"},{"volume-title":"Dynamic Programming","author":"Bellman Richard","key":"e_1_2_1_5_1","unstructured":"Richard Bellman . 1957. Dynamic Programming . Princeton University Press . Richard Bellman. 1957. Dynamic Programming. Princeton University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.71"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375595"},{"key":"e_1_2_1_9_1","unstructured":"Rezaul Chowdhury and Pramod Ganapathi. Divide-and-Conquer Variants of Bubble Selection and Insertion Sorts. Unpublished manuscript.  Rezaul Chowdhury and Pramod Ganapathi. Divide-and-Conquer Variants of Bubble Selection and Insertion Sorts. Unpublished manuscript."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43659-3_42"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087586"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851167"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109622"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378574"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9273-8"},{"volume-title":"Programming Languages and Their Compilers: Preliminary Notes","author":"Cocke John","key":"e_1_2_1_16_1","unstructured":"John Cocke . 1969. Programming Languages and Their Compilers: Preliminary Notes . Courant Institute of Mathematical Sciences, New York University . John Cocke. 1969. Programming Languages and Their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York University."},{"key":"e_1_2_1_17_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.93"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600524"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.15"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1053"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1988783.1988790"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_2_1_28_1","volume-title":"Lieberman","author":"Hillier Frederick S.","year":"2010","unstructured":"Frederick S. Hillier and Gerald J . Lieberman . 2010 . Introduction to Operations Research (9th ed.). McGraw-Hill . Frederick S. Hillier and Gerald J. Lieberman. 2010. Introduction to Operations Research (9th ed.). McGraw-Hill."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2983993"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_2_1_33_1","first-page":"141","article-title":"Applications of dynamic programming to agriculture, forestry and fisheries: Review and prognosis","volume":"49","author":"Kennedy John O. S.","year":"1981","unstructured":"John O. S. Kennedy . 1981 . Applications of dynamic programming to agriculture, forestry and fisheries: Review and prognosis . Review of Market Agricultural Economics 49 , 3 (1981), 141 -- 173 . John O. S. Kennedy. 1981. Applications of dynamic programming to agriculture, forestry and fisheries: Review and prognosis. Review of Market Agricultural Economics 49, 3 (1981), 141--173.","journal-title":"Review of Market Agricultural Economics"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_35_1","volume-title":"Introduction to the Design and Analysis of Algorithms","author":"Levitin Anany","unstructured":"Anany Levitin . 2011. Introduction to the Design and Analysis of Algorithms ( 3 rd ed.). Pearson . Anany Levitin. 2011. Introduction to the Design and Analysis of Algorithms (3rd ed.). Pearson.","edition":"3"},{"key":"e_1_2_1_36_1","volume-title":"Dynamic Programming: A Computational Tool. Studies in Computational Intelligence","author":"Lew Art","year":"2006","unstructured":"Art Lew and Holger Mauch . 2006 . Dynamic Programming: A Computational Tool. Studies in Computational Intelligence , Vol. 38 . Springer . Art Lew and Holger Mauch. 2006. Dynamic Programming: A Computational Tool. Studies in Computational Intelligence, Vol. 38. Springer."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27866-5_133"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2076021.2048076"},{"volume-title":"Automated Parallelisation of Dynamic Programming Recursions","author":"Reitzig Raphael","key":"e_1_2_1_39_1","unstructured":"Raphael Reitzig . 2012. Automated Parallelisation of Dynamic Programming Recursions . Masters Thesis : University of Kaiserslautern (2012) . Raphael Reitzig. 2012. Automated Parallelisation of Dynamic Programming Recursions. Masters Thesis: University of Kaiserslautern (2012)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1971.tb00910.x"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-0021(96)01016-7"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1978.1163055"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0145048"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.10.026"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1201\/EBK0824740993"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.218"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989508"},{"volume-title":"Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar\u201911)","author":"Tang Yuan","key":"e_1_2_1_49_1","unstructured":"Yuan Tang , Rezaul Chowdhury , Chi-Keung Luk , and Charles E. Leiserson . 2011. Coding stencil computations using the Pochoir stencil-specification language . In Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar\u201911) . Yuan Tang, Rezaul Chowdhury, Chi-Keung Luk, and Charles E. Leiserson. 2011. Coding stencil computations using the Pochoir stencil-specification language. In Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar\u201911)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688514"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.107"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2014.80"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2010.38"},{"key":"e_1_2_1_54_1","volume-title":"Hopcroft","author":"Ullman Jeffrey D.","year":"1974","unstructured":"Jeffrey D. Ullman , Alfred V. Aho , and John E . Hopcroft . 1974 . The Design and Analysis of Computer Algorithms. Addison-Wesley , Reading. Jeffrey D. Ullman, Alfred V. Aho, and John E. Hopcroft. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.09.002"},{"volume-title":"Introduction to Computational Biology: Maps, Sequences and Genomes","author":"Waterman Michael S.","key":"e_1_2_1_56_1","unstructured":"Michael S. Waterman . 1995. Introduction to Computational Biology: Maps, Sequences and Genomes . Chapman 8 Hall Ltd . Michael S. Waterman. 1995. Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman 8 Hall Ltd."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125632","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3125632","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3125632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:06Z","timestamp":1750217406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125632"}},"subtitle":["Automatic Discovery of Efficient Recursive Divide-8-Conquer Algorithms for Solving Dynamic Programming Problems"],"short-title":[],"issued":{"date-parts":[[2017,3,31]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/3125632"],"URL":"https:\/\/doi.org\/10.1145\/3125632","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2017,3,31]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}