nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Kahn Process Networks and a Reactive Extension

verfasst von : Marc Geilen, Twan Basten

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

KI-gestützte Suche

Aus

Abstract

Kahn and MacQueen have introduced a generic class of determinate asynchronous data-flow applications, called Kahn Process Networks (KPNs) with an elegant mathematical model and semantics in terms of Scott-continuous functions on data streams together with an implementation model of independent asynchronous sequential programs communicating through FIFO buffers with blocking read and non-blocking write operations. The two are related by the Kahn Principle which states that a realization according to the implementation model behaves as predicted by the mathematical function. Additional steps are required to arrive at an actual implementation of a KPN to take care of scheduling of independent processes on a single processor and to manage communication buffers. Because of the expressiveness of the KPN model, buffer sizes and schedules cannot be determined at design time in general and require dynamic run-time system support. Constraints are discussed that need to be placed on such system support so as to maintain the Kahn Principle. We then discuss a possible extension of the KPN model to include the possibility for sporadic, reactive behavior which is not possible in the standard model. The extended model is called Reactive Process Networks. We introduce its semantics, look at analyzability and at more constrained data-flow models combined with reactive behavior.

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 Integrated Modeling Using Finite State Machines and Dataflow Graphs

Nächstes Kapitel Decidable Signal Processing Dataflow Graphs

Allen G, Evans B, Schanbacher D (1998) Real-time sonar beamforming on a UNIX workstation using process networks and POSIX threads. In: Proc. of the 32nd Asilomar Conference on Signals, Systems and Computers, IEEE Computer Society, pp 1725–1729

Allen G, Zucknick P, Evans B (2007) A distributed deadlock detection and resolution algorithm for process networks. In: Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, vol 2, pp II–33–II–36, https://doi.org/10.1109/ICASSP.2007.366165

Basten T, Hoogerbrugge J (2001) Efficient execution of process networks. In: Chalmers A, Mirmehdi M, Muller H (eds) Proc. of Communicating Process Architectures 2001, Bristol, UK, September 2001, IOS Press, pp 1–14

Benveniste A, Guemic PL (1990) Hybrid dynamical systems theory and the signal language. IEEE Trans Automat Contr 35:535–546MathSciNetCrossRef

Benveniste A, Caillaud B, Carloni LP, Caspi P, Sangiovanni-Vincentelli AL (2008) Composing heterogeneous reactive systems. ACM Trans Embed Comput Syst 7(4):1–36CrossRef

Berry G, Gonthier G (1992) The Esterel synchronous programming language: Design, semantics, implementation. Sci Comput Program 19:87–152CrossRef

Bhattacharya B, Bhattacharyya S (2001) Parameterized dataflow modeling for DSP systems. IEEE Transactions on Signal Processing 49(10):2408–2421MathSciNetCrossRef

Bhattacharyya S, Murthy P, Lee E (1999) Synthesis of embedded software from synchronous dataflow specifications. J VLSI Signal Process Syst 21(2):151–166CrossRef

Bhattacharyya SS, Deprettere EF, Theelen BD (2013) Dynamic Dataflow Graphs, Springer New York, New York, NY, pp 905–944. https://doi.org/10.1007/978-1-4614-6859-2_28, URL http://dx.doi.org/10.1007/978-1-4614-6859-2_28 CrossRef

10.

Brock J, Ackerman W (1981) Scenarios: A model of non-determinate computation. In: Díaz J, Ramos I (eds) Formalization of Programming Concepts, International Colloquium, Peniscola, Spain, April 19–25, 1981, Proceedings, LNCS Vol. 107, Springer Verlag, Berlin, pp 252–259CrossRef

11.

Brookes S (1998) On the Kahn principle and fair networks. Tech. Rep. CMU-CS-98-156, School of Computer Science, Carnegie Mellon University

12.

Broy M, Dendorfer C (1992) Modelling operating system structures by timed stream processing functions. Journal of Functional Programming 2(1):1–21, URL http://citeseer.nj.nec.com/broy92modelling.html CrossRef

13.

Buck J (1993) Scheduling dynamic dataflow graphs with bounded memory using the token flow model. PhD thesis, University of California, EECS Dept., Berkeley, CA

14.

