{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:52:53Z","timestamp":1756385573906,"version":"3.41.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,12,19]],"date-time":"2018-12-19T00:00:00Z","timestamp":1545177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["AP 206\/6"],"award-info":[{"award-number":["AP 206\/6"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>Iterative program optimization is known to be able to adapt more easily to particular programs and target hardware than model-based approaches. An approach is to generate random program transformations and evaluate their profitability by applying them and benchmarking the transformed program on the target hardware. This procedure\u2019s large computational effort impairs its practicality tremendously, though.<\/jats:p>\n          <jats:p>To address this limitation, we pursue the guidance of a genetic algorithm for program optimization via feedback from surrogate performance models. We train the models on program transformations that were evaluated during previous iterative optimizations. Our representation of programs and program transformations refers to the polyhedron model. The representation is particularly meaningful for an optimization of loop programs that profit a from coarse-grained parallelization for execution on modern multicore-CPUs. Our evaluation reveals that surrogate performance models can be used to speed up the optimization of loop programs. We demonstrate that we can reduce the benchmarking effort required for an iterative optimization and degrade the resulting speedups by an average of 15%.<\/jats:p>","DOI":"10.1145\/3291773","type":"journal-article","created":{"date-parts":[[2018,12,19]],"date-time":"2018-12-19T13:07:08Z","timestamp":1545224828000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Speeding up Iterative Polyhedral Schedule Optimization with Surrogate Performance Models"],"prefix":"10.1145","volume":"15","author":[{"given":"Stefan","family":"Ganser","sequence":"first","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"Gr\u00f6\u00dflinger","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norbert","family":"Siegmund","sequence":"additional","affiliation":[{"name":"Bauhaus-University, Weimar, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Apel","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Lengauer","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.37"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502897"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"T. W. Anderson and J. D. Finn. 1996. The New Statistical Analysis of Data. Springer Berlin.  T. W. Anderson and J. D. Finn. 1996. The New Statistical Analysis of Data. Springer Berlin.","DOI":"10.1007\/978-1-4612-4000-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2928270"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872421.2872424"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3124452"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400711"},{"volume-title":"Proceedings of the 12th International Conference on Machine Learning (ICML\u201995)","author":"Baluja S.","key":"e_1_2_1_8_1","unstructured":"S. Baluja and R. Caruana . 1995. Removing the genetics from the standard genetic algorithm . In Proceedings of the 12th International Conference on Machine Learning (ICML\u201995) . Morgan Kaufmann, 38--46. S. Baluja and R. Caruana. 1995. Removing the genetics from the standard genetic algorithm. In Proceedings of the 12th International Conference on Machine Learning (ICML\u201995). Morgan Kaufmann, 38--46."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3011017"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158120"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.4.769"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025127.1025992"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1995.tb02031.x"},{"key":"e_1_2_1_16_1","first-page":"L","article-title":"Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model","volume":"4959","author":"Bondhugula U.","year":"2008","unstructured":"U. Bondhugula 2008 . Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model . In Compiler Construction, LNCS , Vol. 4959 , L . Hendren (Ed.). Springer, Berlin, 132--146. U. Bondhugula et al. 2008. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In Compiler Construction, LNCS, Vol. 4959, L. Hendren (Ed.). Springer, Berlin, 132--146.","journal-title":"Compiler Construction, LNCS"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854317"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2615094"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896389"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010933404324"},{"key":"e_1_2_1_21_1","unstructured":"L. Breiman J. H. Friedman R. A. Olshen and C. J. Stone. 1984. Classification and Regression Trees. Wadsworth.  L. Breiman J. H. Friedman R. A. Olshen and C. J. Stone. 1984. Classification and Regression Trees. Wadsworth."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.32"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2035451"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378859"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1088149.1088169"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065910.1065921"},{"volume-title":"A Performance Prediction Function Based on the Exploration of a Schedule Search Space in the Polyhedron Model. Master\u2019s thesis","author":"Danner D. K.","key":"e_1_2_1_27_1","unstructured":"D. K. Danner . 2017. A Performance Prediction Function Based on the Exploration of a Schedule Search Space in the Polyhedron Model. Master\u2019s thesis . University of Passau . D. K. Danner. 2017. A Performance Prediction Function Based on the Exploration of a Schedule Search Space in the Polyhedron Model. Master\u2019s thesis. University of Passau."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_31_1","unstructured":"P. Feautrier and C. Lengauer. 2011. Polyhedron model. In Encyclopedia of Parallel Computing David A. Padua (Ed.). Vol. 3. Springer Berlin 1581--1591.  P. Feautrier and C. Lengauer. 2011. Polyhedron model. In Encyclopedia of Parallel Computing David A. Padua (Ed.). Vol. 3. Springer Berlin 1581--1591."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/5666.5673"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-010-0161-2"},{"key":"e_1_2_1_34_1","unstructured":"Stefan Ganser etal 2018. Supplementary Web site. Retrieved from https:\/\/stganser.bitbucket.io\/taco2018\/.  Stefan Ganser et al. 2018. Supplementary Web site. Retrieved from https:\/\/stganser.bitbucket.io\/taco2018\/."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3109482"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743016"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"G. Hager and G. Wellein. 2011. Introduction to High Performance Computing for Scientists and Engineers. CRC Press.   G. Hager and G. Wellein. 2011. Introduction to High Performance Computing for Scientists and Engineers. CRC Press.","DOI":"10.1201\/EBK1439811924"},{"key":"e_1_2_1_39_1","volume-title":"Encyclopedia of Parallel Computing, David A","author":"Irigoin F.","year":"2040","unstructured":"F. Irigoin . 2011. Tiling . In Encyclopedia of Parallel Computing, David A . Padua (Ed.). Vol. 4 . Springer , 2040 --2049. F. Irigoin. 2011. Tiling. In Encyclopedia of Parallel Computing, David A. Padua (Ed.). Vol. 4. Springer, 2040--2049."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-016-0535-4"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the IEEE First International Conference on Algorithms and Architectures for Parallel Processing (ICAPP\u201995)","volume":"1","author":"Kelly W.","unstructured":"W. Kelly and W. Pugh . 1995. A unifying framework for iteration reordering transformations . In Proceedings of the IEEE First International Conference on Algorithms and Architectures for Parallel Processing (ICAPP\u201995) , Vol. 1 . IEEE, 153--162. W. Kelly and W. Pugh. 1995. A unifying framework for iteration reordering transformations. In Proceedings of the IEEE First International Conference on Algorithms and Architectures for Parallel Processing (ICAPP\u201995), Vol. 1. IEEE, 153--162."},{"volume-title":"Languages and Compilers for Parallel Computing, LNCS","author":"Kennedy K.","key":"e_1_2_1_42_1","unstructured":"K. Kennedy and K. S. McKinley . 1993. Maximizing loop parallelism and improving data locality via loop fusion and distribution . In Languages and Compilers for Parallel Computing, LNCS , Vol. 768 , U. Banerjee et al. (Eds.). Springer , 301--320. K. Kennedy and K. S. McKinley. 1993. Maximizing loop parallelism and improving data locality via loop fusion and distribution. In Languages and Compilers for Parallel Computing, LNCS, Vol. 768, U. Banerjee et al. (Eds.). Springer, 301--320."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362691"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274653"},{"volume-title":"Proceedings of the 2nd IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201904)","author":"Lattner C.","key":"e_1_2_1_45_1","unstructured":"C. Lattner and V. Adve . 2004. LLVM: A compilation framework for lifelong program analysis 8 transformation . In Proceedings of the 2nd IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201904) . IEEE Computer Society, 75--88. C. Lattner and V. Adve. 2004. LLVM: A compilation framework for lifelong program analysis 8 transformation. In Proceedings of the 2nd IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201904). IEEE Computer Society, 75--88."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1006209.1006243"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"A. Monsifrot etal 2002. A machine learning approach to automatic production of compiler heuristics. In Artificial Intelligence: Methodology Systems and Applications LNCS 2443 D. Scott (Ed.). Springer 41--50.   A. Monsifrot et al. 2002. A machine learning approach to automatic production of compiler heuristics. In Artificial Intelligence: Methodology Systems and Applications LNCS 2443 D. Scott (Ed.). Springer 41--50.","DOI":"10.1007\/3-540-46148-5_5"},{"key":"e_1_2_1_49_1","unstructured":"S. Nembrini I. R. K\u00f6nig and M. N. Wright. 2018. The revival of the gini importance? OUP Bioinformatics (2018) 1--8.  S. Nembrini I. R. K\u00f6nig and M. N. Wright. 2018. The revival of the gini importance? OUP Bioinformatics (2018) 1--8."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/645562.659704"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259042"},{"volume-title":"Proceedings of the 43rd International Conference on Parallel Processing (ICPP\u201914)","author":"Park E.","key":"e_1_2_1_52_1","unstructured":"E. Park , C. Kartsaklis , and J. Cavazos . 2014. HERCULES: Strong patterns towards more intelligent predictive modeling . In Proceedings of the 43rd International Conference on Parallel Processing (ICPP\u201914) . IEEE Computer Society, 172--181. E. Park, C. Kartsaklis, and J. Cavazos. 2014. HERCULES: Strong patterns towards more intelligent predictive modeling. In Proceedings of the 43rd International Conference on Parallel Processing (ICPP\u201914). IEEE Computer Society, 172--181."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038698.2038711"},{"volume-title":"Proceedings of the 9th International Symposium on Code Generation and Optimization (CGO\u201911)","author":"Park E.","key":"e_1_2_1_54_1","unstructured":"E. Park , L.-N. Pouchet , J. Cavazos , A. Cohen , and P. Sadayappan . 2011. Predictive modeling in a polyhedral optimization space . In Proceedings of the 9th International Symposium on Code Generation and Optimization (CGO\u201911) . IEEE Computer Society, 119--129. E. Park, L.-N. Pouchet, J. Cavazos, A. Cohen, and P. Sadayappan. 2011. Predictive modeling in a polyhedral optimization space. In Proceedings of the 9th International Symposium on Code Generation and Optimization (CGO\u201911). IEEE Computer Society, 119--129."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.21"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375594"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.14"},{"key":"e_1_2_1_59_1","volume-title":"Research Report RR-6962. INRIA.","author":"Pouchet L.-N.","year":"2009","unstructured":"L.-N. Pouchet , U. Bondhugula , C. Bastoul , A. Cohen , R. Ramanujam , and P. Sadayappan . 2009 . Hybrid Iterative and Model-Driven Optimization in the Polyhedral Model . Research Report RR-6962. INRIA. Retrieved from https:\/\/hal.inria.fr\/inria-00419974. L.-N. Pouchet, U. Bondhugula, C. Bastoul, A. Cohen, R. Ramanujam, and P. Sadayappan. 2009. Hybrid Iterative and Model-Driven Optimization in the Polyhedral Model. Research Report RR-6962. INRIA. Retrieved from https:\/\/hal.inria.fr\/inria-00419974."},{"key":"e_1_2_1_60_1","unstructured":"L.-N. Pouchet and T. Yuki. {n.d.}. PolyBench 4.1. Retrieved from http:\/\/web.cse.ohio-state.edu\/pouchet\/software\/polybench\/.  L.-N. Pouchet and T. Yuki. {n.d.}. PolyBench 4.1. Retrieved from http:\/\/web.cse.ohio-state.edu\/pouchet\/software\/polybench\/."},{"volume-title":"Advances in Artificial Intelligence, LNAI","author":"Ruvinskiy R.","key":"e_1_2_1_61_1","unstructured":"R. Ruvinskiy and P. van Beek . 2015. An improved machine learning approach for selecting a polyhedral model transformation . In Advances in Artificial Intelligence, LNAI , Vol. 9091 . Springer , 100--113. R. Ruvinskiy and P. van Beek. 2015. An improved machine learning approach for selecting a polyhedral model transformation. In Advances in Artificial Intelligence, LNAI, Vol. 9091. Springer, 100--113."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/335231.335246"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086696.2086729"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429127"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_16"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"key":"e_1_2_1_68_1","unstructured":"S. Verdoolaege. 2018. Integer Set Library: Manual. INRIA. Version isl-0.19.  S. Verdoolaege. 2018. Integer Set Library: Manual. INRIA. Version isl-0.19."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1231-0"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_1_71_1","unstructured":"S. Verdoolaege and G. Janssens. 2017. Scheduling for PPCG. Technical Report CW706. CS Department KU Leuven.  S. Verdoolaege and G. Janssens. 2017. Scheduling for PPCG. Technical Report CW706. CS Department KU Leuven."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/109025.109083"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407876"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178372.3179507"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3291773","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3291773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:06Z","timestamp":1750208526000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3291773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,19]]},"references-count":71,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3291773"],"URL":"https:\/\/doi.org\/10.1145\/3291773","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2018,12,19]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}