{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:33:43Z","timestamp":1769729623211,"version":"3.49.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"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":[[2023,1,31]]},"abstract":"<jats:p>Dataflow Models of Computation (MoCs) are widely used in embedded systems, including multimedia processing, digital signal processing, telecommunications, and automatic control. In a dataflow MoC, an application is specified as a graph of actors connected by FIFO channels. One of the first and most popular dataflow MoCs, Synchronous Dataflow (SDF), provides static analyses to guarantee boundedness and liveness, which are key properties for embedded systems. However, SDF and most of its variants lack the capability to express the dynamism needed by modern streaming applications. In particular, the applications mentioned above have a strong need for reconfigurability to accommodate changes in the input data, the control objectives, or the environment.<\/jats:p><jats:p>We address this need by proposing a new MoC called Reconfigurable Dataflow (RDF). RDF extends SDF with transformation rules that specify how and when the topology and actors of the graph may be reconfigured. Starting from an initial RDF graph and a set of transformation rules, an arbitrary number of new RDF graphs can be generated at runtime. A key feature of RDF is that it can be statically analyzed to guarantee that all possible graphs generated at runtime will be consistent and live. We introduce the RDF MoC, describe its associated static analyses, and present its implementation and some experimental results.<\/jats:p>","DOI":"10.1145\/3544972","type":"journal-article","created":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T12:53:12Z","timestamp":1656334392000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["RDF: A Reconfigurable Dataflow Model of Computation"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4961-9923","authenticated-orcid":false,"given":"Pascal","family":"Fradet","sequence":"first","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, Montbonnot-Saint-Martin, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7500-1655","authenticated-orcid":false,"given":"Alain","family":"Girault","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, Montbonnot-Saint-Martin, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6625-3623","authenticated-orcid":false,"given":"Ruby","family":"Krishnaswamy","sequence":"additional","affiliation":[{"name":"Orange Labs, Ch\u00e2tillon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0469-3348","authenticated-orcid":false,"given":"Xavier","family":"Nicollin","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, Montbonnot-Saint-Martin, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0647-5221","authenticated-orcid":false,"given":"Arash","family":"Shafiei","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, Orange, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/547038"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597809.2597819"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/EMSOFT.2013.6658581"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/78.950795"},{"key":"e_1_3_3_6_2","first-page":"199","volume-title":"Real-Time and Embedded Technology and Applications Symposium (RTAS\u201916)","author":"Bouakaz A.","year":"2016","unstructured":"A. Bouakaz, P. Fradet, and A. Girault. 2016. Symbolic buffer sizing for throughput-optimal scheduling of dataflow graphs. In Real-Time and Embedded Technology and Applications Symposium (RTAS\u201916). 199\u2013208."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2999539"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3007898"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1109\/ICASSP.1993.319147","volume-title":"International Conference on Acoustics, Speech, and Signal Processing (ICASSP\u201993)","author":"Buck J. T.","year":"1993","unstructured":"J. T. Buck and E. A. Lee. 1993. Scheduling dynamic data-flow graphs with bounded memory using the token flow model. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP\u201993). IEEE, 429\u2013432."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2013.6621104"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2013.6621104"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE.2019.8714987"},{"key":"e_1_3_3_13_2","volume-title":"SPDF: A Schedulable Parametric Data-flow MoC (Extended Version)","author":"Fradet Pascal","year":"2011","unstructured":"Pascal Fradet, Alain Girault, and Peter Poplavko. 2011. SPDF: A Schedulable Parametric Data-flow MoC (Extended Version). Research Report RR-7828. INRIA. Retrieved from https:\/\/hal.inria.fr\/hal-00666284."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2012.6176572"},{"key":"e_1_3_3_15_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1880050.1880052"},{"key":"e_1_3_3_17_2","first-page":"275","article-title":"Software-defined radio \u2014 Basics and evolution to cognitive radio","volume":"3","author":"Jondral F.","year":"2005","unstructured":"F. Jondral. 2005. Software-defined radio \u2014 Basics and evolution to cognitive radio. EURASIP J. Wirel. Commun. Netw. 3 (2005), 275\u2013283.","journal-title":"EURASIP J. Wirel. Commun. Netw."},{"key":"e_1_3_3_18_2","first-page":"471","article-title":"The semantics of a simple language for parallel programming","volume":"74","author":"Kahn Gilles","year":"1974","unstructured":"Gilles Kahn. 1974. The semantics of a simple language for parallel programming. Inf. Process. 74 (1974), 471\u2013475.","journal-title":"Inf. Process."},{"key":"e_1_3_3_19_2","volume-title":"System Design, Modeling, and Simulation using Ptolemy II","author":"Lee E. A.","year":"2014","unstructured":"E. A. Lee, S. Neuendorffer, and G. Zhou. 2014. System Design, Modeling, and Simulation using Ptolemy II. Ptolemy.org."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126608004794"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.155"},{"key":"e_1_3_3_23_2","volume-title":"Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig","author":"Padberg Julia","year":"2018","unstructured":"Julia Padberg and La\u00efd Kahloul. 2018. Overview of reconfigurable Petri nets. In Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig, Reiko Heckel and Gabriele Taentzer (Eds.). Lecture Notes in Computer Science, 201\u2013222."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40530-8_4"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57787-4_20"},{"key":"e_1_3_3_26_2","volume-title":"RDF: A Reconfigurable Dataflow Model of Computation","author":"Shafiei Arash","year":"2021","unstructured":"Arash Shafiei. 2021. RDF: A Reconfigurable Dataflow Model of Computation. Ph. D. Dissertation. Universit\u00e9 Grenoble Alpes."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/2830865.2830876"},{"key":"e_1_3_3_28_2","first-page":"183","volume-title":"IEEE Real-time and Embedded Technology and Applications Symposium","author":"Wiggers Maarten H.","year":"2008","unstructured":"Maarten H. Wiggers, Marco J. G. Bekooij, and Gerard J. M. Smit. 2008. Buffer capacity computation for throughput constrained streaming applications with data-dependent inter-task communication. In IEEE Real-time and Embedded Technology and Applications Symposium. 183\u2013194."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544972","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3544972","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:01Z","timestamp":1750186801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544972"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,29]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3544972"],"URL":"https:\/\/doi.org\/10.1145\/3544972","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,29]]},"assertion":[{"value":"2022-01-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}