{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T07:32:50Z","timestamp":1791271970830,"version":"4.1.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,4,8]],"date-time":"2016-04-08T00:00:00Z","timestamp":1460073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"INRIA Associate Team PolyFlow"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2016,5,2]]},"abstract":"<jats:p>Affine transformations have proven to be powerful for loop restructuring due to their ability to model a very wide range of transformations. A single multidimensional affine function can represent a long and complex sequence of simpler transformations. Existing affine transformation frameworks such as the Pluto algorithm, which include a cost function for modern multicore architectures for which coarse-grained parallelism and locality are crucial, consider only a subspace of transformations to avoid a combinatorial explosion in finding transformations. The ensuing practical trade-offs lead to the exclusion of certain useful transformations: in particular, transformation compositions involving loop reversals and loop skewing by negative factors. In addition, there is currently no proof that the algorithm successfully finds a tree of permutable loop bands for all affine loop nests. In this article, we propose an approach to address these two issues (1) by modeling a much larger space of practically useful affine transformations in conjunction with the existing cost function of Pluto, and (2) by extending the Pluto algorithm in a way that allows a proof for its soundness and completeness for all affine loop nests. We perform an experimental evaluation of both, the effect on compilation time, and performance of generated codes. The evaluation shows that our new framework, Pluto+, provides no degradation in performance for any benchmark from Polybench. For the Lattice Boltzmann Method (LBM) simulations with periodic boundary conditions, it provides a mean speedup of 1.33 \u00d7 over Pluto. We also show that Pluto+ does not increase compilation time significantly. Experimental results on Polybench show that Pluto+ increases overall polyhedral source-to-source optimization time by only 15%. In cases in which it improves execution time significantly, it increased polyhedral optimization time by only 2.04 \u00d7 .<\/jats:p>","DOI":"10.1145\/2896389","type":"journal-article","created":{"date-parts":[[2016,4,8]],"date-time":"2016-04-08T23:08:32Z","timestamp":1460156912000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["The Pluto+ Algorithm"],"prefix":"10.1145","volume":"38","author":[{"given":"Uday","family":"Bondhugula","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Acharya","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albert","family":"Cohen","sequence":"additional","affiliation":[{"name":"INRIA and ENS, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,4,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688512"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012293814832"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1177220"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/109625.109631"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Vinayaka Bandishti Irshad Pananilath and Uday Bondhugula. 2012. Tiling stencil computations to maximize parallelism. In Supercomputing. Article 40 11 pages.","DOI":"10.5555\/2388996.2389051"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025127.1025992"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628106"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788374.1788386"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854317"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254123"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.fluid.30.1.329"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90055-8"},{"key":"e_1_2_1_15_1","unstructured":"Cloog 2004. The CLooG Code Generator in the Polyhedral Model. http:\/\/www.cloog.org."},{"key":"e_1_2_1_16_1","volume-title":"Computational Infrastructure for Operations Research. Retrieved","author":"COIN-OR.","year":"2016","unstructured":"COIN-OR. 2001. Computational Infrastructure for Operations Research. Retrieved March 2, 2016 from http:\/\/www.coin-or.org."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Dominique d\u2019Humi\u00e8res. 2002. Multiple--relaxation--time Lattice Boltzmann models in three dimensions. Philosophical Transactions of the Royal Society of London. Series A: Mathematical Physical and Engineering Sciences 360 1792 437--451.","DOI":"10.1098\/rsta.2001.0955"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_22_1","unstructured":"GNU. 2012. GLPK (GNU Linear Programming Kit). Retrieved March 2 2016 from https:\/\/www.gnu.org\/software\/glpk\/."},{"key":"e_1_2_1_23_1","volume-title":"Automatic Parallelization of Loop Programs for Distributed Memory Architectures. Habilitation thesis","author":"Griebl Martin","unstructured":"Martin Griebl. 2004. Automatic Parallelization of Loop Programs for Distributed Memory Architectures. Habilitation thesis. University of Passau, Passau, Germany."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 1st International Workshop on Polyhedral Compilation Techniques (IMPACT\u201911)","author":"Grosser Tobias","year":"2011","unstructured":"Tobias Grosser, Hongbin Zheng, Ragesh Aloor, Andreas Simbrger, Armin Grolinger, and Louis-No\u00ebl Pouchet. 2011. Polly polyhedral optimization in LLVM. In Proceedings of the 1st International Workshop on Polyhedral Compilation Techniques (IMPACT\u201911)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542301"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987237.1987255"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2467268"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"F. Irigoin and R. Triolet. 1988. Supernode partitioning. In ACM SIGPLAN Principles of Programming Languages. ACM New York NY 319--329. 10.1145\/73560.73588","DOI":"10.1145\/73560.73588"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/215532"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/528717.796653"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462187"},{"key":"e_1_2_1_32_1","volume-title":"Filed","author":"Leung A.","year":"2009","unstructured":"A. Leung, N. T. Vasilache, B. Meister, and R. A. Lethin. 2010. Methods and apparatus for joint parallelism and locality optimization in source code compilation. (June 2010). US Patent 2010\/0070956 A1. Filed September 16, 2009, Issued March 18, 2010."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02577874"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/305138.305197"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263719"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00021-0"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.471.0057"},{"key":"e_1_2_1_38_1","volume-title":"Workshop on Asynchrony in the PGAS Programming Model.","author":"Meister Benoit","year":"2009","unstructured":"Benoit Meister, Allen Leung, Nicolas Vasilache, David Wohlford, C\u00e9dric Bastoul, and Richard Lethin. 2009. Productivity via automatic code generation for PGAS platforms with the R-stream compiler. In Workshop on Asynchrony in the PGAS Programming Model."},{"key":"e_1_2_1_39_1","volume-title":"Encyclopedia of Parallel Computing. 1756--1765.","author":"Meister Beno\u00eet","unstructured":"Beno\u00eet Meister, Nicolas Vasilache, David Wohlford, Muthu Baskaran, Allen Leung, and Richard Lethin. 2011. R-stream compiler. In Encyclopedia of Parallel Computing. 1756--1765."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694364"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89740-8_6"},{"key":"e_1_2_1_42_1","unstructured":"Palabos. 2012. Palabos. Retrieved March 2 2016 from http:\/\/www.palabos.org\/."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2739047"},{"key":"e_1_2_1_44_1","unstructured":"Pluto 2008. PLUTO: An automatic parallelizer and locality optimizer for affine loop nests. http:\/\/pluto-compiler.sourceforge.net."},{"key":"e_1_2_1_45_1","volume-title":"Polybench suite. Retrieved","author":"Polybench","year":"2016","unstructured":"Polybench 2010. Polybench suite. Retrieved March 2, 2016 from http:\/\/polybench.sourceforge.net."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375594"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926449"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007554627716"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1964536.1964546"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1175\/1520-0469(1975)032<0680:TDOFDM>2.0.CO;2"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.47"},{"key":"e_1_2_1_53_1","volume-title":"Standard Performance Evaluation Corporation. Retrieved","author":"Swarztrauber Paul N.","year":"2016","unstructured":"Paul N. Swarztrauber. 2000. 171.swim SPEC CPU2000 Benchmark Description File. Standard Performance Evaluation Corporation. Retrieved March 2, 2016 from http:\/\/www.spec.org\/cpu2000\/CFP2000\/171.swim\/docs\/171.swim.html."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989508"},{"key":"e_1_2_1_56_1","volume-title":"International Workshop on Polyhedral Compilation Techniques (IMPACT\u201912)","author":"Vasilache Nicolas","year":"2012","unstructured":"Nicolas Vasilache, Benoit Meister, Muthu Baskaran, and Richard Lethin. 2012. Joint scheduling and layout optimization to enable multi-level vectorization. In International Workshop on Polyhedral Compilation Techniques (IMPACT\u201912)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/113445.113449"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","unstructured":"D. Wonnacott. 2000. Using time skewing to eliminate idle time due to memory bandwidth and network limitations. In IPDPS. 171--180.","DOI":"10.5555\/846234.849346"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02106826"},{"key":"e_1_2_1_62_1","volume-title":"International Workshop on Polyhedral Compilation Techniques (IMPACT\u201914)","author":"Yuki Tomofumi","year":"2014","unstructured":"Tomofumi Yuki. 2014. Understanding Polybench\/C 3.2 kernels. In International Workshop on Polyhedral Compilation Techniques (IMPACT\u201914)."},{"key":"e_1_2_1_63_1","series-title":"Lecture Notes in Computer Science","volume-title":"Languages and Compilers for Parallel Computing","author":"Yuki Tomofumi","unstructured":"Tomofumi Yuki, Gautam Gupta, DaeGon Kim, Tanveer Pathan, and Sanjay Rajopadhye. 2013. AlphaZ: A system for design space exploration in the polyhedral model. In Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science, Vol. 7760. Springer, Berlin, 17--31."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552309.1552310"},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","unstructured":"Qisu Zou and Xiaoyi He. 1997. On pressure and velocity boundary conditions for the Lattice Boltzmann BGK model. Physics of Fluids (1994-present) 9 6 1591--1598.","DOI":"10.1063\/1.869307"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2896389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2896389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:18Z","timestamp":1750221558000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2896389"}},"subtitle":["A Practical Approach for Parallelization and Locality Optimization of Affine Loop Nests"],"short-title":[],"issued":{"date-parts":[[2016,4,8]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,5,2]]}},"alternative-id":["10.1145\/2896389"],"URL":"https:\/\/doi.org\/10.1145\/2896389","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,8]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}