Citation
Edward A. Lee, Eleftherios Matsikoudis. "The Semantics of Dataflow with Firing". Gérard Huet Gordon Plotkin Jean-Jacques Lévy Yves Bertot (ed.), preprint (March 7 2, Cambridge University Press, 2007; Chapter from "From Semantics to Computer Science: Essays in memory of Gilles Kahn".

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.

Electronic downloads

• DataflowWithFiring.pdf · application/pdf · 447 kbytes. (Replaced pdf with version that has citation and copyright info.)

• HTML

  Edward A. Lee, Eleftherios Matsikoudis. <a
  href="http://chess.eecs.berkeley.edu/pubs/428.html"
  ><i>The Semantics of Dataflow with
  Firing</i></a>, Gérard Huet Gordon
  Plotkin Jean-Jacques Lévy Yves Bertot (ed.),
  preprint (March 7 2, Cambridge University Press, 2007;
  Chapter from "From Semantics to Computer Science:
  Essays in memory of Gilles Kahn".

• Plain text

  Edward A. Lee, Eleftherios Matsikoudis. "The Semantics
  of Dataflow with Firing". Gérard Huet
  Gordon Plotkin Jean-Jacques Lévy Yves Bertot
  (ed.), preprint (March 7 2, Cambridge University Press,
  2007; Chapter from "From Semantics to Computer Science:
  Essays in memory of Gilles Kahn".

• BibTeX

  @inbook{LeeMatsikoudis07_SemanticsOfDataflowWithFiring,
      author = {Edward A. Lee and Eleftherios Matsikoudis},
      editor = {Gérard Huet Gordon Plotkin Jean-Jacques Lévy
                Yves Bertot},
      title = {The Semantics of Dataflow with Firing},
      edition = {preprint (March 7 2},
      publisher = {Cambridge University Press},
      year = {2007},
      note = {Chapter from "From Semantics to Computer Science:
                Essays in memory of Gilles Kahn"},
      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
                ba<x>sed on an operational notion of atomic
                firings driven by certain firing rules. Kahn's
                approach was ba<x>sed 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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/428.html}
  }
  

Posted by Christopher Brooks on 6 Jun 2008.
Groups: ptolemy
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.