Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-66644f4456-tnr8b Total loading time: 0 Render date: 2025-02-13T02:45:51.381Z Has data issue: true hasContentIssue false

4 - The semantics of dataflow with firing

Published online by Cambridge University Press:  06 August 2010

By
Edward A. Lee  and
Eleftherios Matsikoudis
Edited by
Yves Bertot ,
Gérard Huet ,
Jean-Jacques Lévy  and
Gordon Plotkin
Edward A. Lee
Affiliation:
University of California, Berkeley
Eleftherios Matsikoudis
Affiliation:
University of California, Berkeley
Yves Bertot
Affiliation:
INRIA-Sophia Antipolis, France
Gérard Huet
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Jean-Jacques Lévy
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Gordon Plotkin
Affiliation:
University of Edinburgh
Get access

Summary

Abstract

Dataflow models of computation have intrigued computer scientists since the 1970s. They were first introduced by Jack Dennis as a basis for parallel programming languages and architectures, and by Gilles Kahn as a model of concurrency. Interest in these models of computation has been recently rekindled by the resurrection of parallel computing, due to the emergence of multicore architectures. However, Dennis and Kahn approached dataflow very differently. Dennis' approach was based on an operational notion of atomic firings driven by certain firing rules. Kahn's approach was based on a denotational notion of processes as continuous functions on infinite streams. This paper bridges the gap between these two points of view, showing that sequences of firings define a continuous Kahn process as the least fixed point of an appropriately constructed functional. The Dennis firing rules are sets of finite prefixes satisfying certain conditions that ensure determinacy. These conditions result in firing rules that are strictly more general than the blocking reads of the Kahn–MacQueen implementation of Kahn process networks, and solve some compositionality problems in the dataflow model. This work was supported in part by the Center for Hybrid and Embedded Software Systems (CHESS) at UC Berkeley, which receives support from the National Science Foundation (NSF awards #0720882 (CSR-EHS: PRET), #0647591 (CSR-SGER), and #0720841 (CSR-CPS)), the US Army Research Office (ARO #W911NF-07-2-0019), the US Air Force Office of Scientific Research (MURI #FA9550-06-0312 and AF-TRUST #FA9550-06-1-0244), the Air Force Research Lab (AFRL), the State of California Micro Program, and the following companies: Agilent, Bosch, DGIST, National Instruments, and Toyota.

Type
Chapter
Information
From Semantics to Computer Science
Essays in Honour of Gilles Kahn
 , pp. 71 - 94
Publisher: Cambridge University Press
Print publication year: 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Arvind, , L., Bic and T., Ungerer. Evolution of data-flow computers. In J.-L., Gaudiot and L., Bic (eds), Advanced Topics in Data-Flow Computing. Prentice-Hall, 1991.Google Scholar
[2]A., Benveniste, P., Caspi, P. L., Guernic and N., Halbwachs. Dataflow synchronous languages. In J. W. d., Bakker, W.-P. d., Roever and G., Rozenberg, (eds), A Decade of Concurrency – Reflections and Perspectives, Volume 803 Lecture Notes in Computer Science, pp. 1–45. Springer-Verlag, 1994.Google Scholar
[3]G., Berry. Bottom-up computation of recursive programs. Revue Française d'Automatique, Informatique et Recherche Opérationnelle, 10(3):47–82, 1976.Google Scholar
[4]J. D., Brock and W. B., Ackerman. Scenarios, a model of non-determinate computation. In Conference on Formal Definition of Programming Concepts, volume 107, Lecture Notes in Computer Science, pp. 252–259. Springer-Verlag, 1981.Google Scholar
[5]M., Broy. Functional specification of time-sensitive communicating systems. ACM Transactions on Software Engineering and Methodology, 2(1):1–46, 1993.Google Scholar
[6]M., Broy and G., Stefanescu. The algebra of stream processing functions. Theoretical Computer Science, 258:99–129, 2001.Google Scholar
[7]P., Caspi. Clocks in dataflow languages. Theoretical Computer Science, 94(1), 1992.Google Scholar
[8]M., Creeger. Multicore CPUs for the masses. ACM Queue, 3(7):63–64, 2005.Google Scholar
[9]B. A., Davey and H. A., Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.Google Scholar
[10]J. B., Dennis. First Version Data Flow Procedure Language. Technical Report MAC TM61, MIT Laboratory for Computer Science, 1974.Google Scholar
[11]M., Geilen and T., Basten. Requirements on the execution of Kahn process networks. In European Symposium on Programming Languages and Systems, Lecture Notes in Computer Science, pp. 319–334, Springer, 2003.Google Scholar
[12]C.-J., Hsu, F., Keceli, M.-Y., Ko, S., Shahparnia and S. S., Bhattacharyya. DIF: An interchange format for dataflow-based design tools. In International Workshop on Systems, Architectures, Modeling, and Simulation, Samos, Greece, July 2004.Google Scholar
[13]A., Jantsch and I., Sander. Models of computation and languages for embedded system design. IEE Proceedings on Computers and Digital Techniques, 152(2):114–129, 2005.Google Scholar
[14]W. M., Johnston, J. R.P., Hanna and R. J., Millar. Advances in dataflow programming languages. ACM Computing Surveys, 36(1):1–34, 2004.Google Scholar
[15]G., Kahn. The semantics of a simple language for parallel programming. In Proc. of the IFIP Congress 74. North-Holland Publishing Co., 1974.Google Scholar
[16]G., Kahn and D. B., MacQueen. Coroutines and networks of parallel processes. In B., Gilchrist (ed.), Information Processing, pages 993–998. North-Holland Publishing Co., 1977.Google Scholar
[17]D., Lazaro Cuadrado, A.P., Ravn and P., Koch. Automated distributed simulation in Ptolemy II. In Parallel and Distributed Computing and Networks (PDCN). Acta Press, 2007.Google Scholar
[18]E. A., Lee and T. M., Parks. Dataflow process networks. Proceedings of the IEEE, 83(5):773–801, 1995.Google Scholar
[19]Y., Lin, R., Mullenix, M., Woh, S., Mahlke, T., Mudge, A., Reid and K., Flautner. SPEX: A programming language for software defined radio. In Software Defined Radio Technical Conference and Product Exposition, Orlando, 2006.Google Scholar
[20]S. G., Matthews. An extensional treatment of lazy data flow deadlock. Theoretical Computer Science, 151(1):195–205, 1995.Google Scholar
[21]A. G., Olson and B. L., Evans. Deadlock detection for distributed process networks. In ICASSP, 2005.Google Scholar
[22]O. M. G., (OMG). A UML profile for MARTE, beta 1. OMG Adopted Specification ptc/07–08–04, August 2007.
[23]T. M., Parks. Bounded Scheduling of Process Networks. PhD, UC Berkeley, 1995.
[24]T. M., Parks and D., Roberts. Distributed process networks in Java. In International Parallel and Distributed Processing Symposium, Nice, France, April 2003.Google Scholar
[25]D., Scott. Outline of a mathematical theory of computation. In 4th Annual Princeton Conference on Information Sciences and Systems, pp. 169–176, 1970.Google Scholar
[26]V., Srini. An architectural comparison of dataflow systems. Computer, 19(3), 1986.Google Scholar
[27]E. W., Stark. An algebra of dataflow networks. Fundamenta Informaticae, 22(1–2):167–185, 1995.Google Scholar
[28]R., Stephens. A survey of stream processing. Acta Informatica, 34(7), 1997.Google Scholar
[29]C. L., Talcott. Interaction semantics for components of distributed systems. In Formal Methods for Open Object-Based Distributed Systems (FMOODS), 1996.Google Scholar
[30]W., Thies, M., Karczmarek and S., Amarasinghe. StreamIt: A language for streaming applications. In 11th International Conference on Compiler Construction, volume 2304, Lecture Notes in Computer Science, Grenoble, France, 2002, Springer-Verlag.Google Scholar
[31]W., Thies, M., Karczmarek, J., Sermulins, R., Rabbah and S., Amarasinghe. Teleport messaging for distributed stream programs. In PPoPP, Chicago, Illinois, USA, 2005. ACM.Google Scholar
[32]A., Turjan, B., Kienhuis and E., Deprettere. Solving out-of-order communication in Kahn process networks. Journal on VLSI Signal Processing-Systems for Signal, Image, and Video Technology, 2003.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×