More Web Proxy on the site http://driver.im/

research-article

A Survey of Parametric Dataflow Models of Computation

Authors:

Alain GiraultAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 22, Issue 2

Article No.: 38, Pages 1 - 25

https://doi.org/10.1145/2999539

Published: 20 January 2017 Publication History

Abstract

Dataflow models of computation (MoCs) are widely used to design embedded signal processing and streaming systems. Dozens of dataflow MoCs have been proposed in the past few decades. More recently, several parametric dataflow MoCs have been presented as an interesting tradeoff between analyzability and expressiveness. They offer a controlled form of dynamism under the form of parameters (e.g., parametric rates), along with runtime parameter configuration. This survey provides a comprehensive description of the existing parametric dataflow MoCs (constructs, constraints, properties, static analyses) and compares them using a common example. The main objectives are to help designers of streaming applications choose the most suitable model for their needs and pave the way for the design of new parametric MoCs.

References

[1]

Shuvra S. Battacharyya, Edward A. Lee, and Praveen K. Murthy. 1996. Software Synthesis from Dataflow Graphs. Kluwer Academic Publishers, Norwell, MA.

Digital Library

[2]

Vagelis Bebelis, Pascal Fradet, and Alain Girault. 2014. A Framework to Schedule Parametric Dataflow Applications on Many-core Platforms. SIGPLAN Notes 49, 5 (2014), 125--134.

Digital Library

[3]

Vagelis Bebelis, Pascal Fradet, Alain Girault, and Bruno Lavigueur. 2013. BPDF: A statically analyzable DataFlow model with integer and boolean parameters. In Proceedings of the 11th ACM International Conference on Embedded Software. 3:1--3:10.

Digital Library

[4]

Evangelos Bempelis. 2015. Boolean Parametric Data Flow: Modeling - Analysis - Implementation. Ph.D. Dissertation. Université Grenoble Alpes.

[5]

Bishnupriya Bhattacharya and Shuvra S. Bhattacharyya. 2001. Parameterized dataflow modeling for DSP systems. Transactions on Signal Processing 49, 10 (2001), 2408--2421.

Digital Library

[6]

Shuvra S. Bhattacharyya, Ed F. Deprettere, and Bart D. Theelen. 2012. Dynamic dataflow graphs. In Handbook of Signal Processing Systems (2nd ed.). Springer.

[7]

G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete. 1996. Cyclo-static dataflow. IEEE Transactions on Signal Processsing 44, 2 (February 1996), 397--408.

Digital Library

[8]

Adnan Bouakaz, Pascal Fradet, and Alain Girault. 2016. Symbolic buffer sizing for throughput-optimal scheduling of dataflow graphs. In Proceedings of the 2016 IEEE 22nd Real-Time and Embedded Technology and Applications Symposium. IEEE, 199--208.

[9]

Joseph T. Buck. 1993. Scheduling Dynamic Dataflow Graphs with Bounded Memory Using the Token Flow Model. Ph.D. Dissertation. EECS Department, University of California, Berkeley.

Digital Library

[10]

Karol Desnos, Maxime Pelcat, Jean-François Nezan, Shuvra S. Bhattacharyya, and Slaheddine Aridhi. 2013. PiMM: Parameterized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration. In Proceedings of the 13th Internation Conference on Embedded Computer Systems: Architecture, Modeling and Simulation. 41--48.

[11]

Johan Eker and Jörn W. Janneck. 2003. CAL Language Report. Technical Report UCB/ERL M03/48. EECS Department, University of California, Berkeley. http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/4186.html.

[12]

Johan Eker, Jörn W. Janneck, Edward A. Lee, Jie Liu, Xiaojun Liu, Jozsef Ludvig, Stephen Neuendorffer, Sonia R. Sachs, and Yuhong Xiong. 2003. Taming heterogeneity - the Ptolemy approach. Proceedings of the IEEE 91, 1 (2003), 127--144.

[13]

Pascal Fradet, Alain Girault, and Peter Poplavko. 2012. SPDF: A schedulable parametric data-flow MoC. In Proceedings of the Conference on Design, Automation and Test in Europe. 769--774.

Digital Library

[14]