Carloni LP, Sangiovanni-Vincentelli AL (2006) A framework for modeling the distributed deployment of synchronous designs. Form Methods Syst Des 28:93–110CrossRef

15.

Castrillon J, Tretter A, Leupers R, Ascheid G (2012) Communication-aware mapping of kpn applications onto heterogeneous mpsocs. In: Proceedings of the 49th Annual Design Automation Conference, ACM, New York, NY, USA, DAC ’12, pp 1266–1271, https://doi.org/10.1145/2228360.2228597, URL http://doi.acm.org/10.1145/2228360.2228597

16.

Cheng S, Wawrzynek J (2016) Synthesis of statically analyzable accelerator networks from sequential programs. In: Proceedings of the 35th International Conference on Computer-Aided Design, ACM, New York, NY, USA, ICCAD ’16, pp 126:1–126:8, https://doi.org/10.1145/2966986.2967077, URL http://doi.acm.org/10.1145/2966986.2967077

17.

Davey BA, Priestley HA (1990) Introduction to Lattices and Order. Cambridge University Press, Cambridge, UKMATH

18.

Dulloo J, Marquet P (2004) Design of a real-time scheduler for Kahn Process Networks on multiprocessor systems. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA, pp 271–277

19.

Eker J, Janneck J, Lee EA, Liu J, Liu X, Ludvig J, Sachs S, Xiong Y (2003) Taming heterogeneity - the ptolemy approach. Proceedings of the IEEE 91(1):127–144, URL http://chess.eecs.berkeley.edu/pubs/488.html CrossRef

20.

Falk J, Haubelt C, Zebelein C, Teich J (2013) Integrated Modeling Using Finite State Machines and Dataflow Graphs, Springer New York, New York, NY, pp 975–1013. https://doi.org/10.1007/978-1-4614-6859-2_30, URL http://dx.doi.org/10.1007/978-1-4614-6859-2_30 CrossRef

21.

Faustini A (1982) An operational semantics for pure dataflow. In: Nielsen M, Schmidt EM (eds) Automata, Languages and Programming, 9th Colloquium, Aarhus, Denmark, July 12–16, 1982, Proceedings, LNCS Vol. 140, Springer Verlag, Berlin, pp 212–224

22.

Geilen M (2009) An hierarchical compositional operational semantics of Kahn Process Networks and its Kahn Principle. Tech. rep., Electronic Systems Group, Dept. of Electrical Engineering, Eindhoven University of Technology

23.

Geilen M (2011) Synchronous data flow scenarios. Transactions on Embedded Computing Systems 10(2):16:1–16:31MathSciNetCrossRef

24.

Geilen M, Basten T (2003) Requirements on the execution of Kahn process networks. In: Degano P (ed) Proc. Of the 12th European Symposium on Programming, ESOP 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7–11, 2003. LNCS Vol.2618, Springer Verlag, BerlinCrossRef

25.

Geilen M, Basten T (2004) Reactive process networks. In: EMSOFT ’04: Proceedings of the 4th ACM international conference on Embedded software, ACM, New York, NY, USA, pp 137–146, http://doi.acm.org/10.1145/1017753.1017778 CrossRef

26.

Geilen M, Stuijk S (2010) Worst-case performance analysis of synchronous dataflow scenarios. In: International Conference on Hardware-Software Codesign and System Synthesis, CODES+ISSS 10, Proc., Scottsdale, Az, USA, 24–29 October, 2010, pp 125–134

27.

Geilen M, Falk J, Haubelt C, Basten T, Theelen B, Stuijk S (2017) Performance analysis of weakly-consistent scenario-aware dataflow graphs. Journal of Signal Processing Systems 87(1):157–175, https://doi.org/10.1007/s11265-016-1193-7, URL http://dx.doi.org/10.1007/s11265-016-1193-7 CrossRef

28.

Girault A, Lee B, Lee E (1999) Hierarchical finite state machines with multiple concurrency models. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems 18(6):742–760CrossRef

29.

Goel M (1998) Process networks in Ptolemy II. Technical Memorandum UCB/ERL No. M98/69, University of California, EECS Dept., Berkeley, CA

30.

Ha S, Oh H (2013) Decidable Dataflow Models for Signal Processing: Synchronous Dataflow and Its Extensions, Springer New York, New York, NY, pp 1083–1109. https://doi.org/10.1007/978-1-4614-6859-2_33, URL http://dx.doi.org/10.1007/978-1-4614-6859-2_33 CrossRef

