{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:30Z","timestamp":1750306890400,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>To preserve the validity of loop nest transformations and parallelization, data dependences need to be analyzed. Memory dependences come in two varieties: true dependences or false dependences. While true dependences must be satisfied in order to preserve the correct order of computations, false dependences are induced by the reuse of a single memory location to store multiple values. False dependences reduce the degrees of freedom for loop transformations. In particular, loop tiling is severely limited in the presence of these dependences. While array expansion removes all false dependences, the overhead on memory and the detrimental impact on register-level reuse can be catastrophic.<\/jats:p>\n          <jats:p>We propose and evaluate a compilation technique to safely ignore a large number of false dependences in order to enable loop nest tiling in the polyhedral model. It is based on the precise characterization of interferences between live range intervals, and it does not incur any scalar or array expansion. Our algorithms have been implemented in the Pluto polyhedral compiler, and evaluated on the PolyBench suite.<\/jats:p>","DOI":"10.1145\/2400682.2400711","type":"journal-article","created":{"date-parts":[[2013,1,22]],"date-time":"2013-01-22T15:28:56Z","timestamp":1358868536000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Improved loop tiling based on the removal of spurious false dependences"],"prefix":"10.1145","volume":"9","author":[{"given":"Riyadh","family":"Baghdadi","sequence":"first","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure and INRIA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Albert","family":"Cohen","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure and INRIA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Verdoolaege","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure and INRIA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konrad","family":"Trifunovi\u0107","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure and INRIA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,1,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"volume-title":"Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC'06)","author":"Bouchez F.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93542.93553"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(81)90048-5"},{"volume-title":"Proceedings of the International Symposium on High Performance Computing","author":"Cohen A.","key":"e_1_2_1_5_1"},{"volume":"1685","volume-title":"Proceedings of the International European Conference on Parallel Processing (Euro-Par'98)","author":"Cohen A.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837303"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-005-4937-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55406"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_12_1","unstructured":"Griebl M. 2004. Automatic parallelization of loop programs for distributed memory architectures. Habilitation thesis Facult\u00e4t f\u00fcr Mathematik und Informatik Universit\u00e4t Passau.  Griebl M. 2004. Automatic parallelization of loop programs for distributed memory architectures. Habilitation thesis Facult\u00e4t f\u00fcr Mathematik und Informatik Universit\u00e4t Passau."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/645607.661494"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20"},{"key":"e_1_2_1_15_1","unstructured":"HMPP. 2012. Hmpp workbench: A directive-based multi-language and multi-target hybrid programming model. http:\/\/www.caps-entreprise.com\/hmpp.html.  HMPP. 2012. Hmpp workbench: A directive-based multi-language and multi-target hybrid programming model. http:\/\/www.caps-entreprise.com\/hmpp.html."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73588"},{"key":"e_1_2_1_17_1","unstructured":"Kennedy K. and Allen J. R. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann.   Kennedy K. and Allen J. R. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/183432.183443"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00029-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/143369.143426"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158515"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01736-0","volume-title":"Automatic Parallelization: An Overview of Fundamental Compiler Techniques","author":"Midkiff S.","year":"2012"},{"key":"e_1_2_1_23_1","unstructured":"Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann.   Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann."},{"volume-title":"Proceedings of the GCC Developers Summit.","author":"Pop S.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/365151.365152"},{"volume-title":"PGI accelerator programming model for Fortran & C v.1.3","author":"The Portland Group","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378852"},{"volume-title":"GCC Research Opportunities Workshop (GROW'10)","author":"Trifunovic K.","key":"e_1_2_1_28_1"},{"volume-title":"3rd GCC Research Opportunities Workshop.","author":"Trifunovic K.","key":"e_1_2_1_29_1"},{"volume":"768","volume-title":"Eds. Lecture Notes in Computer Science","author":"Tu P.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183448"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.97902"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2400682.2400711","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2400682.2400711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:52Z","timestamp":1750234732000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2400682.2400711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1145\/2400682.2400711"],"URL":"https:\/\/doi.org\/10.1145\/2400682.2400711","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2013,1]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}