Marc Geilen. 2011. Synchronous dataflow scenarios. ACM Transactions on Embedded Computer Systems 10, 2 (2011), 16:1--16:31.

Digital Library

[15]

Marc Geilen and Sander Stuijk. 2010. Worst-case performance analysis of synchronous dataflow scenarios. In Proceedings of the IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. 125--134.

Digital Library

[16]

Soonhoi Ha and Hyunok Oh. 2012. Decidable dataflow models for signal processing: Synchronous dataflow and its extensions. In Handbook of Signal Processing Systems (2nd ed.). Springer.

[17]

Chia-Jui Hsu, Ming-Yung Ko, and Shuvra S. Bhattacharyya. 2005. Software synthesis from the dataflow interchange format. In Proceedings of the Workshop on Software and Compilers for Embedded Systems. 37--49.

Digital Library

[18]

Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In Proceedins of the IFIP Congress. 471--475.

[19]

Hojin Kee, Chung-Ching Shen, Shuvra S. Bhattacharyya, Ian C. Wong, Yong Rao, and Jacob Kornerup. 2012. Mapping parameterized cyclo-static dataflow graphs onto configurable hardware. Journal of Signal Processing Systems 66, 3 (2012), 285--301.

Digital Library

[20]

Edward A. Lee. 2001. Computing for embedded systems. In Proceedings of the IEEE Instrumentation and Measurement Technology Conference. 1830--1837.

[21]

Edward A. Lee and David G. Messerschmitt. 1987. Synchronous data flow. In Proceedings of the IEEE. 1235--1245.

[22]

Edward A. Lee and Thomas M. Parks. 2002. Dataflow process networks. In Readings in Hardware/Software Co-design. Kluwer Academic Publishers, Norwell, MA, 59--85.

Digital Library

[23]

Shuoxin Lin, Lai-Huei Wang, Aida Vosoughi, Joseph R. Cavallaro, Markku J. Juntti, Jani Boutellier, Olli Silvén, Mikko Valkama, and Shuvra S. Bhattacharyya. 2015. Parameterized sets of dataflow modes and their application to implementation of cognitive radio systems. Journal of Signal Processing Systems 80, 1 (2015), 3--18.

Digital Library

[24]

Jonathan Piat, Shuvra S. Bhattacharyya, and Mickaël Raulet. 2009. Interface-based hierarchy for synchronous data-flow graphs. In Proceedings of the IEEE Workshop on Signal Processing Systems. 145--150.

[25]

William Plishker, Nimish Sane, Mary Kiemb, Kapil Anand, and Shuvra S. Bhattacharyya. 2008. Functional DIF for rapid prototyping. In Proceedings of the Interational Symposium on Rapid System Prototyping. 17--23.

Digital Library

[26]

Mladen Skelin, Marc Geilen, Francky Catthoor, and Sverre Hendseth. 2014. Worst-case throughput analysis for parametric rate and parametric actor execution time scenario-aware dataflow graphs. In Proceedings of the International Workshop on Synthesis of Continuous Parameters. 65--79.

[27]

Mladen Skelin, Marc Geilen, Francky Catthoor, and Sverre Hendseth. 2015. Parametrized dataflow scenarios. In Proceedings of the International Conference on Embedded Software, Emsoft’15. 95--104.

Digital Library

[28]

Sundarara Sriram and Shuvra S. Bhattacharyya. 2000. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., New York, NY.

Digital Library

[29]

Sander Stuijk. 2007. Predictable Mapping of Streaming Applications on Multiprocessors. Ph.D. Dissertation. Eindhoven University of Technology.

[30]

William Thies, Michal Karczmarek, and Saman P. Amarasinghe. 2002. StreamIt: A language for streaming applications. In Proceedings of the 11th International Conference on Compiler Construction. 179--196.

Digital Library

[31]

Stavros Tripakis, Dai Bui, Marc Geilen, Bert Rodiers, and Edward A. Lee. 2013. Compositionality in synchronous data flow: Modular code generation from hierarchical SDF graphs. ACM Transactions on Embedded Computer Systems 12, 3, Article 83 (April 2013).

Digital Library

[32]