31.

Halbwachs N, Caspi P, Raymond P, Pilaud D (1991) The synchronous programming language LUSTRE. Proceedings of the IEEE 79:1305–1319CrossRef

32.

Jiang B, Deprettere E, Kienhuis B (2008) Hierarchical run time deadlock detection in process networks. In: Signal Processing Systems, 2008. SiPS 2008. IEEE Workshop on, pp 239–244, https://doi.org/10.1109/SIPS.2008.4671769

33.

Jonsson B (1989) A fully abstract trace model for dataflow networks. In: POPL ’89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM, New York, NY, USA, pp 155–165CrossRef

34.

Kahn G (1974) The semantics of a simple language for parallel programming. In: Rosenfeld J (ed) Information Processing 74: Proceedings of the IFIP Congress 74, Stockholm, Sweden, August 1974, North-Holland, Amsterdam, Netherlands, pp 471–475

35.

Kahn G, MacQueen D (1977) Coroutines and networks of parallel programming. In: Gilchrist B (ed) Information Processing 77: Proceedings of the IFIP Congress 77, Toronto, Canada, August 8–12, 1977, North-Holland, pp 993–998

36.

Kock, de et al E (2000) YAPI: Application modeling for signal processing systems. In: Proc. of the 37th. Design Automation Conference, Los Angeles, CA, June 2000, IEEE, pp 402–405

37.

Lee B (2000) Specification and design of reactive systems. PhD thesis, Electronics Research Laboratory, University of California, EECS Dept., Berkeley, CA, memorandum UCB/ERL M00/29

38.

Lee E (2001) Overview of the Ptolemy project. Technical Memorandum UCB/ERL No. M01/11, University of California, EECS Dept., Berkeley, CA

39.

Lee E, Messerschmitt D (1987) Synchronous data flow. IEEE Proceedings 75(9):1235–1245CrossRef

40.

Lee E, Sangiovanni-Vincentelli A (Dec 1998) A framework for comparing models of computation. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 17(12):1217–1229, https://doi.org/10.1109/43.736561 CrossRef

41.

Lee EA, Matsikoudis E (2007) The Semantics of Dataflow with Firing, Cambridge University Press. URL http://chess.eecs.berkeley.edu/pubs/428.html, chapter from “From Semantics to Computer Science: Essays in memory of Gilles Kahn”

42.

Li P, Agrawal K, Buhler J, Chamberlain RD (2010) Deadlock avoidance for streaming computations with filtering. In: Proceedings of the Twenty-second Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, NY, USA, SPAA ’10, pp 243–252, https://doi.org/10.1145/1810479.1810526, URL http://doi.acm.org/10.1145/1810479.1810526

43.

Liu X, Lee EA (2008) Cpo semantics of timed interactive actor networks. Theor Comput Sci 409(1):110–125, http://dx.doi.org/10.1016/j.tcs.2008.08.044 MathSciNetCrossRef

44.

Lynch N, Stark E (1989) A proof of the Kahn principle for Input/Output automata. Information and Computation 82(1):81–92, URL http://citeseer.nj.nec.com/lynch89proof.html MathSciNetCrossRef

45.

Martin A (1985) The probe: An addition to communication primitives. Information Processing Letters 20(3):125–130MathSciNetCrossRef

46.

Neuendorffer S, Lee EA (2004) Hierarchical reconfiguration of dataflow models. In: Proc. Second ACM-IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2004), IEEE Computer Society Press

47.

Olson A, Evans B (2005) Deadlock detection for distributed process networks. In: Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP ’05). IEEE International Conference on, vol 5, pp v/73–v/76 Vol. 5, https://doi.org/10.1109/ICASSP.2005.1416243

48.

Park D (1979) On the semantics of fair parallelism. In: Abstract Software Specifications, Volume 86 of Lecture Notes in Computer Science, Springer Verlag, Berlin

49.

Parks T (1995) Bounded Scheduling of Process Networks. PhD thesis, University of California, EECS Dept., Berkeley, CA

50.

Plotkin G (1981) A structural approach to operational semantics. Tech. Rep. DAIMI FN-19, Århus University, Computer Science Department, Århus, Denmark

51.

