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

research-article

Parameterized Dataflow Scenarios

Authors:

Francky Catthoor,

Sverre HendsethAuthors Info & Claims

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 36, Issue 4

Pages 669 - 682

https://doi.org/10.1109/TCAD.2016.2597223

Published: 01 April 2017 Publication History

Abstract

A number of modeling approaches combining dataflow and finite-state machines (FSMs) have been proposed to capture applications that combine streaming data with finite control. FSM-based scenario-aware dataflow (FSM-SADF) is such an FSM/dataflow hybrid that occupies a sweet spot in the tradeoff between analyzability and expressiveness. However, the model suffers from compactness issues when the number of scenarios increases. This hampers its use in analysis of applications exposing high levels of data-dependent dynamics. In this paper, we address this problem by combining parameterized dataflow with finite control of FSM-SADF. We refer to the generalization as FSM-based parameterized SADF (FSM- \(\pi\)SADF). We introduce the formal semantics of the model, in terms of max-plus algebra and in particular max-plus automata. Thereafter, by leveraging the existing results of FSM-SADF, we propose a worst-case performance analysis framework for FSM- \(\pi\)SADF. We show that by using FSM- \(\pi\)SADF and its analysis framework, one can, unlike with FSM-SADF, compactly capture streaming applications exhibiting high levels of data-dependent dynamics in presence of finite control. Furthermore, we show that for practical models our analysis typically yields tighter bounds on worst-case performance indicators such as throughput and latency than the existing techniques based on conservative FSM-SADF modeling (if such modeling can be applied at all). We evaluate our approach on a realistic case-study from the multimedia domain.

References

[1]

A. Girault, B. Lee, and E. A. Lee, “Hierarchical finite state machines with multiple concurrency models,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. Volume 18, no. Issue 6, pp. 742–760, 1999.

Digital Library

[2]

E. A. Lee and D. G. Messerschmitt, “Synchronous data flow,” Proc. IEEE, vol. Volume 75, no. Issue 9, pp. 1235–1245, 1987.

[3]

S. Stuijk, M. Geilen, B. Theelen, and T. Basten, “Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications,” in Proc. SAMOS, Jul. 2011, pp. 404–411.

[4]

M. Geilen and S. Stuijk, “Worst-case performance analysis of synchronous dataflow scenarios,” in Proc. CODES/ISSS, Scottsdale, AZ, USA, 2010, pp. 125–134.

Digital Library

[5]

S. Neuendorffer and E. Lee, “Hierarchical reconfiguration of dataflow models,” in Proc. MEMOCODE, San Diego, CA, USA, Jun. 2004, pp. 179–188.

Digital Library

[6]

M. Skelin, M. Geilen, F. Catthoor, and S. Hendseth, “Parametrized dataflow scenarios,” in Proc. EMSOFT, Amsterdam, The Netherlands, 2015, pp. 95–104.

Digital Library

[7]

M. Skelin, M. Geilen, F. Catthoor, and S. Hendseth, “Parameterized dataflow scenarios,” <institution content-type=depatment>Dept. Elect. Eng. Electron. Syst</institution>., <institution content-type=institution>Eindhoven Univ. Technol</institution>., Tech. Rep. ESR-2015-01, 2015.

[8]

B. Bhattacharya and S. S. Bhattacharyya, “Parameterized dataflow modeling for DSP systems,” IEEE Trans. Signal Process., vol. Volume 49, no. Issue 10, pp. 2408–2421, 2001.

Digital Library

[9]

P. Fradet, A. Girault, and P. Poplavko, “SPDF: A schedulable parametric data-flow MoC,” in Proc. DATE, Dresden, Germany, 2012, pp. 769–774.

Digital Library

[10]

V. Bebelis, P. Fradet, A. Girault, and B. Lavigueur, “BPDF: A statically analyzable dataflow model with integer and Boolean parameters,” in Proc. EMSOFT, Montreal, QC, Canada, Sep. 2013, pp. 1–10.

Digital Library

[11]

M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit, “Buffer capacity computation for throughput constrained streaming applications with data-dependent inter-task communication,” in Proc. RTAS, St. Louis, MO, USA, Apr. 2008, pp. 183–194.

Digital Library

[12]

M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit, “Buffer capacity computation for throughput-constrained modal task graphs,” ACM Trans. Embedded Comput. Syst., vol. Volume 10, no. Issue 2, pp. 1–59, 2010.

Digital Library

[13]

G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete, “Cycle-static dataflow,” IEEE Trans. Signal Process., vol. Volume 44, no. Issue 2, pp. 397–408, 1996.

Digital Library

[14]

