{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:04Z","timestamp":1750308724823,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1s","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            The Process Networks (PNs) is a suitable parallel model of computation (MoC) used to specify embedded streaming applications in a parallel form facilitating the efficient mapping onto embedded parallel execution platforms. Unfortunately, specifying an application using a parallel MoC is a very difficult and highly error-prone task. To overcome the associated difficulties, we have developed the\n            <jats:italic>pn<\/jats:italic>\n            compiler, which derives specific Polyhedral Process Networks (PPN) parallel specifications from sequential static affine nested loop programs (SANLPs). However, there are many applications, for example, multimedia applications (MPEG coders\/decoders, smart cameras, etc.) that have adaptive and dynamic behavior which cannot be expressed as SANLPs. Therefore, in order to handle dynamic multimedia applications, in this article we address the important question whether we can relax some of the restrictions of the SANLPs while keeping the ability to perform compile-time analysis and to derive PPNs. Achieving this would significantly extend the range of applications that can be parallelized in an automated way.\n          <\/jats:p>\n          <jats:p>The main contribution of this article is a first approach for automated translation of affine nested loop programs with dynamic loop bounds into input-output equivalent Polyhedral Process Networks. In addition, we present a method for analyzing the execution overhead introduced in the PPNs derived from programs with dynamic loop bounds. The presented automated translation approach has been evaluated by deriving a PPN parallel specification from a real-life application called Low Speed Obstacle Detection (LSOD) used in the smart cameras domain. By executing the derived PPN, we have obtained results which indicate that the approach we present in this article facilitates efficient parallel implementations of sequential nested loop programs with dynamic loop bounds. That is, our approach reveals the possible parallelism available in such applications, which allows for the utilization of multiple cores in an efficient way.<\/jats:p>","DOI":"10.1145\/2536747.2536750","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Automated generation of polyhedral process networks from affine nested-loop programs with dynamic loop bounds"],"prefix":"10.1145","volume":"13","author":[{"given":"Dmitry","family":"Nadezhkin","sequence":"first","affiliation":[{"name":"Leiden Institute of Advanced Computer Science, Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hristo","family":"Nikolov","sequence":"additional","affiliation":[{"name":"Leiden Institute of Advanced Computer Science, Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todor","family":"Stefanov","sequence":"additional","affiliation":[{"name":"Leiden Institute of Advanced Computer Science, Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.978374"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1870926.1871107"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209947"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/581199.581216"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016720.1016737"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_9_1","first-page":"23","article-title":"Dataflow analysis of scalar and array references. Para","volume":"20","author":"Feautrier P.","year":"1991","unstructured":"Feautrier , P. 1991 . Dataflow analysis of scalar and array references. Para . Prog. 20 , 1, 23 -- 53 . Feautrier, P. 1991. Dataflow analysis of scalar and array references. Para. Prog. 20, 1, 23--53.","journal-title":"Prog."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/647429.723579"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00063-0"},{"volume-title":"Networks on Chip","author":"Goossens K.","key":"e_1_2_1_12_1","unstructured":"Goossens K. , Guaranteeing the quality of services in networks on chip . In Networks on Chip . Kluwer Publishers , 61--82. Goossens K., et al. 2003. Guaranteeing the quality of services in networks on chip. In Networks on Chip. Kluwer Publishers, 61--82."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 6th Workshop on Compilers for Parallel Computers","volume":"21","author":"Griebl M.","unstructured":"Griebl , M. and Lengauer , C . 1996. The loop parallelizer loopo . In Proceedings of the 6th Workshop on Compilers for Parallel Computers , vol. 21 . Forschungszentrum, 311--320. Griebl, M. and Lengauer, C. 1996. The loop parallelizer loopo. In Proceedings of the 6th Workshop on Compilers for Parallel Computers, vol. 21. Forschungszentrum, 311--320."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ESTMED.2009.5336828"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IFIP Congress 74","author":"Kahn G.","year":"1974","unstructured":"Kahn , G. 1974 . The Semantics of a simple language for parallel programming . In Proceedings of the IFIP Congress 74 . North-Holland Publishing Co. Kahn, G. 1974. The Semantics of a simple language for parallel programming. In Proceedings of the IFIP Congress 74. North-Holland Publishing Co."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268956"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1146980"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Mihal A. and Keutzer K. 2003. Mapping concurrent applications onto architectural platforms. In Networks on Chips A. Jantsch and H. Tenhunen Eds. Kluwer Academic Publishers 39--59.   Mihal A. and Keutzer K. 2003. Mapping concurrent applications onto architectural platforms. In Networks on Chips A. Jantsch and H. Tenhunen Eds. Kluwer Academic Publishers 39--59.","DOI":"10.1007\/0-306-48727-6_3"},{"volume-title":"Proceedings of SAMOS X. 372--379","author":"Nadezhkin D.","key":"e_1_2_1_19_1","unstructured":"Nadezhkin , D. and Stefanov , T . 2010. Identifying communication models in process networks derived from weakly dynamic programs . In Proceedings of SAMOS X. 372--379 . Nadezhkin, D. and Stefanov, T. 2010. Identifying communication models in process networks derived from weakly dynamic programs. In Proceedings of SAMOS X. 372--379."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.911337"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356058.1356074"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of DATE. 340--345","author":"Stefanov T.","year":"2004","unstructured":"Stefanov T. , 2004 . System design using Kahn process networks: The Compaan\/Laura approach . In Proceedings of DATE. 340--345 . Stefanov T., et al. 2004. System design using Kahn process networks: The Compaan\/Laura approach. In Proceedings of DATE. 340--345."},{"volume-title":"Proceedings of the 2nd Samos Workshop.","author":"Turjan A.","key":"e_1_2_1_25_1","unstructured":"Turjan , A. , Kienhuis , B. , and Deprettere , E . 2002. Realizations of the extended linearization model in the Compaan tool chain . In Proceedings of the 2nd Samos Workshop. Turjan, A., Kienhuis, B., and Deprettere, E. 2002. Realizations of the extended linearization model in the Compaan tool chain. In Proceedings of the 2nd Samos Workshop."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023833.1023864"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1155\/2007\/75947"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2536747.2536750","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2536747.2536750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:42Z","timestamp":1750277682000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2536747.2536750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":24,"journal-issue":{"issue":"1s","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2536747.2536750"],"URL":"https:\/\/doi.org\/10.1145\/2536747.2536750","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}