Lai-Huei Wang, Chung-Ching Shen, and Shuvra S. Bhattacharyya. 2013. Parameterized core functional dataflow graphs and their application to design and implementation of wireless communication systems. In Proceedings of the IEEE Workshop on Signal Processing Systems. 1--6.

[33]

Maarten Wiggers, Marco Bekooij, and Gerard Smit. 2011. Buffer capacity computation for throughput-constrained modal task graphs. ACM Transactions on Embedded Computer Systems 10, 2 (2011), 17:1--17:59.

Digital Library

[34]

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 Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium. 183--194.

Digital Library

Cited By

Mohammadat T(2023)A Model of Design for Computing Systems: A Categorical ApproachIEEE Access10.1109/ACCESS.2023.332534911(116304-116347)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3325349
Fradet PGirault AKrishnaswamy RNicollin XShafiei A(2022)RDF: A Reconfigurable Dataflow Model of ComputationACM Transactions on Embedded Computing Systems10.1145/354497222:1(1-30)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1145/3544972
Honorat ABourgoin TMiomandre HDesnos KMenard DNezan J(2022)Influence of Dataflow Graph Moldable Parameters on Optimization CriteriaDesign and Architecture for Signal and Image Processing10.1007/978-3-031-12748-9_7(83-95)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-12748-9_7
Show More Cited By

Index Terms

A Survey of Parametric Dataflow Models of Computation
1. Theory of computation
  1. Models of computation

Recommendations

A Survey of Parametric Static Analysis

Understanding program behaviors is important to verify program properties or to optimize programs. Static analysis is a widely used technique to approximate program behaviors via abstract interpretation. To evaluate the quality of static analysis, ...
Instrumentation-Driven Validation of Dataflow Applications

Dataflow modeling offers a myriad of tools for designing and optimizing signal processing systems. A designer is able to take advantage of dataflow properties to effectively tune the system in connection with functionality and different performance ...
Incremental Analysis of Cyclo-Static Synchronous Dataflow Graphs

In this article, we present a mathematical characterisation of admissible schedules of cyclo-static dataflow (csdf) graphs. We demonstrate how algebra ic manipulation of this characterization is related to unfolding csdf actors and how this manipulation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 22, Issue 2

Special Section of IDEA: Integrating Dataflow, Embedded Computing, and Architecture

April 2017

458 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3029795

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 20 January 2017

Accepted: 01 September 2016

Revised: 01 July 2016

Received: 01 January 2016

Published in TODAES Volume 22, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
310
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mohammadat T(2023)A Model of Design for Computing Systems: A Categorical ApproachIEEE Access10.1109/ACCESS.2023.332534911(116304-116347)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3325349
Fradet PGirault AKrishnaswamy RNicollin XShafiei A(2022)RDF: A Reconfigurable Dataflow Model of ComputationACM Transactions on Embedded Computing Systems10.1145/354497222:1(1-30)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1145/3544972
Honorat ABourgoin TMiomandre HDesnos KMenard DNezan J(2022)Influence of Dataflow Graph Moldable Parameters on Optimization CriteriaDesign and Architecture for Signal and Image Processing10.1007/978-3-031-12748-9_7(83-95)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-12748-9_7
Yasudo RCoutinho JVarbanescu ALuk WAmano HBecker TGuo C(2021)Analytical Performance Estimation for Large-Scale Reconfigurable Dataflow PlatformsACM Transactions on Reconfigurable Technology and Systems10.1145/345274214:3(1-21)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1145/3452742
Zmejev DLevchenko N(2021)Recovery of Parallel Dataflow Computing System From Faults and Failures2021 IEEE East-West Design & Test Symposium (EWDTS)10.1109/EWDTS52692.2021.9581026(1-6)Online publication date: 10-Sep-2021
https://doi.org/10.1109/EWDTS52692.2021.9581026
de Gennaro ASokolov DMokhov A(2020)Design and Implementation of Reconfigurable Asynchronous PipelinesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2020.2975591(1-13)Online publication date: 2020
https://doi.org/10.1109/TVLSI.2020.2975591
Fradet PGirault AKrishnaswamy RNicollin XShafiei A(2019)RDF: Reconfigurable Dataflow2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2019.8714987(1709-1714)Online publication date: Mar-2019
https://doi.org/10.23919/DATE.2019.8714987

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents