{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:26Z","timestamp":1750306106237,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,12,7]],"date-time":"2017-12-07T00:00:00Z","timestamp":1512604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation (DFG) as part of the Transregional Collaborative Research Center \u201cInvasive Computing\u201d","award":["SFB\/TR 89"],"award-info":[{"award-number":["SFB\/TR 89"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            Today\u2019s MPSoCs (multiprocessor systems-on-chip) have brought up massively parallel processor array accelerators that may achieve a high computational efficiency by exploiting multiple levels of parallelism and different memory hierarchies. Such parallel processor arrays are perfect targets, particularly for the acceleration of nested loop programs due to their regular and massively parallel nature. However, existing loop parallelization techniques are often unable to exploit multiple levels of parallelism and are either I\/O or memory bounded. Furthermore, if the number of available processing elements becomes only known at runtime\u2014as in adaptive systems\u2014static approaches fail. In this article, we solve some of these problems by proposing a hybrid compile\/runtime\n            <jats:italic>multi-level symbolic parallelization technique<\/jats:italic>\n            that is able to: (a) exploit multiple levels of parallelism as well as (b) different memory hierarchies, and (c) to match the I\/O or memory capabilities of the target architecture for scenarios where the number of available processing elements is only known at runtime. Our proposed technique consists of two compile-time transformations: (a) symbolic hierarchical tiling followed by (b) symbolic multi-level scheduling. The tiling levels scheduled in parallel exploit different levels of parallelism, whereas the sequential one, different memory hierarchies. Furthermore, by tuning the size of the tiles on the individual levels, a tradeoff between the necessary I\/O-bandwidth and memory is possible, which facilitates obeying resource constraints. The resulting schedules are symbolic with respect to the problem size and tile sizes. Thus, the number of processing elements to map onto does not need to be known at compile time. At runtime, when the number of available processors becomes known, a simple prologue chooses a feasible schedule with respect to I\/O and memory constraints that is latency-optimal for the chosen tile size. In summary, our approach determines the set of feasible, latency-optimal symbolic loop schedule candidates at compile time, from which one is dynamically selected at runtime. This approach exploits multiple levels of parallelism, is independent of the problem size of the loop nest, and thereby avoids any expensive re-compilation at runtime. This is particularly important for low cost and memory-scarce embedded MPSoC platforms that may not afford to host a just-in-time compiler.\n          <\/jats:p>","DOI":"10.1145\/3092952","type":"journal-article","created":{"date-parts":[[2017,12,11]],"date-time":"2017-12-11T13:26:47Z","timestamp":1512998807000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Symbolic Multi-Level Loop Mapping of Loop Programs for Massively Parallel Processor Arrays"],"prefix":"10.1145","volume":"17","author":[{"given":"Alexandru","family":"Tanase","sequence":"first","affiliation":[{"name":"Hardware\/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Witterauf","sequence":"additional","affiliation":[{"name":"Hardware\/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00fcrgen","family":"Teich","sequence":"additional","affiliation":[{"name":"Hardware\/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Hannig","sequence":"additional","affiliation":[{"name":"Hardware\/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.1992.218583"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1105"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS\u201900)","author":"Darte Alain","year":"2000","unstructured":"Alain Darte , Robert Schreiber , B. Ramakrishna Rau , Frederic Vivien , B. Ramakrishna , and Rau Frdric Vivien . 2000 . A constructive solution to the juggling problem in systolic array synthesis . In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS\u201900) . 815--821. Alain Darte, Robert Schreiber, B. Ramakrishna Rau, Frederic Vivien, B. Ramakrishna, and Rau Frdric Vivien. 2000. A constructive solution to the juggling problem in systolic array synthesis. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS\u201900). 815--821."},{"key":"e_1_2_1_4_1","volume-title":"Fran\u00e7ois Jacquet, Samuel Jones, Nicolas Morey Chaisemartin, Fr\u00e9d\u00e9ric Riss, and others.","author":"de Dinechin Beno\u00eet Dupont","year":"2013","unstructured":"Beno\u00eet Dupont de Dinechin , Renaud Ayrignac , Pierre-Edouard Beaucamps , Patrice Couvert , Benoit Ganne , Pierre Guironnet de Massas , Fran\u00e7ois Jacquet, Samuel Jones, Nicolas Morey Chaisemartin, Fr\u00e9d\u00e9ric Riss, and others. 2013 . A clustered manycore processor architecture for embedded and accelerated applications. In HPEC. 1--6. Beno\u00eet Dupont de Dinechin, Renaud Ayrignac, Pierre-Edouard Beaucamps, Patrice Couvert, Benoit Ganne, Pierre Guironnet de Massas, Fran\u00e7ois Jacquet, Samuel Jones, Nicolas Morey Chaisemartin, Fr\u00e9d\u00e9ric Riss, and others. 2013. A clustered manycore processor architecture for embedded and accelerated applications. In HPEC. 1--6."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of Communicating Process Architectures (CPA\u201903)","author":"Duller Andrew","year":"2003","unstructured":"Andrew Duller , Gajinder Panesar , and Daniel Towner . 2003 . Parallel processing\u2014The picoChip way&excl; . In Proceedings of Communicating Process Architectures (CPA\u201903) . IOS Press, Enschede, The Netherlands, 125--138. Andrew Duller, Gajinder Panesar, and Daniel Towner. 2003. Parallel processing\u2014The picoChip way&excl;. In Proceedings of Communicating Process Architectures (CPA\u201903). IOS Press, Enschede, The Netherlands, 125--138."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/PARELEC.2006.43"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.739055"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2584660"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470459"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542301"},{"volume-title":"Proceedings of IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC\u201910)","author":"Howard J.","key":"e_1_2_1_11_1","unstructured":"J. Howard , S. Dighe , Y. Hoskote , S. Vangal , D. Finan , G. Ruhl , D. Jenkins , H. Wilson , N. Borkar , G. Schrom , F. Pailet , S. Jain , T. Jacob , S. Yada , S. Marella , P. Salihundam , V. Erraguntla , M. Konow , M. Riepen , G. Droege , J. Lindemann , M. Gries , T. Apel , K. Henriss , T. Lund-Larsen , S. Steibl , S. Borkar , V. De , R. V. D. Wijngaart , and T. Mattson . 2010. A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS . In Proceedings of IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC\u201910) . 108--109. J. Howard, S. Dighe, Y. Hoskote, S. Vangal, D. Finan, G. Ruhl, D. Jenkins, H. Wilson, N. Borkar, G. Schrom, F. Pailet, S. Jain, T. Jacob, S. Yada, S. Marella, P. Salihundam, V. Erraguntla, M. Konow, M. Riepen, G. Droege, J. Lindemann, M. Gries, T. Apel, K. Henriss, T. Lund-Larsen, S. Steibl, S. Borkar, V. De, R. V. D. Wijngaart, and T. Mattson. 2010. A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS. In Proceedings of IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC\u201910). 108--109."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.38"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13374-9_20"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362691"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/LES.2011.2124438"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2006.270293"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2009.934117"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250780"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160910.2160912"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2014.6961865"},{"volume-title":"Proceedings of the 15th Workshop on Compilers for Parallel Computing (CPC)","author":"Tavarageri Sanket","key":"e_1_2_1_21_1","unstructured":"Sanket Tavarageri , Albert Hartono , Muthu Baskaran , Louis-No\u00ebl Pouchet , J. Ramanujam , and P. Sadayappan . 2010. Parametric tiling of affine loop nests . In Proceedings of the 15th Workshop on Compilers for Parallel Computing (CPC) . Vienna, Austria. Sanket Tavarageri, Albert Hartono, Muthu Baskaran, Louis-No\u00ebl Pouchet, J. Ramanujam, and P. Sadayappan. 2010. Parametric tiling of affine loop nests. In Proceedings of the 15th Workshop on Compilers for Parallel Computing (CPC). Vienna, Austria."},{"key":"e_1_2_1_22_1","unstructured":"J\u00fcrgen Teich. 1993. A Compiler for Application Specific Processor Arrays. Shaker.  J\u00fcrgen Teich. 1993. A Compiler for Application Specific Processor Arrays. Shaker."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1524\/itit.2008.0499"},{"volume-title":"Multiprocessor System-on-Chip -- Hardware Design and Tool Integration","author":"Teich J\u00fcrgen","key":"e_1_2_1_24_1","unstructured":"J\u00fcrgen Teich , J\u00f6rg Henkel , Andreas Herkersdorf , Doris Schmitt-Landsiedel , Wolfgang Schr\u00f6der-Preikschat , and Gregor Snelting . 2011. Invasive computing: An overview . In Multiprocessor System-on-Chip -- Hardware Design and Tool Integration . Springer , 241--268. J\u00fcrgen Teich, J\u00f6rg Henkel, Andreas Herkersdorf, Doris Schmitt-Landsiedel, Wolfgang Schr\u00f6der-Preikschat, and Gregor Snelting. 2011. Invasive computing: An overview. In Multiprocessor System-on-Chip -- Hardware Design and Tool Integration. Springer, 241--268."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2013.6567543"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-014-0905-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/784892.784974"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.1989.100823"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Workshop on Algorithms and Parallel VLSI Architectures","volume":"339","author":"Thiele Lothar","year":"1991","unstructured":"Lothar Thiele and Vwani Prasad Roychowdhury . 1991 . Systematic design of local processor arrays for numerical algorithms . In Proceedings of the International Workshop on Algorithms and Parallel VLSI Architectures , Vol. A: Tutorials. Elsevier, Amsterdam, The Netherlands, 329-- 339 . Lothar Thiele and Vwani Prasad Roychowdhury. 1991. Systematic design of local processor arrays for numerical algorithms. In Proceedings of the International Workshop on Algorithms and Parallel VLSI Architectures, Vol. A: Tutorials. Elsevier, Amsterdam, The Netherlands, 329--339."},{"key":"e_1_2_1_30_1","volume-title":"Homepage Retrieved","author":"Tilera Corporation","year":"2013","unstructured":"Tilera Corporation . 2013. Homepage Retrieved February 1, 2013 from http:\/\/www.tilera.com. Tilera Corporation. 2013. Homepage Retrieved February 1, 2013 from http:\/\/www.tilera.com."},{"volume-title":"Proceedings of the IEEE Symposium on Parallel and Distributed Processing. 360--367","author":"Yang Tao","key":"e_1_2_1_31_1","unstructured":"Tao Yang and Oscar H. Ibarra . 1995. On symbolic scheduling and parallel complexity of loops . In Proceedings of the IEEE Symposium on Parallel and Distributed Processing. 360--367 . Tao Yang and Oscar H. Ibarra. 1995. On symbolic scheduling and parallel complexity of loops. In Proceedings of the IEEE Symposium on Parallel and Distributed Processing. 360--367."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092952","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3092952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:39Z","timestamp":1750217439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,7]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3092952"],"URL":"https:\/\/doi.org\/10.1145\/3092952","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,12,7]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}