Poplavko P, Basten T, van Meerbergen J (2007) Execution-time prediction for dynamic streaming applications with task-level parallelism. In: DSD ’07: Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, IEEE Computer Society, Washington, DC, USA, pp 228–235, http://dx.doi.org/10.1109/DSD.2007.52

52.

Rai D, Schor L, Stoimenov N, Thiele L (2013) Distributed stable states for process networks - algorithm, analysis, and experiments on intel scc. In: 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC), pp 1–10

53.

Russell J (1989) Full abstraction for nondeterministic dataflow networks. Symposium on Foundations of Computer Science 0:170–175, http://doi.ieeecomputersociety.org/10.1109/SFCS.1989.63474

54.

Schor L, Bacivarov I, Yang H, Thiele L (2014) Adapnet: Adapting process networks in response to resource variations. In: Proceedings of the 2014 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, ACM, New York, NY, USA, CASES ’14, pp 22:1–22:10, https://doi.org/10.1145/2656106.2656112, URL http://doi.acm.org/10.1145/2656106.2656112

55.

Sriram S, Bhattacharyya SS (2000) Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., New York, NY, USA

56.

Stark E (1987) Concurrent transition system semantics of process networks. In: Proc. of the 1987 SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Munich, Germany, January 1987, ACM Press, pp 199–210

57.

Stevens R, Wan M, Laramie P, Parks T, Lee E (1997) Implementation of process networks in Java. Technical Memorandum UCB/ERL No. M97/84, University of California, EECS Dept., Berkeley, CA

58.

Strehl K, Thiele L, Gries M, Ziegenbein D, Ernst R, Teich J (2001) FunState - an internal design representation for codesign. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 9(4):524–544, URL http://citeseer.nj.nec.com/strehl01funstate.html CrossRef

59.

Theelen BD, Geilen M, Basten T, Voeten J, Gheorghita SV, Stuijk S (2006) A scenario-aware data flow model for combined long-run average and worst-case performance analysis. In: Proceedings of the Fourth ACM and IEEE International Conference on Formal Methods and Models for Co-Design 2006 (MEMOCODE ’06), pp 185–194

60.

Thies W, Karczmarek M, Amarasinghe S (2002) StreamIt: A language for streaming applications. In: Horspool RN (ed) Compiler Construction, 11th International Conference, CC 2002, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002, Grenoble, France, April 8–12, 2002, Proceedings, LNCS Vol. 2306, Springer Verlag, Berlin, pp 179–196

61.

Thies W, Karczmarek M, Sermulins J, Rabbah R, Amarasinghe S (2005) Teleport messaging for distributed stream programs. In: PPoPP ’05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, ACM, New York, NY, USA, pp 224–235, http://doi.acm.org/10.1145/1065944.1065975 CrossRef

62.

Thomas T Hildebrandt GW Prakash Panangaden (2004) A relational model of non-deterministic dataflow. Mathematical Structures in Computer Science pp 613–649

63.

Vayssière J, Webb D, Wendelborn A (1999) Distributed process networks. Tech. Rep. TR 99-03, University of Adelaide, Department of Computer Science, South Australia 5005, Australia

64.

Verdoolaege S (2013) Polyhedral Process Networks, Springer New York, New York, NY, pp 1335–1375. https://doi.org/10.1007/978-1-4614-6859-2_41 CrossRef

65.

Yates RK (1993) Networks of real-time processes. In: Best E (ed) CONCUR’93: Proc. of the 4th International Conference on Concurrency Theory, Springer Verlag, Berlin, Heidelberg, pp 384–397CrossRef

Titel: Kahn Process Networks and a Reactive Extension
verfasst von: Marc Geilen
Twan Basten
Verlag: Springer International Publishing
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_24

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Nachhaltigkeitsaward Key Visual/© Cometis AG/Global ESG Monitor | Daniel Rupp | Generiert mit KI, Search Icon, Banner Hanser, Beijing Auto Show 2024: Deutsche Hersteller wollen angreifen./© EKH-Pictures / Generated with AI / Stock.adobe.com, Buchstaben, die aus einem Megaphon kommen/© MicroStockHub/Getty Images/iStock, Digitale Lieferkette/© zapp2photo / stock.adobe.com, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Sustainibility Finance/© Robert Kneschke / stock.adobe.com / Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.