{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T08:51:11Z","timestamp":1777625471178,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T00:00:00Z","timestamp":1503360000000},"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\/4 and AP 206\/6"],"award-info":[{"award-number":["AP 206\/4 and 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":[[2017,9,30]]},"abstract":"<jats:p>The polyhedron model is a powerful model to identify and apply systematically loop transformations that improve data locality (e.g., via tiling) and enable parallelization. In the polyhedron model, a loop transformation is, essentially, represented as an affine function. Well-established algorithms for the discovery of promising transformations are based on performance models. These algorithms have the drawback of not being easily adaptable to the characteristics of a specific program or target hardware. An iterative search for promising loop transformations is more easily adaptable and can help to learn better models. We present an iterative optimization method in the polyhedron model that targets tiling and parallelization. The method enables either a sampling of the search space of legal loop transformations at random or a more directed search via a genetic algorithm. For the latter, we propose a set of novel, tailored reproduction operators. We evaluate our approach against existing iterative and model-driven optimization strategies. We compare the convergence rate of our genetic algorithm to that of random exploration. Our approach of iterative optimization outperforms existing optimization techniques in that it finds loop transformations that yield significantly higher performance. If well configured, then random exploration turns out to be very effective and reduces the need for a genetic algorithm.<\/jats:p>","DOI":"10.1145\/3109482","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Iterative Schedule Optimization for Parallelization in the Polyhedron Model"],"prefix":"10.1145","volume":"14","author":[{"given":"Stefan","family":"Ganser","sequence":"first","affiliation":[{"name":"University of Passau, Faculty of Computer Science and Mathematics, Innstrasse, Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"Gr\u00f6sslinger","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norbert","family":"Siegmund","sequence":"additional","affiliation":[{"name":"Bauhaus-University, Weimar, 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":[[2017,8,22]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"T. W. Anderson and J. D. Finn. 1996. The New Statistical Analysis of Data. Springer.  T. W. Anderson and J. D. Finn. 1996. The New Statistical Analysis of Data. Springer.","DOI":"10.1007\/978-1-4612-4000-6"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277691"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1995.tb02031.x"},{"key":"e_1_2_2_5_1","series-title":"Lecture Notes in Computer Science","volume-title":"Compiler Construction","author":"Bondhugula U.","unstructured":"U. Bondhugula and others. 2008. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model . In Compiler Construction . Lecture Notes in Computer Science , Vol. 4959 , Laurie Hendren (Ed.). Springer , 132--146. U. Bondhugula and others. 2008. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In Compiler Construction. Lecture Notes in Computer Science, Vol. 4959, Laurie Hendren (Ed.). Springer, 132--146."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896389"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1049\/ip-sen:20030559"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_2_12_1","volume-title":"Encyclopedia of Parallel Computing","volume":"3","author":"Feautrier P.","unstructured":"P. Feautrier and C. Lengauer . 2011. Polyhedron model . In Encyclopedia of Parallel Computing , Vol. 3 , D. Padua and others (Eds.). Springer, 1581--1591. P. Feautrier and C. Lengauer. 2011. Polyhedron model. In Encyclopedia of Parallel Computing, Vol. 3, D. Padua and others (Eds.). Springer, 1581--1591."},{"key":"e_1_2_2_13_1","first-page":"6","article-title":"Index set splitting","volume":"28","author":"Griebl M.","year":"2000","unstructured":"M. Griebl , P. Feautrier , and C. Lengauer . 2000 . Index set splitting . Int. J. Par. Prog. 28 , 6 (Dec. 2000), 607--631. M. Griebl, P. Feautrier, and C. Lengauer. 2000. Index set splitting. Int. J. Par. Prog. 28, 6 (Dec. 2000), 607--631.","journal-title":"Int. J. Par. Prog."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743016"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOSE.2007.29"},{"key":"e_1_2_2_17_1","volume-title":"Encyclopedia of Parallel Computing","author":"Irigoin F.","year":"2040","unstructured":"F. Irigoin . 2011. Tiling . In Encyclopedia of Parallel Computing , Vol. 4 , D. Padua and others (Eds.). Springer , 2040 --2049. F. Irigoin. 2011. Tiling. In Encyclopedia of Parallel Computing, Vol. 4, D. Padua and others (Eds.). Springer, 2040--2049."},{"key":"e_1_2_2_18_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."},{"key":"e_1_2_2_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Languages and Compilers for Parallel Computing","author":"Kennedy K.","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 . Lecture Notes in Computer Science , Vol. 768 , U. Banerjee and others (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. Lecture Notes in Computer Science, Vol. 768, U. Banerjee and others (Eds.). Springer, 301--320."},{"key":"e_1_2_2_21_1","volume-title":"Handbook of Statistics","volume":"4","author":"Krishnaiah P. R.","unstructured":"P. R. Krishnaiah and P. K. Sen . 1984 . Handbook of Statistics , Vol. 4 . Elsevier. P. R. Krishnaiah and P. K. Sen. 1984. Handbook of Statistics, Vol. 4. Elsevier."},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the BSD Conference (BSDCan\u201908)","author":"Lattner C.","year":"2008","unstructured":"C. Lattner . 2008 . LLVM and clang: Next generation compiler technology . In Proceedings of the BSD Conference (BSDCan\u201908) . C. Lattner. 2008. LLVM and clang: Next generation compiler technology. In Proceedings of the BSD Conference (BSDCan\u201908)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJCSE.2009.027002"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1006209.1006243"},{"key":"e_1_2_2_26_1","volume-title":"An Introduction to Genetic Algorithms","author":"Mitchell M.","unstructured":"M. Mitchell . 1998. An Introduction to Genetic Algorithms . MIT Press . M. Mitchell. 1998. An Introduction to Genetic Algorithms. MIT Press."},{"key":"e_1_2_2_27_1","volume-title":"High-Performance Computing and Networking (HPCN Europe)","author":"Nisbet A.","unstructured":"A. Nisbet . 1998. GAPS: A compiler framework for genetic algorithm (GA) optimised parallelisation . In High-Performance Computing and Networking (HPCN Europe) , P. Sloot, M. Bubak, and B. Hertzberger (Eds.). Springer , 987--989. A. Nisbet. 1998. GAPS: A compiler framework for genetic algorithm (GA) optimised parallelisation. In High-Performance Computing and Networking (HPCN Europe), P. Sloot, M. Bubak, and B. Hertzberger (Eds.). Springer, 987--989."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 9th International Workshop on Compilers for Parallel Computers (CPC\u201901)","author":"Nisbet A.","year":"2001","unstructured":"A. Nisbet . 2001 . Towards retargettable compilers -- Feedback directed compilation using genetic algorithms . In Proceedings of the 9th International Workshop on Compilers for Parallel Computers (CPC\u201901) . A. Nisbet. 2001. Towards retargettable compilers -- Feedback directed compilation using genetic algorithms. In Proceedings of the 9th International Workshop on Compilers for Parallel Computers (CPC\u201901)."},{"key":"e_1_2_2_29_1","unstructured":"M. Odersky L. Spoon and B. Venners. 2008. Programming in Scala. Artima.  M. Odersky L. Spoon and B. Venners. 2008. Programming in Scala. Artima."},{"key":"e_1_2_2_30_1","volume-title":"Encyclopedia of Parallel Computing, D. Padua and others (Eds.).","author":"Padua D.","unstructured":"D. Padua . 2011. Parallelization , automatic . In Encyclopedia of Parallel Computing, D. Padua and others (Eds.). Vol. 3 . Springer , 1442--1450. D. Padua. 2011. Parallelization, automatic. In Encyclopedia of Parallel Computing, D. Padua and others (Eds.). Vol. 3. Springer, 1442--1450."},{"key":"e_1_2_2_31_1","unstructured":"L.-N. Pouchet. 2012. LeTSeE\u2014The LEgal Transformation SpacE Explorator. Retrieved from http:\/\/web.cs.ucla.edu\/ pouchet\/software\/letsee\/.  L.-N. Pouchet. 2012. LeTSeE\u2014The LEgal Transformation SpacE Explorator. Retrieved from http:\/\/web.cs.ucla.edu\/ pouchet\/software\/letsee\/."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.21"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375594"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.14"},{"key":"e_1_2_2_35_1","unstructured":"L.-N. Pouchet and T. Yuki. 2015. PolyBench 4.1. Retrieved May2015 from http:\/\/web.cse.ohio-state.edu\/&sim;pouchet\/software\/polybench\/.  L.-N. Pouchet and T. Yuki. 2015. PolyBench 4.1. Retrieved May2015 from http:\/\/web.cse.ohio-state.edu\/&sim;pouchet\/software\/polybench\/."},{"key":"e_1_2_2_36_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","unstructured":"A. Schrijver . 1994. Theory of Linear and Integer Programming . John Wiley & Sons . A. Schrijver. 1994. Theory of Linear and Integer Programming. John Wiley & Sons."},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the International Workshop on GCC Research Opportunities (GROW\u201910)","author":"Trifunovic K.","year":"2010","unstructured":"K. Trifunovic and others. 2010 . GRAPHITE two years after: First lessons learned from real-world polyhedral compilation . In Proceedings of the International Workshop on GCC Research Opportunities (GROW\u201910) . 1--13. K. Trifunovic and others. 2010. GRAPHITE two years after: First lessons learned from real-world polyhedral compilation. In Proceedings of the International Workshop on GCC Research Opportunities (GROW\u201910). 1--13."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429127"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407876"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3109482","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3109482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:44Z","timestamp":1750212824000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3109482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,22]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3109482"],"URL":"https:\/\/doi.org\/10.1145\/3109482","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,22]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}