{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:09:17Z","timestamp":1774631357211,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARTEMIS joint undertaking through the ALMARVI project","award":["621439"],"award-info":[{"award-number":["621439"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>Multi-scale dataflow models have actors acting at multiple granularity levels, e.g., a dataflow model of a video processing application with operations on frame, line, and pixel level. The state of the art timing analysis methods for both static and dynamic dataflow types aggregate the behaviours across all granularity levels into one, often large iteration, which is repeated without exploiting the structure within such an iteration. This poses scalability issues to dataflow analysis, because behaviour of the large iteration is analysed by some form of simulation that involves a large number of actor firings. We take a fresh perspective of what is happening inside the large iteration. We take advantage of the fact that the iteration is a sequence of smaller behaviours, each captured in a scenario, that are typically repeated many times. We use the (max ,+) linear model of dataflow to represent each of the scenarios with a matrix. This allows a compositional worst-case throughput analysis of the repeated scenarios by raising the matrices to the power of the number of repetitions, which scales logarithmically with the number of repetitions, whereas the existing throughput analysis scales linearly. We moreover provide the first exact worst-case latency analysis for scenario-aware dataflow. This compositional latency analysis also scales logarithmically when applied to multi-scale dataflow models. We apply our new throughput and latency analysis to several realistic applications. The results confirm that our approach provides a fast and accurate analysis.<\/jats:p>","DOI":"10.1145\/3233183","type":"journal-article","created":{"date-parts":[[2018,8,27]],"date-time":"2018-08-27T12:13:23Z","timestamp":1535372003000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Scalable Analysis for Multi-Scale Dataflow Models"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4662-4209","authenticated-orcid":false,"given":"Hadi Alizadeh","family":"Ara","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Behrouzian","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martijn","family":"Hendriks","sequence":"additional","affiliation":[{"name":"ESI, TNO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Geilen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dip","family":"Goswami","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Twan","family":"Basten","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology 8 ESI, TNO, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 2nd Embedded Computing and Architecture (IDEA) Workshop on Integrating Dataflow. ESR-2017-01","author":"Ara H. Alizadeh","year":"2016","unstructured":"H. Alizadeh Ara , A. Behrouzian , M. Geilen , 2016 . Analysis and visualization of execution traces of dataflow applications . In Proceedings of the 2nd Embedded Computing and Architecture (IDEA) Workshop on Integrating Dataflow. ESR-2017-01 , 19--20. H. Alizadeh Ara, A. Behrouzian, M. Geilen, et al. 2016. Analysis and visualization of execution traces of dataflow applications. In Proceedings of the 2nd Embedded Computing and Architecture (IDEA) Workshop on Integrating Dataflow. ESR-2017-01, 19--20."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SIES.2016.7509444"},{"key":"e_1_2_1_3_1","volume-title":"Geert Jan Olsder, and Jean-Pierre Quadrat","author":"Baccelli Fran\u00e7ois","year":"1992","unstructured":"Fran\u00e7ois Baccelli , Guy Cohen , Geert Jan Olsder, and Jean-Pierre Quadrat . 1992 . Synchronization and Linearity, Vol . 2. Wiley , New York. Fran\u00e7ois Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1992. Synchronization and Linearity, Vol. 2. Wiley, New York."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008052406396"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.485935"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen . 2009. Introduction to Algorithms . MIT press . Thomas H. Cormen. 2009. Introduction to Algorithms. MIT press."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2609248.2609249"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.478227"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880050.1880052"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2014.7094470"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-016-1193-7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878961.1878985"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2006.33"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1302494.1302804"},{"key":"e_1_2_1_16_1","volume-title":"Graphs and Algorithms","author":"Gondran Michel","unstructured":"Michel Gondran and Michel Minoux . 1984. Graphs and Algorithms . Wiley . Michel Gondran and Michel Minoux. 1984. Graphs and Algorithms. Wiley."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2000116"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1874620.1874652"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2008.49"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"O. Moreira and H. Corporaal. 2014. Scheduling Real-time Streaming Applications onto an Embedded Multiprocessor. Springer 67--75.   O. Moreira and H. Corporaal. 2014. Scheduling Real-time Streaming Applications onto an Embedded Multiprocessor. Springer 67--75.","DOI":"10.1007\/978-3-319-01246-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2015.04.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951721"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of 1993 International Conference on Application-Specific Array Processors. 285--296","author":"Ritz S.","unstructured":"S. Ritz , M. Pankert , V. Zivojinovic , and H. Meyr . 1993. Optimum vectorization of scalable synchronous dataflow graphs . In Proceedings of 1993 International Conference on Application-Specific Array Processors. 285--296 . S. Ritz, M. Pankert, V. Zivojinovic, and H. Meyr. 1993. Optimum vectorization of scalable synchronous dataflow graphs. In Proceedings of 1993 International Conference on Application-Specific Array Processors. 285--296."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593223"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1550904"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147138"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2006.23"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.58"},{"key":"e_1_2_1_32_1","volume-title":"2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 404--411","author":"Stuijk S.","unstructured":"S. Stuijk , M. Geilen , B. Theelen , and T. Basten . 2011. Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications . In 2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 404--411 . S. Stuijk, M. Geilen, B. Theelen, and T. Basten. 2011. Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications. In 2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. 404--411."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2006.1695924"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3233183","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3233183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:55Z","timestamp":1750212475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3233183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,31]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3233183"],"URL":"https:\/\/doi.org\/10.1145\/3233183","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,31]]},"assertion":[{"value":"2007-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}