{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T12:15:46Z","timestamp":1770639346155,"version":"3.49.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1645514 and CCF-1750399"],"award-info":[{"award-number":["CCF-1645514 and CCF-1750399"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"French program Investissement d'avenir"},{"name":"LabEx PERSYVAL-Lab","award":["ANR-11-LABX-0025-01"],"award-info":[{"award-number":["ANR-11-LABX-0025-01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            The polyhedral model has been successfully used in production compilers. Nevertheless, only a very restricted class of applications can benefit from it. Recent proposals investigated how runtime information could be used to apply polyhedral optimization on applications that do not statically fit the model. In this work, we go one step further in that direction. We propose the\n            <jats:italic>folding-based analysis<\/jats:italic>\n            that, from the output of an instrumented program execution, builds a compact polyhedral representation. It is able to accurately detect affine dependencies, fixed-stride memory accesses, and induction variables in programs. It scales to real-life applications, which often include some nonaffine dependencies and accesses in otherwise affine code. This is enabled by a safe fine-grained polyhedral overapproximation mechanism. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about the potential for complex polyhedral transformations.\n          <\/jats:p>","DOI":"10.1145\/3363785","type":"journal-article","created":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T13:21:11Z","timestamp":1576675271000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Building a Polyhedral Representation from an Instrumented Execution"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2740-6428","authenticated-orcid":false,"given":"Manuel","family":"Selva","sequence":"first","affiliation":[{"name":"University of Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG"}]},{"given":"Fabian","family":"Gruber","sequence":"additional","affiliation":[{"name":"University of Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG"}]},{"given":"Diogo","family":"Sampaio","sequence":"additional","affiliation":[{"name":"University of Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG"}]},{"given":"Christophe","family":"Guillon","sequence":"additional","affiliation":[{"name":"STMicroelectronics"}]},{"given":"Louis-No\u00ebl","family":"Pouchet","sequence":"additional","affiliation":[{"name":"Colorado State University"}]},{"given":"Fabrice","family":"Rastello","sequence":"additional","affiliation":[{"name":"Univeristy of Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG"}]}],"member":"320","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814285"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.and.EUC.2013.103"},{"key":"e_1_2_1_3_1","volume-title":"Generating loops for scanning polyhedra: Cloog users guide. Polyhedron 2","author":"Bastoul C\u00e9dric","year":"2004","unstructured":"C\u00e9dric Bastoul . 2004. Generating loops for scanning polyhedra: Cloog users guide. Polyhedron 2 ( 2004 ). C\u00e9dric Bastoul. 2004. Generating loops for scanning polyhedra: Cloog users guide. Polyhedron 2 (2004)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1247360.1247401"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Erik Berg and Erik Hagersten. 2005. Fast data-locality profiling of native execution. In ACM SIGMETRICS Performance Evaluation Review. ACM.  Erik Berg and Erik Hagersten. 2005. Fast data-locality profiling of native execution. In ACM SIGMETRICS Performance Evaluation Review. ACM.","DOI":"10.1145\/1064212.1064232"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847366_23"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201908)","author":"Bondhugula Uday","unstructured":"Uday Bondhugula , Albert Hartono , J. Ramanujam , and P. Sadayappan . 2008. A practical automatic polyhedral parallelizer and locality optimizer . In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201908) . ACM. Uday Bondhugula, Albert Hartono, J. Ramanujam, and P. Sadayappan. 2008. A practical automatic polyhedral parallelizer and locality optimizer. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201908). ACM."},{"key":"e_1_2_1_8_1","volume-title":"The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, Proceedings.","author":"Brodal G. S.","unstructured":"G. S. Brodal and R. Jacob . 2002. Dynamic planar convex hull . In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, Proceedings. G. S. Brodal and R. Jacob. 2002. Dynamic planar convex hull. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, Proceedings."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICOSST.2012.6472824"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2009.5306797"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2010.5650274"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209947"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3049832.3049864"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISIS.2008.52"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_16_1","volume-title":"Encyclopedia of Parallel Computing","author":"Feautrier Paul","unstructured":"Paul Feautrier and Christian Lengauer . 2011. Polyhedron model . In Encyclopedia of Parallel Computing . Springer . Paul Feautrier and Christian Lengauer. 2011. Polyhedron model. In Encyclopedia of Parallel Computing. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_2_1_18_1","unstructured":"Fabian Gruber Manuel Selva Diogo Sampaio Christophe Guillon Antoine Moynault Louis-No\u00ebl Pouchet and Fabrice Rastello. Python implementation of the folding based analysis. Retrieved from https:\/\/gitlab.inria.fr\/fgruber\/python-folding.  Fabian Gruber Manuel Selva Diogo Sampaio Christophe Guillon Antoine Moynault Louis-No\u00ebl Pouchet and Fabrice Rastello. Python implementation of the folding based analysis. Retrieved from https:\/\/gitlab.inria.fr\/fgruber\/python-folding."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295737"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International QEMU User\u2019s Forum (QUF\u201911)","author":"Guillon Christophe","year":"2011","unstructured":"Christophe Guillon . 2011 . Program instrumentation with QEMU . In Proceedings of the International QEMU User\u2019s Forum (QUF\u201911) . Christophe Guillon. 2011. Program instrumentation with QEMU. In Proceedings of the International QEMU User\u2019s Forum (QUF\u201911)."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams.","author":"Hershberger John","year":"2003","unstructured":"John Hershberger and Subhash Suri . 2003 . Convex hulls and related problems in data streams . In Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. John Hershberger and Subhash Suri. 2003. Convex hulls and related problems in data streams. In Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Justin Holewinski Ragavendar Ramamurthi Mahesh Ravishankar Naznin Fauzia Louis-No\u00ebl Pouchet Atanas Rountev and P. Sadayappan. 2012. Dynamic trace-based analysis of vectorization potential of applications. ACM SIGPLAN Notices 47 6 (2012).  Justin Holewinski Ragavendar Ramamurthi Mahesh Ravishankar Naznin Fauzia Louis-No\u00ebl Pouchet Atanas Rountev and P. Sadayappan. 2012. Dynamic trace-based analysis of vectorization potential of applications. ACM SIGPLAN Notices 47 6 (2012).","DOI":"10.1145\/2345156.2254108"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356058.1356071"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.47"},{"key":"e_1_2_1_26_1","volume-title":"HotPar\u00e210: Proceedings of the USENIX Workshop on Hot Topics in Parallelism.","author":"Kim Minjang","year":"2010","unstructured":"Minjang Kim , Hyesoon Kim , and Chi-Keung Luk . 2010 . Prospector: A dynamic data-dependence profiler to help parallel programming . In HotPar\u00e210: Proceedings of the USENIX Workshop on Hot Topics in Parallelism. Minjang Kim, Hyesoon Kim, and Chi-Keung Luk. 2010. Prospector: A dynamic data-dependence profiler to help parallel programming. In HotPar\u00e210: Proceedings of the USENIX Workshop on Hot Topics in Parallelism."},{"key":"e_1_2_1_27_1","volume-title":"Tools for High Performance Computing","author":"Li Zhen","year":"2014","unstructured":"Zhen Li , Rohit Atre , Zia Ul-Huda , Ali Jannesari , and Felix Wolf . 2015. DiscoPoP: A profiling tool to identify parallelization opportunities . In Tools for High Performance Computing 2014 . Springer . Zhen Li, Rohit Atre, Zia Ul-Huda, Ali Jannesari, and Felix Wolf. 2015. DiscoPoP: A profiling tool to identify parallelization opportunities. In Tools for High Performance Computing 2014. Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2011.5764685"},{"key":"e_1_2_1_29_1","volume-title":"2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS\u201914)","author":"Marin G.","unstructured":"G. Marin , J. Dongarra , and D. Terpstra . 2014. MIAMI: A framework for application performance diagnosis . In 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS\u201914) . G. Marin, J. Dongarra, and D. Terpstra. 2014. MIAMI: A framework for application performance diagnosis. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS\u201914)."},{"key":"e_1_2_1_30_1","volume-title":"Full runtime polyhedral optimizing loop transformations with the generation, instantiation, and scheduling of code-bones. Concurrency and Computation: Practice and Experience 29, 15","author":"Martinez Caama\u00f1o Juan Manuel","year":"2017","unstructured":"Juan Manuel Martinez Caama\u00f1o , Manuel Selva , Philippe Clauss , Artyom Baloian , and Willy Wolff . 2017. Full runtime polyhedral optimizing loop transformations with the generation, instantiation, and scheduling of code-bones. Concurrency and Computation: Practice and Experience 29, 15 ( 2017 ). e4192 cpe.4192. Juan Manuel Martinez Caama\u00f1o, Manuel Selva, Philippe Clauss, Artyom Baloian, and Willy Wolff. 2017. Full runtime polyhedral optimizing loop transformations with the generation, instantiation, and scheduling of code-bones. Concurrency and Computation: Practice and Experience 29, 15 (2017). e4192 cpe.4192."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)81047-8"},{"key":"e_1_2_1_32_1","volume-title":"Languages and Compilers for Parallel Computing","author":"Olschanowsky Catherine Mills","unstructured":"Catherine Mills Olschanowsky , Mustafa M. Tikir , Laura Carrington , and Allan Snavely . 2010. PSnAP: Accurate synthetic address streams through memory profiles . In Languages and Compilers for Parallel Computing , Guang R. Gao, Lori L. Pollock, John Cavazos, and Xiaoming Li (Eds.). Springer , Berlin . Catherine Mills Olschanowsky, Mustafa M. Tikir, Laura Carrington, and Allan Snavely. 2010. PSnAP: Accurate synthetic address streams through memory profiles. In Languages and Compilers for Parallel Computing, Guang R. Gao, Lori L. Pollock, John Cavazos, and Xiaoming Li (Eds.). Springer, Berlin."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11587514_15"},{"key":"e_1_2_1_34_1","unstructured":"Louis-No\u00ebl Pouchet. 2019. The PoCC polyhedral compiler collection. Retrieved from http:\/\/pocc.sourceforge.net.  Louis-No\u00ebl Pouchet. 2019. The PoCC polyhedral compiler collection. Retrieved from http:\/\/pocc.sourceforge.net."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854056"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024597010150"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079098"},{"key":"e_1_2_1_38_1","volume-title":"International Journal of Parallel Programming (Aug.","author":"Simb\u00fcrger Andreas","year":"2018","unstructured":"Andreas Simb\u00fcrger , Sven Apel , Armin Gr\u00f6\u00dflinger , and Christian Lengauer . 2018. PolyJIT: Polyhedral optimization just in time . International Journal of Parallel Programming (Aug. 2018 ). Andreas Simb\u00fcrger, Sven Apel, Armin Gr\u00f6\u00dflinger, and Christian Lengauer. 2018. PolyJIT: Polyhedral optimization just in time. International Journal of Parallel Programming (Aug. 2018)."},{"key":"e_1_2_1_39_1","unstructured":"Aravind Sukumaran-Rajam. 2015. Beyond the Realm of the Polyhedral Model: Combining Speculative Program Parallelization with Polyhedral Compilation. Theses. Universit\u00e9 de Strasbourg. Retrieved from https:\/\/hal.inria.fr\/tel-01251748.  Aravind Sukumaran-Rajam. 2015. Beyond the Realm of the Polyhedral Model: Combining Speculative Program Parallelization with Polyhedral Compilation. Theses. Universit\u00e9 de Strasbourg. Retrieved from https:\/\/hal.inria.fr\/tel-01251748."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2838734"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854321"},{"key":"e_1_2_1_42_1","volume-title":"GCC Research Opportunities Workshop (GROW\u201910)","author":"Trifunovic Konrad","year":"2010","unstructured":"Konrad Trifunovic , Albert Cohen , David Edelsohn , Feng Li , Tobias Grosser , Harsha Jagasia , Razya Ladelsky , Sebastian Pop , Jan Sj\u00f6din , and Ramakrishna Upadrasta . 2010 . GRAPHITE two years after: First lessons learned from real-world polyhedral compilation . In GCC Research Opportunities Workshop (GROW\u201910) . ACM. Konrad Trifunovic, Albert Cohen, David Edelsohn, Feng Li, Tobias Grosser, Harsha Jagasia, Razya Ladelsky, Sebastian Pop, Jan Sj\u00f6din, and Ramakrishna Upadrasta. 2010. GRAPHITE two years after: First lessons learned from real-world polyhedral compilation. In GCC Research Opportunities Workshop (GROW\u201910). ACM."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/647477.727776"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854322"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_1_46_1","first-page":"26","article-title":"Integrating profile-driven parallelism detection and machine-learning-based mapping","volume":"11","author":"Wang Zheng","year":"2014","unstructured":"Zheng Wang , Georgios Tournavitis , Bj\u00f6rn Franke , and Michael F. P. O\u2019Boyle . 2014 . Integrating profile-driven parallelism detection and machine-learning-based mapping . ACM Transactions on Architecture and Code Optimization (TACO) 11 , 1 (2014), 26 . Zheng Wang, Georgios Tournavitis, Bj\u00f6rn Franke, and Michael F. P. O\u2019Boyle. 2014. Integrating profile-driven parallelism detection and machine-learning-based mapping. ACM Transactions on Architecture and Code Optimization (TACO) 11, 1 (2014), 26.","journal-title":"ACM Transactions on Architecture and Code Optimization (TACO)"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3363785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3363785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:26Z","timestamp":1750203866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3363785"}},"subtitle":["Making Dynamic Analyses of Nonaffine Programs Scalable"],"short-title":[],"issued":{"date-parts":[[2019,12,17]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3363785"],"URL":"https:\/\/doi.org\/10.1145\/3363785","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,17]]},"assertion":[{"value":"2019-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}