K. Desnos, M. Pelcat, J.-F. Nezan, S. Bhattacharyya, and S. Aridhi, “PiMM: Parameterized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration,” in Proc. SAMOS, Agios Konstantinos, Greece, Jul. 2013, pp. 41–48.

[15]

J. Piat, S. S. Bhattacharyya, and M. Raulet, “Interface-based hierarchy for synchronous data-flow graphs,” in Proc. SiPS, Tampere, Finland, Oct. 2009, pp. 145–150.

[16]

B. D. Theelen et al., “A scenario-aware data flow model for combined long-run average and worst-case performance analysis,” in Proc. MEMOCODE, Napa, CA, USA, 2006, pp. 185–194.

Digital Library

[17]

N. Cossement, R. Lauwereins, and F. Catthoor, “DF*: An extension of synchronous dataflow with data dependency and non-determinism,” in Proc. FDL, Tübingen, Germany, 2000.

[18]

L. Thiele, K. Strehl, D. Ziegengein, R. Ernst, and J. Teich, “Funstate—An internal design representation for codesign,” in Proc. ICCAD, San Jose, CA, USA, Nov. 1999, pp. 558–565.

Digital Library

[19]

M. Pankert, O. Mauss, S. Ritz, and H. Meyr, “Dynamic data flow and control flow in high level DSP code synthesis,” in Proc. ICASSP, vol. Volume 2 . Adelaide, SA, Australia, Apr. 1994, pp. II-pp.449II-–452.

[20]

J. Buck and R. Vaidyanathan, “Heterogeneous modeling and simulation of embedded systems in El Greco,” in Proc. CODES, San Diego, CA, USA, May 2000, pp. 142–146.

Digital Library

[21]

W. Plishker, N. Sane, and S. Bhattacharyya, “A generalized scheduling approach for dynamic dataflow applications,” in Proc. DATE, Nice, France, Apr. 2009, pp. 111–116.

Digital Library

[22]

W. Plishker, N. Sane, and S. Bhattacharyya, “Mode grouping for more effective generalized scheduling of dynamic dataflow applications,” in Proc. DAC, San Francisco, CA, USA, Jul. 2009, pp. 923–926.

Digital Library

[23]

K. Sudusinghe, I. Cho, M. van der Schaar, and S. S. Bhattacharyya, “Model based design environment for data-driven embedded signal processing systems,” Proc. Comput. Sci., vol. Volume 29, pp. 1193–1202, 2014.

[24]

K. Sudusinghe, Y. Jiao, H. B. Salem, M. van der Schaar, and S. S. Bhattacharyya, “Multiobjective design optimization in the lightweight dataflow for DDDAS environment (LiD4E),” Proc. Comput. Sci., vol. Volume 51, pp. 2563–2572, 2015.

Digital Library

[25]

S. S. Bhattacharyya, E. F. Deprettere, and B. D. Theelen, “<chapter-title>Dynamic dataflow graphs</chapter-title>,” in Handbook of Signal Processing Systems, S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, Eds. New York, NY, USA: Springer, 2013, pp. 905–944.

[26]

L.-H. Wang, C.-C. Shen, and S. S. Bhattacharyya, “Parameterized core functional dataflow graphs and their application to design and implementation of wireless communication systems,” in Proc. SiPS, Taipei, Taiwan, Oct. 2013, pp. 1–6.

[27]

S. Lin et al., “Parameterized sets of dataflow modes and their application to implementation of cognitive radio systems,” J. Signal Process. Syst., vol. Volume 80, no. Issue 1, pp. 3–18, 2015.

Digital Library

[28]

S. Gaubert, “Performance evaluation of (max,+) automata,” IEEE Trans. Autom. Control, vol. Volume 40, no. Issue 12, pp. 2014–2025, 1995.

[29]

F. Bacelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems . New Jersey, USA: Wiley, 1992.

[30]

B. Heidergott, G. J. Olsder, and J. W. van der Woude, Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications . Princeton, NJ, USA: Princeton Univ. Press, 2006.

[31]

C. Ptolemaeus, Ed., System Design, Modeling, and Simulation Using Ptolemy II . Berkeley, CA, USA: Ptolemy, 2014.

[32]

M. Geilen, “Synchronous dataflow scenarios,” ACM Trans. Embedded Comput. Syst., vol. Volume 10, no. Issue 2, pp. 1–31, 2010.

Digital Library

[33]

S. S. Battacharyya, E. A. Lee, and P. K. Murthy, Software Synthesis From Dataflow Graphs . Norwell, MA, USA: Kluwer Academic, 1996.

Digital Library

