Skip to main content

2017 | Supplement | Buchkapitel

Towards Component-Based (max,+) Algebraic Throughput Analysis of Hierarchical Synchronous Data Flow Models

verfasst von : Mladen Skelin, Marc Geilen

Erschienen in: Computer Safety, Reliability, and Security

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Synchronous (or static) dataflow (SDF) is deemed the most stable and mature model to represent streaming systems. It is useful, not only to reason about functional behavior and correctness of such systems, but also about non-functional aspects, in particular timing and performance constraints. When talking about performance, throughput is a key metric. Within the SDF domain, hierarchical SDF models are of special interest as they enable compositional modeling, which is a necessity in the design of large systems.
Techniques exist to analyze throughput of synchronous dataflow models. If the model is hierarchical, it first needs to be flattened before these techniques can be applied (for exact analysis at least). Furthermore, all of these techniques are adversely affected by the increase in the graph’s repetition vector entries. In this paper, for a loosely defined class of hierarchical synchronous dataflow models, we argue that these dependence issues can be mitigated by taking advantage of the hierarchical structure rather than by flattening the graph. We propose a hierarchical extension to an existing technique that is based on the (max,+) algebraic semantics of SDF.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Self-timed execution of an SDF graph consists of a periodic phase preceded by a so-called transient phase.
 
