Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Signal Processing Methods for Light Field Displays Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Decidable Signal Processing Dataflow Graphs

verfasst von : Soonhoi Ha, Hyunok Oh

Erschienen in: Handbook of Signal Processing Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Digital signal processing algorithms can be naturally represented by a dataflow graph where nodes represent function blocks and arcs represent the data dependency between nodes. Among various dataflow models, decidable dataflow models have restricted semantics so that we can determine the execution order of nodes at compile-time and decide if the program has the possibility of buffer overflow or deadlock. In this chapter, we explain the synchronous dataflow (SDF) model as the pioneering and representative decidable dataflow model and its decidability focusing on how the static scheduling decision can be made. Through static scheduling, we can estimate the performance and resource requirement of an SDF graph on a multiprocessor system. In addition the cyclo-static dataflow model and a few other extended models are briefly introduced to show how they overcome the limitations of the SDF model.

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Kahn Process Networks and a Reactive Extension
Nächstes Kapitel Systolic Arrays
Literatur
1.
Ade, M., Lauwereins, R., Peperstraete, J.A.: Implementing dsp applications on heterogeneous targets using minimal size data buffers. In: Proceedings of RSP’96, pp. 166–172 (1996)
2.
Bamakhrama, M., Stefanov, T.: Hard-real-time scheduling of data-dependent tasks in embedded streaming applications. In: Proceedings of the Ninth ACM International Conference on Embedded Software, EMSOFT ’11, pp. 195–204. ACM, New York, NY, USA (2011). http://​doi.​acm.​org/​10.​1145/​2038642.​2038672
3.
Bhattacharyya, S.S., Murthy, P.K., Lee, E.A.: Software Synthesis from Dataflow Graphs. Kluwer Academic Publisher, Norwell MA (1996)CrossRef
4.
Bhattachayya, S.S., Murthy, P.K., Lee, E.A.: Apgan and rpmc: Complementary heuristics for translating dsp block diagrams into efficient software implementations. In: Journal of Design Automation for Embedded Systems, vol. 2, pp. 33–60 (1997)
5.
Bilsen, G., Engles, M., Lauwereins, R., Peperstraete, J.A.: Cyclo-static dataflow. In: IEEE Trans. Signal Processing, vol. 44, pp. 397–408 (1996)
6.
Bodin, B., Kordon, A.M., de Dinechin, B.D.: Periodic schedules for cyclo-static dataflow. In: The 11th IEEE Symposium on Embedded Systems for Real-time Multimedia, Montreal, QC, Canada, October 3–4, 2013, pp. 105–114 (2013). http://​dx.​doi.​org/​10.​1109/​ESTIMedia.​2013.​6704509
7.
Buck, J.T., Ha, S., Lee, E.A., Messerschimitt, D.G.: Ptolemy: A framework for simulating and prototyping heterogeneous systems. In: Int. Journal of Computer Simulation, special issue on Simulation Software Development, vol. 4, pp. 155–182 (1994)
8.
Dennis, J.B.: Dataflow supercomputers. In: IEEE Computer Magazine, vol. 13 (1980)
9.
Govindarajan, R., Gao, G., Desai, P.: Minimizing memory requirements in rate-optimal schedules. In: Proceedings of the International Conference on Application Specific Array Processors, pp. 75–86 (1993)
10.
Graham, R.L.: Bounds on multiprocessing timing anomalies. In: SIAM Journal on Applied Mathematics, vol. 17, pp. 416–429 (1969)MathSciNetMATH
11.
de Groote, R.: Throughput analysis of dataflow graphs. In: S.S. Bhattacharyya, E.F. Deprettere, R. Leupers, J. Takala (eds.) Handbook of Signal Processing Systems, third edn. Springer (2018)
12.
Hoang, P.D., Rabaey, J.M.: Scheduling of dsp programs onto multiprocessors for maximum throughput. In: IEEE Transactions on Signal Processing, pp. 2225–2235 (1993)CrossRef
13.
Jung, H., Yang, H., Ha, S.: Optimized rtl code generation from coarse-grain dataflow specification for fast hw/sw cosynthesis. In: Journal of Signal Processing Systems, vol. 52, pp. 13–34 (2008)
14.
15.
Kermia, O., Sorel, Y.: A rapid heuristic for scheduling non-preemptive dependent periodic tasks onto multiprocessor. In: Proceedings of the ISCA 20th International Conference on Parallel and Distributed Computing Systems, September 24–26, 2007, Las Vegas, Nevada, USA, pp. 1–6 (2007)
16.
Kim, J., Shin, T., Ha, S., Oh, H.: Resource minimized static mapping and dynamic scheduling of sdf graphs. In: ESTIMedia (2011)
17.
Lauwereins, R., Engels, M., Peperstraete, J.A., Steegmans, E., Ginderdeuren, J.V.: Grape: A case tool for digital signal parallel processing. In: IEEE ASSP Magazine, vol. 7, pp. 32–43 (1990)
18.
Lee, E.A., Ha, S.: Scheduling strategies for multiprocessor real-time DSP. In: GLOBECOM ’89: IEEE Global Telecommunications Conference and Exhibition. Communications Technology for the 1990s and Beyond, vol. 2, pp. 1279–1283. IEEE, Los Alamitos, CA, USA (1989). http://​dx.​doi.​org/​10.​1109/​GLOCOM.​1989.​64160
19.
Lee, E.A., Messerschmitt, D.G.: Static scheduling of synchronous dataflow programs for digital signal processing. In: IEEE Transaction on Computer, vol. C-36, pp. 24–35 (1987)
20.
Oh, H., Ha, S.: Memory-optimized software synthesis from dataflow program graphs with large size data samples. In: EURASIP Journal on Applied Signal Processing, vol. 2003, pp. 514–529 (2003)MATH
21.
Oh, H., Ha, S.: Fractional rate dataflow model for memory efficient synthesis. In: Journal of VLSI Signal Processing, vol. 37, pp. 41–51 (2004)
22.
Parhi, K.K., Chen, Y.: Signal flow graphs and data flow graphs. In: S.S. Bhattacharyya, E.F. Deprettere, R. Leupers, J. Takala (eds.) Handbook of Signal Processing Systems, second edn. Springer (2012)
23.
Park, C., Chung, J., Ha, S.: Extended synchronous dataflow for efficient dsp system prototyping. In: Design Automation for Embedded Systems, vol. 3, pp. 295–322. Kluwer Academic Publishers (2002)
24.
Pino, J., Ha, S., Lee, E.A., Buck, J.T.: Software synthesis for dsp using ptolemy. In: Journal of VLSI Signal Processing, vol. 9, pp. 7–21 (1995)
25.
Ritz, S., Pankert, M., Meyr, H.: High level software synthesis for signal processing systems. In: Proceedings of the International Conference on Application Specific Array Processors (1992)
26.
Ritz, S., Willems, M., Meyr, H.: Scheduling for optimum data memory compaction in block diagram oriented software synthesis. In: Proceedings of the ICASSP 95 (1995)
27.
Spasic, J., Liu, D., Cannella, E., Stefanov, T.: Improved hard real-time scheduling of csdf-modeled streaming applications. In: Proceedings of the 10th International Conference on Hardware/Software Codesign and System Synthesis, CODES ’15, pp. 65–74. IEEE Press, Piscataway, NJ, USA (2015). http://​dl.​acm.​org/​citation.​cfm?​id=​2830840.​2830848
28.
Stuijk, S., Basten, T., Geilen, M.C.W., Coporaal, H.: Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs. In: DAC, pp. 777–782 (2007)
29.
Stuijk, S., Geilen, M.C.W., Basten, T.: Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. In: DAC, pp. 899–904 (2006)
30.
Sung, W., Ha, S.: Memory efficient software synthesis using mixed coding style from dataflow graph. In: IEEE Transaction on VLSI Systems, vol. 8, pp. 522–526 (2000)
31.
Woods, R.: Mapping decidable signal processing graphs into FPGA implementations. In: S.S. Bhattacharyya, E.F. Deprettere, R. Leupers, J. Takala (eds.) Handbook of Signal Processing Systems, second edn. Springer (2012)
32.
Yang, H., Ha, S.: Pipelined data parallel task mapping/scheduling technique for mpsoc. In: DATE (Design Automation and Test in Europe) (2009)
Metadaten
Titel
Decidable Signal Processing Dataflow Graphs
verfasst von
Soonhoi Ha
Hyunok Oh
Copyright-Jahr
2019
Buch
Handbook of Signal Processing Systems

Print ISBN: 978-3-319-91733-7

Electronic ISBN: 978-3-319-91734-4

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-319-91734-4_25

Neuer Inhalt

    Bildnachweise