{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:40Z","timestamp":1750306360218,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T00:00:00Z","timestamp":1483488000000},"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. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>The synchronous dataflow model of computation is widely used to design embedded stream-processing applications under strict quality-of-service requirements (e.g., buffering size, throughput, input-output latency). The required analyses can either be performed at compile time (for design space exploration) or at runtime (for resource management and reconfigurable systems). However, these analyses have an exponential time complexity, which may cause a huge runtime overhead or make design space exploration unacceptably slow.<\/jats:p>\n          <jats:p>\n            In this article, we argue that\n            <jats:italic>symbolic<\/jats:italic>\n            analyses are more appropriate since they express the system performance as a function of parameters (i.e., input and output rates, execution times). Such functions can be quickly evaluated for each different configuration or checked with respect to different quality-of-service requirements. We provide symbolic analyses for computing the maximal throughput of acyclic synchronous dataflow graphs, the minimum required buffers for which as soon as possible (ASAP) scheduling achieves this throughput, and finally, the corresponding input-output latency of the graph. The article first investigates these problems for a single parametric edge. The results are extended to general acyclic graphs using linear approximation techniques. We assess the proposed analyses experimentally on both synthetic and real benchmarks.\n          <\/jats:p>","DOI":"10.1145\/3007898","type":"journal-article","created":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T17:02:36Z","timestamp":1483549356000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Symbolic Analyses of Dataflow Graphs"],"prefix":"10.1145","volume":"22","author":[{"given":"Adnan","family":"Bouakaz","sequence":"first","affiliation":[{"name":"Inria, France; Univ. Grenoble Alpes, Lab. LIG, Grenoble, France; CNRS, Lab. LIG, F-38000 Grenoble, France"}]},{"given":"Pascal","family":"Fradet","sequence":"additional","affiliation":[{"name":"Inria, France; Univ. Grenoble Alpes, Lab. LIG, Grenoble, France; CNRS, Lab. LIG, F-38000 Grenoble, France"}]},{"given":"Alain","family":"Girault","sequence":"additional","affiliation":[{"name":"Inria, France; Univ. Grenoble Alpes, Lab. LIG, Grenoble, France; CNRS, Lab. LIG, F-38000 Grenoble, France"}]}],"member":"320","published-online":{"date-parts":[[2017,1,4]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-1389-2"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2555754.2555757"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.950795"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ESTIMedia.2013.6704509"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2016.7461360"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2012.6378644"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06859-7_145"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2013.6621104"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2012.6176572"},{"key":"e_1_2_2_12_1","volume-title":"Synchronous dataflow scenarios. ACM TECS 10, 2","author":"Geilen Marc","year":"2011","unstructured":"Marc Geilen . 2011. Synchronous dataflow scenarios. ACM TECS 10, 2 ( 2011 ), 16:1--16:31. Marc Geilen. 2011. Synchronous dataflow scenarios. ACM TECS 10, 2 (2011), 16:1--16:31."},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of Design, Automation and Test in Europe. 116--121","author":"Ghamarian Amir H.","year":"2008","unstructured":"Amir H. Ghamarian , Marc Geilen , Twan Basten , and Sander Stuijk . 2008 . Parametric throughput analysis of synchronous data flow graphs . In Proceedings of Design, Automation and Test in Europe. 116--121 . Amir H. Ghamarian, Marc Geilen, Twan Basten, and Sander Stuijk. 2008. Parametric throughput analysis of synchronous data flow graphs. In Proceedings of Design, Automation and Test in Europe. 116--121."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2007.4341468"},{"key":"e_1_2_2_15_1","unstructured":"Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In Information Processing. 471--475.  Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In Information Processing. 471--475."},{"volume-title":"Multimedia Multiprocessor Systems: Analysis, Design and Management","author":"Kumar Akash","key":"e_1_2_2_16_1","unstructured":"Akash Kumar , Henk Corp oraal, Bart Mesman , and Yajun Ha. 2011. Multimedia Multiprocessor Systems: Analysis, Design and Management . Springer Science +Business Media B.V., New York, NY. Akash Kumar, Henk Corporaal, Bart Mesman, and Yajun Ha. 2011. Multimedia Multiprocessor Systems: Analysis, Design and Management. Springer Science+Business Media B.V., New York, NY."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.07.037"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.155"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.145.7"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMSOFT.2015.7318264"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147138"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2006.23"},{"key":"e_1_2_2_24_1","volume-title":"Bhattacharyya and Sundararajan Sriram","author":"Shuvra","year":"2000","unstructured":"Shuvra S. Bhattacharyya and Sundararajan Sriram . 2000 . Embedded Multiprocessors : Scheduling and Synchronization. Marcel Dekker , Inc., New York, NY. Shuvra S. Bhattacharyya and Sundararajan Sriram. 2000. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., New York, NY."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854319"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3007898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3007898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:11Z","timestamp":1750222571000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3007898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,4]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3007898"],"URL":"https:\/\/doi.org\/10.1145\/3007898","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2017,1,4]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}