Literatur
2.
Zurück zum Zitat Bekooij, M., Moreira, O., Poplavko, P., Mesman, B., Pastrnak, M., van Meerbergen, J.: Predictable Embedded Multiprocessor System Design, pp. 77–91. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30113-4_7 Bekooij, M., Moreira, O., Poplavko, P., Mesman, B., Pastrnak, M., van Meerbergen, J.: Predictable Embedded Multiprocessor System Design, pp. 77–91. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-30113-4_​7
3.
Zurück zum Zitat Bhattacharya, B., Bhattacharyya, S.: Parameterized dataflow modeling for DSP systems. Signal Process. IEEE Trans. 49(10), 2408–2421 (2001)MathSciNetCrossRefMATH Bhattacharya, B., Bhattacharyya, S.: Parameterized dataflow modeling for DSP systems. Signal Process. IEEE Trans. 49(10), 2408–2421 (2001)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Bhattacharyya, S.S., Deprettere, E.F., Theelen, B.D.: Dynamic dataflow graphs. In: Bhattacharyya, S.S., Deprettere, E.F., Leupers, R., Takala, J. (eds.) Handbook of Signal Processing Systems, pp. 905–944. Springer, New York (2013). doi:10.1007/978-1-4614-6859-2_28 CrossRef Bhattacharyya, S.S., Deprettere, E.F., Theelen, B.D.: Dynamic dataflow graphs. In: Bhattacharyya, S.S., Deprettere, E.F., Leupers, R., Takala, J. (eds.) Handbook of Signal Processing Systems, pp. 905–944. Springer, New York (2013). doi:10.​1007/​978-1-4614-6859-2_​28 CrossRef
6.
Zurück zum Zitat Bilsen, G., Engels, M., Lauwereins, R., Peperstraete, J.: Cycle-static dataflow. Signal Process. IEEE Trans. 44(2), 397–408 (1996)CrossRef Bilsen, G., Engels, M., Lauwereins, R., Peperstraete, J.: Cycle-static dataflow. Signal Process. IEEE Trans. 44(2), 397–408 (1996)CrossRef
7.
Zurück zum Zitat Buck, J.T.: Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. thesis, EECS Department, University of California, Berkeley (1993) Buck, J.T.: Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. thesis, EECS Department, University of California, Berkeley (1993)
8.
Zurück zum Zitat Dasdan, A., Irani, S.S., Gupta, R.K.: Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In: Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, DAC 1999, pp. 37–42. ACM, New York, NY, USA (1999). http://doi.acm.org/10.1145/309847.309862 Dasdan, A., Irani, S.S., Gupta, R.K.: Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In: Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, DAC 1999, pp. 37–42. ACM, New York, NY, USA (1999). http://​doi.​acm.​org/​10.​1145/​309847.​309862
9.
Zurück zum Zitat Deroui, H., Desnos, K., Nezan, J.F., Munier-Kordon, A.: Throughput evaluation of DSP applications based on hierarchical dataflow models. In: International Symposium on Circuits and Systems (ISCAS) (2017) Deroui, H., Desnos, K., Nezan, J.F., Munier-Kordon, A.: Throughput evaluation of DSP applications based on hierarchical dataflow models. In: International Symposium on Circuits and Systems (ISCAS) (2017)
10.
Zurück zum Zitat Desnos, K., Pelcat, M., Nezan, J.F., Bhattacharyya, S.S., Aridhi, S.: PiMM: parameterized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration. In: 2013 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), pp. 41–48, July 2013 Desnos, K., Pelcat, M., Nezan, J.F., Bhattacharyya, S.S., Aridhi, S.: PiMM: parameterized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration. In: 2013 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), pp. 41–48, July 2013
11.
Zurück zum Zitat Eker, J., Janneck, J.W., Lee, E.A., Liu, J., Liu, X., Ludvig, J., Neuendorffer, S., Sachs, S., Xiong, Y.: Taming heterogeneity - the Ptolemy approach. Proc. IEEE 91(1), 127–144 (2003)CrossRef Eker, J., Janneck, J.W., Lee, E.A., Liu, J., Liu, X., Ludvig, J., Neuendorffer, S., Sachs, S., Xiong, Y.: Taming heterogeneity - the Ptolemy approach. Proc. IEEE 91(1), 127–144 (2003)CrossRef
14.
Zurück zum Zitat Geilen, M., Stuijk, S.: Worst-case performance analysis of synchronous dataflow scenarios. In: Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, CODES/ISSS 2010, pp. 125–134. ACM, New York, NY, USA (2010), http://doi.acm.org/10.1145/1878961.1878985 Geilen, M., Stuijk, S.: Worst-case performance analysis of synchronous dataflow scenarios. In: Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, CODES/ISSS 2010, pp. 125–134. ACM, New York, NY, USA (2010), http://​doi.​acm.​org/​10.​1145/​1878961.​1878985
16.
Zurück zum Zitat Ghamarian, A.H., Geilen, M.C.W., Stuijk, S., Basten, T., Theelen, B.D., Mousavi, M.R., Moonen, A.J.M., Bekooij, M.J.G.: Throughput analysis of synchronous data flow graphs. In: Proceedings of the Sixth International Conference on Application of Concurrency to System Design, ACSD 2006, pp. 25–36. IEEE Computer Society, Washington (2006). http://dx.doi.org/10.1109/ACSD.2006.33 Ghamarian, A.H., Geilen, M.C.W., Stuijk, S., Basten, T., Theelen, B.D., Mousavi, M.R., Moonen, A.J.M., Bekooij, M.J.G.: Throughput analysis of synchronous data flow graphs. In: Proceedings of the Sixth International Conference on Application of Concurrency to System Design, ACSD 2006, pp. 25–36. IEEE Computer Society, Washington (2006). http://​dx.​doi.​org/​10.​1109/​ACSD.​2006.​33
17.
Zurück zum Zitat de Groote, R., Kuper, J., Broersma, H., Smit, G.J.M.: Max-plus algebraic throughput analysis of synchronous dataflow graphs. In: 2012 38th Euromicro Conference on Software Engineering and Advanced Applications, pp. 29–38 (Sept 2012) de Groote, R., Kuper, J., Broersma, H., Smit, G.J.M.: Max-plus algebraic throughput analysis of synchronous dataflow graphs. In: 2012 38th Euromicro Conference on Software Engineering and Advanced Applications, pp. 29–38 (Sept 2012)
19.
Zurück zum Zitat Heidergott, B., Olsder, G.J., Van Der Woude, J.: Max Plus at work: modeling and analysis of synchronized systems: a course on Max-Plus algebra and its applications. Princeton University Press, Princeton (2014) Heidergott, B., Olsder, G.J., Van Der Woude, J.: Max Plus at work: modeling and analysis of synchronized systems: a course on Max-Plus algebra and its applications. Princeton University Press, Princeton (2014)
20.
Zurück zum Zitat Kavi, K.M., Buckles, B.P., Bhat, U.N.: A formal definition of data flow graph models. IEEE Trans. Comput. C–35(11), 940–948 (1986)CrossRefMATH Kavi, K.M., Buckles, B.P., Bhat, U.N.: A formal definition of data flow graph models. IEEE Trans. Comput. C–35(11), 940–948 (1986)CrossRefMATH
21.
Zurück zum Zitat Lee, E., Messerschmitt, D.: Synchronous data flow. Proc. IEEE 75(9), 1235–1245 (1987)CrossRef Lee, E., Messerschmitt, D.: Synchronous data flow. Proc. IEEE 75(9), 1235–1245 (1987)CrossRef
23.
Zurück zum Zitat Piat, J., Bhattacharyya, S.S., Raulet, M.: Interface-based hierarchy for synchronous data-flow graphs. In: 2009 IEEE Workshop on Signal Processing Systems. pp. 145–150, October 2009 Piat, J., Bhattacharyya, S.S., Raulet, M.: Interface-based hierarchy for synchronous data-flow graphs. In: 2009 IEEE Workshop on Signal Processing Systems. pp. 145–150, October 2009
24.
Zurück zum Zitat Ritz, S., Pankert, M., Zivojinovic, V., Meyr, H.: Optimum vectorization of scalable synchronous dataflow graphs. In: Proceedings of the International Conference on Application-Specific Array Processors, 1993, pp. 285–296, October 1993 Ritz, S., Pankert, M., Zivojinovic, V., Meyr, H.: Optimum vectorization of scalable synchronous dataflow graphs. In: Proceedings of the International Conference on Application-Specific Array Processors, 1993, pp. 285–296, October 1993
25.
Zurück zum Zitat Sriram, S., Bhattacharyya, S.S.: Embedded Multiprocessors: Scheduling and Synchronization, 2nd edn. CRC Press Inc., Boca Raton (2009)CrossRef Sriram, S., Bhattacharyya, S.S.: Embedded Multiprocessors: Scheduling and Synchronization, 2nd edn. CRC Press Inc., Boca Raton (2009)CrossRef
26.
Zurück zum Zitat Stuijk, S., Geilen, M., Theelen, B., Basten, T.: Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications. In: 2011 International Conference on Embedded Computer Systems (SAMOS), pp. 404–411, July 2011 Stuijk, S., Geilen, M., Theelen, B., Basten, T.: Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications. In: 2011 International Conference on Embedded Computer Systems (SAMOS), pp. 404–411, July 2011
27.
Zurück zum Zitat Stuijk, S., Geilen, M., Basten, T.: SDF\(^3\): SDF For Free. In: Proceedings of the 6th International Conference on Application of Concurrency to System Design, ACSD 2006, pp. 276–278. IEEE Computer Society Press, Los Alamitos, CA, USA. http://www.es.ele.tue.nl/sdf3 Stuijk, S., Geilen, M., Basten, T.: SDF\(^3\): SDF For Free. In: Proceedings of the 6th International Conference on Application of Concurrency to System Design, ACSD 2006, pp. 276–278. IEEE Computer Society Press, Los Alamitos, CA, USA. http://​www.​es.​ele.​tue.​nl/​sdf3
28.
Zurück zum Zitat Stuijk, S.: Predictable mapping of streaming applications on multiprocessors. Ph.D. thesis, Eindhoven University of Technology (2007) Stuijk, S.: Predictable mapping of streaming applications on multiprocessors. Ph.D. thesis, Eindhoven University of Technology (2007)
29.
Zurück zum Zitat Tripakis, S., Bui, D., Geilen, M., Rodiers, B., Lee, E.A.: Compositionality in synchronous data flow: Modular code generation from hierarchical SDF graphs. ACM Trans. Embed. Comput. Syst. 12(3), 1–26 (2013). doi:10.1145/2442116.2442133 CrossRef Tripakis, S., Bui, D., Geilen, M., Rodiers, B., Lee, E.A.: Compositionality in synchronous data flow: Modular code generation from hierarchical SDF graphs. ACM Trans. Embed. Comput. Syst. 12(3), 1–26 (2013). doi:10.​1145/​2442116.​2442133 CrossRef
Metadaten
Titel
Towards Component-Based (max,+) Algebraic Throughput Analysis of Hierarchical Synchronous Data Flow Models
verfasst von
Mladen Skelin
Marc Geilen
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-66284-8_39