[34]

B. Bhattacharya and S. S. Bhattacharyya, “Quasi-static scheduling of reconfigurable dataflow graphs for DSP systems,” in Proc. IWRSP, Paris, France, 2000, pp. 84–89.

Digital Library

[35]

M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit, “Modelling run-time arbitration by latency-rate servers in dataflow graphs,” in Proc. SCOPES, Nice, France, 2007, pp. 11–22.

Digital Library

[36]

L. Granvilliers and F. Benhamou, “Algorithm 852—Realpaver: An interval solver using constraint satisfaction techniques,” ACM Trans. Math. Softw., vol. Volume 32, no. Issue 1, pp. 138–156, 2006.

Digital Library

[37]

F. Siyoum, M. Geilen, O. Moreira, and H. Corporaal, “Worst-case throughput analysis of real-time dynamic streaming applications,” in Proc. CODES+ISSS, Tampere, Finland, 2012, pp. 463–472.

Digital Library

[38]

H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, vol. Volume 31 . New York, NY, USA: Springer, 2013.

[39]

P. Poplavko, T. Basten, M. Bekooij, J. van Meerbergen, and B. Mesman, “Task-level timing models for guaranteed performance in multiprocessor networks-on-chip,” in Proc. CASES, San Jose, CA, USA, 2003, pp. 63–72.

Digital Library

[40]

D. Grois and O. Hadar, “Recent advances in region-of-interest coding,” Recent Advances on Video Coding. Vukovar, Croatia: Intech Open Access, 2011, pp. 49–76.

[41]

V. Bebelis, P. Fradet, and A. Girault, “A framework to schedule parametric dataflow applications on many-core platforms,” in Proc. LCTES, Edinburgh, U.K., 2014, pp. 125–134.

Digital Library

Cited By

Yuan BLu XTang KYao X(2021)Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow MappingACM Transactions on Embedded Computing Systems10.1145/344024620:3(1-25)Online publication date: 27-Mar-2021
https://dl.acm.org/doi/10.1145/3440246
Bonna RLoubach DUngureanu GSander I(2019)Modeling and Simulation of Dynamic Applications Using Scenario-Aware DataflowACM Transactions on Design Automation of Electronic Systems10.1145/334299724:5(1-29)Online publication date: 21-Aug-2019
https://dl.acm.org/doi/10.1145/3342997
Skelin MGeilen M(2018)Compositionality in scenario-aware dataflow: a rendezvous perspectiveACM SIGPLAN Notices10.1145/3299710.321133953:6(55-64)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3299710.3211339
Show More Cited By

Recommendations

Parameterized dataflow modeling for DSP systems

Dataflow has proven to be an attractive computation model for programming digital signal processing (DSP) applications. A restricted version of dataflow, termed synchronous dataflow (SDF), that offers strong compile-time predictability properties, but ...
Parametrized dataflow scenarios
EMSOFT '15: Proceedings of the 12th International Conference on Embedded Software

The FSM-based scenario-aware dataflow (FSM-SADF) model of computation has been introduced to facilitate the analysis of dynamic streaming applications. FSM-SADF interprets application's execution as an execution of a sequence of static modes of ...
Worst-case performance analysis of SDF-based parameterized dataflow

Dynamic dataflow models of computation (MoCs) have been introduced to provide designers with sufficient expressive power to capture increasing levels of dynamism in present-day streaming applications. Among dynamic dataflow MoCs, parameterized dataflow ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Volume 36, Issue 4

April 2017

183 pages

ISSN:0278-0070

Issue’s Table of Contents

Copyright © 2017.

Publisher

IEEE Press

Publication History

Published: 01 April 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yuan BLu XTang KYao X(2021)Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow MappingACM Transactions on Embedded Computing Systems10.1145/344024620:3(1-25)Online publication date: 27-Mar-2021
https://dl.acm.org/doi/10.1145/3440246
Bonna RLoubach DUngureanu GSander I(2019)Modeling and Simulation of Dynamic Applications Using Scenario-Aware DataflowACM Transactions on Design Automation of Electronic Systems10.1145/334299724:5(1-29)Online publication date: 21-Aug-2019
https://dl.acm.org/doi/10.1145/3342997
Skelin MGeilen M(2018)Compositionality in scenario-aware dataflow: a rendezvous perspectiveACM SIGPLAN Notices10.1145/3299710.321133953:6(55-64)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3299710.3211339
Skelin MGeilen MZhang ZDubach C(2018)Compositionality in scenario-aware dataflow: a rendezvous perspectiveProceedings of the 19th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3211332.3211339(55-64)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3211332.3211339

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents