{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:15Z","timestamp":1750220955014,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T00:00:00Z","timestamp":1563408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery"],"award-info":[{"award-number":["Discovery"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            We present a method for compilation of multi-dimensional stream processing programs from affine recurrence equations with unbounded domains into imperative code with statically allocated memory. The method involves a novel polyhedral schedule transformation called periodic tiling. It accommodates existing polyhedral optimizations to improve memory access patterns and expose parallelism. This enables efficient execution of programming languages with unbounded recurrence equations, as well as optimization of existing languages from which this form can be derived. The method is experimentally evaluated on 5 DSP algorithms with large problem sizes. Results show potential for improved throughput compared to hand-optimized C++ (speedups on a 6-core Intel Xeon CPU up to 10\u00d7 with a geometric mean 3.3\u00d7).\n            <jats:sup>1<\/jats:sup>\n          <\/jats:p>","DOI":"10.1145\/3330999","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:14Z","timestamp":1563542234000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Polyhedral Compilation for Multi-dimensional Stream Processing"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3119-929X","authenticated-orcid":false,"given":"Jakob","family":"Leben","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, Canada"}]},{"given":"George","family":"Tzanetakis","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}]}],"member":"320","published-online":{"date-parts":[[2019,7,18]]},"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.5555\/2388996.2389051"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2845078"},{"volume-title":"Numerical Sound Synthesis: Finite Difference Schemes and Simulation in Musical Acoustics","author":"Bilbao Stefan","key":"e_1_2_1_6_1","unstructured":"Stefan Bilbao . 2009. Numerical Sound Synthesis: Finite Difference Schemes and Simulation in Musical Acoustics . John Wiley 8 Sons. Stefan Bilbao. 2009. Numerical Sound Synthesis: Finite Difference Schemes and Simulation in Musical Acoustics. John Wiley 8 Sons."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Uday Bondhugula Muthu Baskaran Sriram Krishnamoorthy J. Ramanujam Atanas Rountev and P. Sadayappan. 2008a. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In Compiler Construction. Springer Berlin 132--146.   Uday Bondhugula Muthu Baskaran Sriram Krishnamoorthy J. Ramanujam Atanas Rountev and P. Sadayappan. 2008a. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In Compiler Construction. Springer Berlin 132--146.","DOI":"10.1007\/978-3-540-78791-4_9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025114.1025159"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951749"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/PARELEC.2006.43"},{"key":"e_1_2_1_13_1","volume-title":"Janneck","author":"Eker Johan","year":"2003","unstructured":"Johan Eker and J\u00f6rn W . Janneck . 2003 . CAL Language Report: Specification of the CAL Actor Language. Technical Report. University of California at Berkeley. Johan Eker and J\u00f6rn W. Janneck. 2003. CAL Language Report: Specification of the CAL Actor Language. Technical Report. University of California at Berkeley."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_16_1","first-page":"6","article-title":"Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time","volume":"21","author":"Feautrier Paul","year":"1992","unstructured":"Paul Feautrier . 1992 a. Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time . Int. J. Parallel Program. 21 , 6 (Dec. 1992), 389--420. Paul Feautrier. 1992a. Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time. Int. J. Parallel Program. 21, 6 (Dec. 1992), 389--420.","journal-title":"Int. J. Parallel Program."},{"volume-title":"Encyclopedia of Parallel Computing","author":"Feautrier Paul","key":"e_1_2_1_17_1","unstructured":"Paul Feautrier and Christian Lengauer . 2011. Polyhedron model . In Encyclopedia of Parallel Computing , David Padua (Ed.). Springer US , Boston, MA , 1581--1592. Paul Feautrier and Christian Lengauer. 2011. Polyhedron model. In Encyclopedia of Parallel Computing, David Padua (Ed.). Springer US, Boston, MA, 1581--1592."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378740"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743016"},{"volume-title":"Scheduling Techniques for High-Throughput Loop Accelerators. Dissertation","author":"Hannig Frank","key":"e_1_2_1_21_1","unstructured":"Frank Hannig . 2009. Scheduling Techniques for High-Throughput Loop Accelerators. Dissertation . University of Erlangen-Nuremberg , Germany. Frank Hannig. 2009. Scheduling Techniques for High-Throughput Loop Accelerators. Dissertation. University of Erlangen-Nuremberg, Germany."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73588"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013208.1013209"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321418"},{"volume-title":"Buffer Analysis for Complete Application Graphs","author":"Keinert Joachim","key":"e_1_2_1_25_1","unstructured":"Joachim Keinert and J\u00fcrgen Teich . 2011. Buffer Analysis for Complete Application Graphs . Springer , New York, NY , 151--208. Joachim Keinert and J\u00fcrgen Teich. 2011. Buffer Analysis for Complete Application Graphs. Springer, New York, NY, 151--208."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250761"},{"key":"e_1_2_1_27_1","first-page":"3","article-title":"The ALPHA language and its use for the design of systolic arrays","volume":"3","author":"Verge Herv\u00e9 Le","year":"1991","unstructured":"Herv\u00e9 Le Verge , Christophe Mauras , and Patrice Quinton . 1991 . The ALPHA language and its use for the design of systolic arrays . J. VLSI Signal Process. Syst. 3 , 3 (Sep. 1991), 173--182. Herv\u00e9 Le Verge, Christophe Mauras, and Patrice Quinton. 1991. The ALPHA language and its use for the design of systolic arrays. J. VLSI Signal Process. Syst. 3, 3 (Sep. 1991), 173--182.","journal-title":"J. VLSI Signal Process. Syst."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2975980.2975983"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3330999"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Jakob Leben and George Tzanetakis. 2019. Polyhedral Compilation for Multi-dimensional Stream Processing: Addendum (Version 1). Zenodo.  Jakob Leben and George Tzanetakis. 2019. Polyhedral Compilation for Multi-dimensional Stream Processing: Addendum (Version 1). Zenodo.","DOI":"10.1145\/3330999"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00029-5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/527214.826063"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2002.800830"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2536747.2536750"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007554627716"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01558666"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(90)90105-I"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90326-O"},{"volume-title":"Compiler Construction","author":"Thies William","key":"e_1_2_1_40_1","unstructured":"William Thies , Michal Karczmarek , and Saman Amarasinghe . 2002a. StreamIt: A language for streaming applications . In Compiler Construction . Springer , Berlin , 179--196. William Thies, Michal Karczmarek, and Saman Amarasinghe. 2002a. StreamIt: A language for streaming applications. In Compiler Construction. Springer, Berlin, 179--196."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 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 Proceedings of the GCC Research Opportunities Workshop (GROW\u201910) . INRIA. Retrieved from https:\/\/hal.inria.fr\/inria-00551516. 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 Proceedings of the GCC Research Opportunities Workshop (GROW\u201910). INRIA. Retrieved from https:\/\/hal.inria.fr\/inria-00551516."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023833.1023864"},{"volume-title":"Handbook of Signal Processing Systems, Shuvra S","author":"Verdoolaege Sven","key":"e_1_2_1_44_1","unstructured":"Sven Verdoolaege . 2013. Polyhedral process networks . In Handbook of Signal Processing Systems, Shuvra S . Bhattacharyya, Ed F. Deprettere, Rainer Leupers , and Jarmo Takala (Eds.). Springer New York , New York, NY, 1335--1375. Sven Verdoolaege. 2013. Polyhedral process networks. In Handbook of Signal Processing Systems, Shuvra S. Bhattacharyya, Ed F. Deprettere, Rainer Leupers, and Jarmo Takala (Eds.). Springer New York, New York, NY, 1335--1375."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178372.3179509"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3330999","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3330999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:04Z","timestamp":1750204444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3330999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,18]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3330999"],"URL":"https:\/\/doi.org\/10.1145\/3330999","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2019,7,18]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}